Материал: kozinova_at_osharina_nn_matematika_lineinaia_algebra_analiti

Смотрите также:

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

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

отрицательных элемента:						YT 0							0	0 \|		4	6 .
Модифицированная задача принимает вид:
	Y T y y														? − план
	Y T y y			y	y		y			y			y		? − план
	1 7	1	2	3		4	5			6			7
	1 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	2 y2	2 y3 y5				y7				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М
	строка	ZM	j	-60		-22			-7							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
	строка	ZM	j	0		-12			+3						-5	0			+30
	строка		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
	строка	ZM	j	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 , являясь искусственной переменной,

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

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

только

во

втором

уравнении

единичным

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

0 | 0 0

Оно не

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

, ZM

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

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

а y6 в

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

Поскольку

y6 ,

являясь

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

переменной,

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

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

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

YT 2 / 9

5/ 3 0 ,

Z o 50 .

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

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

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

, j 1,2 ;

, i 1,3 .

M 3 j

2 i

112

Таблица 6

b j

, a 0

оценочная

-1

-8

-3

строка

F o

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

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

	3
	0

X дo	0		(ед.) – остатки ресурсов,
	1
	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	?
	X T	x x			x		x			x	x	?
	1 6	1	2		3		4			5	6
	1 6
	F x1 x2 M x5 x6 max
	x1 x2 x3				x5			2
			x4			x6 3
	x1 x2		x4			x6 3
	X T	x x			x		x			x	x 0
	X T	x x			x		x			x	x 0
	1 6	1	2		3		4			5	6
	1 6																				Таблица 7
																					Таблица 7

			c j			1			1		0		0		-М	-М	b		bi	, a	0
	cio																		bi


			x	o		x			x		x		x		x	x	i		aik	ik
			x			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М
	строка		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М
	строка		FM j			0			(-2)				-1		0		+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
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		?
X T x x			x x		?
1 4	1	2	3	4
1 4
F 2x1 x2		max
2x1 x2 x3			3
	x1 2x2	x4 6
	x1 2x2	x4 6
X T x x			x x		0
X T x x			x x		0
1 4	1	2	3	4
1 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

Источник: https://studfile.net/preview/15912971/

x ? – план

2418
3033
3499
A решение проблемы
Анализ бизнес-планирования
Аттестация: понятие, назначение, порядок проведения
Всемирная история. от Нового времени до конца XX века. Гурина Е.М
Древнегреческий театр
Значение и смысл положений законодательства о полиции: лингво-юридический аспект
Инвестиции и их классификация