Добавил:

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

Вуз:

Киевский национальный университет им. Т. Шевченко

Предмет:

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

Файл:

ИсследованиеОпераций

.pdf

Скачиваний:

Добавлен:

07.03.2016

Размер:

1.89 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 67 / 117 8 9 10 11 > Следующая >>>

7.2 М-метод побудови допоміжної задачі.

Система обмежень вихідної задачі (7.1−(7.4) доповнюється штучними змінними так, як і у попередньому випадку.

Цільова функція допоміжної задачі будується інакше. Вона складається з двох доданків, першим з яких є цільова функція вихідної задачі, а другим (в задачі максимізації) – сума штучних змінних, помножена на коефіцієнт ( −M ), де M >>0 – велике число (практична нескінченність).

Для вихідної задачі (7.1)−(7.4) допоміжна М-задача має вигляд

m−k

LM = ∑c j x j −M

∑yk → max

(7.10)

j=1

i=1

+ xr+1

= a10 ,

a11 x1 +... + a1r xr

a21 x1 +... + a2r xr

+ xr+2

= a20 ,

...............................................................

+ akr xr

+ xn

= ak0

(7.11)

ak1 x1 +

...

+ +... a

k+1,r

+ y

= a

+1,0

k +1,1 1

...............................................................

+ + a

+ y

= a

m−k

x j ≥0, j =

1, n

≥0,i =

- штучні змінні,

(7.12)

1, m −k

ai0 ≥ 0,i =

(7.13)

1, n

Теорема 7.2 (про розв'язок допоміжної задачі у М-методі).

Нехай

задача

(7.10)−(7.13) розв'язана

симплекс-методом

– її оптимальний розв'язок.

= (x1

,..., xn

, y1

,..., ym−k )

Тоді:

1) якщо серед чисел y1* ,..., ym* −k

є відмінні від нуля, то вихідна

задача (7.1)−(7.4) не має допустимих розв'язків;

2) якщо

y1*

= y2* =... = ym* −k =0 ,

то вектор x* = (x1* , x2* ,..., xn* )T

оптимальним розв'язком задачі (7.1)−(7.4).

Теорема 7.3 (про необмеженість цільової функції М-задачі на її допустимій множині).

Нехай на деякому кроці симплекс-методу при розв'язуванні М- задачі виконується ознака необмеженості цільової функції на її допустимій множині, тобто, вектор αk , для якого

∆k = (cб , αk ) −ck < 0 і всі αik ≤ 0, i = 1, m. .

Тоді цільова функція вихідної задачі (7.1)−(7.4) також

необмежена на її допустимій області, якщо та не порожня.

Зауваження до теореми 7.2.

Покажемо на прикладі, що можливий випадок, коли цільова функція М-задачі при великих M >>0 необмежена зверху на її допустимій множині, а вихідна задача є недопустимою. Розглянемо задачу

L = x1 + x2 → max,

		− x			=1,
				1
		x1		, x2 ≥0.
задачу	Очевидно, що ця задача допустимих розв'язків немає. Будуємо М-
задачу		LM		= x1 + x2 − My1 → max,
		LM		= x1 + x2 − My1 → max,
		− x			+ y = 1,
				1	1
		x1		, x2 ≥0,
		y		≥ 0 - штучназмінна.
			1
~	М-задача допустима, зокрема, її допустимим розв'язком є~вектор
x = (0,θ,1) θ > 0 .			Значення цільової функції М-задачі на розв'язку x					рівне
θ −M і M >>0 (фіксованого) прямує до +∞ при θ → +∞ .
	Із сформульованих теорем та зауваження до теореми 7.2 випливає
таке правило аналізу результатів розв'язування М-задачі:
	1)	якщо	при досить великих M >>0 (при				розв'язуванні М-
задачі	на	ЕОМ	за		М можна прийняти 10 max	c j	) М-задача	має
задачі	на	ЕОМ	за		М можна прийняти 10 max	c j	) М-задача	має
					j=1,n
					j=1,n

