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

z (w )= 1(+ 4w)2 + 2( + 5w)2 + 1(+ 4w)(2 + 5w);

dz =41+122w=0; w=- 0,326; dw

х1(1 )=1-4 × 0,326 =- 0,304; х2 =2 -5 ×0,326 =0,37; z (х1(1 ), х21( )) =0,117.

Таким образом, за один шаг функция z уменьшилась в 60 раз.

Шаг 2
	dz			=- 0,238;	dz			=0,436;
	dx1				dx2
				1				1

х1(2 )=- 0,304 -0,238w; х(22 )=0,37 + 0,436w; z (w )= -(0,304 -0,238w)2 + 0,37( + 0,436w)2 + +(-0,304 -0,238w)(0,37 + 0,436w);

dz =0,247 +0,2855w=0; w=- 0,865; dw

х1(2 )=- 0,304 +0,865 ×0,238=- 0,038; х(22 ) =0,37 -0,865 ×0,436 =- 0,008; z (х1(2 ), х22( ))=0,0018.

Функция z уменьшилась за 2 шаг в 3900 раз. Расстояние до точки минимума после двух шагов сократилось в

	(х1(0 ))2 +(х(20 ))2
										5			= 57,8 раза ,
							=
	(х1(	2 ))	2	+(х(22 ))	2				0,001504

градиент уменьшился в 64 раза. Этот пример показывает быструю сходимость метода наискорейшего спуска.

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

Z =F(x1, x2 ,..., xn )

при наличии m уравнений ограничений (m <n ):

Ф1 (x1, x2 ,..., xn )=0, ü

ï

Ф2 (x1, x2,..., xn )=0, ï

ý .

. . . . . . . . . . . . ï Фm (x1, x2,..., xn )=0.ïþ

(3.51)

(3.52)

33

,..., dz / dx

(n -m)

Произвольно выбираем m зависимых переменных, например x1, x2,..., xm и независимых, например xm+1, xm+2 ,..., xn . Первоначально задаются, ис-

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

dz / dxm+1 , dz / dxm+2 ,..., dz / dx n .

Если все эти производные равны или близки к нулю, то получено оптимальное решение. Если эти производные не равны нулю, то необходимо сделать шаг по антиградиенту, изменив все независимые переменные по формулам градиентного метода (3.44).

Для измененных значений независимых переменных находят новые значения частных производных dz / dx m+1 n и затем вновь изменяют независимые переменные и т.д. Расчет заканчивается тогда, когда абсолютные значения всех указанных частных производных станут меньше некоторой достаточно -ма лой величиныe. По полученным значениям независимых переменных, с помощью уравнений (3.52), определяют значения зависимых переменных, а затем значение минимизируемой функции Z.

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

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

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

3.5. Динамическое программирование

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

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

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

34

Пример 3.6. Требуется минимизировать нелинейную сепарабельную функцию многих переменных:

z =f1 (x1 )+f2 (x2 )+...+fn (xn )	(3.53)
при ограничении
x1 + x2 +...+ xn =X.	(3.54)
Первый шаг. Определяется и запоминается f1 (x1 )	в пределе изменения x1

от 0 до X.

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

z12 =f1 (x1 )+f2 (x2 )

при условии x1 + x2 =X12 , где может изменяться от 0 до X.

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

z12 =f1 (x1 )+f2 (X12 -x1 ).
При фиксированном значении X12 функция z12						зависит только от x1 . Ми-
нимальное значение		(x )+f		(X		)ù.
z	=min éf		2		-x
12мин	ë 1	1		12	1	û

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

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

x1 от 0 до X12 все-

гда можно найти минимальное значениеz12,

которое будет

являться функцией

X12 -z12мин (X12 ).

x1 и

x2 , которые также за-

Аналогично определяют оптимальные значения

висят от X12 : х1опт (X12 ), х2опт (X12 ).

Три последние зависимости запоминаются.

Третий шаг. Определяется минимум функции

z13 =f1 (x1 )+f2 (x2 )+ f3 (x3 )

при условии х1 + х2 + х3 =Х13

