Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Воронежский государственный университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

belousova_method_2

.pdf

Скачиваний:

Добавлен:

21.05.2015

Размер:

195.23 Кб

Скачать

☆

1 / 31 2 3 > Следующая >>>

Ф Е Д Е РАЛ Ь Н О Е АГ Е Н Т С Т В О П О О Б РАЗО В АН И Ю

В О РО Н Е Ж С К И Й Г О С У Д АРС Т В Е Н Н Ы Й У Н И В Е РС И Т Е Т

Методы оп тимизации. Часть 2

Практ и ку м

По с пеци ально с т и

010501 (010200) – П ри кладная мат емат и ка и и нф о рмат и ка

В о ро неж 2005

У т верждено нау чно -мет о ди чес ки м с о вет о м ф аку льт ет а П М М о т 14.06.2005, про т о ко л № 6.

Со с т ави т ели : Бело у с о ва Е.П .

К о с т ру б И.Д.

П ракт и ку м по дго т о влен на каф едре нели нейных ко лебани йф аку льт ет а П М М В о ро нежс ко го го с у дарс т венно го у ни верс и т ет а. Реко менду ет с я для с т у дент о в 3- го ку рс а дневно го о т делени я.

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

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

П РЕ Д В АРИ Т Е Л Ь Н Ы Е С В Е Д Е Н И Я

Рас с мо т ри м ф у нкци ю n

переменных

n ) , xзаданну,...,

ю fx(на неко т о ро м

мно жес т ве

про с т ранс т ва

Rn . Извес т но ,

чт о

ес ли

f (x)

ди ф ф еренци ру ема в

т о чке

n ), тxо в,...эт,о йMт x(о чке с у щес т ву ют

час т ные про и зво дные

∂

n )

,...,

fx(

,...,

1 ,i

∂xi

и нао бо ро т , ес ли ф у кнци я

n ) иxмеет,...,

часfx(т ные

про и зво дные по

вс ем

аргу мент ам

в неко т о ро й о крес т но с т и

т о чки

n ) , xпри,...чем, всx,еMэтx(и

час т ные про и зво дные непрерывны в с амо й т о чке

M0 , т о

у казанная ф у нкци я

ди ф ф еренци ру ема в т о чке M0 .

Г о во рят , чт о ф у нкци я

f (x)

и меет

т о чке

M0 ло кальный макс и му м (

ло кальныйми ни му м), ес ли найдет с я т акая δ-о крес т но с т ь т о чки

M0 , в пределах

ко т о ро й значени е

0 )

являетfM(

с я

наи бо льши м

(наи меньши м) с реди

вс ех

значени й f (x) эт о йф у нкци и .

Ес ли

ф у нкци я

n ) оxбладает,...,

вfx(т о чке

т,...ными,

x,M x(

n ) часx

про и зво дными перво го по рядка по

вс ем переменным

,и...,и меет

в эт о й

т о чке

ло кальный экс т рему м,

т о

вс е

час т ные

про и зво дные перво го по рядка

о бращают с я в т о чке M0

в ну ль, т .е.

∂f

= ,

∂f

(M =

∂f

(M= . 0

)

,...,

)

) (M

∂x1

∂x2

∂xn

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

МИ Н И МИ ЗАЦИ Я Ф У Н К ЦИ И N П Е РЕ МЕ Н Н Ы Х В ЗАД АЧЕ Б Е З О Г РАН И ЧЕ Н И Й .

К Л АС С И ЧЕ С К И Й МЕ Т О Д

	П у с т ь ес т ь задача	I(u) → inf,				(1)

		u Rn .				(2)
П у с т ь u* являет с я т о чко йло кально го			ми ни му ма ф у нкци и I : R n → R и ф у нкци я
I(u) являет с я ди ф ф еренци ру емо йв эт о йт о чке, т .е.				с у щес т ву ет	I ′(u* ) , т о гда
′	* = 0 , где) Iu(0 – ну лево йвект о р и з Rn .
	Для ф о рмули ро вки	до с т ат о чно го у с ло ви я		безу с ло вно го		экс т рему ма
введем по нят и е вт о ро й про и зво дно й ф у нкци и n переменных. П					у с т ь ес т ь т о чка
u0	и з про с т ранс т ва Rn .	Задади м	неко т о ро е при ращени е		h.	Т о гда, ес ли
при ращени е значени йф у нкци и мо жно запи с ат ь в ви де

+ h ),-

)w+ñh 0

