Navch._posibnuk_Ivaschyk

−2x1 − x2 −λ ≤ 5

−x1 − 4x2 −λ ≤ −3 ×(−1),

Тоді			− x1 − x2 ≥ 5			×(−1).
− 2x1 − x2 −λ ≤ 5			ν1		− 2x1 − x2 −λ +ν1 = 5,		(6.9)
x1	+ 4x2 −λ ≥ 3		ν2		x1 + 4x2 −λ −ν2 = 3,		(6.10)
x1	+ x2 ≤ 5		ν3			x1 + x2 +ν3 = 5.	(6.11)

Урівнянні (6.9) і (6.11) базисними змінними є відповідно ν1 і ν3.

Вдруге рівняння вводимо штучну змінну u. Отримуємо таку задачу

лінійного програмування:

F = u → min,
− 2x1 − x2 −λ +ν1						= 5,
	x1 + 4x2 −λ −ν2					+u = 3,
	x + x	2	+	ν	3	= 5.
	1

	Розв’язуємо задачу симплекс-методом.
	З рівняння (6.10) визначаємо u: u = 3 − x1 − 4x2																					+ λ + ν2 .
	Отже,						F = 3 − x1			− 4x2		+ λ + ν2					→ min .
№т.	№р.		Б	ОП				х1		х2↓			λ				v1	v2				v3		u	θ
	0		F		3			1		4			–1				0	–1				0		0
I	1		v1		5			–2		–1			–1				1	0				0		0
	2←		u		3			1		4			–1				0	–1				0		1	3:4
	3		v3		5			1		1		0					0	0				1		0	5:1
	0		F		0			0		0		0					0	0				0		–1
II	1		v1		23/4			–7/4		0			–5/4				1	–1/4				0		1/4
	2		x2		¾			¼		1			–1/4				0	–1/4				0		1/4
	3		v3		17/4			3/4		0		1/4					0	1/4				1		–1/4
Отримали оптимальний розв’язок:
	x0 = 0; x0				=	3	; λ0 = 0; ν 0 =						23	; ν		0	= 0; ν 0		=		17		; u0 = 0.
																2
	1		2		4					1		4						3				4

Перевіряємо виконання необхідних умов, враховуючи такі рівняння:

201

									∂L					= −2x − x							−5 −λ = −ν						, v < 0;
																			2
									∂x1								1									1				1
									∂L					= −x − 4x							+3 −λ =ν					, v				= 0;
																				2					2				2
									∂x2								1
									∂L			= 5 − x − x									=ν			, v > 0.
																				2			3
									∂λ								1							3
		Всі умови виконуються, а це означає, що точка з координатами
x0		= 0;	x0	=	3	;		λ0			= 0					є	сідловою							точкою				функції						Лагранжа для
1			2	4
задачі			квадратичного														програмування.										Точка						з	координатами
	0	0		0			3			0
X		x1	= 0; x2 =					;λ = 0									є точкою,							в якій			цільова						функція досягає
							4
свого максимального значення:																						2
				Zmax		= −0				2	−0					3	− 2	3									3	= −			9	+	9	=	9	.♦
																4						−5 0 +3					4				8		4		8
																		4

Приклад. 6.5. Розв’язати задачу нелінійного програмування:

Z = x12 + 2x1 x2 + 2x22 +3x1 + 2x2 → min,

2x1 + 2x2 ≤10,x1 ≥ 0, x2 ≥ 0.

♦ Розв’язування.

		Z = Z1 + Z2 ,
		Z1 = 3x1 + 2x2 ,
		Z	2	= x2 + 2x x				2	+ 2x2 .
					1		1			2		= x2	+ 2x x		+ 2x2
Розглянемо квадратичну					функцію					Z	2			2		та
												1	1		2
відповідну їй матрицю, складену з коефіцієнтів при змінних
					1	1
			C =				.
						2
					1
Знаходимо власні значення (характеристичні корені) матриці С,
виписавши характеристичне рівняння:
		1−λ			1		= 0.
			1		2 −λ

Тоді

202

(1−λ)(2 −λ) −1 1 = 0, (1−λ)(2 −λ) −1 = 0, 2 − 2λ −λ + λ2 −1 = 0, λ2 −3λ +1 = 0,

D= 9 − 4 1 = 5,

λ= 3 ±2 5 ,

λ =

3 +

5

≈ 2.618 > 0,

1

2

λ2

=

3 −

5

≈ 0.382 > 0.

2

Z

Оскільки

λ1

і λ2 більші

від нуля, то квадратична форма

2

= x2

+ 2x x

2

+ 2x2

є додатно означеною, тобто опуклою.

1

1

2

Функція Лагранжа для початкової задачі має вигляд:

L(x1, x2 , λ) = x12 + 2x1x2 + 2x22 +3x1 + 2x2 + λ(10 − 2x1 − 2x2 ) .

Необхідні умови існування екстремуму цільової функції:

∂L

= 2x

+ 2x

+ 3

− 2λ ≤ 0;

∂L

= 2x

+ 4x

+ 2 − 2λ ≤ 0;

2

2

1

1

∂x1

∂x2

∂L =10 − 2x

− 2x

≥ 0;

∂L

x0

= 0;

∂L

x0

= 0; ∂L λ0

= 0,

2

∂λ

1

1

∂x2

2

∂λ

∂x1

де (x10 , x20 , λ0 ) – координати сідлової точки.

Розглянемо перших три нерівності та зведемо їх до рівнянь

шляхом вводу додаткових змінних:						×(−1),
	2x1 + 2x2 + 2λ ≤ −3
	2x1 + 4x2 − 2λ ≤ −2					×(−1),
Тоді	− 2x1 − 2x2 ≥ −10					×(−1).
− 2x1 − 2x2 + 2λ ≥ 3			ν1 ,	− 2x1 − 2x2 + 2λ −ν1 = 3				u1 ,
− 2x1 − 4x2 + 2λ ≥ 3			ν2 , − 2x1 − 4x2 + 2λ −ν2 = 2					u2 ,
2x1 + 2x2 ≤10			ν3.	2x1 + 2x2 +ν3 =10.

Розглянемо задачу лінійного програмування:

203

F = u1 +u2 → min,

− 2x1 − 2x2 + 2λ −ν1 +u1 = 3,
		+ 2λ −ν2 +u2 = 2,
− 2x1 − 4x2
	2x + 2x	2	+	ν	3	=10.
	1

Оскільки

u1 = 3 + 2x1 + 2x2 − 2λ + ν1 ; u2 = 2 + 2x1 + 4x2 − 2λ + ν2 ,

то маємо таку задачу:

F = 5 + 4x + 6x2 − 4λ +ν1 +ν2 → min,
− 2x1 − 2x2 + 2λ −ν1 +u1 = 3,
		+ 2λ −ν2 +u2 = 2,
− 2x1 − 4x2
	2x + 2x	2	+	ν	3	=10.
	1

Розв’язок знаходимо з допомогою симплекс-методу.

	№т.	№р.	Б	ОП	х1	х2	λ↓	v1	v2	v3	u1	u2
		0	F	5	–4	–6	4	–1	–1	0	0	0
	I	1	u1	3	–2	–2	2	–1	0	0	1	0
		2←	u2	2	–2	–4	2	0	–1	0	0	1
		3	v3	10	2	2	0	0	0	1	0	0
		0	F	1	0	↓
						2	0	–1	1	0	0	–2
	II	1←	u1	1	0	2	0	–1	1	0	1	–1
		2	λ	1	–1	–2	1	0	–1/2	0	0	1/2
		3	v3	10	2	2	0	0	0	1	0	0
		0	F	0	0	0	0	0	0	0	0	–1
	III	1	x2	1/2	0	1	0	–1/2	1/2	0	1/2	–1/2
		2	λ	21	–1	0	1	–1	1/2	0	1	–1/2
		3	v3	9	2	0	0	1	–1	1	–1	1

Отримали оптимальний розв’язок:

x0	= 0; x0	= 1 ; λ0	= 2; ν 0	= 0; ν 0	= 0; ν 0	= 9; u0	= 0; u0	= 0 .
1	2	2	1	2	3	1	2

Необхідні умови оптимальності та їх перевірка:

204

∂L

= 2x

+ 2x

+3 − 2λ

= −ν

;

2

∂x1

1

1

∂L

= −2x − 4x

+ 2λ − 2 = −ν

;

2

2

∂x2

1

∂L

= 2x

+ 2x

−10 =ν

;

2

3

∂λ

1

∂L

x0

= −ν 0

x0

= 0 0 ≥ 0;

1

1

1

∂x1

∂L

x20 = −ν20 x20 = 0 1

≥ 0;

∂x2

2

		∂L	=ν30	λ0 = 9 2 =18 ≥ 0.
		∂λ
	Оскільки виконуються умови оптимальності, то стверджуємо,
	що точка з координатами			x0 = 0;	x0	= 1 ; λ0	= 2	є сідловою точкою
				1	2	2
									1
	функції Лагранжа. В точці з координатами X 0 x10							= 0; x20 =		цільова
								2

функція досягає свого мінімального значення, яке вираховується таким чином:

	Zmax	= 02 −0 2	1	+ 2		1	2	+3 0 + 2	1	=1	1	.♦
			2			2			2		2

6.3. Прикладне використання методу множників Лагранжа

Розглянемо економічний зміст множників Лагранжа. Для цього розглянемо задачу нелінійного програмування стосовно визначення оптимального плану виробництва продукції при обмежених ресурсах:

