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

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

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

Перевіримо оптимальність опорного плану, тобто повторюємо описані раніше дії.

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

Перевірка останнього плану на оптимальність за допомогою методу потенціалів показує, що він оптимальний.

Мінімальні витрати складуть:

F(x) = 1*150 + 1*100 + 1*70 + 2*150 + 1*50 + 2*100 + 3*200 + 0*50 = 1470