>
3
1
[+] 40
2
90
4
[-] 70
0
100
u 2 = -6
а 3 = 150
2
1
3
1
4
0
150
u 3 = -6
vj
v 1 = 1
v 2 = 4
v 3 = 7
v 4 = 8
v 5 = 10
v 6 = 6
У результаті ОТРИМАНО перший опорний план, Який є допустимим, оскількі ВСІ вантажі з баз вівезені, потреба магазинів задоволена, а план відповідає Системі обмежень транспортної задачі.
Підрахуємо число зайнятості клітін табліці, їх 8, а має буті m + n-1 = 8. Отже, опорний план є НЕ вироджених.
Перевірімо оптімальність опорного плану. Знайдемо потенціалі ui, vi. по зайнятості клітінам табліці, в якіх ui + Vi = cij, вважаючі, что u1 = 0:
u 1 = 0, u 2 = -6, u 3 = -6, v 1 = 1, v 2 = 4, v 3 = 7 v 4 = 8, v +5 = 10, v 6 = 6. Ці Значення потенціалів Першого опорного плану запісуємо у транспортної таблиці.
Потім згідно з алгоритмом методу потенціалів перевіряємо Виконання Другої умови оптімальності ui + vj ≤ cij (для порожніх клітінок табліці).
Опорний план не є оптимальним, тому что існують ОЦІНКИ вільніх клітін для якіх ui + vi> cij
(1, 5): 0 + 10> 1
(1, 6): 0 + 6> 0
(3, 4): -6 + 8> 1
Тому від нього звітність, перейти до іншого плану, змінівші співвідношення заповненості и порожніх клітінок табліці. Вібіраємо Максимально оцінку Вільної Клітини ( А 1 B +5): 1. Для цього в перспективну клітку (1; 5) поставімо знак В«+В», а в других вершинах багатокутніка чергуються знаки В«-В», В«+В», В«-В». Цикл наведено в табліці. p> Тепер звітність, перемістіті продукцію в межах побудованого циклу. З вантажів хij что стояти в мінусовіх клітінах, вібіраємо найменша, тоб у = min (1, 3) = 60. Додаємо 60 до обсягів вантажів, что стоять в плюсових клітінах и віднімаємо 60 з хij, что стояти в мінусовіх клітінах. У результаті отрімаємо новий опорний план. p> Для цього у порожню клітинку А 1 B 5 переносимо менше з чисел хij , Які розміщені в клітінках Зі знаком В«-В». Одночасно це самє число хij додаємо до відповідніх чисел, что розміщені в клітінках Зі знаком В«+В», та віднімаємо від чисел, что розміщені в клітінках, позначені знаком В«-В».
УСІ Другие заповнені клітінкі Першої табліці, Які не входили до циклу, перепісуємо у другу Таблицю без змін. Кількість заповненості клітінок у новій табліці такоже має відповідаті умові невіродженості планом, тоб дорівнюваті ( n + m - 1). p> Отже, інших опорних план транспортної задачі матіме такий вигляд:
Ai
Bj
ui
b 1 = 110
b 2 = 80
b 3 = 100
b 4 = 90
b 5 = 70
b 6 = 250
а 1 = 250
1
110
4
[-] 80
7
9
1
[+] 60
0
u 1 = 0
а 2 = 300
2
3
1
100
2
90
4
[-] 10
0
[+] 100
u 2 = 3
а 3 = 150
2
1
[+]
3
1
4
0
[-] 150
u 3 = 3
vj
v 1 = 1
v 2 = 4
v 3 = -2
v 4 = -1
v 5 = 1
v 6 = -3
Перевірімо оптімальність опорного плану. Знайдемо потенціалі ui, vi. по зайнятості клітінам табліці, в якіх ui + vi = cij, вважаючі, что u1 = 0.
Опорний план не є оптимальним...
