Материал: Методы оптимизации в примерах и задачах. Медведь Н.А., Фокин А.А

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

	Поскольку на первой итерации												3		0 , в базис вводится вектор A3 .
		min{	12			,		10	} 3 ,			т.е. в	качестве направляющего									элемента
		min{				,			} 3 ,			т.е. в	качестве направляющего									элемента
			4			3
	выбирается a23 .

	B	CB								0		1		-3			0		2		0
					x
					x						A1	A2		A3			A4		A5		A6
											A1	A2		A3			A4		A5		A6
	x1	0		10						1		5/2		0			0		2		0		4
	x3	-3		3						0		-1/2		1			1/4		0		0		-

	x6	0		1						0		-5/2		0			-3/4		8		1		-

	j			-9						0		1/2		0			-3/4		-2		0

2		0 , то есть в базис вводится вектор A2 .
		4 , т.е. в качестве направляющего элемента выбирается a12 .

	B	CB									0	1	-3			0		2		0
							x
							x				A1	A2		A3			A4		A5		A6
											A1	A2		A3			A4		A5		A6
	x2	1				4					2/5	1	0			0		4/5		0		-
	x3	-3				5					1/5	0	1			1/4		2/5		0		-

	x6	0				11					1	0	0			-3/4		10		1		-

	j					-11					-1/5	0	0			-3/4		-12/5		0

	Все		j			0 ,					то	есть		получена					оптимальная				точка
			j
	x*	(0,4,5,0,0,11) . Поскольку на небазисных векторах																				j	0 , то
																						j

решение в задаче единственно.

Пример 2. Решить задачу

		2x1			x2		x3			3x4	2x5		x6	max
		x1			x2		x3			x4				1,
		x1			x2							x5		1,
		x1		3x2			x3						x6	2,
		xi	0, i			1,6.

B		CB						2			-1		1		3	-2	1
					x
					x				A1		A2		A3		A4	A5	A6
									A1		A2		A3		A4	A5	A6
x4		3		1				-1			1		-1		1	0	0	-
x5		-2		1				1			-1		0		0	1	0	1

x6		1		2				1			-3		1		0	0	1	2

	j			3				-6			3		-3		0	0	0

x4		3		2				0			0		-1		1	1	0
x1		2		1				1			-1		0		0	1	0
x6		1		1				0			-2		1		0	-1	1

	j			9				0			-3		-3		0	6	0

На второй итерации получаем, что оценка 2 0 , но в столбце A2

нет положительных элементов. Это означает, что целевая функция не ограничена на допустимом множестве, т.е sup z(x)

Задачи для самостоятельного решения

Решить симплекс - методом:
4.3.1 x1 + x2 + x3	min,
x1	– x4	– 2 x6 = 5,
x2	+ 2 x4 – 3 x5 + x6 = 3,

x3 + 2 x4 – 5 x5 + 6 x6 = 5;

4.3.2 2 x1 + x2 – x3 – x4 min, x1 + x2 + 2 x3 – x4 = 2,

2x1 + x2 – 3 x3 + x4 = 6, x1 + x2 + x3 + x4 = 7;


4.3.3	x1 – 2x2 + 3x3 min,					4.3.4	2x1	– 3x2	max,
	2x1 + 3x2			+ 4x3 = 1,			5x1	+ 2x2	10,
	–2x1 + x2 + 3x3 = 2;						x1	+ 3x2	12;
4.3.5	6 x1	+ 4 x2		min,		4.3.6	2 x1 – 4 x2		min,
	2 x1 +		x2	3,			8 x1 – 5 x2		16,
	x1 – x2			1;			x1 + 3 x2		2,
4.3.7	7 x1	+ 5 x2		max,		4.3.8	3 x1 + 2 x2		max,
	7 x1 + 5 x2			7,			4 x1 + 2 x2		12,
	7 x1 – 5 x2			35,			x1 + 2 x2		10,
	x1 – x2			0;			2 x1 + 2 x2 = 6;
4.3.9	4 x1	+ 5 x2		+ 9 x3 + 11 x4		max,
	x1 + x2 + x3 +				x4	15,
	7 x1 + 5 x2			+ 3 x3 +	2 x4	80,
	3 x1 + 5 x2			+ 10 x3 + 15 x4		60;

4.3.10	2 x1	+ x2	–	x3 – x4	min,
	x1 + x2 + 2 x3 – x4 = 2,
	2 x1 + x2 – 3 x3 + x4 = 6,
	x1 + x2 + x3 + x4 = 7;
4.3.11	4x1	+ x2	– 2x3 – x4		– x5 min,
				x3 – x4 + x5 = 1,
		x2		+ 2x4	– x5 = 1,
	x1	+ 2x2			+ 2x5 = 4;

100

4.3.12 x1	+ 2 x2		+ 3 x3 – x4	max,
x1	+ 2 x2		+ 3 x3	= 15,
2 x1	+	x2	– 3 x3	= 20,
x1	+	2 x2	+ x4 = 10.

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

В общем случае ограничения ЗЛП могут не содержать единичной матрицы и использование базового симплексного метода будет невозможно из-за отсутствия исходного базиса.

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

По условию исходной задачи (4.3.1)-(4.3.3) (см. 4.3) составляется вспомогательная задача следующего вида:

n		m
	c j x j	M	zi	max
J 1		i	1
Ax	Ez	b	(b	0),
x	0, z	0,

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

Очевидно, что введение слагаемых с положительными zi

уменьшает значение целевой функции. Введение числа M в целевую функцию производит как бы еѐ “штрафование” за выбор точки с

положительными координатами zi . Тогда в оптимальной точке при достаточно большом M все значения zi будут равны нулю. Однако

это возможно только в случае, если в исходной задаче допустимое множество не пусто. Имеет место следующая теорема.

Теорема 2. Если исходная задача имеет решение, то существует такое число М°, что при всех М>М° вспомогательная М-

задача тоже имеет решение, и в любом ее решении	x*	точка z*=0,
	z*

101

0 , то в исходной задаче

а х* будет решением исходной задачи.

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

получена такая оптимальная точка, что z* допустимое множество пусто.

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

		m
0	M	zi	max , а после достижения максимума непрерывно
	i	1

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

переменные	zi	0 , т.е.	являются базисными,			и значение целевой
функции,	и	оценки	j	можно	представить в		виде


j M j , j	1,n . Следовательно, если				вводить в базис		такой
вектор Aj , что соответствующее значение					j	0 , то это приведет к

увеличению значения 0 . Максимальное значение будет получено,

когда, все	j	будут неотрицательными.				Очевидно, что при этом
	j
возможны	две ситуации:		0	0 и	0	0 . Рассмотрим оба эти
			0		0
случая.
1. Оптимальное значение			0	0 . Наличие такой ситуации на одной
			0

из итераций означает, что допустимое множество исходной задачи пусто, т.к. оптимальная точка имеет координаты zi 0 .

2. Оптимальное значение	0	0	. Такой вариант возможен в двух
	0

ситуациях:

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

б) искусственные переменные zi не выведены из базиса, но их

102

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

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



_1966(~1
_Антонян Ю.М., Сексуальные преступления. Чикатило и другие
_РГР № 1 (2)
- Габариты и масса 27
'Образ–Я' и его развитие средствами диалога
"Логистическая технология JIT"
"Особенности правовой системы Российской Федерации" по дисциплине "Теория государства и права"
«Анализ ликвидности и платежеспособности предприятия» (на материалах ОАО Московская кондитерская фабрика «Красный Октябрь»)