Знаходження оптимального плану транспортної задачі методом потенціалів

Всі методи рішення транспортної задачі спираються на виконання таких етапів:

  1. Побудова початкового опорного плану (метод північно-західного кута, метод мінімального елемента, метод апроксимації Фогеля та інші).
  2. Визначення оптимальності отриманого плану.
  3. Поліпшення отриманого плану.

Очевидно, що етапи два і три повторюються до отримання оптимального рішення (плану).

Побудований одним з перелічених вище методів опорний план можна довести до оптимального за допомогою симплекс методу. В силу особливостей моделі транспортної задачі (обмеження мають вигляд рівностей, кожна невідома входить лише в два рівняння, коефіцієнти при невідомих рівні одиниці) процес її рішення симплекс методом є громіздким. Тому, для знаходження оптимального плану транспортної задачі, створені спеціальні методи, найбільш поширеним з яких вважається метод потенціалів.

Розглянемо алгоритм, який реалізує цей метод.

Отже, на першому кроці, кожному рядку і стовпцю транспортної таблиці (кожному постачальнику та споживачеві) ставляться у відповідність числа  і , які називаються їх потенціалами. Дані числа, для кожної базисної змінної поточного рішення, повинні задовольняти умовам . Зазначимо, що ці умови призводять до системи, що складається з  рівнянь (кількість базисних змінних), в яких фігурують  невідомих (кількість потенціалів). Значення потенціалів визначають з цієї системи, надаючи одному з них довільної величини (наприклад, ).

Зауваження: при рішенні транспортної задачі методом потенціалів, значення чисел та , зазвичай, записують в додатковому стовпці та рядку транспортної таблиці.

На наступному кроці, для кожної вільної комірки визначають числа . Якщо серед цих чисел немає додатних, то отримано оптимальний план транспортної задачі. Якщо ж для деякої вільної комірки виявиться, що , то необхідно перейти до нового опорного рішення.

Для цього, розглядаються всі вільні комірки, для яких , і серед них вибирають ту, для якої число є максимальним (якщо таких комірок більше однієї, то вибирають першу по порядку). Обрану комірку варто заповнити — її позначають знаком «+» і формують цикл, по якому необхідно змінити об'єми перевезень. Циклом у таблиці транспортної задачі називається замкнута ламана лінія, вершини якої розташовані в зайнятих комірках таблиці, а ланки (відрізки, що поєднуюють вершини) - уздовж рядків і стовпів, причому в кожній вершині циклу зустрічаються рівно дві ланки, одна з яких перебуває в рядку, а інше - у стовпці.

Метод потенціалів

Представлення можливих конфігурацій циклу перерахунку

При правильній побудові опорного плану, для будь-якої вільної комірки, можна побудувати лише один цикл перерахунку. Вільна комірка, як уже зазначалося вище, позначається знаком «+», потім знаки чергуються «-», «+», «-», «+» і так далі. У вільну комірку переносять менше із чисел , що міститься в комірках позначених знаком «мінус», і одночасно це число додають до чисел, що містяться в комірках позначених знаком «плюс» та віднімають від чисел, що стоять в комірка зі знаком «мінус». В результаті, комірка, що раніше була вільною, стає зайнятою, а «мінусова» комірка (комірка у якій стояло мінімальне число ) - вільною. В отриманому розв'язку знову обчислюються потенціали, здійснюється перевірка оптимальності і, у разі необхідності, оптимізація.

Рішення транспортної задачі методом потенціалів — приклад:

Знайти оптимальний план задачі, заданої наступною таблицею. При цьому, необхідно відштовхуватися від початкового плану, знайденого методом північно-західного кута.

Метод потенціалів приклад

Транспортна таблиця з опорним планом північно-західного кута

Отже, для початку, першому рядку таблиці поставимо у відповідність потенціал , другому — потенціал і третьому — потенціал . Стовпцям відповідно потенціали . Після цього, згідно з співвідношенням , для кожної заповненої комірки, побудуємо лінійне рівняння, визначимо значення потенціалів і запишемо їх в додатковий рядок та ствпець транспортної таблиці:

На наступному кроці, скориставшись формулою , для кожної вільної комірки визначимо числа . В результаті будемо мати:

Виходячи з того, що серед отриманих чисел містяться додатні (опорний план не є оптимальним), здійснюємо перехід до нового опорного рішення. Для цього, серед усіх , для яких виконується умова , вибираємо максимальне. На даній ітерації це число . Тобто комірка, що міститься на перетині першого рядка та четвертого стовпця повинна бути заповненою. Отже, позначимо її знаком «+» і сформуємо цикл, по якому необхідно змінити об'єми перевезень.

Метод потенціалів приклад

Метод потенціалів — ітерація №1

В результаті, отримаємо нове опорне рішення, яке знову-таки необхідно перевірити на оптимальність. Для цього, аналогічним чином, для кожного рядка та стовпця транспортної таблиці обчислюємо значення їх потенціалів і для кожної вільної комірки визначаємо числа :

Переглянувши отримані результати бачимо, що побудований на першій ітерації опорний план також не є оптимальним - . Отже, заповнюємо комірку якій відповідає змінна та змінюємо об'єми поставок в других заповнений комірках, що пов'язані з нею циклом.

Метод потенціалів приклад

Метод потенціалів — ітерація №2

В отриманому розв'язку знову обчислюються потенціали, здійснюється перевірка оптимальності і, у разі необхідності, оптимізація. Подальше рішення транспортної задачі показано в настиупних таблицях.

Метод потенціалів приклад

Метод потенціалів — ітерація №3−5

Зазначимо, що у останній з розміщених вище таблиць міститься оптимальний план транспортної задачі (для кожної незаповненої комірки виконується критерій оптимальності), сумарні витрати на перевезення якого становлять умовних одиниць.

Блок-схема алгоритму побудови оптимального плану транспотрної задачі методом потенціалів

Матеріал був корисним, поділись в соціальних мережах:
Якщо тобі сподобалась дана тема, залиш свій коментар