твертий - 310 тонн. Його необхідно доставити в чотири пункти призначення в такій кількості: перший пункт призначення - 160, другий - 210, третій - 250, четвертий - 300 тонн. Потрібно скласти план вантажоперевезень з мінімумом витрат на транспортування. Відстані між пунктами відправлення та призначення в км наведені в таблиці:
Пункти отправленія1234Пункти назначенія16533241793374542544
Вартість доставки одиниці вантажу з кожного пункту відправлення у відповідні пункти призначення задана матрицею тарифів
Перевіримо необхідна і достатня умова розв'язання задачі.
? a = 160 + 210 + 250 + 300 = 830
? b = 110 + 180 + 230 + 310 = 920
Як видно, сумарна потреба вантажу в пунктах призначення перевищує запаси вантажу на базах. Отже, модель вихідної транспортної задачі є відкритою. Щоб отримати закриту модель, введемо додаткову (фіктивну) базу із запасом вантажу, рівним 90 (920-830). Тарифи перевезення одиниці вантажу з бази в усі магазини вважаємо, дорівнюють нулю. br/>
Занесемо вихідні дані у розподільну таблицю.
. Використовуючи метод найменшої вартості, побудуємо перший опорний план транспортної задачі. P
В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
. Підрахуємо число зайнятих клітин таблиці, їх 8, а має бути
+ n - 1 = 8. br/>
Отже, опорний план є невироджених.
. Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
+ v3 = 3; 0 + v3 = 3; v3 = 3 + v3 = 4; 3 + u3 = 4; u3 = 1 + v4 = 5; 1 + v4 = 5; v4 = 4 + v4 = 4; 4 + u4 = 4; u4 = 0 + v1 = 2; 0 + v1 = 2; v1 = 2 + v5 = 0; 1 + v5 = 0; v5 = -1
u2 + v5 = 0; -1 + u2 = 0; u2 = 1 + v2 = 1; 1 + v2 = 1; v2 = 0
Опорний план не є оптимальним, тому що існують оцінки вільних клітин, для яких
+ vi> cij
(1, 4): 0 + 4> 3;? 14 = 0 + 4 - 3 = 1
Вибираємо максимальну оцінку вільної клітини (1, 4): 3
Для цього в перспективну клітку (1, 4) поставимо знак В«+В», а в інших вершинах багатокутника чергуються знаки В«-В», В«+В», В«-В». Цикл наведено в таблиці. br/>
З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто
у = min (3, 4) = 120. Додаємо 120 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 120 з Хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план. br/>
....
