korobov

141

правильность решения задачи. Из табл. 3.7 мы получаем оптимальное решение задачи (3.60), (3.61):

x =

200

; x

= 0; x

=

1000

; x

= 200; x

= 0.

(3.62)

2

3

4

5

1

3

3

Совокупность неизвестных (3.62) удовлетворяет ограничениям (3.61). При этом 2,

3 и

4-е ограничения

являются

равенствами,

а первое ограничение —

строгим

неравенством

1600

Значение

целевой функции

для

допустимого

решения

3

> 500 .

(3.62)

равно

F =

620

.

3

Составим условие двойственной задачи. При этом неизвестные ее здесь будем

обозначать zi, поскольку символ yi

был использован при решении прямой задачи (3.16),

(3.17) для обозначения искусственных переменных.

Найти максимум целевой функции:

при условиях:

G=500z1+100 z2+200 z3+400 z4

(3.63)

z1≥0, z2≥0; z3≥0; z4≥0

2z2

+ 3z3

≤ 0,5,

z2

+ z4

≤ 0,6,

z1 + 2z2

≤ 0,4,

(3.64)

z

+

z

+ 2z

≤ 0,2,

1

2

4

z

3

+ z

4

≤ 0,3.

Предположим, что z1' , z2' , z3' , z4' неизвестное оптимальное решение двойственной

задачи (3.63), (3.64) и (3.62) действительно оптимальное решение исходной задачи (3.60), (3.61). Переменная z1 соответствует первому ограничению-неравенству в системе (3.61), которое при оптимальном решении (3.62) является строгим неравенством. Следовательно,

по второй теореме двойственности должно быть z1' = 0. По этой же теореме первое,

третье и четвертое ограничения в системе (3.64) должны быть равенствами, так как соответствующие им переменные x1, x3 и x4 положительны:

x	=	200	> 0; x		=	1000	> 0; x		= 200 > 0.
				3				4
1		3			3

Таким образом, учитывая, что z1' = 0, имеем:

2z2' + 3z3' = 0,5, 2z2' = 0,4, z2' + 2z4' = 0,2,

откуда

z2' = 15 , z3' = 301 и z4' = 0.

142

Подставим найденные значения z2' , z3' , z4' во второе и пятое ограничения (3.64) 0,2+0<0,6, 301 + 0 < 0,3,

которые выполняются как строгие неравенства и поэтому соответствующие этим ограничениям переменные x2 и х5 должны равняться нулю (они действительно равны нулю).

Таким образом, допустимое решение (3.62) и допустимое решение двойственной

задачи

	z		= 0, z		=	1	, z		=	1	, z		= 0	(3.65)
		1		2		5		3		30		4

удовлетворяют всем условиям второй теоремы двойственности и поэтому являются оптимальными. Значит, задача (3.60), (3.61) решена правильно. Можно еще раз убедиться в правильности решения этой задачи, применив первую теорему двойственности, по которой должно быть совпадение значений целевых функций на допустимых решениях

.прямой (3.60) и сопряженной (3.63) задач. Действительно, F = 6203 и

G = 500 0 +1000 15 + 200 301 + 400 0 = 6203 .

Итак, доказав с помощью теории двойственности правильность решения раскройной задачи (3.16),(3.17), можно сделать еще одно существенное замечание.

Задачу, условие которой представлено целевой функцией

n

F = ∑cj xj = min

j=1

и ограничениями

n

∑aij x j ≥ bi , i =1,2,...,m

j=1

x j ≥ 0,

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

m

G= ∑bi zi

i=1

и ограничениями

143

m

∑aij zi ≤ c j , j = 1,2,...,n,

i=1

zi ≥ 0.

При решении этой двойственной задачи не требуется решать вспомогательную или М-задачу.

Таким образом, можно было бы в нашем случае решить задачу (3.63), (3.64), и в последней симплексной таблице мы бы имели решение заданной задачи (3.60), (3.61).

Рекомендуется это сделать читателю.

Наконец, проверим, правильно ли решена каноническая задача (3.12), (3.13),

приведенная в 3.2 настоящей главы. Еще раз перепишем условие этой задачи.

Найти минимум целевой функции

F=2x1+x2-x3-x4

(3.66)

при условиях:

x1 − x2 + 2x3 − x4

= 2,

2x1 + x2 − 3x3 + x4

= 6,

(3.67)

x