оптимальний розв'язок, в якому принаймні одна штучна змінна відмінна від нуля, то вихідна задача допустимих розв'язків не має;

2)якщо в оптимальному розв'язку М-задачі всі штучні змінні рівні нулю, то відкинувши їх, отримаємо оптимальний розв'язок вихідної задачі;

3)якщо М-задача нерозв'язна, то нерозв'язна і вихідна задача.

7.2.1.Приклади.

Приклад 1. Розв'язати задачу ЛП

L = 2x1 − 2x2 + 3x3 → min

− 2x + x + 3x = 2,
	1 2	3

	+ 3x2 + 4x3 =1, x j ≥0, j =1,3.
2x1	+ 3x2 + 4x3 =1, x j ≥0, j =1,3.

		62

Розв'язування. Будуємо допоміжну М-задачу
		LM	= −2x1 + 2x2 −3x3 − Mx4 − Mx5 → max,
		− 2x + x			2	+ 3x			+ x			= 2,
			1		2		3			4
											+ x5 =1,
		2x1 + 3x2 + 4x3									+ x5 =1,
			≥0,	j = 1,5,				x4 , x5 −штучнізмінні.
		x j	≥0,	j = 1,5,				x4 , x5 −штучнізмінні.

	Зауважимо,		що	при			складанні					цільової	функції		LM	М-задачі ми
змінили		критерій	оптимізації								з	мінімуму	на		максимум,		тому
LM	= −L − Mx4 − Mx5 .		Розв'язуємо								М-задачу		симплекс-методом				(див.
таблицю 12).																Таблиця 12.
																Таблиця 12.
№	cб	xб	A0						–2			2	–3	– М		– М	θ
кр	cб	xб	A0						x1			x2	x3		x4	x5	θ
кр

0	– М x4		2						–2			1	3		1	0	2 3
0	– М ← x5		1						2			3	4		0	1	1 4
	– М ← x5		1						2			3	4		0	1	1 4
	∆j	LM	−3M						2		−4M −2 −7M + 3 ↑				0	0
1	– М x4		5 4					−7 2			−5 4		0		1
1	−3	x3	1 4						1 2			3 4	1		0
	−3	x3	1 4						1 2			3 4	1		0
	∆j	LM	− 5 M −		3 7			M +		1 5 M − 17			0		0
			4		4		2			2	4	4

Пояснення до змісту таблиці. B

=[ A4 , A5 ] ,

= (0,0,0,2,1)

Оцінка

∆3 = −7M +3 <0 найменша, тому A3 вводимо в базис.

θ = min{θ1 ,θ2 } , тому

буде виведений з базису за допомогою

симплекс-перетворення з ведучим стовпчиком A5

і другим ведучим рядком.

α5

не обчислюємо,

оскільки

він

штучний

небазисний;

штучна

змінна

у опорному розв'язку

М-задачі є вільною змінною,

тому x5

= 0

в x

Всі

оцінки

на 1-му кроці

невід'ємні: ∆1

M +

2 , ∆2

M −

4 ,

∆3 = ∆4

= 0 ;

отже,

вектор

(0,0,

4 ,

,0)

якому

відповідає

базис

B1 =[ A

, A

] , є оптимальним розв'язком М-задачі.

	Оскільки у розв'язку					~	1		штучна змінна				x4 має значення			5	4	≠ 0 , то
	Оскільки у розв'язку					x			штучна змінна				x4 має значення				4	≠ 0 , то
вихідна задача допустимих розв'язків немає.
Приклад 2. Розв'язати задачу лінійного програмування.
		L		= x + 4x		+ x		→ max,
				1	2	3
				− x2 + x3 = 3, x1 −5x2 − x3 = 0, x j ≥0, j = 1,3.
		x1		− x2 + x3 = 3, x1 −5x2 − x3 = 0, x j ≥0, j = 1,3.

