3.6. Метод искусственного базиса

Метод искусственного базиса применяется для решения ЗЛП, когда задача не имеет начального опорного решения с базисом из едиМетод искусственного базиса применяется для решения ЗЛП, когда задача не имеет начального опорного решения с базисом из едиичных векторов.

Для данной задачи составляется расширенная ЗЛП, которая решается симплексным методом. На основе результатов ее решения либо находится оптимальное решение исходной задачи, либо устанавливается причина ее отсутствия. Пусть имеется задача ЛЛП:

Z(X) = c₁x₁+c₂x₂+…+ c_nx_n max(min),

Искусственными называются неотрицательные переменные, которые вводятся в ограничения-равенства для получения начального опорного решения с базисом из единичных векторов. Каждая искусственная переменная вводится в левую часть одного из уравнений системы ограничений с коэффициентом «+1» и в целевую функцию в задаче на максимум с коэффициентом «-М», на минимум – «+М». М – сколь угодно большое положительное число. Таким образом, задача будет иметь вид Z(X) =c₁x₁+…+c_nx_n – M(x_n₊₁+…+x_n₊_m) max(min),

Задача имеет начальное опорное решение Х₁ = (0,...,0,b₁,…b_m) с базисом Б₁=(А_п+1,...,А_п+т). Данная задача называется расширенной ЗЛП.

Теорема 1(признак оптимальности решения). Если расширенная ЗЛП имеет оптимальное решение Х^*=(х₁^*,х₂^*,...,х_п^*,0,...,0), у которого все искусственные переменные равны нулю, то исходная задача также имеет оптимальное решение Х^* = (x₁^*,x₂^*,…,x_n^*), которое получается из Х^*отбрасыванием нулевых искусственных переменных.

Теорема 2. (признак отсутствия решения ввиду несовместности системы ограничений) Если расширенная ЗЛП имеет оптимальное решение, у которого хотя бы одна искусственная переменная отлична от нуля, то исходная задача не имеет решения ввиду несовместности системы ограничений.

Теорема 3 (признак отсутствия решения ввиду неограниченности целевой функции). Если расширенная задача не имеет решения ввиду неограниченности целевой функции, то исходная задача не имеет решения по той же причине.

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

1. Ввиду того, что начальное опорное решение расширенной задачи искусственные переменные, входящие в целевую функцию с коэффициентом «М», то оценки _к состоят из двух слагаемых _к и _к(М), первое не зависит от М, а второе зависит от М. Так как М сколь угодно большое положительное число, то на первом этапе расчета используется только _к(М).

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

3. После того как все векторы, соответствующие искусственным , исключены из базиса, расчет продолжается обычным симплексным методом с использованием оценок  _к.

4. Переход от решения расширенной задачи к исходной осуществляется с использованием теорем 1,2,3.

Пример. Решить методом искусственного базиса ЗЛП

Z(X) = 3x₁ + 2x₂ + x₃ – 8x₄ max,

□ 1.Составим расширенную задачу линейного программирования

Z(X ) = 3x₁+ 2x₂ + x₃ – 7x₄ –Mx₅ – Mx₆ max,

Все вычисления проводим в таблице

3 2 1 -7 -М -М

Б	С_б	А₀	А₁	А₂	А₃	А₄	А₅	А₆
А₅ А₆	-М -М	10 2	3 2	3 1	4 [1]	-7 -2	1 0	0 1
			-5M-3	-4M-3	-5M-1	9M+8	0	0
A₅ A₃	-M 1	2 2	-5 2	-1 1	0 1	[1] -2	1 0
			5M-1	M-1	0	-M+6	0
A₄ A₃	-8 1	2 6	-5 -8	-1 -1	0 1	1 0
		Z=-10	29	5	0	0

Ответ: Х^* = (0,0,6,2), Z(X^*) = -10.

Случай вырождения. Зацикливание.

При определении разрешающего элемента, т.е. когда находим _к, может получиться несколько равных _к. Такие задачи называются вырожденными. В случае вырождения возникает проблема, какую строку выбрать за разрешающую. Если это выбрать произвольно, то может случиться так называемое зацикливание – возврат к одной из старых таблиц. Для того чтобы этого избежать, можно выбрать любую разрешающую строку. При этом в плане А₀ получатся нули и несколько итераций будут «холостыми», т.е. целевая функция не будет изменяться. Если есть возможность можно выбрать другой разрешающий столбец и при этом вырождения не будет и, значит, тем самым можно избежать зацикливания.

Пример. Решить ЗЛП

Z(X) = -3x₁ + x₂ min,