Пособие Методы оптимизации зоу

Для преобразования выражения (3.16) к виду, из которого следует положи-

тельность d2L , определим дифференциал первого порядка от функции балансового условия (3.12) в точке экстремума

dФ =С3 (dx +dx	2	+dx	3	+dx	4	)=0.	(3.17)
1

Возведя выражения (3.17) в квадрат, получил соотношение

dx2	+dx	2	+dx	2	+dx	2	=-2(dx dx	2	+dx dx	3	+
1		2		3		4	1		1		(3.18)

+dx1dx4 +dx2dx3 +dx2dx4 +dx3dx4 ),

всоответствии с которым второй дифференциал функции Лагранжа(3.16) можно преобразовать к виду

d2L =3(dx12 +dx22 +dx32 +dx42 )>0.

(3.19)

Второй дифференциал функции Лагранжа в точке экстремума положителен при любых dxi (i =1, 2,3, 4), не равных нулю одновременно. Достаточное условие

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

Рассмотрим обобщение задачи нелинейного программирования, когда балансовые условия заданы в виде неравенств:

Ф j (х1, х2,..., хn )³С j ( j=1, 2,..., m)	(3.20)
Путем введения дополнительной переменной (хn+ j ³0)	каждое балансовое

неравенство (3.20) можно преобразовать в эквивалентное балансовое уравнение

Ф j (х1, х2,..., хn ) + хn + j =С j .	(3.21)
Здесь переменная хn + j соответствует значению, на которое	не исчерпан

лимит в неравенстве (3.20).

После замены балансовых неравенств на эквивалентные балансовые равенства задача нелинейного программирования(3.4), (3.21) решается по изложенному выше методу Лагранжа с учетом того, что число переменных задачи увеличивается на число балансовых неравенств в исходной задаче. В итоге использование метода Лагранжа для случая, когда часть балансовых условий задана в виде неравенств, сводится к следующему алгоритму: вначале определяется оптимальная программа задачи, в которой учитываются только балансовые уравнения и - ис ключается балансовые неравенства. Для найденной оптимальной программы проверим, выполняются ли балансовые неравенства задачи. Если выполняются все неравенства - задача решена. Если часть балансовых неравенств не выполняется, производится еще одно решение задачи, в котором, помимо балансовых уравнений исходной задачи, учитываются балансовые уравнения, соответствующие исчерпанию лимита тех неравенств, которые не выполняются для найденной первоначально оптимальной программы, и опять исключаются те балансовые неравенства, которые выполняются для найденной первоначально оптимальной программы, для вновь полученной оптимальной программы проверяем выполнение исключенных балансовых неравенств. Если они выполняются - задача решена. Если нет - производится еще одно решение задачи, в балансовые условия которой

23

добавляются уравнения, соответствующие исчерпанию лимита тех балансовых неравенств, которые не выполняются для вновь найденной оптимальной - про граммы. За конечное число шагов всегда будет найдена оптимальная программа, для которой выполняются все балансовые неравенства.

Задача 3.2 Определить оптимальную программу, соответствующую минимуму целевой

функции

Z =х2	+ х	2	+ х	2	+ х	2	,	(3.22)
1		2		3		4

при выполнении балансовых условий

х х		х	3	х	4	-С4		=0,	ü
1	2								ï	(3.23)
х1	+ х2			£		С			ý
									ï
						2
									þ

и обычных граничных условий (хi ³0).

Балансовые условия задачи (3.23) содержат одно уравнение и одно неравенство. Вначале исключаем балансовое неравенство и определяем оптимальную программу полученной задачи. Поскольку такая задача сводится к задаче 3.1, воспользуемся найденным оптимальным решением(3.15). Балансовое неравенство (3.23) при этом решении не выполняется. Производим новое решение задачи при следующих балансовых условиях:

х х		х	3	х	4		-С4		=0,	ü
1	2									ï
х1	+ х2			=		С		.		ý
										ï
					2					þ

Функция Лагранжа задачи имеет вид:

