. У зв'язку з цим на практиці для отримання вихідного плану використовується інший спосіб - метод мінімального елемента, в якому при розподілі обсягів перевезень у першу чергу займаються клітини з найменшими цінами.
Незбалансована завдання
Якщо сума одиниць товару постачальників не дорівнює сумі одиниць товару споживачів, то завдання не збалансована (відкрита), інакше завдання збалансована (закрита).
У разі, якщо завдання незбалансована, то додаємо новий пункт перевезень (фіктивних перевезень) постачальника чи споживача, залежно від надлишку попиту або пропозиції відповідно. Кількість одиниць товару нового пункту визначається покриттям надлишку попиту або пропозиції. Даний пункт НЕ повинен брати участь у загальній вартості плану перевезень, тому вартість перевезень в/з цього пункту повинна бути дорівнює нулю.
В
Алгоритм методу потенціалів для транспортної задачі
Алгоритм починається з вибору деякого допустимого базисного плану (початковий план перевезень, складений, наприклад, методом північно-західного кута). Якщо даний план не вироджений, то він містить m + n -1 ненульових базисних клітин, і по ньому можна так визначити потенціали u i і v j , щоб для кожної базисної клітини (тобто для тієї, в якій x i , j > 0 ) виконувалася умова якщо x i , j > 0
Змінні u i називають потенціалами пунктів виробництва, a v j - потенціалами пунктів споживання.
Для цього складіть систему для заповнених клітин плану перевезень: де c i , j - вартість перевезення з пункту i до пункту j .
Оскільки система містить m + n -1 рівняння і m + n невідомих, то один з потенціалів можна задати довільно. Після цього інші невідомі v j і u i - визначаються однозначно. p> Критерій оптимальності
Для того щоб допустимий план транспортної задачі x i , j був оптимальним, необхідно і достатньо, щоб знайшлися такі потенціали u i , v j , для яких
якщо
x i , j > 0, якщо
x i , j = 0 Обчисліть коефіцієнти зміни вартості ( dc i , j ) для незаповнених кліток плану: d c i , ...
