Методы оптимизации / volsu419

Вычитая из первого равенства второе, получаем

( y − x)z + 2λ1 (x − y) = 0 или ( y − x)(z − 2λ1 ) = 0 .

Аналогично имеем два других уравнения (x − z)( y − 2λ1 ) = 0 и ( y − z)(x − 2λ1 ) = 0 . Из этих уравнений и ограничительных условий видим, что две переменные равны некоторому числу p, а третья равна

−2p (из x + y + z = 0 ). Тогда из x2														+ y2		+ z2 =1 имеем
p2 + p2 + 4 p2 =1 p = ±1 6 .
				Итак,				1	,	1	,−	2			1	,−	2	,	1
						xˆ =		6		6		,			6					,
												6					6			6
	−		2	,	1	,	1		−	1	,−	1	,	2				1	,	2	,−	1
								,								, −						6	,
			6 6 6							6		6 6						6 6
	2		,−		1	,−	1
					6			.
		6					6
				Для первых трёх xyz = −1 3										6 , для следующих трёх
xyz =1 3						6 . Так как			f (x, y, z) = xyz непрерывна и определена на

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

ния дают abs min f , а вторые −

abs max f .

Smin

= −1 3 6 ,

Smax =1 3 6 .

Пример 2. f (x , x

2

) = ex1x2

→ extr,

x

+ x

2

=1.

1

1

Функция Лагранжа Λ(x) = λ ex1x2 + λ (x

+ x

2

−1) = 0 .

0

1

1

Условия стационарности: Λ

x

= 0 λ x

ex1x2

+ λ = 0 ,

0

2

1

1

Λ

= 0 λ x ex1x2

+ λ = 0 ,

x2

0

1

1

λ0 = 0 λ1 = 0 λ0 ≠ 0 .

Пусть λ =1. Тогда x

ex1x2

+ λ = 0 ,

x ex1x2

+ λ = 0 .

0

2

1

1

1

Отсюда x1 = x2 , а из x1 + x2

=1, x1

= x2 =1 2 .

Стационарная точка

xˆ = (1 2 ,1 2),

f (xˆ) = e1 4 . Так как при

x1 → ∞ в силу x1 + x2 =1 x1 и x2 должны быть разных знаков и

11

x2 тоже стремится к ∞, поэтому ex1x2 → ∞. В силу следствия из теоремы Вейерштрасса xˆ abs max , Smax = e14 , Smin = 0 .

3. Конечномерные гладкие задачи с ограничениями типа равенств и неравенств.

Постановка задачи. Пусть fi : Rn → R, i = 0, m , − функ-

ции, обладающие определенной гладкостью. Гладкой конечномерной задачей с

ограничениями типа равенств и неравенств называется задача:

′

fi (x) = 0, i =1, m

′

+1, n

f0 (x) → extr, fi (x) ≤ 0, i =1, m ,

(P)

Правило решения. Для решения задачи (P) нужно:

m

1. Составить функцию Лагранжа

Λ(x) = ∑λi fi (x) .

i=0

2. Написать необходимые условия экстремума первого порядка:

′

∂Λ(xˆ)

(x) = 0

j =1, n ;

а) условие стационарности: Λ

∂x j

= 0,

б) условие дополняющей нежёсткости:

λi fi (xˆ) = 0, i =

1, m′

;

в) условие неотрицательности: λi

≥ 0,

i =

1, m′ .

3. Найти критические точки xˆ , удовлетворяющие условиям а) − в). При этом рассматриваются случаи λ0 = 0, λ0 =1 , (или любое положи-

тельное число), λ0 = −1 (или любое отрицательное число).

В случае а) xˆ может быть точкой как минимума так и максимума, в

случае б) xˆ может быть точкой минимума, в случае в) xˆ может быть точкой максимума.

При нахождении критических точек в условиях дополняющей нежёсткости λi fi (xˆ) = 0, надо рассматривать случаи λi = 0 и λi ≠ 0 .

