ТЕОРИЯ ОПТИМИЗАЦИИ И Алгоритмов / Методы_оптимизации

31

F(z) = z1 + z2 = (−4x1 − 2x2 + 4 − λ + v1 ) +

+(−2x1 − 4x2 + 6 − 2λ + v2 ) = 10 − 6x1 − 6x2 − 3λ + v1 + v2 .

Составляем вспомогательную задачу ЛП:

F (z) = 10 − 6x1 − 6x2 − 3λ + v1 + v2 → min,

4x1 + 2x2 + λ − v1 + z1 = 4, 2x1 + 4x2 + 2λ − v2 + z2 = 6, x1 + 2x2 + w = 2,

x1, x2 , λ, v1, v2 , w, z1, z2 ≥ 0.

Решаем задачу симплекс-методом с учетом условий дополняющей нежесткости. В качестве базисных выберем перемен-

ные z1 , z2			и w . Таким образом, начальный базис Б0 = {z1, z2 , w}.
В результате приходим к табл. 3.1.																Таблица 3.1
					↓
	Базис		Своб.		x1				x2	λ		v1	v2		w		z1	z2
			член
→
		z1	4		4				2	1		−1	0		0		1	0	4/4=1
		z2	6		2			4		2		0	−1		0		0	1	6/2=3
		w	2		1			2		0		0	0		1		0	0	2/1=2
		F	10		6			6		3		−1	−1		0		0	0
																			ДБР0=
		Начальное				допустимое						базисное				решение
= (z1		= 4, z2 = 6, w = 2). ДБР0 не является оптимальным, посколь-

ку в строке целевой функции есть положительные коэффициенты

Fx1 = 6 , Fx2 = 6 , Fλ = 3.

Согласно условиям дополняющей нежесткости, в базис можно вводить x1, так как v1 = 0 , либо x2 , так как v2 = 0 , но нель-

									32
	зя вводить λ , так как w > 0 . Находим Б1 :
				Fx		> 0		→ x1 вводим в базис,
					1
		4		6			2
	min		= 1,		=	3,		= 2	= 1	→	z1 выводим из базиса.
		4		2			1

Таким образом, Б1 = {x1, z2 , w}. В результате приходим к

табл. 3.2.

Таблица 3.2

					↓
		Базис	Своб.	x	x	λ	v	v		w	z	z	2
			член	1	2		1	2			1
		x1	1	1	1/2	1/4	−1/4	0		0	1/4	0		2
		z2	4	0	3	3/2	1/2	−1		0	−1/2	1		4/3
→
		w	1	0	3/2	−1/4	1/4	0		1	−1/4	0		2/3
		F	4	0	3	3/2	1/2	−1		0	−3/2	0
		Получили		ДБР1 = (x1 = 1, z2 = 4, w = 1).						ДБР1 не является

оптимальным, поскольку в строке целевой функции есть положи-

тельные коэффициенты F

= 3 ,

F

= 3 и

F = 1 .

x2

λ

2

ν1

2

Согласно условиям дополняющей нежесткости, в базис

можно вводить x2 ,

так как v2 = 0 ,

но нельзя вводить λ, так как

w > 0 , и v1 , так как x1 > 0 . Находим Б2 :

Fx2 > 0

→ x2

вводим в базис,

1 2

4

1 2

2

2

→ w

min

= 2,

,

=

=

выводим из базиса.

3

3

3

3

1

Таким образом, Б2 = {x1, x2 , z2}. В результате приходим к табл. 3.3.

							33
						↓						Таблица 3.3
		Базис	Своб.	x	x	λ				v	v	w	z	z	2
			член	1	2				1		2		1
		x1	2/3	1	0	1/3				−1/3	0	−1/3	1/3	0			2
		x2	2/3	0	1	−1/6			1/6		0	2/3	−1/6	0
→
		z2	2	0	0	2				0	−1	−2	0	1			1
		F	2	0	0	2			0		−1	−2	−1	0

