Материал: kozinova_at_osharina_nn_matematika_lineinaia_algebra_analiti

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

Таблица 8

			c j		2		-1	0	0	-М		b			bi	,	a		0
	cio											b				,	a		0
	cio		x	o	x		x	x	x	x		i			aik		ik
			x		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М
	строка		FM j		-2		+1	0	М	0		-6М
	0		x3		0		5	1	-2			15
	2		x1		1		2	0	-1			6
	оценочная		FM j		0		5	0	-2			12
	строка		FM j		0		5	0	-2			12
	На третьем шаге, переводя x4							в группу основных переменных, не удается
отправить в число неосновных любую из переменных x1 , x3 и получить
допустимое базисное решение. Система ограничений имеет вид:
		5x2 x3 2x4 15
		2x2		x4	6
	x1	2x2		x4	6
Согласно		данной системе				уравнений, переменная 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 ?

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										c				,	a 0
	bo	y	o		y1	y2	y3		y4	y5		i		a		ik
	i	y			y1	y2	y3		y4	y5				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М
	строка	ZM		j	-1	+1	0			0
	строка			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
	строка	ZM		j	-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
	строка	ZM		j	1	0	-1		0		-3
	строка			j

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

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

117

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

нарушен критерий оптимальности анализируемого допустимого базисного
решения, имеется положительное оценочное число ZM					4	.
					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
1 2

Z 2 y1 y2 min

2 y1 y2		2
	y1 2 y2	6

YT y		y	0
1 2	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	. Третье допустимое базисное решение
					4
YT 0	3 \| 0	0	\|	совпало со вторым. Но критерий оптимальности для
III

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

множество оптимальных планов, поскольку в оптимальном базисном решении
имеется неосновная переменная y1							с нулевым оценочным числом ZM1									0 .
															Таблица 10

		b j			2	-1	0	0	М	c			ci	,	a 0
	bo												ci

		y	o		y1	y2	y3	y4	y5		i		a		ik
	i	y			y1	y2	y3	y4	y5				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М
	строка	ZM		j	-2	+1	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
	строка	ZM		j	-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
	строка	ZM		j	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

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

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

3033
A решение проблемы
Анализ бизнес-планирования
Древнегреческий театр
Значение и смысл положений законодательства о полиции: лингво-юридический аспект
Инвестиции и их классификация
Коммуникационная политика рекламного агентства Коперник
Математика (90
Особенности разработки наружной рекламы
Производительность и эффективность труда на предприятии