kozinova_at_osharina_nn_matematika_lineinaia_algebra_analiti

Можно легко указать базисное решение системы ограничений, включающее два

отрицательных элемента:								YT 0								0	0 |		4	6 .
Модифицированная задача принимает вид:
	Y T y y																	? − план
				y			y		y			y				y
	1 7	1	2	3				4	5			6				7
	ZM 60 y1 22 y2 7 y3 M y6 y7 min − функция цели
	3y1 2 y2			y4				y6				4				− ограничения
		2 y2	2 y3 y5						y7
	12 y1													6
	Y T 0 – естественные ограничения
	1 7
																										Таблица 5
		b j		60				22			7					0		0	М		М	c		ci	,	a 0
	bio	yo		y1				y2			y3					y4		y5	y6		y7	i		aik		ik
	М	y6		3				2			0					-1		0	1		0	4	4/3
	М	y7		(12)				2			2					0		-1	0		1	6	6/12 − min
	оценочная	ZM		15М				4М		2М					-М			-М	0		0	10М
	строка		j	-60				-22			-7
	М	y6		0			(3/2)			-1/2						-1		1/4	1			5/2	(5/2)/(3/2) − min
	60	y1		1				1/6		1/6						0		-1/12	0			1/2	(1/2)/(1/6)
	оценочная	ZM		0			3М/2			-М/2					-М			М/4	0			5М/2
	строка		j					-12			+3							-5				+30
	22	y2		0				1		-1/3				-2/3				1/6				5/3
	60	y1		1				0		2/9					1/9			-1/9				2/9
	оценочная	ZM		0				0			-1					-8		-3				50
	строка		j

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

YT 0	0 0 | 0 0 | 4 6 . План не является оптимальным, так как
I

нарушен критерий оптимальности анализируемого допустимого базисного решения при минимизации функции цели, имеются положительные оценочные числа ZM1 , ZM 2 , ZM 3 .

111

На втором шаге переведем y1 в группу основных переменных, а y7 в группу неосновных. Поскольку y7 , являясь искусственной переменной,

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

переменная осталась

только

во

втором

уравнении

с

единичным

1

5

коэффициентом. Получим решение: YIIT

0

0 | 0 0

|

.

Оно не

2

2

ZM

.

является оптимальным, имеются положительные оценочные числа

2

, ZM

5

На третьем шаге переведем

y2 в группу основных переменных,

а y6 в

группу неосновных.

Поскольку

y6 ,

являясь

искусственной

переменной,

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

	YIIIT		2	5
Получим решение:							0 | 0 0 |	.	Оно является
				3
		9

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

YT 2 / 9

5/ 3 0 ,

Z o 50 .

Используя теоремы двойственности, найдем решение двойственной задачи планирования оптимального выпуска продукции:

X T x		x		x	x	x ? – план
1 5	1	2		3	4	5

F 4x1 6x2 max – прибыль (функция цели)

3x1 12x2 x3 60
	2x1	2x2 x4	22 – ограничения на ресурсы
		2x2 x5	7

X T x		x		x	x	x 0	– естественные ограничения
1 5	1	2		3	4	5

Между переменными предложенных взаимно-двойственных задач существует взаимно однозначное соответствие:

Y X д ,

Yд X

Согласно схеме соответствия переменных получим:

xo

xo

Z

, j 1,2 ;

Z

, i 1,3 .

j

M 3 j

2 i

Mi

112

Таблица 6

b j

60

22

7

0

0

М

М

c

ci

, a 0

bo

a

y

o

y1

y2

y3

y4

y5

y6

y7

i

ik

i

ik

оценочная

ZM

0

0

-1

-8

-3

50

строка

j

x3

x4

x5

x1

x2

F o

Используя теоремы двойственности, определим оптимальный выпуск продукции, обеспечивающий предприятию максимальную прибыль (табл. 6).

	8
X o		(ед.) – оптимальный план выпуска продукции,
	3
	0
X дo	0		(ед.) – остатки ресурсов,
	1

F o max F min Z Z o 50 (ед.) – максимальная прибыль.

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