Получили	ДБР2		=	2	,	x2	=	2	,	z2	= 2		ДБР2 не явля-
		= x1		3				3				.

ется оптимальным, поскольку в строке целевой функции есть по-

ложительный коэффициент Fλ = 2 .

Согласно условиям дополняющей нежесткости, в базис

можно вводить λ, так как w = 0 . Находим Б3 :

3

Fλ > 0

→ λ вводим в базис,

2

2

→ z2

min

= 2,

=

1 = 1

выводим из базиса.

1

2

3

Таким образом, Б3 = {x1, x2 , λ} . В результате приходим к

табл. 3.4.

Таблица 3.4

Базис

Своб.

x

x

λ

v

v

w

z

z

2

член

1

2

1

2

1

x1

1/3

1

0

0

−1/3

1/6

0

1/3

−1/6

x2

5/6

0

1

0

1/6

−1/12

1/2

−1/6

1/12

34

Окончание табл. 3.4

λ	1	0		0		1		0		−1/2	−1	0	1/2
F	0	0		0		0		0		0	0	−1	−1
	Получили		ДБР3		= (x1 = 1 3,			x2	= 5 6,		λ = 1).	ДБР3	явля-

ется оптимальным решением.

Таким образом, вспомогательная задача ЛП решена. Поскольку min F(z) = 0, то оптимальное ДБР вспомога-

		z									x* задачи КП. Поэтому по-
тельной задачи определяет решение
лагаем		x* = (x* = 1 3, x*											5 6),
												=
						1				2
f * = f (x*) = 2			1				1	5			25		1		5		1
			9 + 2				3	6 + 2			36		− 4 3	− 6	6	= −4	6 .
Ответ: x	*	1	,	5			f	*	= −4		1	.
		=		6	,						6
		3

Задачи

1. Решить задачу квадратичного программирования

f (x) = 2x12 + 3x22 + 4x1x2 − 6x1 − 3x2 → min , x1 + x2 ≤ 1,

2x1 + 3x2 ≤ 4 ,

x1 ≥ 0, x2 ≥ 0.

2. Решить задачу квадратичного программирования

f (x) = x1 + 2x2 − x22 → max , 3x1 + 2x2 ≤ 6 ,

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

35

4. ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ (МИНИМИЗАЦИИ) УНИМОДАЛЬНЫХ ФУНКЦИЙ

Унимодальными называются функции, имеющие на заданном отрезке ∆ = [a, b] единственный экстремум. На практиче-

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

Пусть f(x) унимодальна на ∆, x1, x2 ∆, x1 < x2. Тогда, ес-

ли f (x ) ≤ f (x ) , то		x* ≤ x ; если же		f (x	) ≥ f (x	) , то x* ≥ x .
1	2		2	1	2	1
Таким образом, на основании вычисленных значений f(x)
можно указать отрезок ∆′ = [a′, b′], в котором заключена точка x ,
меньшей	длины,	чем	исходный	отрезок		∆ = [a, b], т.е.
L′ = b′ − a′ < L = b − a.		Говорят, что точка минимума x локализо-
вана в отрезке [a′, b′], при этом сам отрезок называют отрезком
локализации минимума.
На	практических		занятиях рассматриваются алгоритмы

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

При записи алгоритмов и решении задач используются следующие обозначения:

∆i = [ai ,bi ] и Li = bi − ai , i = 1,2,", − соответственно отрезок локализации и его длина после i вычислений значений f(x),

∆0 ≡ [a,b], L0 ≡ b − a;

N – количество вычислений значений f(x).

Исходными данными для решения задачи минимизации унимодальной функции являются исходный отрезок локализации

∆0 и N, результатами решения − итоговый отрезок локализации

∆N , а также оценки точки минимума x и величины минимума

f * .

36

4.1. ПАССИВНЫЙ МЕТОД ПОИСКА МИНИМУМА

