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

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

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

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

   1  2  3  4  Запаси
 1  5  9  10  4  120
 2  2  9  6  6  380
 3  3  5  4  7  200
 Потреби  230  170  140  160  

 Перевіримо необхідна і достатня умова розв'язання задачі.
∑a = 120 + 380 + 200 = 700
∑b = 230 + 170 + 140 + 160 = 700
 Умова балансу дотримується. Запаси рівні потребам.
 Занесемо вихідні дані у розподільну таблицю.
   1  2  3  4  Запаси
 1  5  9  10  4  120
 2  2  9  6  6  380
 3  3  5  4  7  200
 Потреби  230  170  140  160  

 1. Використовуючи метод найменшої вартості, побудуємо перший опорний план транспортної задачі.
   1  2  3  4  Запаси
 1  5  9  10  4[120]  120
 2  2[230]  9[110]  6  6[40]  380
 3  3  5[60]  4[140]  7  200
 Потреби  230  170  140  160  

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

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

 З вантажів х ij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (2, 2) = 110. Додаємо 110 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 110 з Хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
   1  2  3  4  Запаси
 1  5  9  10  4[120]  120
 2  2[230]  9  6[110]  6[40]  380
 3  3  5[170]  4[30]  7  200
 Потреби  230  170  140  160  

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

 Опорний план є оптимальним.
 Витрати складуть:
 F(x) = 4*120 + 2*230 + 6*110 + 6*40 + 5*170 + 4*30  = 2810

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