Metody_optimizatsii_Shatina_A_V

31

ì2x1 + 2 + 4λ3 = 0,

ï

+ λ2 + 3λ3 = 0,

ìx1 = -5,

ï- 8

ï

- 2 + λ3 = 0,

ï

= 0,

ïx2

ï

Û

ï

= 60,

íx2 = 0,

íx3

ï4x

+ 3x

2

+ x = 40,

ïλ

= 2,

ï

1

3

ï

2

ï3x1 + 3x2 + x3 ³ 9,

ïλ

= 2.

î

3

ï

îλ2 > 0.

точка P(- 5;0;60) при

Таким образом,

получена

критическая

λ0 = 1,λ1 = 0,λ2 = 2,λ3 = 2 .

2.3) λ1 ¹ 0, λ2 = 0. Тогда второе и третье уравнения системы

(4) принимают вид:

ì− 8 − 3λ1 + 3λ3 = 0,

í- 2 - λ + λ

3

= 0,

î

1

откуда следует, что система (4) решений не имеет.

2.4) λ1 ¹ 0, λ2 ¹ 0. Тогда

ì2x1 + 2 − 3λ1 + 4λ3 = 0,

ìx1 = 31,

ï- 8 - 3λ + λ

2

+ 3λ

3

= 0,

ïx

2

= 0,

ï

1

ï

ï - 2 - λ1 + λ3 = 0,

ïx3 = -84,

ï

+ x3 = 9,

Û

ï

= -72,

í3x1 + 3x2

íλ1

ï

= 0,

ï

= -2,

ïx2

+ x

= 40,

ïλ2

ï4x + 3x

ïλ

= -70,

ï

1

2

3

ï

3

îλ1

> 0, λ2 > 0.

îλ1 > 0, λ2 > 0.

Не выполняются условия неотрицательности для множителей Ла-

гранжа λ1,λ2 .

Проведем исследование полученного в пункте 2.2) решения. Рассмотрим допустимую точку P(- 5 + ε1, ε 2 , 60 + ε 3 ) из

32

окрестности точки

P(- 5;0;60) . Из ограничений задачи получим

условия на ε1, ε 2 , ε3:

ì9 − 3(− 5 + ε1 )

− 3ε 2 − 60 − ε 3 ≤ 0,

ìε 3 = −3ε 2 − 4ε1

ï

Û

ï

£ 0,

íε 2 £ 0,

) + 3ε

íε 2

ï4(- 5 + ε

1

2

+ 60 + ε

3

= 40.

ï3ε

1

+ 3ε

2

+ ε

3

³ -36.

î

î

Оценим разность f0 (P) - f0 ( P) :

~

+ ε1 ) 2 + 2(- 5 + ε1 ) - 8ε 2 - 2(60 + ε 3 ) - (-105) =

