загрузка...
Пошук по сайту

Приклад вирішення транспортної задачі методом північно-західного кута

Рішення транспортної задачі online

Вартість доставки одиниці вантажу з кожного пункту відправлення у відповідні пункти призначення задана матрицею тарифів.

   1  2  3  4  Запаси
 1  4  4  2  5  170
 2  5  3  1  2  50
 3  2  1  4  2  70
 Потреби  110  40  60  80  

Перевіримо необхідна і достатня умова розв'язання задачі.
∑a = 170 + 50 + 70 = 290
∑b = 110 + 40 + 60 + 80 = 290
Умова балансу дотримується. Запаси рівні потребам.
Занесемо вихідні дані у розподільну таблицю.
   1  2  3  4  Запаси
 1  4  4  2  5  170
 2  5  3  1  2  50
 3  2  1  4  2  70
 Потреби  110  40  60  80  

1. Використовуючи метод північно-західного кута, побудуємо перший опорний план транспортної задачі.
   1  2  3  4  Запаси
 1  4[110]  4[40]  2[20]  5  170
 2  5  3  1[40]  2[10]  50
 3  2  1  4  2[70]  70
 Потреби  110  40  60  80  

В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
2. Підрахуємо число зайнятих клітин таблиці, їх 6, а має бути m+n-1 = 6. Отже, опорний план є невироджених.
4. Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
   v1=4  v2=4  v3=2  v4=3
 u1=0  4[110]  4[40]  2[20]  5
 u2=-1  5  3  1[40]  2[10]
 u3=-1  2  1  4  2[70]

Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких u i + vi > cij
(3;1): -1 + 4 > 2
(3;2): -1 + 4 > 1
Вибираємо максимальну оцінку вільної клітини (3;2): 1
Для цього в перспективну клітку (3;2) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
   1  2  3  4  Запаси
 1  4[110]  4[40][-]  2[20][+]  5  170
 2  5  3  1[40][-]  2[10][+]  50
 3  2  1[+]  4  2[70][-]  70
 Потреби  110  40  60  80  

З вантажів х ij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (2, 3) = 40. Додаємо 40 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 40 з Хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
   1  2  3  4  Запаси
 1  4[110]  4[0]  2[60]  5  170
 2  5  3  1  2[50]  50
 3  2  1[40]  4  2[30]  70
 Потреби  110  40  60  80  

4. Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
   v1=4  v2=4  v3=2  v4=5
 u1=0  4[110]  4[0]  2[60]  5
 u2=-3  5  3  1  2[50]
 u3=-3  2  1[40]  4  2[30]

Опорний план є оптимальним. Витрати складуть:
F( x) = 4*110 + 2*60 + 2*50 + 1*40 + 2*30  = 760

Завантажити у форматі rtf