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