4. Исследовать на локальный и абсолютный экстремум критические точки непосредственной проверкой и, если нет абсолютных экстремумов,

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

12

Пример 1. f (x , x	2	, x	3	) = x x			2	x		3			→ extr, x2 + x2					+ x2		≤1.
1					1											1	2		3
Функция Лагранжа Λ(x) = λ x x									2		x		3	+ λ (x2		+ x2	+ x2		−1) .
					0	1								1	1	2		3
Необходимые условия экстремума:
				λ0 x2 x3 + 2λ1 x1 = 0
а) условия стационарности: λ0 x2 x3 + 2λ1 x2																= 0 ;
					λ x x							2	+ 2λ x		3	= 0
						0		1						1

б) условие дополняющей нежёсткости: λ1 (x12 + x22 + x32 −1) = 0 ;

в) условие неотрицательности: λ1 ≥ 0 .

а)

λ0 = 0 λ1 > 0 x1 = x2 = x3 = 0 .

б)

Если λ1 > 0 x12 + x22 + x32 =1. Противоречие.

Пусть λ0

=1.

2

x2 x3 + 2λ1 x1 = 0

x1 x2 x3 + 2λ1 x1

= 0

Тогда x1 x3 + 2λ1 x2

= 0

x1 x2 x3 + 2λ1 x22

= 0 .

(1)

x x

2

+

2λ x

3

= 0

x x

2

x

3

+ 2λ x2

= 0

1

1

1

1

3

x2 x3

= 0

Пусть λ1

= 0 .

= 0 . Тогда x1 x3

x x

2

= 0

1

Это выполняется только при двух переменных, равных 0. Т.е. в этом

случае xˆ = (t,0,0), (0, t,0), (0,0, t) , где

t

≤1.

xˆ loc extr f

, так как, например, для (0, t, 0) имеем

f (x + h1 ) > 0 при t > 0 ,

h = (ε,0,ε)

и

f (x + h2 ) < 0 при

h2

= (ε,0,−ε), ε > 0 .

Пусть λ > 0 . Тогда из (1)

x2

= x2

= x

2

. Отсюда и из

1

1

2

3

x2

+ x2

+ x2 =1 следует x2 =1 3,

i =1, 2, 3 , т.е.

x

i

= ±1

3 .

1

2

3

i

Возможные значения x x

2

x

3

есть

1

и

−

1 .

1

3

3

3

3

13

				Из следствия теоремы Вейерштрасса
xˆ =				1		,		1		,	1			1	,−		1	,−	1			−	1	,	1	,−	1
					3			3					,	3			3				,							,
											3								3				3 3				3
	−	1			,−			1	,	1
			3					3				abs max f ;
											3
xˆ =			−		1			,−		1		,−	1				1	,	1	,	1			1	,−	1	,	1
						3				3				,	−		3		3		,			3		3		,
													3								3							3
	1	,			1		,−		1			abs min f .
					3					3
	3
												Smax		=	1	3	,	Smin		= −		1 .
														3							3		3

n

Пример 2. f (x) = ∑

i=1

n

xi4 → extr ; ∑x12 ≤1.

i=1

Функция Лагранжа

Λ(x) = λ0 (x14 +K+ xn4 ) + λ1 (x12 +K+ xn2 −1) .

Необходимые условия экстремума:

а) условие стационарности: Λxi = 0 4λ0 xi3 + 2λ1 xi = 0 , i =1, n ;

б) условие дополняющей нежёсткости: λ1 (x12 +K+ xn2 −1) = 0 ;

в) условие неотрицательности: λi ≥ 0 .

а)

x

: x2 +K+ x2

≤1. Отсюда λ1 = 0, но

λ

= 0 λ x

i

= 0

i

0

1

1

n

λ0 и λ1 не могут быть равны 0 одновременно.

0

= 1

x13 + λ1 x1 = 0

x1 (x12 + λ1 ) = 0