Розв'язування. Будуємо М-задачу.
		LM		= x1 + 4x2 + x3 − Mx4 − Mx5 → max,
		x		− x + x + x					= 3,	x	j	≥0, j =1,5,
			1	2	3	4					j
				−5x	− x	+ x			=0,	x	, x −штучні змінні.
		x		−5x	− x	+ x			=0,	x	, x −штучні змінні.
			1	2	3			5		4		5
Розв'язуємо М-задачу симплекс-методом (див. таблицю 13).															Таблиця 13.
															Таблиця 13.
№	cб	xб		A0		1						4	1	–М	–М			θ
№
кр						x1						x2	x3	x4	x5
кр						x1						x2	x3	x4	x5
0	–М x4			3		1						–1	1	1	0			3 1
0		x5
	–М	x5		0		1						–5	–1	0	1			0
		←
	∆ j	LM		–3М −2M − 1 ↑						6М – 4			–1	0	0
	–М	x4		3		0						4	2	1
1		←
1		x1
	1	x1		0		1						–5	–1	0
	∆ j	LM		–3М		0				−4M − 9 ↑			–2М-2	0
2	4	x2		3 4		0						1	1 2
2	1	x1		15 4		1						0	3 2
	1	x1		15 4		1						0	3 2
	∆ j	LM		27 4		0						0	5 2

Пояснення до змісту таблиці. Симплекс-різниці обчислюємо на всіх кроках за

формулою ∆j = (cб, αj ) − c j , На	першому кроці	α12 = 4	єдина				додатна
компонента вектора α2 , тому θi	не обчислюємо.	Отже,	~*	= (	15	4 ;	3	4	;0)	T	–
компонента вектора α2 , тому θi	не обчислюємо.	Отже,	x	= (		4 ;		4	;0)		–
	64

оптимальний розв'язок вихідної задачі. Її оптимальне значення рівне

L* = 27 4 .

Приклад 3. Розв'язати задачу ЛП.

L = −x		− x	− x	→ min,
	1	2	3

	+ x2 + x3 = 4, − x1 + 2x2 − x3 = −1, x j ≥0, j =1,3.
− 2x1	+ x2 + x3 = 4, − x1 + 2x2 − x3 = −1, x j ≥0, j =1,3.

Розв'язування. Змінюємо критерій оптимізації з мінімізації на максимізацію, множимо почленно друге рівняння на ( −1 ) та записуємо допоміжну М- задачу.

			LM = x1 + x2 + x3 − Mx4 − Mx5 → max,
			− 2x
			− 2x			+ x		+ x		+ x			= 4, x	j	≥0, j =		1,5	,
				1			2	3			4			j
					x	−	2x	+ x			+ x		= 1, x		, x −штучні				змінні.
					x	−	2x	+ x			+ x		= 1, x		, x −штучні				змінні.
				1			2		3		5			4	5
Розв'язуємо задачу симплекс-методом (див. таблицю 14).																				Таблиця 14.
																				Таблиця 14.
	№	cб	xб			A0				1			1			1			–М	–М	θ
	кр									x1			x2			x3			x4	x5
	кр

	0	–М	x4			4				–2			1			1			1	0	4 1
	0	–М	x5			1				1			–2			1			0	1	1 4
		–М	x5			1				1			–2			1			0	1	1 4
			←
		∆ j	LM		–5М			М – 1					М – 1			−2M − 1 ↑			0	0

	1	–М	x4			3				–3			3			0			1
	1		←
		1	x3			1				1			–2			1			0
		∆ j	LM		–3М+1				3М			3M − 3 ↑				0			0
	2	1	x2			1				-1			1			0
	2	1	x3			3				-1			0			1
		1	x3			3				-1			0			1
		∆j	L			4				-3			0			0
		Пояснення до змісту таблиці. На всіх кроках симплекс-різниці
обчислюємо за формулою ∆j									= (cб, αj )				− c j ,
		На нульовому кроці								α23 =1 – ведучий елемент перетворення; A3
вводиться у базис,				A5		виводиться з базису.
											65

