Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Запорожский институт экономики и информационных технологий

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

2_0

.pdf

Скачиваний:

Добавлен:

23.02.2016

Размер:

1.63 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 45 / 145 6 7 8 9 10 11 12 13 14 > Следующая >>>

дача несовместна. Иначе целевая функция расширенной задачи будет неог- раниченно уменьшаться с ростом М и не сможет достичь максимума.

Расширенная задача решается обычным симплекс-методом. Числа в

индексной строке имеют вид a+bM. Для их записи в симплексной таблице

индексную строку разбиваем на две подстроки и записывают их в виде . b

Другими словами индексную строку записывают в двух уровнях: в (m+1)

строку вносят а, а в (m+2) b. Знак числа определяется знаком числа b если b

b ≠ 0 . Поэтому сначала направляющий столбец выбирают по нижней строке, а после перевода всех искусственных переменных в свободные оптимизация производится по верхней индексной строке.

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

При использовании метода искусственного базиса в качестве критерия надо руководствоваться следующим правилом:

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

Замечание. Если m+2 индексная строка в результате преобразований превращается в нулевую (с неположительными оценками искусственных векторов), то это свидетельствует о том, что построен начальный опорный план исходной задачи и дальнейшая оптимизация производится по предпо- следней индексной строке.

Имеем начальный опорный план

	X	Б1 = (0,0,0,0,6,4,6) и
			0
			0
Z′(X Б1 )= 2 0+ 0 − 0+ 0 + 0 6− M 4− M 6 = −10М =			.
			−10

Проверяем полученный план на оптимальность. Для этого составляем симплекс-таблицу (табл. 2.3.1).

																			Таблица 2. 3.1
													↓
																					bi
									А1		А2		А3		А4	А5		А6		А7	bi
				СБ
		Б1																			a
		Б1					В1														a
				1																	i3
								2		1		–1			0	0	–М			–М
					–M	6		1		1			2	–1		0	1			0	3	← \|
		А	6		–M	6		1		1			2	–1		0	1			0	3	← \|
←			6
					–M	4		–1		2		[2]			0	0	0			1	2	(–1) (1)
	А7				–M	4		–1		2		[2]			0	0	0			1	2	(–1) (1)
				0		6		4		–1		–2			0	1	0			0	–
		А5		0		6		4		–1		–2			0	1	0			0	–
			z j − cj			0		–2		–1		1			0	0	0			0
						–10		0		–3		–4			1	0	0			0

Покажем как находится индексная строка.

Z′(		Б		)	= −	6M	−	4M	+	0	6	=	0	−	10М		0	,	z − c = −M + 1 M + 0 4 − 2 = −2 =	−2		,
	X		1
																=			1 1		0
																	−10

z2 − c2	= −M − 2 M + 0 − 1 = −3M − 1 = −1	,
	−3
z − c = −2M − 2 M + 0 (−2) − (−1) = 1− 4M =			1
3 3			−4
			−4

и так далее.

План будет оптимальным, если все оценки в индексной строке поло- жительны или нулевые, т. е. z j − cj ≥ 0 .

Если находится минимум Z , то в целевую функцию искусственные пе- ременные дописываются с большим положительным числом (M ) . Целевая

функция достигнет минимального значения, если все оценки будут неполо- жительными (z j − cj ≤ 0).

Первый план не оптимален. В нижней индексной строке наименьшую отрицательную оценку имеет À3 . Вектор, выводимый из базиса определяем

по симплексному отношению θ = θ03	= min	6	,	4	= 2 . Из базиса выводим

		2	2

вектор А7 . Составляем новую симплекс-таблицу.

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

Составляем вторую симплекс-таблицу

																				Таблица 2.3.2
									↓
																									bi
									А1			А2		А3		А4	А5		А6		А7				bi
	Б2																								a

				2			В2
				2																					i1
								2			1		–1		0		0	–М			–М
←		6		–M		2		[2]			–1		0		–1		0	1			–1			1		(1/4)( -3/2)
←	А	6		–M		2		[2]			–1		0		–1		0	1			–1			1		(1/4)( -3/2)
					–1	2		−		1	1		1		0		0	0				1			–		\|
	А3									1												1
	А3																				2
								2													2
				0		10		3			1		0		0		1	0			1			10/3
	А5			0		10		3			1		0		0		1	0			1			10/3
			z j − cj			–2		−		3	–2		0		0		0	0			−		1
						–2		−			–2		0		0		0	0			−
								2													2
						–2		–2			1		0		1		0	0			1