xi = 0,

Пусть λ

2

.Тогда

K

K

x3

+ λ x

= 0

x

(x2

+ λ ) = 0

n

n

n

1

n

1

i =

(так как λ1 ≥ 0)

xˆ = (0,K,0) abs min f . Smin = 0.

1, n

14

0

x13 − λ1 x1 = 0

x1 (x12 − λ1 ) = 0

K

K

.

Пусть λ = − 1

2

.Тогда

x3 − λ x

= 0

x

(x2 − λ ) = 0

n

n

1 1

n

1

Если λ1 > 0 и все xi ≠ 0, то все

xi2 =1 n ,

xi

= ±1

n ,

чему соответствуют 2n точек xˆ abs max f с координатами

(±1

n,K,±1 n ),

Smax = n 1 n2

=1 n .

Если m координат xi

≠ 0, а n − m , равны 0, то имеется Cnm 2m

критических точек, у которых m координат, равных ±1

m и n − m

равны 0. Пусть для определённости x2

=K= x2

=1 m , а

1

m

xm2 +1 =K= xn2 = 0 .

Если x1 изменить так, чтобы x2

=1 m −ε , а xn изменить так, что-

1

бы xn2

= ε , то

x14 + xn4 + (1 m −ε)2

+ε2

=1 m2 − 2ε

n + 2ε2

<1 m2 при доста-

точно малом ε > 0.

Отсюда видно, что все Cnm 2m критических точек xˆ loc max f .

n

n

Пример 3. f (x) = ∑xi2 → extr ; ∑x14

≤1.

i=1

i=1

Функция Лагранжа

Λ(x) = λ0 (x12 +K+ xn2 ) + λ1 (x14 +K+ xn4 −1) .

Необходимые условия экстремума:

а) условие стационарности: Λxi = 0 2λ0 xi + 4λ1 xi3 = 0 , i =1, n ;

б) условие дополняющей нежёсткости: λ1 (x12 +K+ xn2 −1) = 0 ;

в) условие неотрицательности: λ1 ≥ 0.

Если λ0 = 0, то как в предыдущем примере λ1 = 0 и опять получаем λ0 ≠

0.

15

				3
xi		+ λ1 x1			= 0	xi =0
Пусть λ0 = 2. Тогда			K
x	n	+ λ x3			= 0
			1	1
xˆ = (0,K,0) abs min f .
					2	= 0
x1 (1 − λ1 x1 )
Пусть λ0 = −2. Тогда				K		.
x		n	(1 −	λ x2 ) = 0
					1 n

Если λ1

> 0, то x4 +K+ x4 =1 . Если все xi

≠ 0, то x4

=1 n ,

1

n

i

xi = ±1 4 n , xi2 =1 n

По следствию из теоремы Вейерштрасса

ˆ

= ±

4

n ,

K

±

1

4

n )

abs max f

.

Smax

=

n

n

=

n

.

x