L = х12 + х22 + х32 + х42 -l1 (х1х2х3х4 -С4 )-

-l		æ	х	+ х		-	С	ö.
	2	ç			2
			1				2	÷
		è						ø

(3.24)

(3.25)

Необходимые условия существования экстремума функции Лагранжа (3.25) определяются системой уравнений:

2х1 -l1х2х3х4 -l2 =0,ü

2х

2

-l х х

3

х

4

-l

2

=0,ï

1

1

ï

2х3 -l1х1х2х4 =0,

ï

2х4 -l1х1х2х3 =0,

ï

(3.26)

ý

х1х2х3х4 -С4 =0,

ï

ï

С

ï

х1

+ х2

-

=0.

ï

2

þ

24

Путем деления первого уравнения системы(3.26) на второе получаем соотношение:

2х1 -l2

=

х2

,

(3.27)

2х

2

-l

2

х

1

которое можно преобразовать к эквивалентному:

æ

х -

l2

ö2

=æ х

-

l2

ö2 .

(3.28)

ç

÷

2

1

4

ç

4

÷

è

ø

è

ø

Из выражения (3.28)

вытекает,

что

х1 =х2 . С

учетом этого

из последнего

уравнения системы (3.26) следует, что

х

0 = х0

=

С

.

Аналогично

путем деления

1

2

4

третьего уравнения системы (3.26) на четвертое получаем соотношение:

х3

=

х4

;

(3.29)

х4

х3

из которого следует, что х3 =х4. С учетом этого из предпоследнего уравнения си-

стемы (3.26) вытекает, что х30 =х04 =4С. Таким образом, оптимальная программа задачи (3.22), (3.23) имеет вид:

х0	=х	0	=	С	,	х0	= х0	=4С, Z0	=32	1	С2 .	(3.30)
1		2	4			3	4	мин	8

Оптимальная программа (3.30) значительно отличается от оптимальной программы (3.15) задачи 3.1.

3.3. Квадратичное программирование

Квадратичное программирование - наиболее разработанный частный случай нелинейного программирования. Отличительной чертой его задач является то, что целевая функция таких задач есть квадратичная форма переменных хi (i =1, 2,..., n )

(т.е. сумма всевозможных произведений рik xix k ), а балансовые условия - линейные равенства или неравенства. Наиболее общую задачу квадратичного программирования можно сформулировать следующим образом: определить оптимальную программу, соответствующую минимуму целевой функции

n	n
Z =å å pik xixk ,		(3.31)
i=1 k =1
при выполнении балансовых условий
n	( j=1,2,...,m)
å a jixi =C j		(3.32)
i>1
и граничных условий
хi ³0 (i =1, 2,..., n ).		(3.33)

Функцию Лагранжа задачи квадратичного программирования в соответствии с (3.7) можно представить в виде:

25

L =

n n

p

x

x

-

n

l

æ

n

a

x

-C

ö

(3.34)

å å

ik

k

å

ç

å

ji

i

÷ .

i

j ç

j ÷

i=1 k =1

j=1

è i=1

ø

Необходимые условия существования экстремума функции Лагранжа в за-

дачах квадратичного программирования			выражаются системой n +m линейных
уравнений:
n	m		(i =1, 2,..., n ),
2 å pik xk =å lja ji				(3.35)
k=1	j=1
	n	( j=1, 2,...,m).
	å a jixi =C j			(3.36)

i=1

Система уравнений (3.35), (3.36) однозначно определяет значения переменных (хi ) и неопределенных множителей Лагранжа (lj ), поэтому в задачах квад-

ратичного программирования экстремум (если он существует) всегда единствен. При расчетах без использования автоматических вычислительных средств решение системы (3.35), (3.36) рекомендуется проводить следующим образом: вначале разрешить систему n уравнений (3.35) относительно переменных xi , т.е. выразить их в виде линейной функции от неопределенных множителей Лагранжа:

m	(i =1, 2,..., n).
хi =å bijl j		(3.37)