Метод оптимизации называется пассивным, когда все точки xi , i = 1, N, вычислений характеристик задачи (в данном слу-

чае значений целевой функции) выбираются одновременно до начала вычислений.

Если N четное, т.е. N = 2l, l = 1,2,", то наилучшее (в смысле максимального уменьшения длины отрезка локализации)

размещение точек xi ,

i =

1, N

, получается разбиением их на рав-

ноотстоящие ε-пары, т.е.

x

2 j −1

= a +

b − a

j − ε ,

x

2 j

= a +

b − a

j + ε , j = 1, N 2,

(4.1)

N 2 +1

N 2 +1

2

2

где ε − некоторое малое положительное число.

При этом

b − a

ε

L0

+ ε .

LN =

+

=

N 2 +1

2

l +1

2

Если N нечетное,

т.е. N = 2l +1, l = 1,2,", то наилучшим

является равномерное распределение точек, т.е.

x

= a +

b − a

i,

i =

.

(4.2)

1, N

i

N +1

При этом

b − a

L0

LN

= 2

=

.

N +1

l +1

Нетрудно заметить, что использование нечетного числа точек при пассивном методе поиска неэффективно.

	После определения точек			xi , i =	1, N	, вычисляются значе-
ния	функции f (xi ) . Пусть		f (xk ) = min f (xi ).				Тогда, полагая
				i =1, N
x0 = a, xN +1 = b ,		определяется		итоговый		отрезок локализации
∆N	= [xk −1, xk +1] .	Точка xk	принимается			за	аппроксимацию

37

(оценку) точки минимума x , значение функции f (xk ) − за оцен-

ку f * = f (x*) , т.е.

x* xk , f * f (xk ).

Пример. Определить с помощью пассивного поиска ми-

нимум функции

f (x) = x + 1 ,

заданной на отрезке ∆ = [0,2]: а)

x

при N=6, ε=0,1; б) при N=7.

Решение.

а) N=6, ε

=0,1.

x2 j−1,

x2 j

Определяем пары точек

с помощью соотноше-

ния (4.1):

2 − 0

j − 0.1 = 0,5 j − 0,05,

x2 j−1

= 0 +

j =

1,3;

3 +1

2

x2 j

= 0 +

2 − 0

j +

0.1 =

0,5 j + 0,05,

j =

1,3.

3 +1

2

Результаты вычислений x и

f (x) заносим в табл. 4.1.

Таблица 4.1

Номер

1

2

3

4

5

6

отсчета

x

0,45

0,55

0,95

1,05

1,45

1,55

f (x)

2,67

2,37

2,0026

2,0024

2,14

2,20

Поскольку

f (x4 ) = min f (xi ) ,

то

полагаем

∆6=[x3, x5]=

i =1,6

=[0,95; 1,45], x x4

= 1,05,

f *

f (x4 ) = 2,0024.

Ответ: ∆6

= [0,95; 1,45] ,

x* 1,05,

f * 2,0024.

б) N=7.

Определяем xi помощью соотношения (4.2):

xi = 0 +

2 − 0

i = 0,25i,

i =

1,7.

7 +1

38

Результаты вычислений x и f (x) заносим в табл. 4.2. Таблица 4.2

	Номер	1				2	3			4			5	6	7
	отсчета
	x	0,25			0,5		0,75			1			1,25	1,5	1,75
	f (x)	4,25		2,50			2,08		2,00				2,05	2,17	2,32
	Поскольку					f (x4 ) = min f (xi ) ,						то полагаем ∆7=[x3, x5]=
							i =1,7
=[0,75, 1,25], x* x					4	=1,	f * f (x		4	) =	2 .
	Ответ: ∆7			= [0,75; 1,25], x* 1,								f * 2 .

4.2. АКТИВНЫЕ МЕТОДЫ ПОИСКА МИНИМУМА

Метод оптимизации называется активным, если точки xi ,

