Всі методи рішення транспортної задачі спираються на виконання таких етапів:
- Побудова початкового опорного плану (метод північно-західного кута, метод мінімального елемента, метод апроксимації Фогеля та інші).
- Визначення оптимальності отриманого плану.
- Поліпшення отриманого плану.
Очевидно, що етапи два і три повторюються до отримання оптимального рішення (плану).
Побудований одним з перелічених вище методів опорний план можна довести до оптимального за допомогою симплекс методу. В силу особливостей моделі транспортної задачі (обмеження мають вигляд рівностей, кожна невідома входить лише в два рівняння, коефіцієнти при невідомих рівні одиниці) процес її рішення симплекс методом є громіздким. Тому, для знаходження оптимального плану транспортної задачі, створені спеціальні методи, найбільш поширеним з яких вважається метод потенціалів.
Розглянемо алгоритм, який реалізує цей метод.
Отже, на першому кроці, кожному рядку і стовпцю транспортної таблиці (кожному постачальнику та споживачеві) ставляться у відповідність числа і , які називаються їх потенціалами. Дані числа, для кожної базисної змінної поточного рішення, повинні задовольняти умовам . Зазначимо, що ці умови призводять до системи, що складається з рівнянь (кількість базисних змінних), в яких фігурують невідомих (кількість потенціалів). Значення потенціалів визначають з цієї системи, надаючи одному з них довільної величини (наприклад, ).
Зауваження: при рішенні транспортної задачі методом потенціалів, значення чисел та , зазвичай, записують в додатковому стовпці та рядку транспортної таблиці.
На наступному кроці, для кожної вільної комірки визначають числа . Якщо серед цих чисел немає додатних, то отримано оптимальний план транспортної задачі. Якщо ж для деякої вільної комірки виявиться, що , то необхідно перейти до нового опорного рішення.
Для цього, розглядаються всі вільні комірки, для яких , і серед них вибирають ту, для якої число є максимальним (якщо таких комірок більше однієї, то вибирають першу по порядку). Обрану комірку варто заповнити – її позначають знаком «+» і формують цикл, по якому необхідно змінити об’єми перевезень. Циклом у таблиці транспортної задачі називається замкнута ламана лінія, вершини якої розташовані в зайнятих комірках таблиці, а ланки (відрізки, що поєднуюють вершини) – уздовж рядків і стовпів, причому в кожній вершині циклу зустрічаються рівно дві ланки, одна з яких перебуває в рядку, а інше – у стовпці.
Представлення можливих конфігурацій циклу перерахунку
При правильній побудові опорного плану, для будь-якої вільної комірки, можна побудувати лише один цикл перерахунку. Вільна комірка, як уже зазначалося вище, позначається знаком «+», потім знаки чергуються «–», «+», «–», «+» і так далі. У вільну комірку переносять менше із чисел , що міститься в комірках позначених знаком «мінус», і одночасно це число додають до чисел, що містяться в комірках позначених знаком «плюс» та віднімають від чисел, що стоять в комірка зі знаком «мінус». В результаті, комірка, що раніше була вільною, стає зайнятою, а «мінусова» комірка (комірка у якій стояло мінімальне число ) – вільною. В отриманому розв’язку знову обчислюються потенціали, здійснюється перевірка оптимальності і, у разі необхідності, оптимізація.
Рішення транспортної задачі методом потенціалів – приклад:
Знайти оптимальний план задачі, заданої наступною таблицею. При цьому, необхідно відштовхуватися від початкового плану, знайденого методом північно-західного кута.
Транспортна таблиця з опорним планом північно-західного кута
Отже, для початку, першому рядку таблиці поставимо у відповідність потенціал , другому – потенціал і третьому – потенціал . Стовпцям відповідно потенціали . Після цього, згідно з співвідношенням , для кожної заповненої комірки, побудуємо лінійне рівняння, визначимо значення потенціалів і запишемо їх в додатковий рядок та ствпець транспортної таблиці:
На наступному кроці, скориставшись формулою , для кожної вільної комірки визначимо числа . В результаті будемо мати:
Виходячи з того, що серед отриманих чисел містяться додатні (опорний план не є оптимальним), здійснюємо перехід до нового опорного рішення. Для цього, серед усіх , для яких виконується умова , вибираємо максимальне. На даній ітерації це число . Тобто комірка, що міститься на перетині першого рядка та четвертого стовпця повинна бути заповненою. Отже, позначимо її знаком «+» і сформуємо цикл, по якому необхідно змінити об’єми перевезень.
Метод потенціалів – ітерація №1
В результаті, отримаємо нове опорне рішення, яке знову-таки необхідно перевірити на оптимальність. Для цього, аналогічним чином, для кожного рядка та стовпця транспортної таблиці обчислюємо значення їх потенціалів і для кожної вільної комірки визначаємо числа :
Переглянувши отримані результати бачимо, що побудований на першій ітерації опорний план також не є оптимальним – . Отже, заповнюємо комірку якій відповідає змінна та змінюємо об’єми поставок в других заповнений комірках, що пов’язані з нею циклом.
Метод потенціалів – ітерація №2
В отриманому розв’язку знову обчислюються потенціали, здійснюється перевірка оптимальності і, у разі необхідності, оптимізація. Подальше рішення транспортної задачі показано в настиупних таблицях.
Метод потенціалів – ітерація №3-5
Зазначимо, що у останній з розміщених вище таблиць міститься оптимальний план транспортної задачі (для кожної незаповненої комірки виконується критерій оптимальності), сумарні витрати на перевезення якого становлять умовних одиниць.