Стандартная форма записи задачи линейного программирования

1) Если в ограничении есть знак ≤, то мы прибавляем к левой части остаточную переменную

x ₁ – 2 x ₂ ≤ 5; x ₁ – 2 x ₂ + s ₁ = 5; s ₁ – остаточная переменная s ₁ ≥ 0;

2 x ₁ + 3 x ₂ ≥ 10; 2 x ₁ + 3 x ₂ – s ₂ = 10; s ₂ – избыточная переменная s ₂ ≥ 0.

2) max z = (– a) Û min (– z) = a.

Решение, полученное занулением n – m переменных называется базисным. Переменные не равные нулю называются базисными переменными, а равные нулю – небазисными.

шаг 0 начальное решение (x_i = 0).

z – строка оценок;

“С” ´ столб – (оценка в верхней строчке);

X _опт = 0·120 + 0·300 + 0·600 – 0 = 0;

x ₁: 0·2 + 0·3 + 0·8 – 2 = – 2 и т.д.

шаг 1

Если в строке нет отрицательных, то оптимальное решение получено. Столбец, в котором стоит наибольшая по модулю отрицательная оценка является разрешающим. Переменная этого столбца вводится в базис. x ₂ – разрешающая; x ₂ вводится в базис.

шаг 2

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

s ₂ выводится из базиса, разрешающая.

На пересечении разрешающей строки и разрешающего столбца стоит главный элемент.

шаг 3

Пересчитываем коэффициенты таблицы с помощью преобразований Гаусса.

базис	С	X опт						r
x 1	x 2	s 1	s 2	s 3
s 1
x 2
s 3
z
s 1
x 2
x 1
z
s 2
x 2
x 1
z

Особые случаи применения симплекс-метода

1. Вырождение решение

Одна из базисных переменных на некотором этапе равна 0. Графически это означает избыточное ограничение.

пример. max z = 3 x ₁ + 9 x ₂.

Б	С	X опт					r
x 1	x 2	s 1	s 2
s 1							2;
s 2							2;
z			– 3	– 9
s 1			– 1			– 2
x 2
z

x ₂ = 2; s ₁ = 0; x ₁ = s ₂ = 0; z = 18.

2. Альтернативное решение

пример. max z = 2 x ₁ + 4 x ₂.

АВ – множество решений

Б	С	X опт					r
x 1	x 2	s 1	s 2
s 1
s 2
z			– 2	– 4
x 2
s 2
z
x 2						– 1
x 1					– 1
z

Используем формулу: x = a ·α + b ·(1 – α); α Î [0; 1]

3. Неограниченное решение

пример. max z = 2 x ₁ + x ₂.

max z = ∞

Столбец x ₂ не содержит положительных, значит сразу можно сделать вывод о неограниченности максимума.

max z = ∞