x(á ñ0+

u( I

)

u(I

u(I ), h,

h, h) A(3)u 0

á =

где квадрат ные с ко бки о бо значают

с калярно е про и зведени е вект о ро в,

0 )-Au(

с и ммет ри чная мат ри ца по рядка n, w

) h,удо(uвлет во ряет

ус ло ви ю

) h,

lim

0 ,

→ 0

т о ф у нкци я I(u) являет с я дважды ди ф ф еренци ру емо й в т о чке u0 . О бо значи м

вт о ру ю про и зво дну ю через ′′

0 ) .Iu(Ес ли

про и зво дная с у щес т ву ет , т о

элемент ы

ее выпи с ывают с я с леду ющи м о бразо м

¶2

)

u(I¶2

)

u(I

¶2

)

ö u(I

¶u2

...

¶u ¶u

¢¢

...

0 ) =Iu(

u(I ¶2

...

¶2

)

u(I

¶2

)

÷ u(I

¶u

¶u2

¶u

Т еорем а : ес ли

т о чка u* R n

являет с я с т аци о нарно йт о чко йф у нкци и

I(u)

и в эт о й т о чке с у щес т ву ет

вт о рая про и зво дная

′′

* ) ,Iu(т о для т о го

чт о бы

была

т о чко й ло кально го

ми ни му ма

ф у нкци и

I(u)

до лжно

выпо лнят ьс я

неравенс т во

′′

. 0

) Iu(

(4)

′′

* ) Iявляетu(

Ес ли ж е

с я по ло жи т ельно о пределенно ймат ри цей, т .е.

′′

, 0

) Iu(

(5)

т о u*

- т о чка ло кально го ми ни му ма ф у нкци и

I(u).

Кри т

ери й С и львест

ра : для т о го, чт о б ы с и ммет ри чная мат ри ца

′′

* ) Iu(

была

по ло жи т ельно

о пределенно й нео бхо ди мо

до с т ат о чно ,

чт о бы вс е

ее

главные ми но ры были по ло жи т ельны.

Ес ли

т о чка u*

т о чка ми ни му ма ф у нкци и

I(u)

с у щес т ву ет

I ′′(u* ) ,

т о

выпо лняют с я у с ло ви я

′

′′

необх оди м ост

ь:

* =

, 0

)

u( I, 0

) Iu(

дост

а т

очност

ь:

ес ли

в неко т о ро й

т о чке

выпо лнены

у с ло ви я:

′′

> 0 , т)о u(u*I,- т0о чк) аu(Iми ни му ма ф у нкци и

I(u) .

П ример1. М и ни ми зи ро ват ь ф у нкци ю

2 → inf+.

− u

+u2=

−u

u u

u )

2 1

П о с чи т аем

первые про и зво дные по

каждо й переменно й и при равняем

и х к

ну лю

∂I

-0∂I

= =,

2- u 2u

= 0+. 1u +u2= -

¶u1

¶u2

Изс и с т емы у равнени й

-= 0 - 2

= 0 +-2 +u4 2u

найдем с т аци о нарну ю т о чку . О на б удет

и мет ь ви д

* =

)u. Со0, 1(с т ави м мат ри цу

и звт о рых про и зво дных:

¶2

) u(I

)

u(I

)

u(I

¶2

) u(I

¶u2

= 2,

= -1,

¶u2

= 2.

¶u ¶u

¶u

П о кри т ери ю

Си львес т ра

о на

б удет

по ло жи т ельно

о пределена, т ак как

по с ледо ват ельные главные ми но ры эт о ймат ри цы с о о т вет с т венно

равны

1 =

2 =

. 3

Т аки м о бразо м, т о чка u* являет с я т о чко йми ни му ма ф у нкци и

I(u) и

значени е в

эт о й т о чке равно

I(u) = −1.

О с т ает с я

про вери т ь,

како й ми ни му м

реали зу ет

т о чка u* -

ло кальный и ли

гло бальный. Для эт о го

рас с мо т ри м

про и зво льно е

при ращени е в т о чке u* , т .е. введем в рас с мо т рени е но ву ю т о чку u по

прави лу

+ =

) +h, =h 1(+ ) h

