Page 61 - 5007

Примітка. У подальшому клітинку, в яку необхідно заносити нульову
поставку, потрібно визначати, враховуючи можливість визначення
потенціалів(див. п.6).

4 Перевірка на оптимальність базисних планів виконується за умовою
c ij  u i + v j для всіх кліток, де u i і v j – так звані потенціали, або
“псевдоплатежі”, які вносять як постачальник, так і споживач за
перевезення у т.ч. неіснуючих вантажів. Потенціали знаходять за такими
правилами.

4.1 Вводять термінологію: клітка з вантажем – базисна клітка; клітка
без вантажу – вільна клітка.

4.2 Для базисних кліток c ij = u i + v j , звідки, надаючи одному з
потенціалів довільного значення (наприклад 0), знаходять інші потенціали
для всіх споживачів і постачальників (тобто стовпців і рядків). Значення
суми потенціалів для кожної клітки проставляють у нижньому кутку
клітки.
Для плану, отриманого за діагональним методом, маємо такі значення
потенціалів та їх сум

350 400 400 200 u i

15 17 16 0
250
250 0
15 12
8 -1
13 10 12 0
100 300
400 -2
13 6 -3
10
14 13 9 0
700 100 400 200 1
16 13 9 0

15 12 8 -1
v j

5 Оскільки клітка з координатами А 3В 1 не відповідає умові
оптимальності (14  16), то виконуємо оптимізацію плану, вміщуючи в
дану клітку вантаж (тобто перевозимо вантаж від постачальника А 3 до
споживача В 1), цим самим прирівнюючи собівартість перевезень до суми
потенціалів.
Для того щоб помістити в дану клітку вантаж, його необхідно
“перекинути” з інших кліток. “Перекидування” виконується із базисних
кліток-вершин, які з даною вільною кліткою утворюють геометричну
фігуру.
Всі вершини цих циклів мають бути розміщені у базисних клітках,
окрім тієї вільної, для якої не справджується умова оптимальності.

60