Второй план X Б2 = (0,0,2,0,10,2,0) тоже не оптимальный, вектор А1 имеет отрицательную оценку. Составляем третью симплекс-таблицу. В базис

вводим вектор А1 , из базиса выводим вектор А6																													по симплексному отноше-
нию θ = θ01						= min					2		,	10	= 1.
нию θ = θ01						= min							,		= 1.
										2 3
																												Таблица 2.3.3

																																	bi
												А1				А2			А3		А4		А5		А6					А7			bi
	Б3	С																														a
	Б3	С		Б				В3																								a
				Б																													i2
					3
											2				1				–1	0			0	–М					–М
		2					1				1				−			1	0	−		1	0			1			−		1		–		← \|
	А1																	1				1				1					1
	А1																							2
															2					2				2					2			10
							5								3					1				1					1						\|
							5								3					1				1					1						\|
	А3		–1								0								1	−			0												\|	← \|
	А3		–1				2				0				4				1	−		4	0	4					4			3			\|	← \|
		0					7				0				5				0	3			1	−			3		5					14	1	−	3
															5					3							3		5					14	1		3
	А5
	А5														2					2							2		2			5					10
															2					2							2		2			5			5		10
	z j − cj						−		1		0				−		11		0	−		3	0			3			−		5
							−				0				−				0	−			0	4					−
							2								4					4				4					4
							0				0				0				0	0			0	1					1

= (1,0,

,0,7,0,0)

оптимальный, вектора

Третий

план

X Б3

тоже

не

А2 , А4 имеют отрицательные

оценки.

Составляем

четвёртую

симплекс-

таблицу. В базис вводим вектор

, из базиса выводим вектор

5 по сим-

А2

плексному отношению θ = θ02 = min

(10/3,14/5) = 14/5 .

Таблица 2.3.4

СБ

А1

А2

А3

А4

А5

А6

А7

Б4

В4

–1

–М

12/5

–1/5

1/5

А1

–1

2/5

–7/10

–3/10

7/10

–1/2

А3

14/5

3/5

2/5

–3/5

А2

z j − cj

36/5

9/10

11/10

–9/10

3/2

− y

Четвёртый план оптимальный.

Z′	=	36	,		Opt. =		Б		=	12	,	14	,	2	,0,0,0,0	. Все искусственные пере-
				X		X
								4
max	5										5 5
										5

менные равны нулю, поэтому значения начальных переменных определяют оптимальный план.

		36			12		14		2

Ответ. Zmax	=		, Х max =			,		,		.
		5					5		5
				5

Решим задачу с помощью Поиска решений в Excel

Решение состоит из двух этапов:

ввести, согласно стандартного приёма, формулы математической мо- дели задачи в Excel;

в диалоговом режиме провести решение задачи по выбранной про-

грамме «Поиск решения».

1. Набрать исходные данные ЗЛП в произвольном месте таблицы Excel, как показано в табл. 2.3.5. Клетки D2:D4, где должны находиться знаки огра- ничений, оставляем свободными (они обведены двумя линиями). В клетке D1 (обведённой жирной линией) будет находиться значение целевой функции. В клетках: A5: C5 (обведённых жирной штриховой линией) будут находиться

значения переменных х1, х2				, х3 ,	на них в процессе решения будет делаться
абсолютная ссылка.
Таблица 2.3.5. Данные примера 2.3.1, внесённые в Excel

			A	B		C	D	E
	1	2		1		–1
	2	1		1		2		6
	3		–1	2		2		4
	3		–1	2		2		4
	4	4		–1		–2		6
	4	4		–1		–2		6
	5
	5

По общим правилам вводим формулы математической модели задачи. Вводим зависимости для целевой функции и ограничений. Для этого

курсор ставится в клетку D1 и выполняются действия: «Вставка»; «Функ-

ция»; «Математические»; «СУММПРОИЗ»; «ОК».

В строку «Массив 1» вводится A1:C1; в строку «Массив 2» вводится A5:C5; чтобы на массив A5:C5 была абсолютная ссылка, надо нажать F4, ко-

гда этот массив выделен; возле номеров второго массива появится знак $; «OK».

Протянуть “маленький” + вниз по клеткам, выделенных двойными ли- ниями. В этих клетках появятся нули. Таблица будет иметь вид