На першому кроці α12 = 3 − ведучий елемент перетворення; A2 вводиться у базис, A4 виводиться з базису.

На другому кроці ∆1 = −3 <0 і α11 = −1 , α21 = −1 . Отже, цільова функція М-задачі не обмежена зверху на її допустимій множині.

Таблиця кроку 2 містить коефіцієнти канонічної форми вихідної задачі, тобто вихідна задача допустима і для неї також виконується ознака необмеженості цільової функції на її допустимій множині.

Зауважимо, що відкидати штучні вектори з симплекстаблиці після їх виведення з базису можна лише за умови, що остання симплекс-таблиця, яка визначає оптимальний розв'язок М- задачі, не використовується надалі для додаткових обчислень, наприклад, для обчислення матриці, що є оберненою до початкової

базисної матриці B0 .

7.3. Вправи.

Розв'язати задачі ЛП: 1) використати М-метод,

L = −2x1 + 3x2 → min,

x1 + 2x2 ≥10,3x1 + x2 ≥15,x1, x2 ≥0.

3) використати М-метод,

L = 3x1 + 3x2 → min,

x1 + 4x2 ≥ 4,4x1 + x2 ≥ 4,x1, x2 ≥ 0.

5) використати М-метод,

L = 3x1 +2x2 → max,

4x1 +2x2 ≥ 12,x1 +2x2 ≤ 10,2x1 +2x2 = 6,

x1 , x2 ≥ 0.

2) використати метод штучного базису,

L = 2x1 −3x2 → max,

5x1 +2x2 ≥10,x1 +3x2 ≤ 12,x1 , x2 ≥ 0.

4) використати метод штучного базису,

L = −2x1 + x2 → min,

x1 + x2 ≤ 6,

−3x1 +2x2 ≥ 3,x1 , x2 ≥ 0.

6) використати метод штучного базису,

L =6 x1 +4x2 → min,

2x1 + x2 ≥ 3,x1 − x2 ≤ 1,x1 , x2 ≥ 0.

8. Розв'язування задач ЛП модифікованим симплексметодом.

8.1. Основні факти.

При розв'язуванні канонічної задачі ЛП симплекс-методом на кожному його кроці відбувається переобчислення всіх елементів розширеної матриці коефіцієнтів системи обмежень (за винятком компонент базисних векторів – вони одиничні).

Модифікований симплекс-метод дозволяє здійснювати кроки симплекс алгоритму, знаючи лише розширену матрицю коефіцієнтів системи обмежень вихідної задачі та обернену до базисної матриці поточного опорного розв'язку задачі. При цьому вихідна задача може мати стандартну форму.

Розглянемо задачу ЛП

			n
	L(x) = ∑c j x j → max,									(8.1)
			j=1
	n
	∑x j Aj = A0 ≥0, j =							0, n	,	(8.2)
	j=1
	x j	≥0,	j =				,			(8.3)
	x j	≥0,	j =		1, n		,			(8.3)
де Aj = (a1 j , a2 j ,...,amj )T ,			j =			, і ранг матриці A =[ A1 , A2 ,..., An ]				рівний m .
де Aj = (a1 j , a2 j ,...,amj )T ,			j =	0, n		, і ранг матриці A =[ A1 , A2 ,..., An ]				рівний m .
	Нехай для деякого невідомого опорного розв'язку x									задачі (8.1) −
(8.3)	відома матриця		B−1 (s) , що є оберненою до базисної матриці								B(s)
цього	розв'язку.	Не	обмежуючи загальності, будемо							вважати,	що

B(s) =[ A1 , A2 ,..., Am ] ,			оскільки цього завжди можна досягти перестановкою
стовпчиків матриці A , тобто перенумеруванням невідомих										x j	системи
(8.2). Очевидно, що тоді xs матиме вигляд:				xs = (αs			,αs	,...,αs		,0,...,0)T , де
				10			20	m0		123
										n−m