f0 (P) - f0 ( P) = (- 5

= ε12 - 8ε1 - 8ε 2 - 2ε3 = ε12 - 2ε 2 ³ 0 "ε1 Î R, "ε2 £ 0.

Так как разность

f0 (P) - f0 ( P) принимает неотрицательные зна-

чения не обязательно для малых по модулю значений ε1, ε 2 , ε3, то P(- 5;0;60) Î absmin з, Smin = -105.

Ответ: P(- 5;0;60) Î absmin з, Smin = -105. ●

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

Пример 3. Найти наибольшее и наименьшее значение функ-

ции f ( x1, x2 ) = x1x2 (9 - x1 - x2 ) на множестве

D = {( x1, x2 ) :x1 + x2 £ 12, x1 ³ 0, x2 ³ 0 } .

Решение: Множество D представляет собой треугольник,

расположенный в первой четверти на плоскости Ox1x2 с верши- нами в точках O(0;0), A(12;0), B(0;12) .

Найдем стационарные точки функции f :

						33
							éx1 = x2 = 0,
ì	¶f						êìx1 = 9,
ï			= x2	(9	- 2x1	- x2 ) = 0,	êí	= 0,
	¶x1
ï							êîx2
í	¶f						Û ê	= 0,
ï			= x1(9 - x1 - 2x2 ) = 0.				êìx1
ï	¶x2						êí	= 9,
î							êîx2
							êx = x		2	= 3.	.
							ë 1

Таким образом, получены стационарные точки функции f : P1(0;0), P2 (9;0), P3 (0;9), P4 (3;3) . Заметим, что только одна точка

P4 (3;3) является внутренней точкой множества D . Остальные точки лежат на границе этого множества. Вычислим значение функции в этих точках:

f ( P1 ) = 0, f ( P2 ) = 0, f ( P3 ) = 0, f ( P4 ) = 27 . Исследуем функцию f на границе множества D . На стороне OA x2 = 0, f ≡ 0 .

На стороне OB x1 = 0, f ≡ 0.

На стороне AB x2 = 12 − x1, 0 ≤ x1 ≤ 12, f = −3x1(12 − x1) . Найдем значение этой функции в стационарной точке и на кон-

цах отрезка [0;12] . Имеем									f ′ = 6x1 − 36, f ′ = 0 при x1 = 6 . Далее,
f		x =0 = 0,	f		x =12	= 0, f		x	=6 = -108	. Сравнивая полученные зна-
1			1			1
чения функции f						, заключаем:
					fmax = f (3;3)				= 27, fmin = f (6;6) = −108.
									Ответ: fmax = 27, fmin = −108. ●

В ряде случаев, когда n = 2, эффективным оказывается графический метод решения задач на экстремум. Графическое решение задачи включает себя следующие этапы:

1)построение множества допустимых точек X ;

2)построение семейства линий уровня целевой функции

f0 ( x1, x2 ) = c и нахождение точек их касания с кривыми, ограничивающими множество X ;

34

3) исследование поведения целевой функции при движении вдоль ограничения к исследуемой точке и от нее. 0100090000030202000002008a01000000008a01000026060f000a035 74d464301000000000001005e860000000001000000e802000000000 000e8020000010000006c00000000000000000000002c000000710000 000000000000000000582300001221000020454d4600000100e80200 000e0000000200000000000000000000000000000080120000a81a000 0c800000021010000000000000000000000000000400d0300e868040 0160000000c000000180000000a00000010000000000000000000000 009000000100000005c080000d0070000250000000c0000000e000080 120000000c000000010000005200000070010000010000009cffffff00 000000000000000000000090010000000000cc07400012540069006d 006500730020004e0065007700200052006f006d0061006e000000000 00000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000 0000000000000d935093000000000040000000000ae3016360930000 0000047169001cc0002020603050405020304ff3a00e0417800c00900 000000000000ff01000000000000540069006d0065007300200000006 5007700200052006f006d0061006e000000333f00002c0c0000101400 0074481700387d086e000000005848170012b50230584817004c6eaf3 0704817006476000800000000250000000c000000010000001800000 00c00000000000002540000005400000000000000000000002c00000 07100000001000000982287408d858740000000005a0000000100000 04c0000000400000000000000000000005a080000d00700005000000 02000ffff2d00000046000000280000001c0000004744494302000000f fffffffffffffff5d080000d1070000000000004600000014000000080000 004744494303000000250000000c0000000e0000800e0000001400000 00000000010000000140000000400000003010800050000000b02000 00000050000000c02f0000101040000002e0118001c000000fb020200 010000000000bc02000000cc0102022253797374656d000000003f3f3f 3f0000000000000000000000003f3f3f3f3f00040000002d0100000400 0000020101001c000000fb02f4ff0000000000009001000000cc074000 1254696d6573204e657720526f6d616e0000000000000000000000000

35

000000000040000002d010100050000000902000000020d000000320

a0b00000001000400000000000001f00020000500040000002d010000

030000000000

Рис.3.1

