> b 5 = 180
а 1 = 300
1
100
4
[-] 20
2
70
1
90
2
[+] 20
u 1 = 0
а 2 = 90
2
2
3
1
3
90
u 2 = 1
а 3 = 70
3
4
[+]
5
6
7
[-] 70
u 3 = 5
v j
v 1 = 1
v 2 = 4
v 3 = 2
v 4 = 1
v 5 = 2
У результаті ОТРИМАНО перший опорний план, Який є допустимим, оскількі ВСІ вантажі з баз вівезені, потреба магазинів задоволена, а план відповідає Системі обмежень транспортної задачі.
Підрахуємо число зайнятості клітін табліці, їх 7, а має буті m + n-1 = 7. Отже, опорний план є НЕ вироджених.
Перевірімо оптімальність опорного плану. Знайдемо потенціалі u i , v i . по зайнятості клітінам табліці, в якіх u i + v i = c ij , вважаючі, что u 1 = 0:
u 1 = 0, u 2 = 1, u 3 = 5 , v 1 = 1, v 2 = 4, v 3 = 2 v 4 = 1, v 5 = 2. Ці Значення потенціалів Першого опорного плану запісуємо у транспортної таблиці.
Потім згідно з алгоритмом методу потенціалів перевіряємо Виконання Другої умови оптімальності u i + v j ≤ c ij (для порожніх клітінок табліці).
Опорний план не є оптимальним, тому что існують ОЦІНКИ вільніх клітін для якіх u i + v i > c ij
(2, 2): 1 + 4> 2; О” 22 = 1 + 4 - 2 = 3
(2, 4): 1 + 1> 1; О” 24 = 1 + 1 - 1 = 1
(3; 1): 5 + 1> 3; О” 31 = 5 + 1 - 3 = 3
(3, 2): 5 + 4> 4; О” 32 = 5 + 4 - 4 = 5
(3, 3): 5 + 2> 5; О” 33 = 5 + 2 - 5 = 2
max (3,1,3,5,2) = 5
Тому від нього звітність, перейти до іншого плану, змінівші співвідношення заповненості и порожніх клітінок табліці. Вібіраємо Максимально оцінку Вільної Клітини (3, 2): 4. Для цього в перспективну клітку (3, 2) поставімо знак В«+В», а в других вершинах багатокутніка чергуються знаки В«-В», В«+В», В«-В». Цикл наведено в табліці. p> Тепер звітність, перемістіті продукцію в межах побудованого циклу. З вантажів х ij что стояти в мінусовіх клітінах, вібіраємо найменша, тоб у = min (1, 2) = 20. Додаємо 20 до обсягів вантажів, что стоять в плюсових клітінах и віднімаємо 20 з х ij , что стояти в мінусовіх клітінах. У результаті отрімаємо новий опорний план.
УСІ Другие заповнені клітінкі Першої табліці, Які не входили до циклу, перепісуємо у другу таблицю без змін. Кількість заповненості клітінок у новій табліці такоже має відповідаті умові невіродженості планом, тоб дорівнюваті ( n + m - 1). p> Отже, інших опорних план транспортної задачі матіме такий вигляд:
A i
B j
u i
b 1 = 100
b 2 = 20
b 3 = 70
b 4 = 90
b 5 = 180
а 1 = 300
1
[-] 100
4
2
70
1
90
2
[+] 40
u 1 = 0
а 2 = 90
2
2
3
1
3
90
u 2 = 1
а 3 = 70
3
[+]
4
20
...