+ x

+ x

+ x

= 7,

2

3

4

1

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0.

Оптимальное решение этой задачи получено из последней симплексной таблицы

(3.9)

x1 = 3, x2 = 0, x3=1, x4 =

3 и Fmin=2.

(3.68)

В табл. 3.9 столбцы для искусственных переменных опущены, следовательно, мы

не имеем возможности прочесть оптимальное решение двойственной задачи:

найти максимум целевой функции

G=2y1+6y2+7y3

(3.69)

при условиях:

y1 + 2y2 + y3 ≤ 2,

− y1 + y2 + y3 ≤ 1,

(3.70)

2y1 − 3y2 + y3 ≤ −1,

− y

+

y

2

+ y

3

≤ −1.

1

Однако

мы

его

можем

просто

найти. Пусть y'

, y'

, y' — оптимальное

решение

1

2

3

двойственной

задачи

(3.69),

(3.70).

Если

(3.68)

оптимальное

решение,

то

при

y

= y'

, y

2

= y

'

, y

3

= y'

первое,

третье

и

четвертое

ограничения

(3.70) должны

быть

1

1

2

3

равенствами:

y1' + 2y2' + y3' = 2,

2y1' − 3y2'

+ y3' = −1,

(3.71)

− y'

+ y

'

+ y'

= −1,

1

2

3

так как они соответствуют положительным значениям переменных в оптимальном решении (3.68) (x1 = 3>0; х3=1>0; x4 = 3>0). Система (3.71) имеет единственное решение:

y1 = 12/11, y2 = 9/11, y3= -8/11.

(3.72)

Подставляя эти числа во второе ограничение (3.70), получим строгое неравенство

144

-12/11+9/11-8/11=-1<1,

которому соответствует в решении (3.68) х2 = 0. Таким образом, выполняется условие второй теоремы двойственности и допустимые решения (3.68) и (3.72) действительно являются оптимальными решениями. В этом можно еще дополнительно убедиться проверкой равенства Fmin = Gmax. Действительно, подставляя значения (3.72) в выражение (3.69), имеем

Gmax=2 12/11+6 9/11-7 8/11=2

Ииз (3.66), (3.68) Fmin =2.

Воптимальном решении двойственной задачи (3.69), (3.70) переменная y3 = -8/11 приняла

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

3.4. Понятие о вырожденности

Вычислительные правила симплексного метода выводятся в предположении, что в каждой программе все т базисных переменных имеют положительные значения. Такие программы называются невырожденными. Программа, в которой хотя бы одна из базисных переменных принимает нулевое значение, является вырожденной, а задача линейного программирования, имеющая хотя бы одну вырожденную программу,—

вырожденной задачей.

Условие невырожденности используется только при обосновании правил перехода (см. 3.1) от одной программы (опорного решения) к «лучшей» программе, т. е. к такому решению, при котором происходит увеличение значения целевой функции. Там же установлена связь между двумя смежными значениями целевой функции F и F' в виде формулы

F ' = F − β			k	,	где
β	b
	= min	i		> 0.
	aik

В невырожденном случае всегда β>0, в вырожденном же случае, когда не все bi>0,

минимум отношения	bi	может оказаться равным нулю, т. е. β = 0, и никакого
	aik

«улучшения» при переходе к новому опорному решению не получится. Не исключена возможность неограниченного количества итераций без какого-либо увеличения значения целевой функции. Это случится, если последовательные замещения базисных переменных образуют так называемый цикл, т. е. если будет происходить повторение нескольких программ при невыполнении признака оптимальности по знакам чисел j оценочной строки.

Хотя вырожденные задачи линейного программирования встречаются относительно часто, «зацикливание» при решении их симплексным методом появляется лишь в исключительных случаях. Это объясняется тем, что зацикливание обусловлено не только вырождением, но и другими условиями, которые встречаются весьма редко. Установлено, что зацикливание невозможно, если каждая программа содержит не менее чем т—1 положительных значений переменных.

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

145

вектора. После ряда замещений «без улучшения» в конце концов становится возможным либо произвести замещение с улучшением, либо получить оптимальное решение.

Рассмотрим конкретный числовой пример.

Найти неотрицательные числа x1, x2, x3, максимизирующие целевую функцию

F= x1+2x2+3x3

(3.73)

при условиях:

3x1 + 2 x2 + x3 ≤ 6,