Пример 4. x12 + ( x2 - 4) 2 ® extr; x12 + x22 £ 4, 4x12 + x22 ³ 4.

Решение: Множество допустимых точек задачи ограничено

эллипсом 4x12 + x22 = 4 и окружностью x12 + x22 = 4 и на рисунке 1 изображено в виде заштрихованной замкнутой области на плос-

кости Ox1x2 . Линии уровня целевой функции задаются уравнени-

ем

x2 + ( x

2

- 4) 2 = c

и при c

>

0 представляют собой множество

1

концентрических окружностей с центром в точке (0;4)

и радиу-

x2

+ ( x

- 4) 2 = c

сом

c . Окружность

2

имеет общие точки со

1

множеством

допустимых точек при

выполнении

условия

2 £

c £ 6 .

Поэтому

минимальное

значение

функции

f0 ( x1, x2 ) = x12 + ( x2 - 4) 2

достигается в точке P1(0;2) и равно 4, а

максимальное

значение

этой

функции

достигается

в точке

P2 (0;−2) и равно 36.

Линии 1,2,3 на рисунке 1 задаются соответственно уравне-

ниями:

- 4) 2

- 4) 2 = 36, x2 + ( x

- 4) 2 = c, c Î (4;36)

x2 + ( x

2

= 4, x2

+ ( x

2

2

.

1

1

1

Ответ: P2 (0;−2) absmax з, Smax = 36.

P1(0;2) absmin з, Smin = 4; P2 (0;−2) absmax з, Smax = 36. ●

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

3.1.x1x2 ® extr; x12 + x22 £ 1.

3.2.x1x22 ® extr; x12 + x22 £ 1.

3.3.ex1−x2 - x1 - x2 ® extr; x1 + x2 £ 1, x1 ³ 0, x2 ³ 0.

3.4.x12 + x22 - x1x2 - x1 - x2 ® extr; x1 + x2 £ 3, x1 ³ 0, x2 ³ 0.

36

3.5.x1x2 x3 ® extr; x12 + x22 + x32 £ 1.

3.6.x12 + x22 + x32 ® extr; x1 + x2 + x3 £ 1; x1 ³ 0, x1 + x2 - x3 = 12.

3.7.2x12 + 2x1 + 4x2 - 3x3 ® extr;

-2x1 + x2 - x3 £ -3, x2 ³ 0, 8x1 - 3x2 + 3x3 = 40 .

3.8.x1x3 - 2x2 ® extr; 2x1 - x2 - 3x3 £ 10, x2 ³ 0; 3x1 + 2x2 + x3 = 6

3.9.Найти наибольшее из значений, которые принимает выраже-

ние A = x + 16y , если x и y удовлетворяют неравенству

x2 + 27xy +187 y2 £ 209. Найти все пары чисел ( x; y) , при которых это значение достигается.

3.10. Найти наибольшее и наименьшее значение функции

f ( x1, x2 ) = x12 + x22 - 4x1 - 3x2

на множестве D = {( x1, x2 ) :x12 + x22 £ 25}.

3.11. Найти наибольшее и наименьшее значение функции

f ( x1, x2 ) = x1x2 ( x1 - 2)( x2 - 4)

на множестве D = {( x1, x2 ) :0 £ x1 £ 4, 0 £ x2 £ 3} .

Указание: в задачах 3.1-3.8 на нахождение всех экстремумов целевой функции при применении метода Лагранжа следует сначала решать задачу на минимум, а затем на максимум, предварительно сведя ее к задаче на минимум.

Занятие 4. Элементы выпуклого анализа. Выпуклые задачи.

Определение.	Множество	AÎ Rn называется выпуклым,
если "x1, x2 Î A	и "α Î[0;1]	элемент αx1 + (1-α ) x2 Î A.
▲

Другими словами, множество AÎ Rn выпукло, если с двумя любыми своими точками оно целиком содержит и отрезок, соединяющий их.

	f : Rn ®		(		= R È ±¥)
Пусть задана функция		R		R		. Рассмот-

37

рим два множества:

dom f = {x Î Rn : f ( x) < +¥}					- эффективное множество,
epi f = {(a, x) Î Rn+1 : f ( x) £ a, x Î dom f }									- надграфик.
Определение. Функция f				называется выпуклой, если epi f							-
выпуклое множество. Функция				f называется собственной, если
f ( x) > −∞ x и dom f ¹ Æ .										▲
Утверждение. Собственная функция выпукла тогда и толь-
ко тогда, когда выполняется неравенство Иенсена:
f (αx	+ (1- α ) x	2	) £ αf ( x ) + (1- α ) f ( x			2	)	"x , x	2	Î Rn , "α Î [0;1]	.
1			1					1

■

Утверждение. Сумма конечного числа выпуклых функций есть выпуклая функция.

Действительно, пусть функции j = 1,...,m . Тогда

		m
f ( x) = å f j ( x)			, где f j ( x) - выпуклые
		j =1
"x , x	2	Î Rn , "α Î[0;1]
1

m

f (αx1 + (1-α ) x2 ) = å f j (αx1 + (1-

j=1

α ) x2 ) £ m [αf j ( x1) + (1-α ) f j ( x2 )] =

å

j=1

	m		m	-α ) f ( x2 )
	= α å f j (	x1 ) + (1-α ) å f j ( x2 ) = αf ( x1 ) + (1
	j=1		j=1	.	■
			Примеры выпуклых функций.
	ì f		( x), x Î (a,b)
	f ( x) = í	0
1)	î+ ¥, x Ï (a,b) ,

где функция одной переменной f0 ( x) дифференцируема на ин-

тервале (a;b) , причем производная f0¢( x) не убывает на этом интервале.

	ìx ln x, x > 0
f ( x) =	ï0, x = 0
	í
1а)	ï	1б) f ( x) = e	x	,
	î+ ¥, x < 0 ,

			38