( 1

,

Если m координат xi ≠ 0, а n − m , равны 0, то имеется Cnm 2m

критических точек, у которых m координат, равных ±1 4

m и n − m

равно 0. Пусть для определенности x4

=K= x4

=1 m , а

1

m

x4 + =K= x4 = 0 .

m 1 n

Если изменить x1 так, чтобы x14 =1m −ε , а xn изменить так, чтобы xn4 = ε , то

x12 + xn2 = 1 m −ε + ε = 1 m ( 1 − mε + mε ) =

=1 m (1 − mε 2 + mε + o(ε)) >1 m при достаточно малом

ε > 0 , а при x14 = −1m , xn = 0, x12 + xn2 <1 m . Поэтому Cnm 2m критических точек xˆ loc min f .

16

4. Линейное программирование

Стандартная задача линейного программирования:

z = c1x1 + c2x2 + …+ cnxn → max

при условиях:

a x

+ a x

2

+K+ a

x

n

≤ b

11 1

12

1n

1

a21 x1 + a22 x2 +K+ a2n xn ≤ b2

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

a

x

+ a

m2

x

2

+K+ a

mn

x

n

≤ b

m1 1

m

x1 ≥ 0, x2 ≥ 0, …, xn ≥ 0.

Двойственная ей задача линейного программирования: w = b1y1 + b2y2 + …+ bmym → min

a y

+ a

21

y

2

+K+ a

m1

y

m

≤ c

11 1

1

a12 y1

+ a22 y2 +K+ am2 ym

≤ c2

,

K K K

a y

+ a

2n

y

2

+K+ a

mn

y

m

≤ c

n

1n 1

y1 ≥ 0, y2 ≥ 0, …, ym ≥ 0.

(1)

(2)

Каждое неравенство в (1) и (2) определяет полупространство. Множество точек, удовлетворяющих (1) и (2), есть пересечение полупространств и, следовательно, есть выпуклый многогранник. Он называется

областью допустимых решений. Множество точек, в которых z = a есть гиперплоскость

c1x1 +…+ cnxn= a.

Отсюда следует, что экстремальные значения целевая функция z принимает в вершинах этого многогранника.

Стандартная и двойственная ей задачи решаются одновременно симплекс-методом, который состоит в следующем:

1) Ограничения в стандартной задаче заменяются равенствами введением дополнительных переменных s1, …, sm в каждом из m неравенств:

a x		+K+ a		x	n	+ s		= b
	11 1		1n				1	1
a21 x1		+K+ a2n xn + s2						= b2	(3)
... ... ... ... ... ...
a	x	+K+ a	mn	x	n	+ s	m	= b
	m1 1							m
				17

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

x1	x2	…	xn	s1	s2 … sm
a11	a12	…	a1n	1	0	…	0	b1
a21	a22	…	a2n	0	1	…	0	b2
.	.	.	.	.	.		.	.
.	.	.	.	.	.		.	.
.	.	.	.	.	.		.	.
am1	am2	…	amn	0	0	…	1	bm
c1	c2	…	cn	0	0	…	0	z
	В системе уравнений (3) можно считать si , i =											базисными пе-
											1, m
ременными, а x1, …, xn − свободными.
	Будем считать сначала, что все bi ≥ 0, i =								1, m	. Тогда при свобод-
ных переменных, равных нулю,
	si = bi, z = c1x1 + … + cnxn + 0 s1 + … + 0 sm = 0.
	Числа, стоящие в последней строчке таблицы (кроме z), называются

индикаторами. Если все они не положительны, c1 ≤ 0, то z = 0 есть максимальное значение, т.е. решение задачи.

Если имеются положительные индикаторы, то выбирается какойнибудь столбец с положительным индикатором, скажем, k-й и в этом столбце выбирается центральный элемент, скажем, ajk, такой что ajk ≥ 0 и

отношение bj a jk было бы минимальным для всех				bi aik с положи-
тельными aik. Отмечаем в таблицеa jk .
3) Делим всю k-ю строку на ajk, чтобы вместо a jk				получить	1	.

4) Из каждой из остальных (кроме j-ой), скажем, i-ой строки, надо вычесть j-ю, умноженную на aik (чтобы все элементы k-го столбца, кроме

ajk, стали нулями,	в том числе и индикатор).	При этом z заменится на
z − bj ck . z − bj	ck = 0 , откуда z = bj ck	> 0 .

Если после этого остались положительные индикаторы, то опять выбираем столбец с положительным индикатором, центральный элемент и

т.д., как описано выше, превращаем центральный элемент в 1, а остальные

элементы столбца в 0. Таким образом действуем до тех пор, пока не будет положительных индикаторов. Как только положительные индикаторы исчезнут, то задача решена.

18

Если в заключительной таблице стоит z − p, то zmax = p, причём значения xi находятся следующим образом: если xi − базисный элемент, т.е. в заключительной таблице в i-м столбце одна единица в каждой строке, а остальные нули, а последним в k-й строке стоит bi′, то xi = bi′, а

