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

Выше было показано, что если ограничения ЗЛП содержат единичную матрицу порядка m или приводятся к такому виду, то тем самым при неотрицательных правых частях уравнений определен первоначальный план, исходя из которого, симплексным методом, находится оптимальный план. В частности, если ограничения ЗЛП можно преобразовать к виду АX£A₀ при А₀³0, то система ограничений всегда содержит единичную матрицу. Если же ЗЛП, имеющая решения, не содержит единичную матрицу и не приводится к указанному виду, то для решения применяется метод искусственного базиса.

Найдем минимальное значение функции L=С₁x₁+С₂x₂+…+С_nx_n при ограничениях

.

причем x_j ³ 0 j=1,2,..,n; b_i ³ 0, i=1,2,…,m, и система ограничений не содержит единичную матрицу.

Для получения единичной матрицы в каждое уравнение вводим по одной вспомогательной переменной y₁,y₂,...,y_m с коэффициентом +1, называемой искусственной. В целевую функцию в задаче на максимум искусственная переменная войдет с коэффициентом –М, а в задаче на минимум с коэффициентом +М. Число М сколь угодно большое по сравнению с единицей (М>>1). Выражение М(y₁+…+y_m) назовем М-функцией.

Тогда рассмотрим расширенную задачу, связанную с отысканием наименьшего значения новой линейной функции =L+М(y₁+…+y_m)=С₁x₁+С₂x₂+…+С_nx_n+Мy₁+…+Мy_m при ограничениях:

(1)

Единичные векторы А_n+1,…,A_n+m, соответствующие искусственным переменным, образуют искусственный базис:

(2)

Тогда в целевой функции в расширенной задаче при коэффициенте М вместо переменных y_i подставляем их выражения из (2).

Очевидно, что решение исходной системы (1) эквивалентно решению системы (2) при равенстве нулю дополнительных переменных y₁=0, y₂=0, ...,y_m=0.

Для отыскания оптимального плана исходной задачи используют следующую теорему.

Теорема.

1. Если в оптимальном решении расширенной задачи при нахождении минимума =(x*₁,x*_2,…,x*_n,0,…0) все искусственные переменные y_i=0 (i=1,2,…,m), то решение Х*=(x*₁,x*_2,…,x*_n) является оптимальным решением исходной задачи.

2. Если оптимальное решение расширенной задачи содержит, по крайней мере, одну искусственную переменную y_i>0, то исходная задача не имеет решения (т.е. она не совместна).

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

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

Заметим, что если решение - оптимальное решение расширенной задачи, то решение Х* - решение исходной задачи, при этом ( )=L(X*). Равенство значений функции следует из того, что решение от решение Х* отличается m последними компонентами, равными нулю.

Докажем, что план Х* - оптимальное решение исходной задачи. Предположим противное, допустим, что Х* не является оптимальным решением. Тогда существует такое оптимальное решение Х=(x₁,x_2,…,x_n), для которого L(X)<L(X*). Отсюда для вектора =(x₁,x_2,…,x_n,0,…0), являющегося решением расширенной задачи, получим

( )= L(X)<L(X*)= ( ),

т.е.

( ) < ( ),

что противоречит условию задачи о том, что - оптимальное решение расширенной задачи.¨

Из теоремы следует, что вначале следует найти оптимум М-функции. Если он равен 0 и все искусственные переменные y_i=0, то далее их можно отбросить и решать исходную задачу, исходя их полученного допустимого базисного решения. На практике находят оптимум (- М)-функции.

Метод искусственного базиса в основном совпадает с обычным симплексным методом, но имеет некоторые особенности:

1. Ввиду того, что первоначальный опорный план расширенной задачи содержит искусственные переменные, входящие в целевую функцию с коэффициентом –М (в задаче на максимум), с коэффициентом +М (в задаче на минимум), то симплексные таблицы имеют на одну строку больше, чем обычные таблицы. В (m+1)-ю строку записываем коэффициенты слагаемых целевой функции расширенной задачи, независящие от М, в (m+2)-ю - зависящие от М. Таким образом, последняя строка – это (- М)-функция. Из теоремы следует, что вначале следует найти оптимум М-функции.

2. Соответствующие искусственным переменным вектора, выводимые из базиса опорного решения, в дальнейшем исключаются из рассмотрения.

3. После того как все векторы, соответствующие искусственным переменным, исключаются из базиса, расчет продолжается обычным симплексным методом по виду коэффициентов (m+1)-ой строки.

Пример. L=x₁+2x₂ ®max при ограничениях

Умножим 1-е и 2-е неравенство на (-1), получим

Приведем систему ограничений к канонической форме, имеем

Прежде всего, замечаем, что, например, x₄ и x₅ входят только во 2-е и 3-е уравнения соответственно, причем коэффициенты при них имеют тот же знак, что и свободные члены. Поэтому можем объявить их базисными переменными. Тогда чтобы получить первоначальный опорный план, в 1-ое уравнение введем искусственную переменную y₁:

Тогда базисные переменные:

Линейная функция расширенной задачи = x₁+2x₂-Мy₁=x₁+2x₂-М(x₁-x₂+х₃)®max

Первоначальный опорный план ₁=(0;0;0;3;3;1).

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

Базис	Свобод.	переменные	Оценочное
	член А0	x1	X2	х3	x4	x5	Y1	Отношение
Y1		-1		-1
Х4		-1
x5								µ
L		-1	-2					Max
Mф			-1					Max

В (m+1)-ю строку записываем слагаемые, независящие от М, в (m+2)-ю - зависящие от М. Проверяя выполнения критерия оптимальности при отыскании максимума (-М)-функции, определяем, что в последней строке имеется отрицательный элемент во 2-ом столбце, значит он разрешающий, х₂ переходит в базисные. Минимальное оценочное отношение в 1-ой строке, она разрешающая. Переменная y₁ переходит в свободные, обращается в 0 на следующем базисном решении и далее исключается из рассмотрения. Получаем новую таблицу 2.

Таблица 2.

Базис	Свобод.	переменные	Оценочное
	член А0	x1	x2	х3	x4	x5	отношение
х2		-1		-1
х4
х5
L		-3		-2			Max
-Mф							Max

Последняя строка показывает, что критерий оптимальности выполнен;

max(-М_ф)=0, далее эту строку можно не рассматривать. Получено допустимое базисное решение ₂= (0; 1; 0; 2; 3;0), начиная с которого решаем исходную задачу в соответствии с обычным алгоритмом.

Таблица 3.

Базис	Свобод.	переменные	Оценочное
	член А0	x1	x2	х3	x4	X5	Отношение
х2				-1			µ
х4	2						2/1
х1		-1					µ
L				-2

₃= (3; 4; 0; 2; 3)

Таблица 4.

Базис	Свобод.	Переменные	Оценочное
	член А0	x1	x2	х3	x4	x5	Отношение
х2
х3
х1
L

Получаем следующее опорное решение ₄= (3; 6; 2; 0; 0), которое является оптимальным решением расширенной задачи, т.к. оценки для всех векторов положительные. Исходная задача имеет оптимальное решение, которое получается отбрасыванием нулевых дополнительных и искусственной переменных. X*=(3;6) L_max=15.

Контрольные вопросы

1. Геометрическая интерпретация симплексного метода.

2. Построение первоначального опорного плана.

3. Критерии оптимальности решения задач линейного программирования симплексным методом.

4. Табличный вариант реализации симплексного метода.

Рекомендованная литература: [ 1, 5, 6, 7]