Контрольная работа: Симплексний метод лінійного програмування

Перевіримо оптимальність опорного плану. Знайдемо потенціали u_i , v_i . по зайнятих клітинам таблиці, в яких u_i + v_i = c_ij , вважаючи, що u₁ = 0.

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

(1;3): 0 + 5 > 3

(2;1): -1 + 5 > 1

(2;4): -1 + 6 > 4

(4;1): -1 + 5 > 0

(4;2): -1 + 2 > 0

(4;3): -1 + 5 > 0

(4;4): -1 + 6 > 0

Вибираємо максимальну оцінку вільної клітини (А₄ B₄ ): 0

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

З вантажів х_ij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А₂ B₃ ) = 30. Додаємо 30 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 30 з Х_ij , що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.

Ai	Bj					ui
	b1 = 110	b2 = 170	b3 = 200	b4 =180	b5 =110
а1 = 200	5 [-] 110	2 20	3	6	1 [+] 70	u1 = 0
а2 = 150	1	1 150	4	4	2	u2 = -1
а3 = 350	4	3	1 200	2 150	1	u3 = 1
а4 = 70	0 [+]	0	0	0 30	0 [-] 40	u4 = -1
vj	v1 = 5	v2 = 2	v3 = 0	v4 = 1	v5 = 1

Перевіримо оптимальність опорного плану. Знайдемо потенціали u_i , v_i . по зайнятих клітинам таблиці, в яких u_i + v_i = c_ij , вважаючи, що u₁ = 0.

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

(2;1): -1 + 5 > 1

(3;1): 1 + 5 > 4

(3;5): 1 + 1 > 1

(4;1): -1 + 5 > 0

(4;2): -1 + 2 > 0

Вибираємо максимальну оцінку вільної клітини (А₄ B₁ ): 0

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

З вантажів х_ij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А₄ B₅ ) =40. Додаємо 40 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 40 з Х_ij , що стоять в мінусових клітинах.

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

Ai	Bj					ui
	b1 = 110	b2 = 170	b3 = 200	b4 =180	b5 =110
а1 = 200	5 [-] 70	2 [+] 20	3	6	1 110	u1 = 0
а2 = 150	1 [+]	1 [-] 150	4	4	2	u2 = -1
а3 = 350	4	3	1 200	2 150	1	u3 = -3
а4 = 70	0 40	0	0	0 30	0 110	u4 = -5
vj	v1 = 5	v2 = 2	v3 = 4	v4 = 5	v5 = 1

Перевіримо оптимальність опорного плану. Знайдемо потенціали u_i , v_i . по зайнятих клітинам таблиці, в яких u_i + v_i = c_ij , вважаючи, що u₁ = 0.

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

(1;3): 0 + 4 > 3

(2;1): -1 + 5 > 1

Вибираємо максимальну оцінку вільної клітини (А₂ B₁ ): 1

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