Z = f (x1, x2 ,…, xn ) → max qi (x1, x2 ,…, xn ) ≤ bi , i =1, m,

xj ≥ 0, j =1, n.

Головною метою виробництва продукції є отримання найбільшого прибутку від її реалізації, тому цільовою функцією Z задачі є прибуток від реалізації продукції обсягом Х=(х1, х2,…хn) одиниць. Зауважимо, що функція f(х1, х2,…хn) – нелінійна.

205

Для виробництва продукції використовується m видів сировини,

обсяги запасів яких обмежені і	становлять bi (i =						) одиниць.
						1, m
Запишемо систему нерівностей
qi (x1, x2 ,…, xn ) ≤ bi , (i =			)
		1, m
у вигляді
di (X ) = bi − qi (x1, x2 ,…, xn ) ≥ 0, (i =					).
				1, m
Тобто, якщо qi (x1, x2 ,…, xn )	– обсяг сировини і-го виду, що

використовується для виробництва всієї продукції, то di(X) – залишок цього ресурсу після її виробництва. Якщо di(X)=0, то сировина використана повністю; якщо di(X)>0, то на виробництво продукції використана не вся сировина; якщо di(X) <0, то наявної сировини не вистачає для виробництва продукції.

Розглянемо функцію Лагранжа для описуваної задачі:

		m
L(x, λ,b) =		f (x) + ∑λi (qi (x) −bi ) .
		i=1
Очевидно, що	∂L(x, λ,b) = λ , тобто ця похідна показує, як
	∂bi	i

змінюється значення цільової функції залежно від обмежень. Множники Лагранжа є двоїстими змінними задачі про використання ресурсів. Вони можуть бути ціною, за якою на ринку продається чи купується одиниця і-го виду сировини. Якщо λi ≥ 0 і di(X)>0, то

можна продати залишки сировини і отримати додатковий прибуток в розмірі λi di ( X ) . Якщо ж di(X)<0, то можна купити потрібну кількість,

витративши λi di ( X ) грошових одиниць і забезпечити виробництво

продукції обсягом Х=(х1, х2,…хn). Функцію Лагранжа можна трактувати як загальний прибуток від виробництва, який містить прибуток від реалізації виготовленої продукції f(x) та прибуток від продажу залишків сировини (або витрати на придбання потрібної

m

кількості сировини) ∑λi di ( X ) .

i=1

Розглянемо деякі приклади розв’язання економічних задач з допомогою методу множників Лагранжа розв’язування задач нелінійного програмування.

Приклад 6.6. Фірма планує витрати 20000 грн. на рекламу. Одна хвилина реклами на телебаченні коштує 1000 грн., а на радіо – 500 грн. Аналітики фірми прогнозують збільшення приросту доходу фірми від використання рекламних засобів за такою функцією:

206

Z (x, y) = −x2 − y2 + xy +10x +5y ,

де Z(x,y) – приріст доходу фірми (тис. грн.) від реклами; х – тривалість (хв.) рекламного ролика на телебаченні; y – тривалість (хв.) рекламного ролика на радіо. Яким чином потрібно поєднати рекламу на телебаченні та радіо, щоби отримати максимальне значення приросту доходу фірми, економно використавши при цьому наявні грошові засоби на рекламу?

♦ Розв’язування.

Цільова функція – це максимум приросту доходу фірми

Z (x, y)= −x2 − y2 + xy +10x +5y → max

при виконанні наступних умов:

а) з наявності обсягів грошових ресурсів на рекламу

1000x +500y = 20000;

б) стосовно невід’ємності змінних x ≥ 0, y ≥ 0 .

Оптимальне рішення знаходимо з допомогою методу множників Лагранжа.

Функція Лагранжа набуває вигляду:

L(x, y, λ) = −x2 − y2 + xy +10x +5y + λ (20000 −1000x −500 y).

Частинні похідні прирівнюємо до нуля:

	∂L		= −2x + y +10 −1000λ = 0,
	∂x
	∂L		= −2 y + x +5 −500λ = 0,
	∂y
	∂L		= 20000 −1000x −500 y = 0.
	∂λ
Ми отримали систему рівнянь такого виду:
	− 2x + y +10 −1000λ = 0,
				(6.11)
	− 2 y + x +5 −500λ = 0,
	20000 −1000x −500 y = 0.

Зробимо відповідні перетворення:

207

− 2x + y −1000λ = −10,			− 2x + y −1000λ		= −10
				x − 2 y −500λ	= −5		×−2
− 2 y + x −500λ = −5,
				− 2x − y	= −40
−1000x −500 y = −20000.
− 2x + y −1000λ		= −10,
		=10,
− 2x + 4 y +1000λ
	= −40.
