Navch._posibnuk_Ivaschyk

x2 = 4 −22x1 = 2 −1 x1 = 2 − x1 .

Отже, k = −1.

Рівняння дотичної до досліджуваної параболи має вигляд:

x2 − x20 = f ′(x10 ) (x1 − x10 ).

З іншого боку, кут нахилу лінії l2 можна виразити таким чином: k = f ′(x10 ).

Проведемо розрахунки на основі цих міркувань:

		f ′(x10 )= ((x1 −1)2 +1)′
															= 2(x1					−1)			x =x0 = 2x10 − 2 .
													x =x0									1		1
											1			1			1
	Маємо:	−1 = 2x0	− 2.				Звідси x0								=			.
		1									1					2
	Тепер	знаходимо				x	0	= 2 − x0						= 3 .					Отже,						координати точки
							2				1					2
			D			1		3
	дотику параболи до l2:						;			. Знайдемо значення цільової функції
				2				2
		1	;	3				2		1			1			2			3	=	5		−	1	=	9	.
	в цій точці: Z (D)= Z			2	=					2	−					+			2		2			4		4
		2											2

Визначивши значення цільової функції у вершинах допустимої множини (О(0;0), А(0;2), С(2;0)), переконуємося, що екстремальними значеннями цільової функції є такі значення:

Zmin = Z (O)= Z (0;0)= 0;

Zmax = Z (D)= Z 12 ; 32 = 94 . ♦

6.2. Основні види задач нелінійного програмування

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

Методи нелінійного програмування бувають прямі та непрямі. Прямими методами оптимальні розв’язки шукають у напрямку найшвидшого збільшення (зменшення) цільової функції. Типовими

191

для цієї групи методів є градієнтні. Непрямі методи полягають у зведенні задачі до такої, знаходження оптимального розв’язку якої вдається спростити. Найпоширенішими методами цього класу є методи квадратичного програмування.

Оптимізаційні задачі, на змінні яких накладаються обмеження, розв’язуються методами класичної математики. Оптимізацію з обмеженнями-рівностями виконують методами зведеного градієнта, наприклад, методом множників Лагранжа. У задачах оптимізації з обмеженнями-нерівностями досліджують необхідні та достатні умови існування екстремуму Куна-Таккера.

Розглянемо метод множників Лагранжа на прикладі такої задачі нелінійного програмування:

Z = f (x1, x2 ,..., xn )	max(min),			(6.3)
qi (x1 , x2 ,..., xn ) = bi , i =			,	(6.4)
		1, m
де f (x1 , x2 ,..., xn ) та qi (x1 , x2 ,..., xn )	– диференційовані.

Ідея методу Лагранжа полягає в заміні окресленої задачі простішою – знаходження екстремуму складнішої функції, але без обмежень. Ця функція називається функцією Лагранжа і записується у вигляді:

m

L(x1, x2 ,..., xn ;λ1, λ2 ,...,λm ) = f (x1, x2 ,..., xn ) + ∑λi [qi (x1, x2 ,..., xn ) −bi ], (6.5)

i=1

де λi – невизначені поки що величини, так звані множники Лагранжа.

Необхідною умовою екстремуму функції багатьох змінних є рівність нулю частинних похідних стосовно всіх змінних функції. Візьмемо ці частинні похідні і прирівняємо їх до нуля:

∂L

= 0,

j =

,

1, n

∂x j

∂L

= 0,

i =1, m,

∂λ

або

i

∂f (x , x

,..., x

)

m

∂q (x , x

,..., x

)

+

= 0,

j =1, n,

1

2

n

∑λi

i

1

2

n

∂x j

i=1

∂x j

q (x , x

,..., x

) −b =

0

i =

.

n

1, m

i

1

2

i

Отримуємо

систему

(m+n) рівнянь із (m+n) невідомими,

розв’язавши яку,

знайдемо

X

* = (x , x

,..., x

)

та

λ

0

= (λ , λ

,..., λ

m

) –

1

2

n

1 2

стаціонарні

точки. Оскільки

їх

знайдено

з

необхідної

умови

192

екстремуму, то в них можливий максимум або мінімум. Іноді стаціонарна точка є сідловою (точкою перегину графіка функції).

Теорема. Нехай в околі критичної точки (x0; y0) функція f(x, y) має неперервні частинні похідні до другого порядку включно. Розглянемо вираз

D(x, y)=	∂2	f (x, y)		∂2	f (x, y)		∂2	f (x, y)		2
		∂x2			∂y2	−		∂x∂y	.

1) Якщо D(x0 , y0 )> 0 , то в точці (x0; y0) функція f(x, y) має такі

екстремуми:

а) досягає свого максимального значення, якщо ∂2 f (x0 , y0 )< 0 ;