j=1

Затем выражения (3.37) необходимо подставить в систему(3.36), в результате чего будет получена системаm уравнений относительно m неизвестных неопределенных множителей Лагранжа. Решая эту систему, можно найти значе-

ния неопределенных множителей Лагранжа(lj ), подставляя которые в (3.37),

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

Дифференциал второго порядка от функции Лагранжа в задачах квадратичного программирования является квадратичной формой от дифференциалов -пе ременных dxi :

n n
d2L =å å pikdxidx k .	(3.38)

i=1 k =1

Квадратичная форма, которая принимает только положительные значения при любых значениях dxi и dxk , не равных нулю одновременно, называется положительно определенной. Таким образом, достаточные условия существования минимума функции Лагранжа в задаче квадратичного программирования совпадают с условиями положительной определенности квадратичной формы, задаваемой коэффициентами целевой функции задачи.

26

é	р		р		р	...	р		ù
ê	11		12		13			1n	ú
ê	р21 р22 р23					...	р2n		ú	(3.39)
[Р ]=ê	р	31	р	32	р	...	р	3n	ú .
ê					33				ú
ê ... ... ...						... ...			ú
ê	рn1		рn 2		рn3	...			ú
ë							рnn û

Условия положительной определенности квадратичной формы выражающей через определители Сильвестра: все n определителей Сильвестра матрицы [Р] должны быть положительными, т.е.

det[p11

ép11 p12

det êêp21 p22

êp31 p32

ë

> 0;			det	ép11	p12	ù	> 0;
]				ê	p22	ú
				ëp21		û
p	ù						(3.40)
13	ú	> 0;	...det [P		]> 0.
p23	ú
p33	ú
	û

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

Ниже приведено несколько задач на поиск оптимальных программ квадратичного программирования.

Задача 3.3 Определить минимум целевой функции

Z =5х12 +4х1х2 + х22

при выполнении балансового уравнения

16х1 +7х2 =53

и обычных граничных условий (хi ³0).

Функция Лагранжа для задачи имеет вид:

L = 5х12 + 4х1х2 + х22 -l(16х1 +7х2 -53).

Необходимые условия существования экстремума функции Лагранжа определяются системой уравнений:

10х1 +4х2 -16l=0,ü

ï

4х1 +2х2 -7l =0,ý 16х1 +7х2 - 53 =0. ïþ

Из первых двух уравнений системы находим: х1 =l; х2 =1,5l. Подставляя эти значения в третье уравнение системы, находим значение неопределенного множителя Лагранжа l=2 . Таким образом, оптимальная программа задачи имеет вид:

х10 =2, х02 =3, Z0мин =53.

27

Проверим достаточные условия существования минимума задачи квадратичного программирования. Определители Сильвестра матрицы коэффициентов квадратичной формы

é5 2ù [Р ]= êë2 1úû

соответственно равны:

é5		2ù	=1> 0.
det[5 ]=5> 0; det ê	2	ú
ë		1û

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

Задача 3.4 Найти оптимальную программу, соответствующую минимуму целевой

функции

Z =5х12 +4х1х2 +2х1х3 +х22 +2х2х3 +2х32 ,

в области допустимых решений, определяемой балансовыми уравнениями

18х1 +10х2 +12х3 =124,ü

ý

8х1 + 4х2 + 4х3 =48 þ

и обычными граничными условиями (хi ³0).

Функция Лагранжа для этой задачи имеет вид:

L =5х12 +4х1х2 +2х1х3 +х22 +2х2х3 +2х32 -

-l1 (18х1 +10х2 +12х3 -124)-l2 (8х1 + 4х2 + 4х3 -48).

Необходимые условия существования экстремума функции Лагранжа -оп ределяются системой уравнений:

10х1 +4х2 +2х3 =18l1 +8l2 , ü
4х + 2х		2	+ 2х		3	=10l + 4l	2	,ï
1						1		ï
								ï
2х1 + 2х2 + 4х3 =12l1 + 4l2 ,ý
18х1 +10х2 +12х3 =124,								ï
								ï
