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

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

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

З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (1, 1) = 0. Додаємо 0 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 0 з Х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 [-] 100	4	2 [+]	0	u2 = 6
а3 = 400	4	1	2 [+] 0	3 200	5 [-] 150	0 50	u3 = 4
vj	v1 = -5	v2 = -5	v3 = -2	v4 = -1	v5 = 1	v6 = -4

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

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

(2;4): 6 + -1 > 4; ∆24 = 6 + -1 - 4 = 1

(2;5): 6 + 1 > 2; ∆25 = 6 + 1 - 2 = 5