u, h u u(

и по с чи т аем в нейзначени е целево йф у нкци и

= h h+ h -1

+ h- =) h +1(

12 1( h

(

W+,

)

=u(I )

)

- +

где Ω - неко т о рая по ло жи т ельная вели чи на. О т с юда с леду ет , чт о

- эт о т о чка

гло бально го

ми ни му ма.

П ример2. М и ни ми зи ро ват ь ф у нкци ю

2 →=

.+− inf−

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

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

∂

) u(I

∂

) u(I

2u 2

= .+0 =6− 2u

∂u1

1 = = ,−0

∂u

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

ви д

1 =

2 =

. 3Значениu u, 2 е ф у нкци и в

эт о й т о чке

равно

* = . 5В ычи) u(Iс ли м значени я вт о рых про и зво дных ф у нкци и

I(u) в т о чке

по до зри т ельно йна экс т рему м. П о лу чаем

¶2

) u(I

¶2

)

u(I

¶2 )

u(I

¶2

) u(I

¶u12

= 2,

¶22

= -2.

¶u1¶u2

¶u2¶u1

Г лавный ми но р вт о ро го

по рядка

2 = −4. О т с юда с леду ет , чт о т о чка * =

u)3,

не являет с я т о чко йми ни му ма. П о дт верди м эт о . В ведем в рас с мо т рени е другу ю


т о чку	= + 1 + 2 )	иhпо 3,с чиhuт аем2(			в нейзначени е ми ни ми зи ру емо йф у нкци и .

О но равно						12 − 222 + . 5 h=
		2		2
1			2		1

u u ) u(I

h + ) h+(3 6

П о ло жи м				2	h=	h2.		Т о гда					2	< +* ) =. u(I− Ес5 ли h3 h				2	)=uh1 , т о
П о ло жи м					h=	h2.		Т о гда					2	< +* ) =. u(I− Ес5 ли h3 h					)=uh1 , т о
						1						1							2
	1					3													2
				2				2	>	+	*	) . u(IhО=т с юда5+ = с леду- ет , чт о				*
				2				2			*					*
	1(	)	u(I	1	5		)	h 1							u		- не		являет с я
4						4

то чко йло кально го ми ни му ма.

Пример3. М и ни ми зи ро ват ь ф у нкци ю

4	4		2	→ . + inf −= +) u u(	u u ) u(I
1	2	1	2	→ . + inf −= +) u u(	u u ) u(I

П о с чи т аем час т ные про и зво дные целево й ф у нкци и

при равняем и х к ну лю.

П о лу чи м

∂

) u(I

2 =

∂

+=)

) u(I

−

2 = . 0 +=) u − u( 2

∂u1

, 0

2u( 2 41u

∂u2

Н айдем о т с юда кри т и чес ки е т о чки . Их б удет т ри и о ни и меют

с леду ющи йви д:

= − − ). 1 , 1 (

u ), ,11(

u ),u 0, 0(

В ычи с ли м в эт и х т о чках вт о рые час т ные про и зво дные и с о с т ави м в каждо й и з

ни х мат ри цу Я ко би :

¶2

) u(I

¶2

) u(I

¶2

) u(I

¶2

) u(I

¶u12

1 -

;

12=

= -2;

¶u22

2 - . 2

u 12

¶u

¶u1¶u2

2¶u1

П о с чи т аем значени е

мат ри цы

Я ко би в

каждо й и з найденных т о чек.

О ни

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

æ- 2 - 2

÷,

) 0,(0

- 2

è- 2

у ко т о ро йпервыйглавныйми но р о т ри цат ельныйи равный-2, а вт о ро йглавный

ми но р – ну лево й. Рас с мо т ри м по ведени е целево йф у нкци и

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

т о чки

(0,0).

В о зьмем две други е т о чки

u = (h,−h) ,

u = (h,h)

по с чи т аем

в ни х

значени я ф у нкци и . О ни равны

2 4

< 0

h( =h2

−h4

) u(I

(I, 0

. −) 2

О т с юда с леду ет , чт о т о чка (0,0) не являет с я т о чко йэкс т рему ма. М ат ри ца Я ко би

в т о чке (1,1) и меет ви д

- 2

= ç

÷ .

),1(1

-10

è- 2

О ба

по с ледо ват ельных главных

ми но ра

по ло жи т ельны. Следо ват ельно ,

и с с леду емая т о чка являет с я т о чко й экс т рему ма.

В ычи с ли м

мат ри цу Я ко би в

по с леднейт о чке. О на равна

- 2

−

= ç

÷ .

) 1( , 1ç

- 2

О чеви дно , чт о т о чки (1,1) и (-1,-1)

являют с я т о чками

ло кально го

ми ни му ма.

П о с чи т аем в ни х значени е целево йф у нкци и . О но

равно

=h2=

*	2	− =. 2 )−= 2(+ 1 1 ) u(I

За да ни я для са м ост оят ельной ра бот ы

Н айт и вс е значени я парамет ра k, при ко т о рых т о чка (1,0) являет с я т о чко й экс т рему ма для ф ункци и

3	u	2	2	a − 3	- e u k ) u(I	+	u+ bu 2-		+-kcu+
	1	2		u ln+=( a k	- e u k ) u(I	+	u+ bu 2-		+-kcu+	1
	1			a			2	1	2	1
				a
при у с ло ви ях: а) а=-2,				b=2, с =8; б ) а=3/2, b=-1/2, c=-3/2.

ЗАД АЧА Н А У С Л О В Н Ы Й Э К С Т РЕ МУ М Ф У Н К ЦИ И

Н Е С К О Л Ь К И ХП Е РЕ МЕ Н Н Ы Х.

МЕ Т О Д МН О Ж

И Т Е Л Е Й Л АГ РАН Ж А

П редпо ло жи м,

чт о

по с т авлена задача о б

о т ыс кани и

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

I(u) при

у с ло ви и , чт о

u при ни мает значени я в неко т о ро м мно жес т ве

U Ì Rn ,

т .е.

I(u) → inf,

(6)

u Î U Ì Rn .

(7)

Здес ь мно жес т во

U мо жет

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

{

= }, s

,...=,

Î1 i, 0

) u(

g|(8)UR

= 1

где

n i

,...,

u( g

)gu(

Для решени я задачи (6)-(8) надо выпи с ат ь ф у нкци ю Л агранжа

+ ).

u(l g=

l) lu(I l

)(9)u,

,...,

ål

Т еорем а : пу с т ь

i=1

т о чка ло кально го

ми ни му ма в задаче (6)-(8)

и в

о крес т но с т и

эт о й т о чки

ф у нкци и

I(u) и

s являют,..., 1с яi непрерывно),gu(

ди ф ф еренци ру емыми , т о гда и меют

мес т о

с леду ющи е с о о т но шени я:

с у щес т ву ет

набо р ко нс т ант

*0 ,

*1,...,l*slт акиl х, чт о

¹| 0 ,|

å l*i

i=0

2) l*0

¢i

l*i

= 0 ,

)