i = 1, N, вычислений характеристик задачи (в данном случае зна-

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

лизации после j итераций будет обозначаться ∆( j) = [a( j) , b( j ) ]. Если при этом произведено i вычислений значений f(x), то

∆( j) ≡ ∆i , a( j) ≡ ai , b ( j ) ≡ bi .

На практических занятиях рассматриваются такие активные методы поиска, как метод дихотомии, метод Фибоначчи и метод золотого сечения. Для каждого из этих методов на j-й,

j =1,2,…, итерации рассматривается пара точек x1( j ) и x2( j ) , при этом x1( j ) < x2( j ). Значения функции в этих точках будут обозначаться соответственно f1( j) и f2( j) .

39

Метод дихотомии (половинного деления)

В данном случае общее количество вычислений f(x) четное, т.е. N = 2l, l = 1,2,", на j-м шаге (j-й итерации) произво-

дится пара вычислений x( j ) и x( j ) , отстоящих на расстоянии ε / 2
	1	2
по обе стороны от	середины текущего			отрезка локализации
[a( j −1) ,b( j −1) ]. Если	f ( j) ≤	f ( j) , то отбрасывается часть отрезка,
	1	2	f ( j) > f ( j ) , то отбрасывается
расположенная справа от		x( j ) ; если
		2	1	2
часть отрезка, расположенная слева от x( j ) .
			1
Используются два условия окончания вычислений:
а) выполнение заданного количества вычислений N;
б) достижение заданной величины δ			уменьшения отрезка лока-
лизации.

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

1. Задаются N (либо δ) и ε, полагается j=1. 2. На j-й итерации вычисляются

x( j) = 1		(a( j −1) + b( j −1) ) − ε ,		x( j) = 1		(a( j −1) + b( j −1) ) + ε ,
1	2		2	2	2	2
		f ( j)	= f (x( j) ),	f ( j) = f (x( j) ).
		1	1	2		2
Если	f ( j)	≤ f ( j) , то	a( j ) = a( j −1) , b( j) = x( j) .
	1	2				2
Если	f ( j)	> f ( j) , то	a( j) = x( j) ,	b( j) = b( j −1) .
	1	2	1

3. Проверяется условие окончания вычислений:

а) j=N/2 либо б) L2 j ≤ δ .

L0

Если оно выполняется, то определяются итоговый отрезок локализации, оценки точки минимума x и величины минимума

f * = f (x*) , и вычисления завершаются.

Если условие не выполняется, то полагается j = j +1 и

40

осуществляется переход к п.2.

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

Пример. Определить методом дихотомии минимум функции f (x) = x4 − 6x2 +10 , заданной на отрезке ∆=[1,3], при N=8,

ε=0,1.

Решение.

В данном случае будут выполнены N/2=4 итерации. Результаты вычислений заносим в табл. 4.3.

Таблица 4.3

Номер	x1( j )	x2( j )	f1( j)	≤	f2( j)	a( j)	b( j)
итерации				>
0	—	—	—		—	1	3
1	1,95	2,05	1,644	<	2,446	1	2,05
2	1,475	1,575	1,680	>	1,270	1,475	2,05
3	1,713	1,813	1,004	<	1,082	1,475	1,813
4	1,594	1,694	1,211	>	1,017	1,594	1,813

Поскольку j=N/2=4, то вычисления завершаются.

Точка минимума локализована на отрезке ∆8 = [1,594; 1,813] . На данном отрезке исследованы 4 точки:

a(4)	= 1,594 → f (a(4) ) = 1, 211;
b(4)	= 1,813 → f (b(4) ) = 1,082;
				*	(3)	= 1,713, f	*		(3)	) = 1,004.
x2(4)				x	x1				f (x1
	=1,694 → f (x2(4) ) =1,017;
x(3)	=1,713	→ f (x(3) ) =1,004;
1		1
Ответ: ∆8		= [1,594; 1,813] , x* 1,713,				f * 1,004 .