− x + 2x

2

+ 2x

3

≤ 3,

1

x1

− 2x2

+

x3

≤ 0,

(3.74)

− x

+ 2x

+

x

≤ 0.

1

2

3

.

Приведем данную задачу к эквивалентной канонической задаче. Найти

неотрицательные числа x1, x2,…, x7, максимизирующие целевую функцию

F= x1+2x2+3x3+0x4+0x5+0x6+0x7

(3.75)

при условиях:

3x1 + 2x2 + x3 + x4

= 6,

− x + 2x

2

+ 2x

3

+ x

5

= 3,

1

x1

− 2x2

+ x3

+ x6

(3.76)

= 0,

− x + 2x

+ x

+ x

= 0

1

2

3

7

														Т а б л. 3.10
			1	2	3			0		0	0	0
со	Ро	В	x1	x2		xз		x4		x5	x6	x7	∑	β	α
						1-я итерация
0	x4	6	3	2	1			1		0	0	0	13	6	1
0	x5	3	-1	2	2			0		1	0	0	7	3/2	2
						1
0	x6	0	1	-2				0		0	1	0	1	0	-
0	x7	0	-1	2	1			0		0	0	1	3	0	1
		0	-1	-2	-3			0		0	0	0	-6	-	-3

146

2-я итерация

0	x4	6	2			4			0	1		0	-1	0	12	3/2	1
0	x5	3	-3			6			0	0		1	-2	0	5	1/2	3/2
3	xз	0	1			-2			1	0		0	1	0	1	-	-1/2
0	x7	0	-2				4		0	0		0	-1	1	2	0	-
		0	2			-8			0	0		0	3	0	-3	-	-2
									3-я итерация
0	x4	6		4		0			0	1		0	0	-1	10	3/2	-
0	x5	3	0			0			0	0		1	-1/2	-3/2	2	∞	0
3	xз	0	0			0			1	0		0	1/2	1/2	2	-	0
2	x2	0	-1/2			1			0	0		0	-1/4	1/4	1/2	-	-1/8
		0	-2			0			0	0		0	1	2	1	-	-1/2
									4-я итерация
1	x1	3/2
0	x5	3
3	x3	0
2	x2	3/4
		3	0			0			0	1/2		0	1	3/2	6

Эта задача имеет очевидную вырожденную исходную программу x1=0, х2=0, х3=0, x4=6, x5=3, х6=0, х7=0, связанную с единичной подматрицей. Здесь две базисных неизвестных х6 и х7 равны нулю. Составим симплексную табл. (3.10) и проведем последующие итерации.

Несмотря на явную вырожденность предложенной задачи (все программы вырожденные), применение обычного алгоритма симплексного метода привело очень быстро к оптимальному решению xl = 3/2, x2 = 3/4, x3 = 0, x4=0, x5 = 3, x6 = 0, x7 =0. При этом только на последней итерации получилось приращение целевой функции. На всех предыдущих итерациях значение целевой функции оставалось неизменным нулевым исходным значением.

3.5. Обнаружение неразрешимости задачи линейного программирования

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

В первом случае неразрешимость задачи обнаруживается тем, что в процессе решения М-задачи будет получено ее оптимальное решение еще до того, как будут выведены из базисных все искусственные переменные. При этом из оставшихся искусственных базисных переменных yi хотя бы одна будет отлична от нуля. Это значит,

147

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

Рассмотрим два небольших примера неразрешимых задач линейного программирования (на две причины неразрешимости).

В отличие от всех уже рассмотренных нами задач в этих примерах примем ограничительные условия смешанного типа:

n

∑aij x j {≤,≥}bi , (i = 1,2,...,m),

j=1

чтобы читатель попутно освоил решение и этого типа задач.

Необходимо найти неотрицательные числа x1≥0 и, x2≥0 максимизирующие целевую функцию

F=2x1+x2		(3.77)
при условиях:
2x1 − 3x2 ≥ 3,		(3.78)
3x1 − x2 ≤ 2.

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

Найти неотрицательные числа x1, x2, x3, x4, максимизирующие целевую функцию

при условиях:	F=2x1+x2+0x3+0x4					(3.79)
	2x1 − 3x2	− x3	= 3,			(3.80)
	3x1 − x2
		+ x4 = 2.
