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

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

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

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

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

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

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

(1;2): 0 + 5 > 2; ∆12 = 0 + 5 - 2 = 3

(1;3): 0 + 8 > 3; ∆13 = 0 + 8 - 3 = 5

(3;1): 4 + 5 > 4; ∆31 = 4 + 5 - 4 = 5

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