авки зменшуються на величину D. При цьому суми поставок по рядках і стовпцях не змінюються. У результаті клітина, для якої будувався цикл, стане зайнятою, а в одній з колишніх зайнятих клітин виявиться нульова поставка і її треба оголосити вільною. Загальна кількість заповнених клітин не зміниться, отже, новий план перевезень є невиродженим.
Якщо в результаті перерахунку одночасно в декількох раніше зайнятих клітинах циклу поставки візьмуть нульові значення, то вільної оголошується лише одна з них. Решта вважаються умовно зайнятими з нульовими поставками.
Значення змінних, включених в цикл, після перерахунку переносяться в нову таблицю без змін. Отриманий новий план перевіряється на оптимальність.
Таке поліпшення плану можна проводити неодноразово доти поки всі критерії для незаповнених клітин виявляться dij <= 0. Потім обчислюється оптимальна вартість перевезень.
Приклад рішення транспортної задачі методом найменшої вартості
Вартість доставки одиниці вантажу з кожного пункту відправлення у відповідні пункти призначення задана матрицею тарифів
1234Запасы1124362438583276310Потребности4688
Перевіримо необхідна і достатня умова розв'язання задачі.
Як видно, сумарна потреба вантажу в пунктах призначення менше запасів вантажу на базах. Отже, модель вихідної транспортної задачі є відкритою. Щоб отримати закриту модель, введемо додаткову (фіктивну) потреба, рівним 2 (26-24). Тарифи перевезення одиниці вантажу з бази в усі магазини вважаємо дорівнюють нулю.
1234Запасы1124362438583276310400002Потребности4688
. Використовуючи метод найменшої вартості, побудуємо перший опорний план транспортної задачі.
транспортний завдання постачальник потенціал
1234Запасы11[4]2[2]436[0]243[4]8[4]58[0]3276[2]3[8]10[0]4000[2]02[0]Потребности4[0]6[0]8[0]8[0]
В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
. Підрахуємо число зайнятих клітин таблиці, їх 7, а має бути m + n - 1=7. Отже, опорний план є невироджених.
. Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi=cij, вважаючи, що u1=0.
u1=1u2=2u3=7u4=4v1=01 [4] 2 [2] 43v2=143 [4] 8 [4] 5v3=- 1276 [2] 3 [8] v4=-7000 [2] 0
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi> cij
(1, 3): 0 + 7> 4
(1, 4): 0 + 4> 3
Вибираємо максимальну оцінку вільної клітини (1, 3): 4
Для цього в перспективну клітку (1; 3) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-» . Цикл наведено в таблиці.
1234Запасы11[4]2[2][-]4[+]36243[4][+]8[4][-]583276[2]3[8]104000[2]02Потребности4688
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у=min (1, 2)=2. Додаємо 2 до обсягів вантажів, що стоять в плюсових клітинах і відн...