Таблица 2.3.6

	A	B	C	D	E
1	2	1	–1	0
2	1	1	2	0	6
3	–1	2	2	0	4
4	4	–1	–2	0	6
5

2. Запустись команду «Поиск Решения»: «Сервис»; «Поиск реше-

ния» (если «Поиск Решения» нет, то в надстройке поставить галочку возле Поиск Решения); OK.

Дальше работаем в диалоговом режиме. Действия, которые надо вы- полнять перечислим кратко: установить целевую ячейку D1; Указать макси- мальное значение; «Изменяя ячейки» A5:C5 ; «Добавить»; в ссылке на ячейку вводится ячейка D2, выделенная двумя линиями, знак неравенства ос- тавляем ≥ , в ограничения выделяем клетку F2 с числом 6; «Добавить»; в ссылке на ячейку вводится ячейка D3, выбираем знак «=», ограничения вы- деляем клетку F3 с числом 4; «Добавить»; в ссылке на ячейку вводится ячей- ка D4, знак неравенства оставляем ≤ , в ограничения выделяем клетку F4 с числом 6;. «ОК».

После этих действий экран будет иметь вид:

Рис. 2.3.1

«Параметры»; «Линейная модель»; «Неотрицательные значения»; «ОК»; «Выполнить»; «Сохранить найденное решение»; «Выделить Ре- зультаты»; «Устойчивость»; «Пределы»; «ОК».

В результате получим решение и его анализ:

Таблица 2.3.7. Решение задача 2.3.1

	A	B	C	D	E
1	2	1	− 1	7,2
2	1	1	2	6	6
3	− 1	2	2	4	4
4	4	− 1	− 2	6	6
5	2,4	2,8	0,4

Анализ решения ЗЛП в Excel

Подробное объяснение этих отчётов изложено в примере 2.2.1.

Рис. 2.3.1

Рис. 2.3.2

	Рис. 2.3.3
Напишем двойственную задачу.
F = 6y + 4y						2	+ 6y → min,
	1					2			3
	y	− y		2	+ 4y				≥ 2,
	1			2			3
y +		2y	2		− 2y			≥ 1
	1		2				3
2y + 2y					2	− 2y			≥ −1,
	1				2		3
y1 ≤ 0,		y2 − люб. знак., y3 ≥ 0.

Найдём решение двойственной задачи.

По первой теореме двойственности Fmin = Zmax = 7,2 .

Значения двойственных переменных можно выписать из теневых цен или из индексной строки последней симплекс-табл. 2.3.4:

y = −		9	, y =	3	, y =		11	.
							11

1	10		2	2	3	10
	10			2		10
			46

Двойственный симплекс-метод

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

Решать ЗЛП двойственным методом начинают, как всегда, сведением ее к канонической форме и образованию полного единичного базиса методом Жордана-Гаусса. Знаки свободных членов могут быть произвольными. Если задача на max, то ее можно и оставлять на max.

Решение задач с помощью двойственного симплекса разделяется на два этапа. Рассматривается случай Z → min .

І-й этап. Достигается условие оптимальности.

1.Разрешающая строка выбирается произвольно. Пусть это будет r-я

строка.

2.Разрешающий столбец выбирается по min небазисного двойственно- го отношения:

					z j	− cj	=	z	k	− c
min									k	k	,
min				≥ 0		xrj					,
x > 0, z	j	−c	j	≥ 0		xrj				xrk
rj	j		j

xrk – разрешающий элемент.

Итерации продолжаем до тех пор, пока получим условия оптимально- сти, то есть получим псевдоплан.

Псевдопланом называется базисное решение, для которого выполняют- ся условия оптимума.

Если в псевдоплане все компоненты неотрицательные, то решение за- дачи закончено.

ІІ-й этап. Псевдоплан преобразовывают в план

1.Разрешающую строку выбираем по наименьшему отрицательному свободному члену. Пусть это будет p-ая строка.

2.Разрешающий столбец выбираем по min двойственного симплексно- го отношения:

		min					z j − cj	=	zq − cq	,
x						≤ 0 xpj
	pj	< 0, z	j	−c	j				xpq

xpq . – разрешающий элемент.

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

этом уравнении отрицательных нет, то задача не имеет решения.

Это очевидно, так как левая и правая части уравнения будут иметь раз- ные знаки.