Пример 7. Решим модифицированным симплексным методом задачу: (каноническая форма задачи)

X	x		?	X T x x					x x ?
	1
2 1				1 4	1	2			3	4
	x2
F x1 x2 max				F x1 x2 max
x1 x2 2				x1 x2 x3					2
		3			x2	x4			3
x1 x2				x1
X	x		0	X T x x					x x 0
	1
2 1				1 4	1	2			3	4
	x2

Легко указать базисное решение системы ограничений:

X T 0 0 | 2 3 .

Составим модифицированную задачу.

113

	X T	x x				x		x			x		x	?
	1 6	1	2			3		4			5		6
	F x1 x2 M x5 x6 max
	x1 x2 x3					x5			2
			x4				x6 3
	x1 x2
	X T	x x				x		x			x		x 0
	1 6	1	2			3		4			5		6
																							Таблица 7
			c j				1			1			0		0		-М	-М	b		bi	, a	0
	cio
			x	o			x			x			x		x		x	x	i		aik	ik
							1			2			3		4		5	6
	-М		x5				-1			1			-1		0		1	0	2	−
	-М		x6				(1)			-1			0		-1		0	1	3	3/1 − min
	оценочная		FM j				(-1)			-1			М		М		0	0	-5М
	строка
	-М		x5				0			0			-1		-1		1		5	−
	1		x1				1			-1			0		-1		0		3	−
	оценочная		FM j				0			(-2)			М		М		0		-5М
	строка														-1				+3
	В группу основных переменных первого допустимого базисного решения
включены искусственные переменные:															X T	0 0		| 0	0 |	2		3 .	Решение
															I

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

На втором шаге переведем x1 в группу основных переменных, а x6 в группу неосновных. Поскольку x6 , являясь искусственной переменной, перешла в группу неосновных, исключаем ее из дальнейшего рассмотрения.

Полученное допустимое базисное решение X T 3 0	| 0 0	| 5 не
II
является оптимальным, имеется отрицательное оценочное число FM 2 .
На третьем шаге, переводя x2 в группу основных переменных, не удается
отправить в число неосновных любую из переменных	x1 , x5 ,	и получить

допустимое базисное решение. Благодаря наличию в системе ограничений
одного уравнения	x3 x4 x5 5 , включающего искусственную
	114

переменную x5 5 , можно утверждать, что область допустимого планирования пуста и предложенная задача не имеет решения.

Пример 8. Решим модифицированным симплексным методом задачу: (каноническая форма задачи)

	x		?
X 1
2 1
	x2

F 2x1 x2 max

	2x1 x2 3
	x1	2x2 6
X		x		0
		1
2 1
		x2

X T x x							x x		?
1 4	1	2					3	4
F 2x1 x2		max
2x1 x2 x3							3
	x1 2x2	x4 6
X T x x							x x		0
1 4	1	2					3	4

Легко указать базисное решение системы ограничений:

X T 0

0 | 3 6 .

Модифицированная задача принимает вид:

X T		x x			x x			x	?
1 5		1	2		3	4		5
F 2x1 x2 M x5 max
2x1 x2 x3							3
	x1	2x2		x4 x5			6
X T		x x			x x			x	0
1 5		1	2		3	4		5

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

X T 0	0 | 3 0 | 6 . Оно не является оптимальным, так как нарушен
I

критерий оптимальности анализируемого допустимого базисного решения при максимизации функции цели, имеются отрицательные оценочные числа

FM1 , FM 2 .

На втором шаге переведем x1 в группу основных переменных, а x5 в группу неосновных. Поскольку x5 , являясь искусственной переменной, попала в группу неосновных, исключаем ее из дальнейшего рассмотрения. Получим

допустимое базисное решение:	X T 6 0 | 15	0 | . Оно не является
	I

оптимальным, нарушен критерий оптимальности анализируемого допустимого базисного решения, имеется отрицательное оценочное число FM 4 .

115

