2.3. Матричний розв’язок транспортної задачі методом потенціалів

Одним з найбільш простих і широко розповсюджених способів розв’язок транспортної задачі є метод потенціалів. Потенціалами – називають умовні числа U_i _j, привласнені певним чином кожному рядкові i і кожному стовпцеві j матриці. Розв’язок зводиться до відшукання таких значень потенціалів, за яких виконується наступна умова оптимальності: для кожної клітки сума (різниця) потенціалів рядка і стовпця повинна бути меншою або дорівнює вартості перевезень, причому для зайнятих кліток - точно дорівнювати вартості перевезень, тобто

U

(2.3)

_i  _j С_i при x_ij =0;

U_i  _j= С_i при x_ij  0.

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

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

Для максимізації цільової функції необхідно: або змінити умову оптимальності для вільних елементів матриці U_i + _j С_i або змінити знак на зворотний у всіх значеннях вартості. Розглянемо застосування методу на прикладі.

2.3.1. Побудова початкового плану

У даному випадку він побудований методом найменшої вартості (табл. 8), і загальна його вартість З=585.

2.3.2. Обчислення потенціалів

Потенціали рядків записуються ліворуч від матриці, а стовпців - угорі (замість нумерації). Одному зі стовпців (або рядків) привласнимо довільне значення потенціалу, наприклад С. Щоб серед потенціалів було менше негативних чисел, нуль привласнюють стовпцеві або рядкові з можливо меншими значеннями вартості в зайнятих клітках, наприклад, третьому стовпцеві (див. табл. 8). Використовуючи умову оптимальності (2.3), обчислимо за зайнятими елементами все інше потенціали. Оскільки для клітки 2.3 повинна дотримуватися умова U₂ + ₃= З₂₃, а ₃=0 і З₂₃=1, потенціал другого рядка U₂= З₂₃-₃=1-0=1. Тепер легко визначити потенціал четвертого стовпця ₄. ₄= З₂₄- U₂=6-1=5. Аналогічно знаходимо інші потенціали.

2.3.3. Перевірка за умовою оптимальності

Усі вільні елементи матриці необхідно перевірити за умовою оптимальності (2.3). Якщо воно виконано для кожного елемента, то план оптимальний. У протилежному випадку у відповідному елементі проставляють величину порушення цієї умови зі знаком плюс. Так, для клітки 1.2 U₁+ ₂=-2+7=5. Умова не виконана (5>3), величину порушення +2 заносимо в клітку. Аналогічно для клітки 2.2 U₁+ ₂=1+7=8. Вона також потенційна (8>7), і в ній проставляємо величину порушення +1. Для інших вільних елементів умова виконана.

2.3.4. Цикл перерахування

Вибираємо потенційну клітку з найбільшою величиною порушення і позначаємо в ній перевезення. Це елемент 1.2 з порушенням +2. Щоб визначити величину перевезення, що вводиться, будують замкнутий контур, рухаючись від обраної клітки прямолінійними ходами з поворотами в зайнятих клітках. Контур (1.2-3.2-1.3-1.1-1.2) може бути прямокутним, як у даному випадку, або більш складної конфігурації. Потім визначають мінімальну величину перевезення в парних вершинах контуру, вважаючи першої вершину в обраній клітці. Це і буде величина перевезення, що вводиться, вона дорівнює 10 (клітка I.I). На цю величину необхідно збільшити всі перевезення в непарних вершинах і зменшити у парних. У результаті отримано новий поліпшений план (табл. 9 ), у якому замість перевезення I.I з'явилося перевезення 1.2, а величина перевезень 3.1 і 3.2 змінилася. Число перевезень у плані залишилося без зміни m+n-1. Зниження загальної вартості перевезень дорівнює добуткові величини перевезення, що вводиться, на величину порушення. Таким чином, загальна вартість перевезень за новим планом дорівнює

585-210=565.

Я

Таблиця 8

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

Початковий план

Друга ітерація починається з присвоєння нових потенціалів. Результати наступної ітерації приведені в табл.10.

Таблиця 10

Результат другої ітерації (оптимальний план)

Таблиця 9

Результат першої ітерації

Якщо за якихось причин окремі перевезення неможливі, то їхньої вартості у відповідних клітках матриці заміняються буквою М, що виражає число, свідомо більше будь-якої суми потенціалів U_i+ _j. У такі клітки перевезення ніколи не буде призначена.

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