В литературе под двойственным симплекс-методом часто понимают только второй этап, то есть в задаче псевдоплан уже найден.

Задача 2.3.2. Решить двойственным симплексом ЗЛП

		x	+ x	+ x	=	8,
		1	2	3
Z = x1 + x2 + 2x3 → max,		x1	− x2		≥	4,	xj ≥ 0 ( j =	1,3)	.
	− x − 2x				≤ − 6,
		1	2

Решение. Переходим к каноническому виду.

	x1	+ x2 + x3						= 8,
Z ′ = − x1 − x2 − 2x3 + 0x4 + 0 x5 → min,	− x1	+ x2		+ x4				= −4,

	− x	− 2x	2	+ x		5		= − 6,
	1
		x j ≥ 0		( j =			.
					1,5)

Задачу решаем двойственным симплекс-методом.

Таблица 2.3.8

										↓

	Б1		СБ					А1		А2		А3	А4	А5
						В1		А1		А2		А3	А4	А5
						В1	− 1		− 1		− 2		0	0
			1				− 1		− 1		− 2		0	0
				− 2	8		1		1		1		0	0
	А3			− 2	8		1		1		1		0	0
			0		− 4		− 1		1		0		1	0
	А4		0		− 4		− 1		1		0		1	0
←			0		− 6		− 1		[ − 2]		0		0	1
←	А5		0		− 6		− 1		[ − 2]		0		0	1
		z j	− cj		− 16		− 1		− 1		0		0	0

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

псевдоплан X Б1 = (0,0,8, − 4, − 6) .

Делаем пересчёт симплекс-таблицы. Разрешающую строку выбираем по наименьшему свободному члену, наименьший свободный член − ( − 6). Разрешающий столбец выбираем по минимуму двойственного симплексного отношения:

z j − cj

−1

min

= min

−1

≤ 0 x3 j

< 0, z

−c

−2

3 j

Следовательно, в базис вводим вектор А2 , а из базиса выводим вектор

А5 .

Выполняем такие итерации пока все свободные члены станут неотри- цательными.

Таблица 2.3.9

↓

Б2

СБ

В2

А1

А2

А3

А4

А5

− 1

− 2

1/2

− 1

1/2

Наименьший

А3

←

− 7

[ − 3/2]

1/2

свободный член − 7

А4

− 1/ 2

А2

− 1

1/2

− 1/2

min

− 3/ 2

z j

− cj

− 13

− 1/2

Таблица 2.3.10

Все условия

Б3

А1

А2

А3

А4

А5

В3

− 1

− 2

оптимальности

выполнены.

− 2

8/3

1/3

2/3

− 1

− 2/3

− 1/3

Ответ: Zmax = Z =

14/3

А1

− 1

2/3

1/3

− 1/3

А2

z j − cj

− 32/3

− 1/3

− 2/3

;

Напишем двойственную задачу и её решение.

Двойственная задача

F = 8y1 + 4 y2 − 6 y3 → min,

y	+ y	2	− y	≥ 1,
1		2	3
y1	− y2		− 2 y3	≥ 1,
y			≥	2,
1
	y2 ≤ 0,		y3 ≥ 0.

Решение двойственной задачи

		F =	32	, Y	=	2; -	1	;		2		.
		F =		, Y	=	2; -		;				.
			3			3			3
				Контроль:
F	= 8y + 4y − 6y = 8 2 + 4								−		1		− 6	2	=	32	.
F	= 8y + 4y − 6y = 8 2 + 4								−				− 6		=		.
	1	2	3										3		3
											3		3		3

<<< < Предыдущая 1 2 3 45 / 145 6 7 8 9 10 11 12 13 14 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
16.12.2018625.66 Кб7--план_практики_2011_2012_КМ.doc
#
23.02.201670.14 Кб1104_Лаб.раб._IF+CASE.doc
#
23.02.201669.12 Кб1101.1. Вправи на дієслово to be (Голіцинський).doc
#
23.02.20161.63 Mб452_0.pdf
#
23.02.2016114.98 Кб14Aktsionerne_tovaristvo.docx
#
23.02.2016130.56 Кб23bestref-123391.doc
#
16.07.20191.71 Mб7Bibury_systems.doc
#
23.02.20161.38 Mб110Bibury_Systems_-_Dialogues.pdf
#
23.02.2016121.86 Кб4BO_kurs_rob.doc