или Х12 + х3 =Х13 , причем X13

изменяется от 0 до

X.

Используя условия ограничения, получим

(X

)ù.

z

=min éz

(Х

)+f

3

-Х

13мин

ë 12мин

12

13

12

û

При фиксированном значении X13 функция z13

зависит только от X12 . При

изменении X12 от 0 до

X13

можно

найти z13мин (Х13 ) и, используя уравнения

ограничений, определить Х12опт (Х13 ), х1опт (Х13 ), х2опт (Х13 ), х3опт (Х13 ) . Следующие шаги аналогичны предыдущим.

На последнем шаге получаются значенияzмин (Х), х1опт (Х), х2опт (Х),..., что, очевидно, является решением поставленной задачи.

Как видно из изложенного, динамическое программирование связано с получением и хранением излишней информации, что является его недостатком. Запоминаемые в каждом шаге зависимости используются только в одной точке. По-

35

этому динамическое программирование эффективно лишь в задачах, в которых требуется многократное применение этого метода при многочисленных -изме нениях X.

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

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

4.Задания для контрольной работы

иметодические указания по их выполнению

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

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

		03-ЭППу-008				Задача № 2, вариант № 8
						Задача № 1,	вариант № 10
	Варианты заданий к задаче № 1								Таблица 1
№	Целевая		Балансовые						Граничные
варианта	функция		условия						условия
1	2		3						4
1	2х1 +3х2 + 2х3 + х4		х1 + х2 +3х3 +4х4 =9						хi ³0
			2х1 + х2 +5х3 +6х4 =13
2	х1 +4х2 +3х3		2х1 + х2 +4х3 =16						хi ³0
			х1 + 2х2 +5х3 =11
3	5х1 + х2 + 2х3 + х4		х1 + х2 +2х3 =7						хi ³0
			х1 +4х2 +5х3 +3х4 =13
4	2х1 +3х2 + х3 + х4		2х1 + х2 +2х4 =14						хi ³0
			х1 + х2 + х3 +2х4 =9
5	2х1 + 4х2 +2х3 +3х4		х1 + х2 +3х3 + 4х4 =11						хi ³0
			х1 +2х3 + 2х4 =6
6	3х1 + х2 + 2х3 + х4		х1 + х2 +2х3 +4х4 =6						хi ³0
			х1 +3х2 + 4х3 +10х4 =17

36

1										2																					3		4
7					7х1 + 2х2 +3х3 + х4																	х1 + х2 + х4 =8											хi ³0
																						3х1 + х2 +2х3 +3х4 =14
8					10х1 +12х2 + х3 + х4																	3х1 +6х2 +3х3 =27											хi ³0
																						5х1 +7х2 +2х3 +3х4 =39
9					2х1 + х2 +4х3 +5х4																	х1 +4х2 +6х3 +7х4 =14											хi ³0
																						2х1 + х2 +5х3 +7х4 =14
10					2х1 + 4х2 +3х3																	х1 + х2 +2х3 =8											хi ³0
																						3х1 + х2 +4х3 =18
													Варианты заданий к задаче № 2																				Таблица 2
№										Целевая																					Балансовые		Граничные
вари
ри-										функция																					условия		условия
анта
1		4х2	+4х х				2	+2х х					3	+3х				2	+2х		2	х		3			+2х2				2х1 +5х2 +7х3 =48		хi ³0
		1			1					1								2											3		6х1 + 4х2 +3х3 =24
2		7х2	+6х х				2	+4х х					3	+4х				2	+2х		2	х		3			+х2				х1 +4х2 +5х3 =16		хi ³0
		1			1					1								2											3		2х1 +6х2 +10х3 =28
3		9х2	+8х х				2	+4х х				3		+4х				2	+2х		2	х		3		+3х2					7х1 +5х2 + х3 =20		хi ³0
		1			1					1								2											3		х1 +6х2 +2х3 =15
4		11х2			+10х х				2	+6х х					3	+5х2				+4х			2		х		3	+ х2			х1 +8х2 +9х3 =49		хi ³0
		1				1					1								2										3		3х1 + 4х2 +5х3 =23