Таблица 8

				c j			2		-1		0	0	-М		b			bi	,	a		0
	cio
				x	o		x		x		x	x	x		i			aik		ik
							1		2		3	4	5
	0			x3			-2		1		1	0	0		3		−
	-М			x5			(1)		2		0	-1	1		6		6/1 −min
	оценочная			FM j			-М		-2М		0	М	0		-6М
	строка						-2		+1
	0			x3			0		5		1	-2			15
	2			x1			1		2		0	-1			6
	оценочная			FM j			0		5		0	-2			12
	строка
	На третьем шаге, переводя x4										в группу основных переменных, не удается
отправить в число неосновных любую из переменных x1 , x3 и получить
допустимое базисное решение. Система ограничений имеет вид:
		5x2 x3 2x4 15
		2x2			x4		6
	x1
Согласно		данной системе						уравнений, переменная x4									может				неограниченно
увеличиваться одновременно с переменными x1														и x3 ,		при этом функция цели
F 12 5x2 2x4 также будет неограниченно														увеличиваться								F , т.е.

задача не имеет решения.

Пример 9. Решим модифицированным симплексным методом задачу: (каноническая форма задачи)

Y			y		?	YT y y					y
			1
2 1						1 4	1	2			3
		y2
Z y1 y2 min						Z y1 y2 min
2 y1 y2 3						2 y1 y2 y3
	y1		2 y2 6				y1 2 y2				y4
Y			y		0	YT y y					y
			1
2 1						1 4	1	2		3
		y2

Легко указать базисное решение системы ограничений:

YT 0 0 | 3 6 .

Составим модифицированную задачу.

y4 ?

3

6

y4 0

116

Y T y y		2		y	y		y	?
1 5	1			3	4		5
Z y1 y2 M y5 min
2 y1 y2 y3						3
	y1 2 y2			y4	y5	6
Y T y y		2		y	y		y	0
1 5	1			3	4		5

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

YT 0	0 | 3 0 | 6 . Решение не является оптимальным, нарушен
I

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

ZM1 , ZM 2 .

Таблица 9

		b j			1	-1	0		0	М	c			ci	,	a 0
	bo
		y	o		y1	y2	y3		y4	y5		i		a		ik
	i													ik
	0	y3			-2	1	1		0	0	3		3/1 − min
	М	y5			1	(2)	0		-1	1	6		6/2 − min
	оценочная	ZM			М	2М	0		-М	0	6М
	строка			j	-1	+1
	0	y3			-2,5	0	1		(0,5)		0		0/0,5 − min
	-1	y2			0,5	1	0		-0,5		3		−
	оценочная	ZM			-1,5	0	0		0,5		-3
	строка			j
	0	y4			-5	0	2		1		0
	-1	y2			-2	1	1		0		3
	оценочная	ZM			1	0	-1		0		-3
	строка			j
	На втором шаге переведем						y2	в группу основных переменных, а y5 в
группу неосновных.				Поскольку y5 , являясь искусственной, перешла в группу

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

117

базисное решение YT 0 3 | 0	0 |	не является оптимальным,
II

нарушен критерий оптимальности анализируемого допустимого базисного
решения, имеется положительное оценочное число ZM					4	.
На третьем шаге переведем y4			в группу основных переменных, а y3 в
группу	неосновных.	Третье	допустимое			базисное	решение:
YT 0	3 | 0 0 |	совпало	со вторым.	Решение не			является
III

оптимальным, нарушен критерий оптимальности анализируемого допустимого базисного решения, имеется положительное оценочное число ZM1 .

На четвертом шаге, переводя y1 в группу основных переменных, не удается отправить в число неосновных любую из переменных y2 , y4 и

получить новое допустимое базисное решение. Система ограничений принимает вид:

5 y1	2 y3 y4 0
	y2 y3	3
2 y1

Согласно данной системе уравнений, переменная y1 , может неограниченно

увеличиваться одновременно с переменными y2 и y4		, при этом функция цели
Z 3 y1 y3	может неограниченно уменьшаться	Z , т.е. задача не
имеет решений.
Пример 10. В предыдущем примере поменяем лишь функцию цели на
новый вариант	Z 2 y1 y2 . Решим модифицированным симплексным

