Метод искусственных переменных

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

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

Обеспечивая получение НДБР, эти переменные играют роль остаточных переменных, но, не имея физического смыс- ла, в процессе оптимизации они должны оказаться равными нулю.

С применением искусственных переменных связаны два основных метода: метод больших штрафов (М-метод) и двух- этапный метод.

Метод больших штрафов. В этом методе в задачу ЛП вводится обратная связь, которая обеспечивает получение оптимального решения при нулевых искусственных перемен- ных. В качестве такой обратной связи используется штраф, накладываемый на ЦФ за использование искусственных пе- ременных.

Пример 9.6. Рассмотрим задачу ЛП примера 9.1, введя в условия дополнительное ограничение:

определить max W(x) = x1 + 4x2 при ограничениях: x1 + x2 ≤ 4

-x1 + x2 ≤ 2

x1 + 3x2 ≥ 3 x1, x2 ≥ 0.

После приведения задачи ЛП к стандартному виду, по- лучим:

найти max W(x) = x1 + 4x2 + 0s1 + 0s2 + 0s3 при ограничениях:

x1 + x2+ s1                         = 4;

- x1 + x2          + s2          = 2; x1 +  3x2                                          − s3 = 3;

x1, x2 ≥ 0, s1, s2, s3 ≥ 0.

При обычном подходе для получения начального допус- тимого базисного решения необходимо приравнять нулю не- базисные переменные x1, x2, а базисные переменные s1, s2, s3 приравнять правым частям уравнений. Однако в этом слу- чае переменная s3 имеет отрицательное значение, что про- тиворечит условию неотрицательности всех переменных задачи ЛП. Введем в третье уравнение искусственную пе- ременную R1, которая будет играть роль остаточной пере- менной. За использование этой переменной в ЦФ вводится штраф — достаточно большой отрицательный коэффициент М. В задачах минимизации ЦФ этот коэффициент является положительным. В результате задача ЛП приводится к сле- дующему виду:

найти max W(x) = x1 + 4x2 + 0s1 + 0s2 + 0s3 − MR1 при ограничениях:

x1 +  x2+ s1                                         = 4;

- x1 +  x2         + s2                           = 2; x1 +  3x2                         − s3 + R1 = 3;

x1, x2 ≥ 0, s1, s2, s3, R1 ≥ 0.

Cистема линейных равенств содержит m = 3 уравнения и   n = 6 переменных, поэтому начальное базисное решение долж- но содержать n − m = 3 нулевых переменных и 3 базисных пере- менных. Если положить равными нулю свободные переменные x1, x2, s3, то сразу будет получено требуемое начальное базисное решение: s1 = 4, s2 = 2, R1 = 3.

После этого условия задачи переформулируются таким

образом, чтобы процесс решения можно было представить в удобной табличной форме (табл. 9.3).

Таблица 9.3

№ ите- рации	Базис. перем.	x 1	x 2	s 1	s 2	s 3	R 1	Реше- ние	Условие допусти- мости
0 (x 2 вкл., R 1 искл.)	Z	-1-M	-4-M	0	0	M	0	-M
	s1	1	1	1	0	0	0	4	4
	s2	-1	1	0	1	0	0	2	2
	R1	1	1	0	0	-1	1	1	1
1 (s 3 вкл., s 2 искл.)	Z	3	0	0	0	-4	4+M	4
	s1	0	0	1	0	1	-1	3	3
	s2	-2	0	0	1	1	-1	1	1
	x2	1	1	0	0	-1	1	1	-
2 (x 1 вкл., S 1 искл.)	Z	-5	0	0	4	0	M	8
	s1	2	0	1	-1	0	0	2	1
	s3	-2	0	0	1	1	-1	1	-
	x2	-1	1	0	1	0	0	2	-
3 (опти- мум)	Z	0	0	5/2	1/2	0	M	13
	x1	1	0	1/2	-1/2	0	0	1
	s3	0	0	1	0	1	-1	7
	x2	0	1	1/2	1/2	0	0	3

Для этого необходимо, чтобы начальное решение в явном виде присутствовало в столбце, характеризующем правые час- ти всех уравнений задачи. С этой целью в уравнение ЦФ под- ставляется выражение для искусственной переменной, полу- ченное из соответствующего ограничения: R1 = 3 − x1 − 3x2 + s3. В результате получается следующее выражение для ЦФ:

W(x) = x1 + 4x2 − М(3 − x1 − 3x2 + s3).

После приведения подобных членов Z-уравнение в симп- лекс-таблице будет иметь вид: W(x) − (1 + М)x1 − (4 + 3М)x2 +

+ Мs3 = − 3M.

Последовательность решения задачи представлена в табл. 9.3.

Оптимальному решению соответствует точка x1 = 1, x2 = 3, где ЦФ W(x) = 13. Так как в решении отсутствует искусствен- ная переменная, то оно является допустимым оптимальным ре- шением задачи.

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

На первом этапе вводятся искусственные переменные, необходимые для получения стартовой точки; формируется фиктивная ЦФ ϕ как сумма искусственных переменных, вы- раженных из соответствующих ограничений. Решается задача минимизации функции ϕ. Если минимальное значение функции ϕ равно нулю, то исходная задача имеет допустимое решение, в противном случае задача решения не имеет. Основная цель пер- вого этапа — получение начального решения исходной задачи.

На втором этапе решается исходная задача, при этом в качестве начального решения используется оптимальное ре- шение, полученное на первом этапе.

В симплекс-таблице для двухэтапного метода вводится еще одна строка для фиктивной ЦФ ϕ. На первом этапе усло- вие оптимальности проверяется только по элементам ϕ-строки, а с элементами Z-строки выполняются обычные для симплекс- метода процедуры расчетов. С достижением нулевого значения функции ϕ-строка, соответствующая этой функции, из симп- лекс-таблицы исключается и дальнейшие итерации, составля- ющие второй этап, осуществляются с использованием элемен- тов Z-строки.

Пример 9.7. Рассмотрим задачу примера 9.6. После приве- дения исходной задачи ЛП к стандартному виду и введения ис- кусственной переменной формируется фиктивная ЦФ:

ϕ = R1 = 3 − x1 − 3x2 + s3.

Для включения в симплекс-таблицу функция приводится к виду: ϕ + x1 + 3x2 − s3 = 3.

Решение задачи симплекс-методом представлено в

табл. 9.4.

Таблица 9.4

№ ите- рации	Базис. перем.	x 1	x 2	s 1	s 2	s 3	R 1	Реше- ние	Условие допусти- мости
0 (x 2 вкл., R 1 искл.)	Z	-1	-4	0	0		0	0
	ϕ	1	3	0	0	-1	0	3
	s1	1	1	1	0	0	0	4	4
	s2	-1	1	0	1	0	0	2	2
	R1	1	1	0	0	-1	1	1	1
1 (s 3 вкл., s 2 искл.)	Z	1/3	0	0	0	-4/3	4/3	4
	ϕ	0	0	0	0	0	-1/3	0
	s1	2/3	0	1	0	1/3	-1/3	3	3
	s2	-4/3	0	0	1	1/3	-1/3	1	1
	x2	1/3	1	0	0	-1/3	1/3	1	-
2 (x 1 вкл., s 1 искл.)	Z	-5	0	0	4	0	0	8
	s1	2	0	1	-1	0	0	2	1
	s3	-4	0	0	3	1	-1	3	-
	x2	-1	1	0	1	0	0	2	-

Опти- мум)