αis0 ≥ 0 , i =		– компоненти вектора
αis0 ≥ 0 , i =	1, m	– компоненти вектора
		αs = B−1 (s) A .								(8.4)
0			0
Щоб перевірити опорний розв'язок xs на оптимальність спочатку
потрібно обчислити			симплекс-оцінки ∆sj ,	j =		.	Маємо		для		задачі
потрібно обчислити			симплекс-оцінки ∆sj ,	j =	1, n	.	Маємо		для		задачі
максимізації (8.1) − (8.3):
			67


∆sj = (cб(s),αsj ) −c j = cбT (s) Aj −c j , j =				1, n	,	(8.5)
де αsj = B−1 (s) Aj , а	cб (s) – вектор коефіцієнтів при					бажаних змінних
розв'язку xs у цільовій функції задачі (8.1) − (8.3). Тому
∆sj = cбT (s) B−1(s) Aj −c j , j =			.			(8.6)
		1, n
Компоненти вектора
(Y s )T	= cбT (s) B−1 (s)					(8.7)

називають симплекс-множниками, що відповідають розв'язку xs .

Отже, знаючи матрицю B−1 (s) та номери векторів базису розв'язку xs , можна обчислити симплекс-множники yis , i =1, m за формулою (8.7), а потім і симплекс-оцінки

∆sj = ( ys )T Aj −c j , j =	1, n	;	(8.8)
після чого перевірити їх знак і з'ясувати, чи буде розв'язок xs			оптимальним.
Якщо серед оцінок ∆sj є від'ємні , то по мінімальній з них знаходимо
номер
k = arg min ∆sj			(8.9)
{ j:∆sj <0}

вектора Ak , який належить ввести у базис (номер направляючого стовпця

симплекс-перетворення).

Щоб визначити у базисі порядковий номер l вектора, який повинен бути виведений з базису (номер направляючого рядка сиплексперетворення), обчислюємо вектори

αs = B−1(s) A		,	αs = B−1	(s) A ,		(8.10)
0	0		k	k
і знаходимо
l = arg min	αs					(8.11)
l = arg min	i0 .					(8.11)
{i:αiks >0}	αiks
Знаючи елемент	bs	матриці B −1 (s) та компоненти			αs	вектора	αs ,
	ij				ik		k
елементи матриці B−1 (s +1) ,			оберненої до базисної для нового опорного

розв'язку xs+1 , обчислюємо за формулами повного виключення ЖорданаГаусса

		bs
bs+1	=	lj		, j =1,
bs+1	=			, j =1,
lj		αs
		lk
					bs
bs+1	=bs		−		lj	αs
bs+1	=bs		−		αs	αs
ij		ij			αs	ik
					lk

(8.12)

, i =1, m, j =1, n, i ≠ l.

Далі, знаючи матрицю	B−1 (s +1) ми знову можемо обчислити
відповідний їй опорний розв'язок	xs+1 та перевірити його на оптимальність і

т.д. Ці дії здійснюються доти, поки не отримаємо оптимальний розв'язок задачі (8.1) − (8.3) або не з'ясуємо , що вона недопустима.

Якщо ввести матрицю
		1 0 ..	0	−			s	0		..	0
		1 0 ..	0	−		α1k		0		..	0
							as
	.. .. .. ..						lk	..		..	..
	.. .. .. ..			.........				..		..	..
					αs
		0 0 ..	1	−			l−1,k	0		..	0
		0 0 ..	1	−			alks	0		..	0
							alks
							1
		0 0 ..	0				1	0			0
E(s) =		0 0 ..	0	− as				0		..	0	←l - й рядок,
							lk
					αs
		0 0 ..	0	−			l+1,k		1	..	0
		0 0 ..	0	−			as		1	..	0
							as
	.. .. .. ..						lk	..		..	..
	.. .. .. ..			.........				..		..	..
						αs
		0 0 ..	0	−			mk	0		..	1
							s
							alk

	↑l - йстовпчик