8х + 4х	2	+4х		3	=48.			ï
1								þ

Из первых трех уравнений системы находим:

х1 =l1 +l2 , üï х2 =l1 -l2 , ý

х3 =2l1 +l2 .ïþ

Подставляя выражения в последние два уравнения системы, получаем систему уравнений относительно неопределенных множителей Лагранжа:

52l1 + 20l2 =124,ü

ý

20l1 + 8l2 =48, þ

28

из которой определяем l1 =2, l2 =1. Оптимальная программа задача имеет вид:

х10 =3, х02 =1, х30 =5, Z0мин =148.

Проверим выполнение достаточного условия существования минимума целевой функции. Определители Сильвестра от матрицы коэффициентов квадратичной формы

é5 2 1ù

[р ]= êê2 1 1úú

ê1 1 2ú

ë û

	соответственно равны					é5 2		1
	é5		2ù						ù
					=1> 0, det	ê2	1	1	ú	=2 > 0.
	det[5 ]=5> 0, det ê	2	1	ú
	ë			û		ê			ú
						ê	1		ú
						ë1		2û

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

3.4. Градиентный метод

Этот метод является численным методом поиска экстремума целевой функции Z многих переменных и используется для решения задач оптимизации, когда аналитическое решение невозможно или является весьма громоздким. Метод применим при любом виде функции Z и уравнений ограничений при условии, что Z дифференцируема.

Градиентом скалярной функции Z(х1, х2 ,..., хn ) называется вектор, который

по численному значению и направлению характеризует наибольшую скорость возрастания функции Z.

Формально градиент определяется следующим выражением:

		n	dz
	grad Z = Ñ Z =å ei			,	(3.41)
		i=1	dxi

где ei - единичный вектор, направленный вдоль оси хi .

Координатами градиента являются частные производные функции Z по переменным хi .

Скорость изменения функции в направлении градиента характеризуется модулем градиента

n

grad Z = å

i=1

æ	dz ö2
ç		÷ .	(3.42)
è dxi ø

Таким образом, направление градиента является направлением наискорейшего возрастания функции Z. Следовательно, противоположное направление (антиградиент) является направлением наискорейшего убывания функции Z. Это замечательное свойство градиента лежит в основе ряда итерационных методов ми-

29

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

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

О п т и м и з а ц и я б е з о г р а н и ч е н и й . Этот метод, как и все итерационные методы, предполагает выбор начального приближения – некоторой точки Z(0) с

координатами (х1(0), х(20),..., х(n0) ). Общих правил выбора точки Z(0) не существу-

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

Будем считать, что начальная точка Z(0) уже выбрана. Тогда, двигаясь из начальной точки в направлении антиградиента, т.е. давая приращения координатам (аргументам) функции Z по каждой оси хi , пропорциональные координатам

Ñ Z(0) в заданной точке Z(0) , мы переместимся в новую точку Z(1)			с координата-
ми (х1(0) +Dх1(1), х(20) + Dх(21), ..., х(n0) +Dх(n1) ).
Здесь Dхi =-w	dz(0)
		- приращение аргумента хi ;	(3.43)
	dxi

w- коэффициент пропорциональности.

Вточке Z(1) следует скорректировать направление дальнейшего движения,

т.е. найти снова координаты градиента Ñ Z(1) (частные производные dzdxi ), а за-

тем делать новый шаг в направление антиградиента -Ñ Z(1) и переместиться в новую точку Z(2) с координатами (х1(1) +Dх1(2), х(21) + Dх(22), ..., х(n1) +Dх(n2) ) и т.д.

Таким образом, каждые последующие значения аргументов функции Z определяются через предыдущие согласно формуле

хi(k +1) =хi(k )+w

dz

,

(3.44)

dz

dxi

k

где

- частная производная функции Z по аргументу хi

в k -й точке.

dxi

k

Коэффициент w можно менять от шага к шагу, однако он должен быть одинаковым для всех аргументов (координат) при выполнении очередного шага.