методом измененную задачу:

(модифицированная задача)

YT y		y	?
1 2	1		2

Z 2 y1 y2 min

2 y1 y2		2
	y1 2 y2	6

YT y		y	0
1 2	1		2

Y T		y y	2		y	y		y	?
1 5		1			3	4		5
Z 2 y1 y2 M y5 min
2 y1 y2 y3							3
	y1 2 y2				y4	y5	6
Y T		y y	2		y	y		y	0
1 5		1			3	4		5

В составе основных переменных первого допустимого базисного решения

имеется искусственная переменная:	YT 0	0 | 3 0 | 6 . Решение не
	I

является оптимальным, нарушен критерий оптимальности анализируемого допустимого базисного решения при минимизации функции цели, имеются положительные оценочные числа ZM1 , ZM 2 . Второе допустимое базисное

118

решение	YT 0	3	|	0 0 |		не является оптимальным, имеются
	II					. Третье допустимое базисное решение
положительные оценочные числа ZM					4
YT 0	3 | 0	0	|	совпало со вторым. Но критерий оптимальности для
III

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

множество оптимальных планов, поскольку в оптимальном базисном решении
имеется неосновная переменная y1								с нулевым оценочным числом ZM1									0 .
																Таблица 10
		b j			2	-1		0	0	М	c			ci	,	a 0
	bo
		y	o		y1	y2		y3	y4	y5		i		a		ik
	i													ik
	0	y3			-2	1		1	0	0	3		3/1 − min
	М	y5			1	(2)		0	-1	1	6		6/2 − min
	оценочная	ZM			М	2М		0	-М	0	6М
	строка			j	-2	+1
	0	y3			-2,5	0		1	(0,5)		0		0/0,5 − min
	-1	y2			0,5	1		0	-0,5		3		−
	оценочная	ZM			-2,5	0		0	0,5		-3
	строка			j
	0	y4			-5	0		2	1		0
	-1	y2			-2	1		1	0		3
	оценочная	ZM			0	0		-1	0		-3
	строка			j

Система ограничений задачи на третьем (последнем) шаге модифицированного симплексного метода принимает вид:

5 y1	2 y3 y4	0	.
	y2 y3	3
2 y1

Согласно системе ограничений, переменная y1 , может принимать любые

значения (в том числе сколь угодно большие) одновременно с переменными y2
и	y4 ,	но	при этом	значение функции цели Z 3 y3 не меняется
y3	0		Z 3 , т.е.	предложенная задача имеет бесчисленное множество

решений.

119

6.6.Задания для самостоятельной работы

Задача 1. Предприятие выпускает два вида продукции, используя три вида ресурсов. Известны A − матрица норм затрат ресурсов, B − запасы ресурсов, C − прибыль на единицу продукции. Требуется: а) составить модель задачи планирования выпуска продукции, обеспечивающего получение максимальной прибыли; найти решение; б) найти оптимальное решение и оптимум двойственной задачи с помощью теорем двойственности.

		4				2							80								4				2				80
																			, C 3	2																	4
1. A				2		3					, B			60							2. A	2			2			,	B	60				, C 2
				0		1								15								2			4
																													100
	4				2						80										7				4				56
																			, C 2	3																, C 6	4
3.	A		4		6					, B 120											4. A		6		7		, B				42
			0		2																		3		2						18
											30
			8		4						160													8	2							80
																			, C 4	2																, C 4 1
5. A			2		3					,	B		60								6. A			3	3				, B			60
			0		3								45											1	4							40
			4		2									32								4			2				120
																			, C 4	8																, C 5	2
7. A			4		6						, B			48							8. A	1 3						,	B	90
			0 10											60								1 1								40
		4			2							40												4		2				80
																	, C 10			20	10. A 2					3			, B 60 , C 3								1
9.	A	6			9			,			B	90
		1			2							20										4 1								20
	1				4								8									0			2							8
																	, C 12			18															, C 8		12
11. A		2			3			,			B 12										12. A		2		3				, B			6
		4 1											8											4 1								4

120