1в)	f ( x) = ax2 + bx + c, a ³ 0			.
	ì f		( x), x ÎU
	f ( x) = í	0
2)	î+ ¥, x ÏU ,

где U - выпуклое открытое множество пространства Rn , функция f0 ( x) определена и дважды непрерывно дифференцируема на

множестве U и "h Î Rn , "x Î Rn
n	¶2 f ( x)			hi h j ³ 0
å	¶x	¶x
=			j	.
i, j 1	i

3)f : R ® R, f ( x) = x .

4)f : R2 ® R, f ( x) = f ( x1, x2 ) = x1 + x2 + a .

Действительно, "x = ( x1, x2 ),

y = ( y1, y2 )

и "α Î[0;1]

f (αx + (1- α ) y) =

αx + (1- α ) y + αx + (1- α ) y + a

=

=

α ( x1 + x2 + a) + (1-α )( y1 + y2 + a)

£

≤ α

x1 + x2 + a

+ (1 − α )

y1 + y2 + a

=

т.е. для функции f

= αf ( x) + (1-α ) f ( y) ,

выполняется неравенство Иенсена.

5)

f : R2 ® R,

f ( x) = f ( x , x

2

) = max{ x , x

2

}

.

1

1

Действительно, "x = ( x1, x2 ), "y = ( y1, y2 )

f ( x) ³ x1, f ( x) ³ x2 , f ( y) ³ y1, f ( y) ³ y2 .

Кроме того, "α Î[0;1]

либо f (αx + (1- α ) y) = αx1 + (1- α ) y1 £ αf ( x)

+ (1- α ) f ( y) ,

либо f (αx + (1- α ) y) = αx2 + (1- α ) y2 £ αf ( x) + (1- α ) f ( y) ,

т.е. для функции f выполняется неравенство Иенсена.

f : Rn ® R, f ( x) =

x

= x2 + x2

+ ××× + x2

6)

1

2