яку називають елементарною, то матрицю		B−1 (s +1) можна	подати у
мультиплікативному вигляді
	B−1 (s +1) = E(s)B−1 (s) = E(s) E(s −1) ... E(0)B−1 (0) ,
де B−1 (0)	– обернена до базисної матриці	B(0) початкового	опорного
розв'язку x0	задачі (8.1) − (8.3).

8.2. Алгоритм модифікованого симплекс-методу.

1. Обчислити матрицю, обернену до початкової базисної B−1 (0) . Бажано, щоб початкова базисна матриця була одиничною B(0) = E . В іншому випадку базисна матриця повинна бути вибрана так, щоб виконувалась умова α00 = B−1 (0) A0 ≥0 . Перейти до наступного пункту.

2.	Обчислити	вектор	( ys )T = cбT (s)B−1(s) .				Перейти			до наступного
пункту.
3.	Обчислити	оцінки	∆sj = ( ys )T Aj			−c j ,	j =		.	Перейти	до
								1, n
наступного пункту.
4.	Перевірити умову ∆sj ≥0 , j =			1, n	.	Якщо умова виконується,					то

кінець обчислень – поточний розв'язок є оптимальним. В іншому випадку перейти до наступного пункту.

5. Знайти номер k = arg min ∆sj . Перейти до наступного пункту.

{ j:∆sj <0}

6. Обчислити вектор αks = (α1sk ,α2sk ,...,αmks )T = B−1(s) Ak . Перейти до наступного пункту.

7. Перевірити умову: всі αiks ≤0 , i = 1, m . Якщо умова виконується, то кінець обчислень – цільова функція необмежена зверху на допустимій

множині. В іншоому випадку перейти до наступного пункту.
	8.	Якщо		вектор		α0s		невідомий,	то обчислити	його
αs = B−1	(s) A	= (αs	,αs	,...,αs	)T . Якщо			αs відомий,	то перейти до наступного
0	0	10	20	m0				0
пункту.
	9. Знайти номер l = arg min						αs	. Перейти до наступного пункту.
	9. Знайти номер l = arg min						i0	. Перейти до наступного пункту.
						{i:αiks >0}	αiks
	10. Виконати крок методу повного виключення з направляючим
стовпцем αks		і направляючим рядком з номером l							на матриці B−1 (s) ,	тобто
обчислити матрицю B−1(s +1)						за формулами (8.12). Перейти до пункту 2.

8.3. Приклади.

Приклад 1. Розв'язати модифікованим симплекс-методом задачу ЛП.

	L = 4x1 +22					→ max
	− x1 + x2 + x3								= 2,
		x1 − x2				+ x4			= 4,
		x1 − x2				+ x4			= 4,
		x	1	+ x	2		+ x	5	=6,
			1		2			5
		x		≥0, j		=
		x	j	≥0, j		=	1,5.
			j
Розв'язування.	Задача має канонічну форму, тому базисна матриця B(0) ,
обернена до	неї	B−1(0) та початковий опорний розв'язок визначаються
легко:									70
									70

<<< < Предыдущая 1 2 3 4 5 67 / 117 8 9 10 11 > Следующая >>>

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

#
19.03.201558.07 Кб184Инструкция по учету Агентуры.docx
#
07.03.2016577.32 Кб16Интроверт.pdf
#
19.03.201545.04 Кб9Информационные.docx
#
08.07.20191.67 Mб1Иоанна Хмелевская -- (Nie)Boszczyk maz_POL.doc
#
19.03.201573.33 Кб5иппв.docx
#
07.03.20161.89 Mб17ИсследованиеОпераций.pdf
#
19.03.201554.77 Кб6Исторія модуль 2.docx
#
28.04.2019197.84 Кб3Историография. Шпоры.docx
#
23.12.2018332.8 Кб4история 2 - 2003.doc
#
19.03.2015199.17 Кб5история дипломатии том 2 ГЛАВА 7.doc
#
07.03.20162.04 Mб53История Медицины. Т.1..pdf