Контрольная работа: Решение задач симплекс-методом

+ n - 1 = 9.

Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:(x) = 1*100 + 2*100 + 2*100 + 5*100 + 6*100 + 4*100 + 3*100 + 3*200 + 1*100 = 3000

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

₁ + v₁ = 1; 0 + v₁ = 1; v₁ = 1₂ + v₁ = 2; 1 + u₂ = 2; u₂ = 1₁ + v₄ = 2; 0 + v₄ = 2; v₄ = 2₃ + v₄ = 6; 2 + u₃ = 6; u₃ = 4₃ + v₂ = 5; 4 + v₂ = 5; v₂ = 1₄ + v₂ = 4; 1 + u₄ = 4; u₄ = 3₄ + v₃ = 3; 3 + v₃ = 3; v₃ = 0₅ + v₂ = 3; 1 + u₅ = 3; u₅ = 2₅ + v₅ = 1; 2 + v₅ = 1; v₅ = -1

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

(3;1): 4 + 1 > 3; ∆₃₁ = 4 + 1 - 3 = 2

Выбираем максимальную оценку свободной клетки (3;1): 3

Цикл приведен в таблице (3,1 → 3,4 → 1,4 → 1,1).

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

₁ + v₄ = 2; 0 + v₄ = 2; v₄ = 2₃ + v₄ = 6; 2 + u₃ = 6; u₃ = 4₃ + v₁ = 3; 4 + v₁ = 3; v₁ = -1₂ + v₁ = 2; -1 + u₂ = 2; u₂ = 3₃ + v₂ = 5; 4 + v₂ = 5; v₂ = 1₄ + v₂ = 4; 1 + u₄ = 4; u₄ = 3₄ + v₃ = 3; 3 + v₃ = 3; v₃ = 0₅ + v₂ = 3; 1 + u₅ = 3; u₅ = 2₅ + v₅ = 1; 2 + v₅ = 1; v₅ = -1

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

(2;2): 3 + 1 > 3; ∆₂₂ = 3 + 1 - 3 = 1

(2;4): 3 + 2 > 4; ∆₂₄ = 3 + 2 - 4 = 1(1,1) = 1

Выбираем максимальную оценку свободной клетки (2;2): 3

Цикл приведен в таблице (2,2 → 2,1 → 3,1 → 3,2).

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

₁ + v₄ = 2; 0 + v₄ = 2; v₄ = 2₃ + v₄ = 6; 2 + u₃ = 6; u₃ = 4₃ + v₁ = 3; 4 + v₁ = 3; v₁ = -1₃ + v₂ = 5; 4 + v₂ = 5; v₂ = 1₂ + v₂ = 3; 1 + u₂ = 3; u₂ = 2₄ + v₂ = 4; 1 + u₄ = 4; u₄ = 3₄ + v₃ = 3; 3 + v₃ = 3; v₃ = 0₅ + v₂ = 3; 1 + u₅ = 3; u₅ = 2₅ + v₅ = 1; 2 + v₅ = 1; v₅ = -1

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ≤ c_ij.

Минимальные затраты составят: F(x) = 2*200 + 3*100 + 3*200 + 4*100 + 3*100 + 3*200 + 1*100 = 2700