∂x2

б) досягає свого мінімального значення, якщо ∂2 f (x0 , y0 )> 0 ;

∂x2

2)Якщо D(x0 , y0 екстремумів.

3)Якщо D(x0 , y0 )= 0 , то в точці (x0; y0) для функції f(x, y) екстремуми можуть існувати чи не існувати.)<

Для наглядності в деяких випадках цю теорему формулюють інакше. Складаємо матрицю такого виду:

∂2 Z

∂2 Z

H (x, y)=

∂2x

2

∂x2∂y

.

∂ Z

∂ Z

∂y∂x

∂y2

∂2 Z

Обчислюємо H1 (x, y)=

і визначник матриці H (x, y):

∂x2

∂2 Z

∂2 Z

∂

2

Z

∂

2

Z −

∂

2

Z

∂

2

Z

= ∂

2

Z

∂

2

Z

∂

2

Z

2

H

(x, y)=

∂x

2

∂x∂y

=

−

.

2

∂2 Z ∂2 Z

∂

2

2

2

∂ ∂

∂

2

∂ ∂ ∂ ∂

∂

∂

x

y

y x x y

x

y

x y

∂y∂x

∂y2

Якщо

H2 (x0 , y0 )= D(x0 , y0 )> 0

,

то в точці (x0;

y0)

досліджувана

функція має екстремум.

Якщо при цьому H1 (x0 , y0 )> 0 ,

то в окресленій точці функція

досягає

мінімального

значення;

якщо

H1 (x0 , y0 )< 0 ,

то

–

максимального значення.

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

193

Приклад 6.3. Визначити оптимальні значення функції

		z = 3x2 + 2x2			+ 2x x			2	− 2x +3x				2
при обмеженні			1	2			1			1
				x1 + x2 = 3.
♦ Розв’язування.
Перед тим, як будувати функцію Лагранжа, запишемо
обмеження	у	такому	вигляді,		щоб				в	правій			частині був нуль:
x1 + x2 −3 = 0 . Тоді функція Лагранжа матиме вигляд:
L(x , x		, λ) = 3x2	+ 2x2	+ 2x x		2	− 2x +3x				2	+ λ(x + x		2	−3).
1	2	1	2		1				1				1

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

	∂L	= 0,
	∂x				6x +		2x			− 2 + λ = 0,
	1
	∂L					1			2
			= 0,		4x2 + 2x1 + 3 + λ = 0,
	∂x2
					x	+ x	2	−3 = 0.
	∂L	= 0.			1
	∂λ

Віднімемо від першого рівняння друге, щоб виключити отримаємо таку систему рівнянь:

4x1 − 2x2 −5 = 0,

x1 + x2 −3 = 0.

Розв’яжемо її:

	4(3 − x2 ) − 2x2 −5 = 0,		12	− 4x2 − 2x2 −5 = 0,
	x1 = 3 − x2 .		x1	= 3 − x2 .
				7
	6x2 = 7,		x2	= 6 ,
				= 3 − 7 = 11.
	x1 = 3 − x2 .		x
			1	6 6

λ,

Точка	x* =	11			;	7		є підозрілою на оптимальність. Для
			7
						6

визначення типу оптимальності обчислюємо частинні похідні другого порядку

∂2 L

= 6;

∂2 L

= 4;

∂2 L

=

∂2 L

= 2,

∂x2

∂x2

∂x

∂x

2

∂x

∂x

1

2

1

2

1

а потім визначник

194

																∂2 L							∂2 L										6		2
								H				=				∂x12							∂x2∂x1							=								= 24 − 4 = 20.
										2						∂2 L							∂2 L										2		4
															∂x ∂x					2			∂x2
																1								2
Оскільки H												=		∂		2 L		= 6				> 0						i				H				> 0 , то це означає, що в точці
											1				∂x2																			2
	11		7													1
x* =		;				функція досягає мінімуму:
7			6
												z	min			= 3x2						+ 2x2					+ 2x x							2		− 2x +3x					2	=
																				1				2								1						1
						11			2		+ 2					7			2		+ 2			11				7			− 2				11			+3	7	=		609	=101,5.	♦
= 3
																								6				6							6				6			6
							6									6

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

Функція f (x1, x2 ,…, xn ) , яка визначена на опуклій множині М, називається опуклою, якщо для будь-яких двох точок х1 і х2 з множини М і довільної константи λ з проміжку [0; 1], (0≤λ≤1) справджується співвідношення:

f [λx1 + (1−λ)x2 ]≤ λf (x1 ) + (1−λ) f (x2 ) .

Функція f (x1, x2 ,…, xn ) , яка визначена на опуклій множині М, називається вгнутою, якщо для будь-яких двох точок х1 і х2 з множини М і довільної константи λ з проміжку [0; 1], (0≤λ≤1)