n .

Выпуклость этой

функции

следует

из свойств нормы:

x + y £ x + y, αx = α x = α x (α ³ 0) .

39

Определение. Субдифференциалом выпуклой собственной

f

: Rn ®

n

функции

R

ˆ

Î R

называется следующее мно-

в точке x

жество в пространстве Rn :

¶f

( ˆ)

=

{

y Î R

n

:

(

ˆ

)

£ f

(

x

)

- f

( ˆ)

"x Î R

n }

.

▲

x

x - x, y

x

∂

(

ˆ)

Геометрический

смысл

субдифференциала:

f

x

-

это

множество

угловых

коэффициентов

линейных

функций

(

x

) =

f

( ˆ)

+ (

x

− ˆ

)

таких, что "x Î R

n

(

x

) ≤

f

(

x

)

и

a

( ˆ)

= f

( ˆ)

a

x

x, y

a

x

x

. Если

f

- дифференцируемая функция одной переменной, то

∂

(

ˆ)

- это угловой коэффициент касательной, проведенной к гра-

f

x

ˆ

f

ˆ

фику функции в точке x . Если

не дифференцируема в точке x ,

то

∂ (

ˆ)

- это множество угловых коэффициентов прямых, прохо-

f

x

дящих через точку

(

ˆ

f

( ˆ))

и лежащих целиком ниже графика

x,

x

функции y = f ( x) .

Свойства субдифференциала.

1)Субдифференциал ∂f ( xˆ) является выпуклым множеством

впространстве Rn .

2)Если f - выпуклая собственная функция и f дифференцируема в точке xˆ , то ¶f ( xˆ) = f ′( xˆ) .

Примеры субдифференциалов выпуклых функций.

1) f : R ® R, f ( x) =

x

,

1, x > 0,

ì

¶f ( x)

ï

= í-1, x < 0,

ï[-1;1], x = 0.

® R, f ( x) =

î

2)

f : R2

x

=

x2

+ x2

,

1

2

40

ì

ö

æ

x1

x2

x

ïç

,

÷

=

,

x ¹ 0,

ï

¶f (

x2

+ x2

x2

+ x2 ÷

x) = íç

x

ïè

1

2

1

2

ø

ï{y Î R2 :

y

£ 1}, x = 0.

î

3)

f : R2

® R, f ( x) = f ( x , x

) =

x + x

+ a

,

1

2

1

2

ì(1;1), если

x1 + x2 + a > 0,

¶f ( x , x

2

) = ïï( -1;-1), если

x1 + x2 + a < 0,

1

í

(1

-α )(

-1;-1) = ( 2α -1,2α -1), α Î[0;1],

α (1;1) +

ï

ï

если x1 + x2 + a = 0.

î

4)

f : R2

® R,

f ( x)

= f ( x , x

2

)

= max{ x , x

2

}

,

1

1

ì(1;0), если

x1 > x2 ,

¶f ( x1, x2 ) = íï(0;1), если

x1

< x2 ,

ïα (1;0) + (1- α )(0;1) = (α ,1- α ), α Î[0;1], если x = x

2

.

î

1

Теорема Моро-Рокафеллара.

Пусть

f

j

:Rn ® R (

j = 1,...,m)

-

выпуклые собственные

функции и в некоторой точке

x

все функции, кроме, быть может,

одной непрерывны, а эта последняя в

конечна. Тогда "x Î Rn

x

æ

m

ö

m

¶çç

å f j

÷÷( x) =

å¶f j ( x)

■

è j =1

ø

j =1

.

Выпуклые задачи без ограничений.

f ( x)

→ min , где

f

: Rn ®

- выпук-

Постановка задачи:

R

лая функция.

Теорема. (Аналог теоремы Ферма)

Для того чтобы точка xˆ доставляла в выпуклой задаче без ограничений абсолютный минимум, необходимо и достаточно, чтобы 0 ∂f ( xˆ) .