5		15х2			+12х х				2	+10х х							+7х			2 +6х					2		х	3	+2х	2	3х1 +7х2 +11х3 =51		хi ³0
		1				1							1			3				2										3	4х1 +12х2 +14х3 =64
6		7х2	+ х х			2	+ х2																								14х1 +5х2 =51		хi ³0
		1			1					2
7		х12 +2х1х2 + 5х22																													7х1 +8х2 =41		хi ³0
8		10х12 +2х1х2 + 3х22																													4х1 +5х2 =37		хi ³0
9		3х12 + 2х1х2 + 4х22																													7х1 + 4х2 =13		хi ³0
10		9х12 +3х1х2 + 8х22																													19х1 +21х2 =3		хi ³0

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

Рассмотрим систему линейных уравнений с тремя неизвестными х1, х2 , х3 .

37

а х + а х					2		+ а х			3		=b ,			ü
11	1	12					13					1			ï	(4.1)
а21х1		+ а22х2 + а23х3 =b2,ý
а х + а			32	х		2	+ а	33	х		3	=b	3	.	ï
31	1														þ
Если определитель системы (4.1)

			éa	a	a	ù
D =det	é ù	=	ê 11	12	13	ú
	ëaij û		êa21	a22	a23	ú
			ê	a32		ú
			ëa31		a33 û

не равен нулю, то она имеет единственное решение.

хк =

Dк

(к =1, 2,3)

(правило Крамера).

D

n

Здесь Dк =åAikbi (к =1,2,3) - определитель, получающийся из D при за-

i=1

мене элементов а1k, а2k, а3k . . .

k -го столбца соответствующими свободными чле-

нами b1,b2 ,... Aik - алгебраическое дополнение элемента аik

в определителе D .

Для нашего примера

D = а11 а22 а33 -а11 а23 а32 + а12 а23 а31 -а12 а21 а33 +а13 а21 а32 - а13 а22 а31 .

b1

a12

a13

D1 = det

b2

a22

a23

= b1 a22 a33 - b1 a23 a32 + b2 a 23 a31 -

b3

a32

a33

-b2 a21 a33 +b3 a21 a32 -b3 a22 a31.

а11

b1

a13

D2 = det

а21

b2

a23

= a11 b2 a33 + b1 a23 a31 + a21b3 a23 -

а31

b3

a33

-a31 b2 a13 -b3 a23 a11 -a21b1 a33 .

а11

a12

b1

D3 = det

а21

a22

b2

= a11 a22 b3

+ a21 a32 b1 + a12b2 a31 -

а31

a32

b3

-a31 a22 b1 - a32 b2 a11 -a21 a12 b3.

x =

D1

; x

2

=

D2

; x

3

=

D3

.

1

D

D

D

Для системы из двух уравнений

D = det

а11

а12

= a

11

a

22

- a a

21

, D = det

b1

а12

, D

2

= det

а11

b1

.

а21

а22

12

1

b2

а22

а21

b2

38

Литература

1.Электрические системы. Кибернетика электрических систем. Под.ред. Веникова В.А. – М.: “Высшая школа”, 1974.

2.Гамазин С.И., Черепанов В.В. Применение методов математического программирования при проектировании систем электроснабжения. – изд. Горьковского государственного университета, 1980.

3.Гамазин С.И., Черепанов В.В. Применение методов нелинейного и динамического программирования в задачах электроснабжения. – изд. Горьковского государственного университета, 1981.

Оглавление

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1. Формулировка общей задачи математического программирования . . . . . . 4

2. Линейное программирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1. Геометрическая интерпритация линейного программирования . . . . . . 6 2.2. Симплексный метод решения задач линейного программирования . . . 8 2.3. Примеры применения симплексного метода . . . . . . . . . . . . . . . . . . . . . . 11

3. Нелинейное программирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.1. Геометрическая интерпритация задачи . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2. Метод Лагранжа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3. Квадратичное программирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.4. Градиентный метод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.5. Динамическое программирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4. Задания для контрольной работы и методические указания по их выполнению . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

Оглавление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

39