справджується співвідношення
f [λx1 + (1 − λ)x2 ]≥ λf (x1 ) + (1 − λ) f (x2 ) .
Розглянемо задачу опуклого програмування.
f (x1, x2 ,…, xn ) → max(min),					(6.6)
qi (x1, x2 ,…, xn ) ≤ bi , i =				,	(6.7)
			1, m
x j ≥ 0, j =		,			(6.8)
	1, n
де f (x1, x2 ,…, xn ) – вгнута (опукла) функція; qi (x1, x2 ,…, xn )					– опуклі

функції.

Множина допустимих рішень задачі (6.6)-(6.8) задовольняє умову регулярності, якщо існує хоч би одна точка X = (x1 , x2 ,…, xn ) в

описуваній множині з координатами, що задовольняють нерівності qi (x1, x2 ,…, xn ) < bi ,i =1, m .

195

Якщо f (x1, x2 ,…, xn ) – вгнута (опукла) функція, яка задана на

опуклій множині, то будь-який локальний максимум (мінімум) є глобальним максимумом (мінімумом).

Функція Лагранжа для задачі опуклого програмування записується в такому ж виді, як і для будь-якої задачі нелінійного програмування

m

L(x1, x2 ,…, xn , λ1, λ2 ,…, λm ) = f (x1, x2 ,…, xn ) + ∑λi [bi −qi (x1, x2 ,…, xn )],

i=1

де λ1 , λ2 ,…, λm – множники Лагранжа.

Точка( X 0 ; Λ0 ) = (x10 , x20 ,…, xn0 ;λ10 , λ02 ,…, λ0m ) називається сідловою точкою функції Лагранжа, якщо

L(x1 ,…, xn ,λ10 ,…,λ0m ) ≤ L(x10 ,…, xn0 ;λ10 ,…,λ0m ) ≤ L(x10 ,…, xn0 ;λ1 ,…,λm ),

для всіхxj ≥ 0, j =1, n іλi ≥ 0,i =1, m.

Теорема (теорема Куна-Таккера). Якщо множина допустимих розв’язків задачі опуклого програмування (6.6)-(6.8) задовольняє умову регулятивності, то точка X 0 = (x10 , x20 ,…, xn0 ) буде оптимальним

розв’язком задачі	тільки тоді, коли існує такий вектор
Λ0 = (λ10 , λ02 ,…, λ0m ),	λ0i ≥ 0,i =		, що ( X 0 ; Λ0 ) – сідлова точка функції
		1, m

Лагранжа.

Теорема Куна-Таккера дає можливість сформулювати математичні вирази, що визначають необхідні та достатні умови наявності сідлової точки. Це відображає така теорема.

Теорема. Якщо задачу нелінійного програмування

Z = f (x1, x2 ,…, xn ) → max, qi (x1, x2 ,…, xn ) ≥ 0,i =1, m; x j ≥ 0, j =1, n,

де Z = f (x1, x2 ,…, xn ) та qi (x1, x2 ,…, xn ), i =1, m – неперервно диференційовані по х функції, то для того, щоб векторX 0 ≥ 0 був оптимальним розв’язком задачі, необхідно щоб існував такий вектор

Λ0 ≥ 0, що точка з координатами( X 0 ; Λ0 ) була би сідловою точкою функції Лагранжа, тобто щоб виконувалися умови:

196

	∂L( X 0 , Λ0 ) ≤ 0, j =					;
				1, n
	∂x j
	∂L( X 0 , Λ0 ) x0j = 0, j =									;
								1, n
	∂x j
	∂L( X 0 , Λ0 ) ≥ 0,i =				;
			1, m
	∂λi
	∂L( X 0 , Λ0 ) λ0	= 0,i =							;
							1, m
	i
	∂λi
∂L0 ;	∂L0 – значення відповідних	похідних функції Лагранжа,
∂xj	∂λi

обчислені в сідловій точці.

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

Квадратичною формою відносно змінних x1, x2 ,…, xn є числова

функція цих змінних вигляду:

Z = c11x12 + c22 x22 +…+ cnn xn2 + 2c12 x1x2 + 2c13 x1x3 +…+ 2c1n x1xn +…+

n	n
+ 2cn−1,n xn−1xn = ∑∑cij xi x j
i=1 j=1
Квадратична форма Z(X) називається додатно (від’ємно)
визначеною, якщо	Z(X)>0 (Z(X)<0) для всіх значень змінних

X = (x1, x2 ,…, xn ) , крім Х=0.

Квадратична форма Z(X) називається напіввизначеною, якщо

