Двойственный симплекс-метод

прямая задача: min z = CX;

двойственная задача: max u = BY;

пример: min z = 3 x ₁ + 2 x ₂ – x ₃.

max u = 4 y ₁ + 5 y ₂

Утверждение: max u = min z.

Если в столбце X _опт есть хотя бы один отрицательный элемент, а в строке оценок отрицательных элементов нет, то можно применять двойственный симплекс-метод.

1. (Находим перемененную, выводимую из базиса). В столбце X _опт выбирается наибольший по модулю отрицательный элемент. Соответствующая строка разрешающая.

2. Ищут отношение элементов строки оценок к отрицательным элементам разрешающей строки. Столбец, в котором это отношение наибольшее (или наименьшее по модулю) – разрешающий.

Условие оптимальности: в столбце X _опт и в строке оценок нет отрицательных элементов.

пример.

min z = 10 x ₁ + 8 x ₂; max (– z) = – 10 x ₁ – 8 x ₂.

базис	С	X опт	– 10	– 8
x 1	x 2	s 1	s 2	s 3
s 1		– 5	– 1	– 2
s 2		– 12	– 2
s 3		– 4	– 1	– 3
– z
s 1				– 5/2		– 1/2
x 1	– 10			– 1/2		– 1/2
s 3				– 7/2		– 1/2
– z		– 60

Итак, x ₁ = 6, x ₂ = 0; s ₁ = 1; s ₃ = 2; max (– z) = – 60; min z = 60.