если i-й столбец имеет другой вид, то xi = 0.

Решение двойственной задачи wmin = p (= z), а yi равны индикатору в столбцеsi взаключительнойтаблице, собратным знаком(т.е. с"+").

Рассмотрим теперь случай с присутствием отрицательных bi в (1). Этапы решения 1) и 2) те же.

3) Выбираем строку с отрицательным bi (если их несколько, то любую из них). Выбираем в этой строке любой отрицательный элемент (если такого

не найдётся, товсилунеотрицательностиxi задачанеимеетрешения). Опять центральный элемент превращаем в единицу, а остальные

элементы этого столбца превращаем в нуль. Так действуем, пока отрицательных bi не окажется. После этого мы получаем случай с положительными bi, решение которого описано выше.

Пример 1.	z = x1 + 2x2 → max
	2x1 + 3x2 +2x3 ≤ 2
	−x1 +4x3 ≤ 2
	x1 ≥ 0, x2 ≥ 0, x3 ≥0.
Двойственная задача.	w = 2 y1 + 2 y2 → min
	2y1	− y2 ≥ 1
	3y1	≥ 2
	2y1	+ 4y2	≥ 0
	y1 ≥ 0, y2		≥ 0.

Симплекс-таблицы

x1			x2	x3		s1		s2		b					x1				x2	x3				s1	s2			b
	2		3	2		1		0		2						1			3/2	1			1/2		0			1
-1			0	4		0		1		1		→			-1				0	4				0	1			2		→
1			2	0		0		0		z					1				2	0				0	0			z
x1			x2	x3		s1	s2		b				x1				x2		x3			s1		s2		b
1			3/2	1	1/2		0		1				2/3				1		2/3			1/3		0		2/3
0			3/2	5	1/2		1		3		→		0		3/2				5			1/2		1		3				→
0			1/2	-1	-1/2		0		z-1				0		1/2				-1			-1/2		0		z-1
											19

	x1	x2	x3	s1	s2	b
	2/3	1	2/3	1/3	0	2/3
→	-1	0	1	0	1	2
	-1/3	0	-4/3	-2/3	0	z- 4/3

Ответ: zmax = wmin = 4/3; x1 = 0, x2 = 2/3; y1 = 2/3, y2 = 0.

			Пример 2.								z = 5x1 + x2 → max
											4x1 + 3x2 ≤ 12
											−2x1 +3x2 ≥ 6
											x1 ≥ 0, x2 ≥ 0.
			Стандартный вид задачи: z = 5x1 + x2															→ max
											4x1 + 3x2 ≤ 12
											2x1 − 3x3 ≤ −6
											x1 ≥ 0, x2 ≥ 0.
			Двойственная задача:								w =12 y1 − 6 y2
											4y1 + 2y2 ≥ 5
											3y1 − 3y2 ≥ 1
											y1 ≥ 0, y2 ≥ 0.
									Симплекс-таблицы
	x1				x2			s1	s2		b					x1		x2		s1	s2		b
	4			3				1	0		12				4			3		1	0	12
	2				-3			0	1		-6		→		-2/3			1		0	-1/3	2		→
	5				1			0	0		z				5			1		0	0		z
	x1			x2				s1	s2		b				x1			x2		s1	s2		b
		6		0			1		1		6					1		0		1/6	1/6		1
→	-2/3			1			0		-1/3		2	→			-2/3			1		0	-1/3		2		→
	17/3			0			0		1/3		z-2				12/3			0		0	1/3		z-2

	x1	x2	s1	s2	b
	1	0	1/6	1/6	1
→	0	1	1/9	-2/9	8/3
	0	0	-17/18	-11/18	z- 23/3

Ответ: zmax= 23/3 при x1= 1, x2 = 8/3 и wmin= 23/3 при y1= 17/18, y2 = 11/18.

20