Z(X)≥0 (Z(X)≤0) для всіх	значень змінних X = (x1, x2 ,…, xn ) , крім
цього існує такий вектор	X * = (x1* , x2* ,…, xn* ) , не всі координати
котрого рівні нулю і для якого Z ( X * ) = 0.

Квадратична форма Z(X) називається неозначеною, якщо її значення є додатними для одних значень Х і від’ємними для інших.

Вид квадратичної форми можна визначити через власні значення (характеристичні корені) Λ = (λ1, λ2 ,…, λn ) матриці коефіцієнтів С, де

197

c11	c12	… c1n
c21	c22	… c2n
C =		…	.
	cn2	…
cn1			cnn

Складаємо характеристичне рівняння матриці С:

	c11 −λ1	c12	… c1n
	c21	c22 −λ2	…	c2 n	= 0.
			…
	cn1	cn 2	… cnn −λn

З цього рівняння визначаємо вектор характеристичних коренів:

Λ = (λ1 , λ2 ,…, λn ) .

Теорема. Квадратична форма є додатно (від’ємно) визначеною тільки тоді, коли всі компоненти вектора характеристичних коренів є додатними (від’ємними).

Якщо власні числа мають різні знаки, то квадратична форма є невизначеною.

Задача квадратичного програмування – це задача виду

n	n	n
f (x1, x2 ,…, xn ) = ∑d j x j + ∑∑cij xi x j → extr
j=1	i=1	j=1

при обмеженнях

	n
		xj	≤ bi ,i =1, m;
	∑aij
	j=1
	xj ≥ 0, j =				,
				1, n
n	n
де ∑∑cij xi x j – додатно (від’ємно) напіввизначена квадратична
i=1	j=1

форма.

Умови Куна-Таккера для задачі випуклого програмування мають вигляд:

198

∂L0	+ν j = 0, j =				;
			1, n
∂xj
∂L0	− w = 0,i =			;
		1, m
∂λi	i

x0jν j = 0, j =1, n;

λ0i wi = 0,i =1, m;

x0j ≥ 0, λ0i ≥ 0,ν j ≥ 0, wi ≥ 0.

Теорема. Х0 є оптимальним розв’язком задачі квадратичного програмування тільки тоді, коли існують такі m-вимірні вектори

Λ0 ≥ 0, w ≥ 0 і n-вимірний вектор V ≥0, для яких виконуються умови:
I.	∂L(X 0 ; Λ0 )+ν j = 0. j =					.
				1, n
	∂x0j
II.	ν j x0j = 0, j =		.
		1, n
III.	∂L(X 0 ; Λ0 )− w = 0.i =						.
					1, m
	∂λi
		i

IV. wi λ0i = 0,i =1, m.

Приклад. 6.4. Розв’язати задачу квадратичного програмування.

Z = −x2			− x x			2	− 2x2 −5x								+ 3x		2	→ max,
		1		1						2				1
x	+ x		≤ 5,
1		2
x1 ≥ 0, x2 ≥ 0.
♦ Розв’язування.			Z = Z1 + Z2 ,
			Z1 = −5x1 +3x2 ,
			Z	2	= −x2				− x x				2	− 2x		2 .
							1			1					2			Z		= −x2	− x x		− 2x2
Розглянемо	квадратичну									функцію									2			2		та
																				1	1		2
відповідну їй матрицю, складену з коефіцієнтів при змінних
								−1				−		1
														2
										1
				C =				−				−		2	.
										2

Знаходимо власні значення (характеристичні корені) матриці С, виписавши характеристичне рівняння

199

			−1−λ							−		1
				1								2		= 0 .
			−						− 2 −λ
	Тоді			2
													1			1
	(−1−λ)(−2 −λ) −											−			−		= 0,
													2			2
	(1+ λ)(2 + λ) −								1	= 0,
									4	1
	2 + 2λ + λ +							2	−		= 0,
								λ
										4
	2			3
	λ +3λ +1							= 0,
					4
	D = 9 − 4			7				= 2,
				4
	λ =	−3 ±		2				,
		2
	λ = −3 +			2				≈ −3 +1.4 = −0.8 < 0,
	1	2								2
	λ2 =	−3 −		2				≈	−3 −1.4 = −2.2 < 0.
		2								2

Оскільки λ1 і λ2 є меншими від нуля, то квадратична форма Z2 = −x12 − x1 x2 − 2x22 є від’ємно означеною, тобто увігнутою.

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

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

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

∂L

= −2x

− x

−5 −λ ≤ 0;

∂L

= −x

− 4x

+3 −λ ≤ 0;

2

2

∂x1

1

1

∂x2

∂L = 5 − x

− x

≥ 0;

∂L

x0

= 0;

∂L

x0

= 0; ∂L λ0 = 0,

2

∂λ

1

1

∂x2

2

∂λ

∂x1

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

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

200