Iu(

i=1

l*0 ¹ 0

для

т о го ,

чт о бы

до с т ат о чно ,

чт о бы

вект о ры

′

* )

былиu( gли нейно),...,

незавиu(

gс и),мыg u(.

s u

С П О С О Б РЕ Ш

Е Н И Я ЗАД АЧИ Н А У С Л О В Н Ы Й

Э К С Т РЕ МУ М

П о

и с хо дно йзадаче (6)-(8) нео бхо ди мо выпи с ат ь ф у нкци ю Л агранжа.

В ыпи с ат ь с и с т ему у равнени й.

			9
ì¶L			=l0	l)(u,	,
ï	¶u	0	=l0	l)(u,	,
ï	¶u		.		(10)
í	¶L		.		(10)
ï	¶u	0	=l0	l)(u,	,
î	¶u

3.	Рас с мо т рев	о т дельно	два	с лу чая:	λ*0 = 1(ес ли задача		на	ми ни му м),
	*0 λ−1=(ес ли задача на макс и му м) и				λ*0 = 0 , найт и вс е		с т аци о нарные
	т о чки задачи (6)-(8).
4.	П ро ведя	до по лни т ельные		и с с ледо вани я,		у с т ано ви т ь,		каки е	и з
	с т аци о нарных т о чек		являют с я т о чками			ло кально го	ми ни му ма		и
	ло кально го	макс и му ма для задачи (6)-(8) и ли до казат ь, чт о					решени я нет .

Для задачс о грани чени ями т и па равенс т в, мо жно не о бращат ь вни мани е на т и п экс т рему ма и , у беди вши с ь, чт о l0 ¹ 0 , по лагат ь l0 равным любо й

ко нс т ант е.

П ример1. М и ни ми зи ро ват ь ф у нкци ю

при о грани чени и

1 +

2 → inf

) u(I

12 +

22 =

.u1

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

данно м с лу чае о на и меет

ви д

2 − )1. +

