= 180
b5 = 110
а1 = 200
1
120
4
80
7
8
1
u1 = 0
а2 = 150
2
3
1
150
4
1
u2 = -5
а3 = 350
5
1
50
3
50
2
180
3
70
u3 = -3
а4 = 40
0
0
0
0
0
40
u4 = -6
vj
v1 = 1
v2 = 4
v3 = 6
v4 = 5
V5 = 6
Перевірімо оптімальність опорного плану. Знайдемо потенціалі ui, vi. по зайнятості клітінам табліці, в якіх ui + vi = cij, вважаючі, что u1 = 0.
Опорний план не є оптимальним, тому что існують ОЦІНКИ вільніх клітін для якіх ui + vi> cij
А1B5: u1 + v5 = 0 + 6 = 6> 1
Вібіраємо Максимально оцінку Вільної Клітини (1, 5): 1
Для цього в Перспективними клітку (А1B5) поставімо знак В«+В», а в других вершинах багатокутніка чергуються знаки В«-В», В«+В», В«-В». Цикл наведено в табліці. p> Зх вантажів хij что стояти в мінусовіх клітінах, вібіраємо найменша, тоб у = min (А3B5) = 70. Додаємо 70 до обсягів вантажів, что стоять в плюсових клітінах и віднімаємо 70 з Хij, что стояти в мінусовіх клітінах. У результаті отрімаємо новий опорний план. br/>
Ai
Bj
ui
b1 = 120
b2 = 130
b3 = 200
b4 = 180
b5 = 110
а1 = 200
1
120
4
[-] 10
7
8
1
[+] 70
u1 = 0
а2 = 150
2
3
1
150
4
1
u2 = -5
а3 = 350
5
1
[+] 120
3
[-] 50
2
180
3
u3 = -3
а4 = 40
0
0
0
[+]
0
0
[-] 40
u4 = -1
vj
v1 = 1
v2 = 4
v3 = 6
v4 = 5
V5 = 1
Перевірімо оптімальність опорного плану. Знайдемо потенціалі ui, vi. по зайнятості клітінам табліці, в якіх ui + vi = cij, вважаючі, что u1 = 0.
Опорний план не є оптимальним, тому что існують ОЦІНКИ вільніх клітін для якіх ui + vi> cij
(А4B2): -1 + 4> 0
(А4B3): -1 + 6> 0
(А4B4): -1 + 5> 0
Вібіраємо Максимально оцінку Вільної Клітини (А4B3): 0
Для цього в Перспективними клітку (А4B3) поставімо знак В«+В», а в других вершинах багатокутніка чергуються знаки В«-В», В«+В», В«-В». Цикл наведено в табліці. p> Зх вантажів хij что стояти в мінусовіх клітінах, вібіраємо найменша, тоб у = min (А1B2) = 10. Додаємо 10 до обсягів вантажів, что стоять в плюсових клітінах и віднімаємо 10 з Хij, что стояти в мінусовіх клітінах. p> У результаті отрімаємо новий опорний план.
Ai
Bj
ui
b1 = 120
b2 = 130
b3 = 200
b4 = 180
b5 = 110
а1 = 200
1
120
4
7
8
1
80
u1 = 0
а2 = 150
2
3
1
150
4
1
u2 = 0
а3 = 350
5
1 <...