Шаг изменения аргументов принято оценивать параметром h , называемым длиной шага, или шагом градиентного метода

n	2) .
h = å (Dxi		(3.45)
i=1

30

Процедура поиска минимума функции Z, будет выглядеть следующим обра-

зом:

1) задается начальная точка Z(0) с координатами (х1(0), х(20),..., х(n0) ) в допу-

стимой области изменения аргументов;

2) находится градиент функции Z, т.е. его координаты dz / dxi z(0) в точке

Z(0) ;

3) определяются приращения аргументов функцииZ, пропорциональные координатам градиента:

Dх(i 0 )=-w dz / z(0 ); dxi

4) вычисляются новые значения аргументов (координаты точки Z(1) ):

х(i1) = хi(0) +Dхi(0) , i =1,..., n.

Данная процедура выполняется до тех пор, пока не выполнится условие

grad Z z(k <) e или	Z(k +1) -Z(k)	< d,	(3.46)
	Z(k +1)

где e и d - заданные числа, близкие к нулю, характеризующие допустимую погрешность решения задачи.

В процессе расчета h может оставаться одним и тем же на каждом шаге, либо изменяться. Существуют различные способы выбора h . Рассмотрим наиболее употребительные на практике способы.

1. w=const на протяжении всего расчета. В этом случае величина шага определяется по формуле

h

æ n

Dx

(k )ö2

æ n

dz

ö2

grad Z

.

=

ç

÷ =

ç

÷

= w

(3.47)

k

çå

i

÷

çå

dxi

÷

k

è i=1

ø

è i=1

k ø

Шаг h будет уменьшаться по мере приближения к точке экстремума, .к. модуль градиента уменьшается (в точке экстремума grad Z =0 ). Это обстоятельство увеличивает необходимое число шагов, т.е. замедляет скорость приближения

кэкстремуму, увеличивая в конечном итоге время расчета.

2.Шаг постоянный. h =const . Тогда коэффициент w определяется на каж-

дом шаге по формуле

wk =			h			.	(3.48)
			grad Z		k

В этом случае движение к точке экстремума происходит с постоянной скоростью, что уменьшает время расчета по сравнению с первым случаем. Однако, если выбрать шаг достаточно большим, то можно “проскочить” точку экстремума.

31

3. w=var и h = var , т.е. величина шага меняется и его целесообразно уменьшать по мере приближения к точке экстремума. Если h известно, то w определяется по формуле (3.48). В этом случае можно выбрать w таким образом, чтобы в данном направлении функцияZ изменялась бы на максимально возможную величину.

Для этого представим Z на каждом шаге функцией одного аргумента w согласно (3.44)

æ

dz

dz

dz

ö

Z =f ç x(k )+w

, x(k )+w

,..., x(k )+w

÷.

(3.49)

ç

1

dx1

2

dx2

n

dxk

÷

è

k

k

k ø

Дифференцируя Z по w, найдем

df

= j(w )

и приравняем его к нулю

dw

j(w) = 0.

(3.50)

Уравнение (3.50)

позволяет найти

значение w, доставляющее функции

f (w) максимум.

Такое определение w производится на каждом шаге,

и новые значения ар-

гументов функции Z определяются по формуле (3.44).

В этом

случае

градиентный

метод называется

методом

наискорейшего

спуска, т.к. очень быстро приводит к определению экстремума функции Z.

Пример 3.5 Найдем минимум функции

z =х12 + х22 +х1х2 .

Очевидно, этот минимум расположен в точке х1 =0, х2 =0 . Рассмотрим работу метода наискорейшего спуска.

Шаг 1

х1(0) =1; х(20) =2; z(х1(0), х(20) )=7;

dz

=

2х + х

2

;

dz

=2х

2

+ х ;

dx1

1

dx2

1

dz

=4;

dz

=5;

dx1

dx2

0

0

х1(1 )=1+ 4w; х(21 )=2 + 5w;

32