λ +u(

)+ u3 λu4(=

)λ

П о с чи т аем час т ные

про и зво дные о т

эт о й

ф у нкци и

по

с о о т вет с т ву ющи м

переменным:

∂L

= λ +4;

λ +=3. λu 2

∂u1

∂u2

Со с т ави м с и с т ему ви да (10), при пи с ав в нее о грани чени е и зу с ло ви я задачи

= 0 4

2 =1 0 3λu + 2

. u1

П редпо ло жи м с начала, чт о λ0 = 0. Изс и с т емы с разу с леду ет , чт о

λ1 = 0 . Э т о

нас не у с т раи вает .

П о эт о му

б у дем

с чи т ат ь,

чт о

l0 =1.

Т о гда

с и с т ема

при о брет ает ви д

1 = 0

2 = 0+

.l3u

=u1

О т с юда

u1 = -

, u2 = -

. П о дс т авляя и х в т рет ье уравнени е с и с т емы,

2l1

нахо ди м

мно жи т ель Л агранжа и з у равнени я

=1.

О н

при ни мает

4l1

два значени я

l± = .

Ес ли

т о

т о чка

по до зри т ельная

на

экс т рему м и меет

ви д

uˆ 1* =

,uˆ *2 =

. Значени е ф у нкци и

в эт о й т о чке равно

I(uˆ

)=5. Ес ли

l1 =

, т о

,u2

.Значени= - е ф у нкци и

в эт о й т о чке

I(~*

равно

= − . 5Расu с)мо т ри м

по ведени е ф у нкци и

I(u)

вбли зи

т о чки

uˆ *.

П у с т ь u

(

+ h= ) при+ надлежи т

мно жес т ву U. П

о дс т ави м ее в наше

о грани чени е

(

h ) 2

2 =

. 1+hО+т)с юда+

легко

замет и т ь,

чт о

)

h4(2

+ +2 ).

-Пh=о дс(hт ави м

т о чку

целеву ю

ф у нкци ю.

П о лу чи м

1 2

(Iuˆ

5h£) (Iuˆ

+)).

h (h-

(

) u(I

(

3h )

)

1 1

Следо ват ельно , т о чка uˆ * до с т авляет наи бо льшее значени е ф у нкци и .

П ример2. М и ни ми зи ро ват ь ф у нкци ю

→= inf,+

) u(I

при о грани чени и

1 +

2 =

. 1

Со с т ави м ф у нкци ю Л агранжа для по с т авленно йзадачи . О на и меет

ви д

− ).

u4 λ +u3(

+ )

u λ =u(

Ч ас т ные про и зво дные с о о т вет с т венно

равны

∂L

;+ =32 l u

. + =42 l u

¶u1

¶u2

Со с т ави м с и с т ему у равнени йдля нахо ждени я с т аци о нарных т о чеки

парамет ро в

ì l

= 0

=l0l.

+ 42

1 +

2 =1

Ес ли

λ0 = 0 , т о

о чеви дно

чт о

λ1 = 0 . Э т о

решени е нас

не у с т раи вает .

о эт о му б у дем по лагат ь λ0 =1. В эт о м с лучае с и с т ема при о брет ает

ви д

1 / 31 2 3 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
19.03.2016510.54 Кб4A_slabo_2012-06-01.pdf
#
20.05.201571.68 Кб23Babaev.doc
#
21.05.201540.8 Mб1456BC400_RU_ECC_2005.pdf
#
21.05.201521.37 Mб203BC430_EN_Col62_FV_Part_A4_-_ABAP_Dictionary.pdf
#
19.03.201649.15 Кб10Beda_Dostopochtenny.doc
#
21.05.2015195.23 Кб12belousova_method_2.pdf
#
21.05.20151.05 Mб29besov.pdf
#
21.05.20156.89 Mб26Betekhtin.pdf
#
25.11.201999.33 Кб2Bilety_po_glazam.doc
#
21.05.2015879.83 Кб13bilet_1-50.pdf
#
21.05.2015789.95 Кб8block_ciphers.pdf