− 2x − y

Додамо перші два рівняння останньої системи і отримаємо:

				− 4x +5y = 0 y =														4 x .
																		5
Підставимо в третє рівняння: − 2x − 4 x = −40 x = 100 =14																													2 .
		4		100			80					3				5									7				7
Звідси, y =					=					=11			.		Знайдемо								значення					множника
							7
5			7							7
Лагранжа з другого рівняння системи (6.11):
							100							80				25
	x − 2 y +5										− 2					+5	=		−							1	.
λ =							=			7				7						7			= −
										500								500							140
			500
Отже, розв’язком цієї системи є:
	x =14 2 ;									y =11				3 ;			λ = −						1	.
																					140
			7											7

Переконаємося, чи досягає наша функція екстремального значення в знайденій точці.

Для цього на основі вищезгаданої теореми знайдемо частинні похідні першого порядку заданої функції:

Z (x, y) = −x2 − y2 + xy +10x +5y .

∂∂Zx = −2x + y +10; ∂∂Zy = −2 y + x +5.

Знаходимо частинні похідні другого порядку:

	∂2 Z	= −2;	∂2 Z	= −2;	∂2 Z	=	∂2 Z	=1.
	∂x2		∂y2		∂x∂y		∂y∂x

Звідси,

208

											− 2						1						H1 (x, y)= −2 < 0,
				H (x, y)=														,
											1						− 2
				H2 (x, y)=										− 2 1					− 2 (− 2)−1 1 = 3 > 0.
														1			− 2
Відповідно до умови теореми стверджуємо, що точка з
координатами 14						2		;11			3				буде точкою максимуму функції.
						7
											7
Максимальним значенням функції є
				2	;11		3								100		2		80			2		100		80	+10	100	+5	80	=
Zmax = Z 14				7			7			= −					7			−				+		7		7		7		7
																			7
= −	10000		−	6400			+			8000					+	1000			+	400			=	−16400 +8000 +9800						=
										49																	49
49				49													7		7
= 1400 = 200 = 28									4 .
49			7						7
Фірма отримає додатковий дохід від використання реклами у
розмірі 28 4			тис.				грн.						якщо гроші,								призначені на рекламу будуть
7						2 хвилини											реклами на телебаченні та 11 3 хвилини
використані на 14
– на радіо. ♦						7																							7
				6.7.					Компанія									виробляє						два		види		взаємозамінної
Приклад

продукції виду А і В. Аналітики фірми експертно визначили функцію сумарних витрат, які необхідні для випуску продукції

Z (x, y)= 8x2 − xy +12 y2 .

Відомо, що сумарний обсяг продукції обох видів буде дорівнювати 42 одиницям. Перед менеджерами компанії поставлене завдання: визначити обсяги продукції А і В, при яких сумарні затрати на виробництво будуть мінімальними.

♦ Розв’язування.

Введемо позначення: х – кількість продукції виду А (одиниць); y – кількість продукції виду B (одиниць).

Математична модель задачі набуває вигляду: знайти мінімум сумарних витрат

Z (x, y)= 8x2 − xy +12 y2 → min

за обмежень:

а) стосовно необхідного сумарного обсягу продукції обох видів

209

x + y = 42 ;

б) стосовно невід’ємності змінних x ≥ 0, y ≥ 0 .

Задачу розв’язуємо з допомогою методу множників Лагранжа. Для цього зробимо перетворення першого обмеження, представивши його таким чином: 42 − x − y = 0 .

Функція Лагранжа має вигляд:

L(x, y, λ) = 8x2 − xy +12 y2 + λ (42 − x − y) .

Знаходимо частинні похідні першого порядку та прирівнюємо їх до нуля.

	∂L		=16x	− y −λ,
	∂x				16x − y −λ = 0,		16x − y −λ = 0,
	∂L
	∂y	= −x + 24 y −λ, − x + 24 y −λ = 0,					− x + 24 y −λ = 0,
	∂L		= 42 − x − y.		42 − x − y = 0.		x + y = 42.
	∂λ
	Розв’язуємо отриману систему трьох рівнянь із трьома
невідомими за формулами Крамера:
	16 −1			−1
= −1 24 −1 =16 24 0 + (−1) (−1) 1+ (−1) (−1) 1−1 24 (−1)−

1 1 0 −1 (−1) 16 −0 (−1) (−1)= 0 +1+1+ 24 +16 −0 = 42,

			0					−1	−1
1 =			0					24	−1		= 42 + 24			42	= 25 42 =1050,
			42					1	0
							16	0	−1
2	=						−1	0	−1				= 42 +16	42	=17 42 = 714,
							1	42	0
					16			−1	0
3	=				−1			24	0				=16 24 42 − 42 = 383 42 =15286,
					1			1	42

210