Составляем	условие	эквивалентной		М-задачи.	Требуется	найти
неотрицательные числа x1, x2, x3, x4, y1, максимизирующие целевую функцию
при условиях:	F1=2x1+1x2+0x3+0x4-My1,					(3.81)
	2x1 − 3x2 − x3 + y1 = 3,					(3.82)
	3x1 − x2	+ x4
			= 2.

Составим симплексную табл.3.11 (столбец для искусственной переменной y1 в таблицу не включаем) и проделаем последовательные итерации.

Исходная программа (y1= 3, x4=2, x1 = 0, x2=0, x3 = 0) оказалась не оптимальной. Для улучшения плана проводим замещение базисной переменной x4 свободной переменной x1, поскольку в этом столбце отрицательная двойственная оценка.

									Табл. 3.11
			2	1	0	0
Со	P0	B	x1	x2	x3	x4	∑	β		α

													148
					1-я итерация
-М	y1	3	2				-3	-1		0	1	3/2	2/3
0	x4	2					-1	0		1	5	2/3	-
				3
	M→	-3	-2				3	1		0	-1	-	-2/3
		0	-2				-1	0		0	-3	-	-2/3
							2-я итерация
-M	y1	5/3
2	x1	2/3
	M→	-5/3	0				7/3	1		2/3	7/3
		4/3	0				-5/3	0		2/3	1/3

Уже на второй итерации решения задачи в оценочной строке нет отрицательных оценок, следовательно, полученное решение системы (3.82).

x1=2/3, x2=0, x3=0, x4=0, y1=5/3

является оптимальным решением М-задачи, в котором искусственная переменная y1 не равна нулю.

Следовательно, задача (3.79, 3.80), а значит и задача (3.77, 3.78) не имеют решения.

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

Тогда по правилам симплексного метода нет возможности определить, какую переменную следует ввести в базисные и какую переменную следует вывести из базисных. В таком случае задача неразрешима (целевая функция не ограничена сверху при максимизации и снизу при минимизации).

Требуется найти неотрицательные числа x1≥0, x2≥0, максимизирующие целевую функцию

F=x1+2x2		(3.83)
при условиях:
− 2x1 + x2	≤ 3,	(3.84)
x1 + x2
	≥ 2.

149

Путем введения дополнительных (выравнивающих) неотрицательных переменных x3, х4 приводим эту задачу к эквивалентной канонической задаче.

Найти неотрицательные числа x1 x2, х3, х4, максимизирующие целевую функцию

F=x1+2x2+0 x3+0 x4

(3.85)

при условиях:

− 2x1 + x2 + x3	= 3,	(3.86)
x1 + x2
	− x4 = 2.

Составляем условие M-задачи. Требуется найти неотрицательные числа x1 x2, х3, х4, y2, максимизирующие целевую функцию

F=x1+2x2+0 x3+0 x4-My2			(3.87)
при условиях:
− 2x1 + x2 + x3	= 3,		(3.88)
x1 + x2	− x4 + y2 = 2.

Составляем симплексную табл. 3.12 (без столбца у2) и проводим соответствующие вычисления по итерациям.

Для перехода от 1-й итерации ко 2-й исключаем из базисных переменных искусственную переменную у2, заменяя ее свободной переменной x2.

На 2-й итерации двойственная оценка 4 отрицательная, следовательно, надо перейти к третьей итерации. Для этого исключаем из базисных переменную x3, заменяя ее свободной переменной х4.

На 3-й итерации в оценочной строке имеется отрицательная двойственная оценка

1.

																			150
																	Т а б л .		3.12
						1		2			0		0
С0		P0	В			x1			x2		x3			x4		∑	β		α
							1-я итерация
0		x3	3			-2		1			1		0			3	3		1
-M		y2	2			1					0		-1			3	2		-
									1
	M→		-2			-1		--1			0		1			-3	-		-1
			0			-1		-2			0		0			-3	-		-2
							2-я итерация
0		х3	1			-3	0				1					0	1		-
														1
2		x2	2			1	1				0		-1			3	-		-1
			4			1	0				0		-2			3	-		-2
							3-я итерация
0		x4	1			-3	0				1		1			0
2		х2	3			-2	1				1		0			3
			6			-5	0				2		0			3

По признаку знаков двойственных оценок следовало бы ввести в базисные переменные только x1, но в столбце x1 нет положительных элементов, следовательно, задача решения не имеет. Целевая функция условиями задачи не ограничена сверху.