Применение метода искусственного базиса

Иногда при решении ЗЛП в матрице коэффициентов при неизвестных системы ограничений нет единичных столбцов, из которых можно составить единичную матрицу, т.е. возникает проблема выбора базисных переменных, либо первоначальное решение является недопустимым. В таких случаях используют метод искусственного базиса (М - метод). Во все ограничения, где нет базисных переменных, вводятся искусственные переменные.

В целевую функцию искусственные переменные вводятся с коэффициентом (- М) для задач на max и с коэффициентом (+ М) для задач на min, где М – достаточно большое положительное число.

Затем решается расширенная задача по правилам симплексного метода. Если все искусственные переменные окажутся равными нулю, т.е. будут исключены из базиса, то либо будет получено оптимальное решение исходной задачи, либо исходная задача решается далее и находится ее оптимальное решение, или устанавливается ее неразрешимость.

Если хотя бы одна из искусственных переменных окажется отличной от нуля, то исходная задача не имеет решения.

Задача.

Решите ЗЛП методом искусственного базиса: найти максимальное значение при условиях

 

Составим матрицу коэффициентов системы уравнений:

 

 

В матрице нет единичных векторов, из которых можно образовать единичную матрицу, т.е. возникает проблема выбора базисных переменных в каждом из уравнений.

Введем искусственные переменные .

 

 

Введем их в целевую функцию с коэффициентами (-М), т.к. решается задача нахождения z_max:

Единичную матрицу образуют коэффициенты при неизвестных х₅ и х₆, значит эти переменные являются базисными. А так как они являются искусственными переменными, то исходный базис называют искусственным. Переменные х₁, х₂, х₃ и х₄ являются свободными.

Таким образом, мы получили расширенную ЗЛП, и будем решать ее симплекс-методом.

Полагая , находим первоначальный опорный план: При этом плане:

1. Заполним первую симплекс-таблицу.

хБазис		В				-1	-М	-М
		х3	х4	х5	Х6
х5	-М
х6	-М
Δj	-7М	-3М-2	-6М-3	-3М-1	-3М+1

 

min (Δ_j < 0) = Δ₂ = - 6М – 3, значит в базис введем переменную х₂.

, значит, из базиса выводим искусственную переменную х₅, поэтому столбец х₅ в следующей таблице можно не заполнять.

1. Производим заполнение второй таблицы по правилам симплекс-метода.

 

 

хБазис		В				-1	-М
х1	х2	х3	х4	х6
х2			1/3		2/3	2/3
х6	-М				-1	-1
Δj	-М+3	-М-1		М+1	М+3

 

min (Δ_j < 0) = Δ₁ = - М - 1, значит в базис введем переменную х₁.

, значит, из базиса выводим искусственную переменную х₆, поэтому столбец х₆ в следующей таблице можно не заполнять.

2. Заполняем третью таблицу.

хБазис		В				-1
х1	х2	х3	х4
х2		2/3
х1					-1	-1
Δj

В третьей таблице обе искусственные переменные оказались равными нулю и все , следовательно, получено оптимальное решение исходной задачи.

Ответ: ,