Контрольная работа: Математичне програмування

Вибираємо максимальну оцінку вільної клітини (2;5): 2

Для цього в перспективну клітку (2;5) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.

З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (2, 3) = 100. Додаємо 100 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 100 з Хij, що стоять в мінусових клітинах.

В результаті отримаємо новий опорний план.

Ai	Bj						ui
b1 = 100	b2 = 120	b3 = 100	b4=200	b5=300	b6=50
а1 = 150	5	2	3	6	1 150	0	u1 = 0
а2 = 320	1 100	1 [-] 120	4	4	2 [+] 100	0	u2 = 1
а3 = 400	4	1 [+]	2 100	3 200	5 [-] 50	0 50	u3 = 4
vj	v1 = 0	v2 = 0	v3 = -2	v4 = -1	v5 = 1	v6 = -4

Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.

Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij

(3;2): 4 + 0 > 1; ∆32 = 4 + 0 - 1 = 3