Методы оптимизации. Часть 2: Практикум по специальности ''Прикладная математика и информатика''

1

Ф Е Д Е Р АЛ Ь Н О Е АГ Е Н Т С Т В О П О О Б Р АЗО В АН И Ю В О Р О Н Е Ж С К И Й Г О С У Д АР С Т В Е Н Н Ы Й У Н И В Е РС И Т Е Т

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

П ракт и ку м

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

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

В о р о неж 2005

2

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

Со с т ави т ели : Бело у с о ва Е.П . К о с т ру б И.Д.

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

3

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

4

П Р Е Д В АР И Т Е Л Ь Н Ы Е С В Е Д Е Н И Я Рас с мо т ри м ф у нкци ю n переменных f ( x 1 ,..., x n ) , заданну ю на неко т о р о м мно ж ес т ве про с т ранс т ва R n . Извес т но , что ес ли f ( x ) ди ф ф еренци р у ема в т о чке M ( x1 ,..., x n ) , т о в эт о й т о чке с у щес т ву ют час т ные про и зво дные ∂f ( x 1 ,..., x n ) , i = 1,..., n ∂x i и нао б о ро т , ес ли ф у кнци я f ( x1 ,..., x n ) и меет час т ные про и зво дные по вс ем аргумент ам в неко т о ро й о крес т но с т и т о чки M 0 ( x10 , x 02 ,..., x 0n ) , пр и чем вс е эт и час т ные про и зво дные непр ерывны в с амо й т о чке M 0 , т о у казанная ф у нкци я ди ф ф ер енци р у ема в т о чке M 0 . Г о во рят , что ф у нкци я f ( x ) и меет в т о чке M 0 ло кальный макс и му м ( ло кальный ми ни му м), ес ли найдет с я т акая δ -о крес т но с т ь т о чки M 0 , в пр еделах ко т о ро й значени е f ( M 0 ) являет с я наи б о льши м (наи меньши м) с р еди вс ех значени й f ( x ) эт о й ф у нкци и . Ес ли ф у нкци я f ( x 1 ,..., x n ) о б ладает в т о чке M 0 ( x10 , x 02 ,..., x 0n ) час т ными про и зво дными перво го по р ядка по вс ем переменным x1 ,..., x n и и меет в эт о й т о чке ло кальный экс т р ему м, т о вс е час т ные про и зво дные пер во го по рядка о б ращают с я в т о чке M 0 в ну ль, т .е. ∂f ∂f ∂f ( M 0 ) = 0, (M 0 ) = 0,..., ( M 0 ) = 0. ∂x n ∂x 1 ∂x 2 Т о чки , в ко т о рых о б ращают с я в ну ль вс е час т ные про и зво дные пер во го по р ядка ф у нкци и f ( x ) , называют с я с т аци о нарными т о чками эт о й ф у нкци и .

МИ Н И МИ ЗАЦИ Я Ф У Н К ЦИ И N П Е Р Е МЕ Н Н Ы Х В ЗАД АЧ Е Б Е З О Г Р АН И Ч Е Н И Й . К Л АС С И Ч Е С К И Й МЕ Т О Д П у с т ь ес т ь задача

I(u ) → inf,

(1)

u∈R . (2) n П у с т ь u * являет с я т о чко й ло кально го ми ни му ма ф у нкци и I : R → R и ф у нкци я I(u ) являет с я ди ф ф еренци р у емо й в эт о й т о чке, т .е. с у щес т ву ет I ′(u* ) , т о гда n

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

5

1 I(u 0 + h ) − I( u 0 ) = 〈 I′(u 0 ), h 〉 + 〈 A(u 0 ) h, h 〉 + ω( x 0 , h ), (3) 2 где квадр ат ные с ко б ки о б о значают с калярно е про и зведени е вект о ро в, A ( u 0 ) с и ммет ри чная мат ри ца по рядка n, ω(u 0 , h ) у до влет во ряет у с ло ви ю ω( u 0 , h ) lim = 0, h →0 h т о ф у нкци я I(u ) являет с я дваж ды ди ф ф еренци р у емо й в т о чке u 0 . О б о значи м вт о р у ю про и зво дну ю чер ез I′′(u 0 ) . Ес ли про и зво дная с у щес т ву ет , т о элемент ы ее выпи с ывают с я с леду ющи м о б р азо м  ∂ 2 I ( u 0 ) ∂ 2 I( u 0 ) ∂ 2 I( u 0 )    ... ∂u1∂u 2 ∂u1∂u n   ∂u12 I′′(u 0 ) =  ... ... ... .  ∂ 2 I( u ) ∂ 2 I( u ) ∂ 2 I( u )  0 0 0   2  ∂u n ∂u1  ∂u n ∂u 2 ∂ u n   n Т еорем а : ес ли т о чка u * ∈ R являет с я с т аци о нар но й т о чко й ф у нкци и I(u ) и в эт о й т о чке с у щес т ву ет вт о рая про и зво дная I′′(u * ) , т о для т о го что б ы u * б ыла т о чко й ло кально го ми ни му ма ф у нкци и I(u ) до лж но выпо лнят ьс я неравенс т во I′′(u * ) ≥ 0. (4) Ес ли ж е I′′(u * ) являет с я по ло ж и т ельно о пределенно й мат ри цей, т .е. I′′(u * ) > 0, (5) т о u * - т о чка ло кально го ми ни му ма ф у нкци и I(u ). К ри т ери й С и львест ра : для т о го, что б ы с и ммет р и чная мат ри ца I′′(u * ) б ыла по ло ж и т ельно о пределенно й нео б хо ди мо и до с т ат о чно , что б ы вс е ее главные ми но р ы б ыли по ло ж и т ельны. Ес ли т о чка u * - т о чка ми ни му ма ф у нкци и I(u ) и с у щес т ву ет I ′′(u* ) , т о выпо лняют с я у с ло ви я необх оди м ост ь: I′( u * ) = 0, I′′( u * ) ≥ 0, дост а т очност ь: ес ли в неко т о ро й т о чке u * выпо лнены у с ло ви я: I(u * ) = 0, I′′( u * ) > 0 , т о u * - т о чка ми ни му ма ф у нкци и I(u ) . П ример 1. М и ни ми зи ро ват ь ф у нкци ю I(u ) = u 12 − u1u 2 + u 22 − 2u 1 + u 2 → inf . П о с чи т аем первые про и зво дные по каж до й переменно й и при равняем и х к ну лю ∂I ∂I = 2u1 − u 2 − 2 = 0, = − u 1 + 2u 2 + 1 = 0 . ∂u1 ∂u 2

6

Из с и с т емы у равнени й  2u 1 − u 2 − 2 = 0  − 2 u 1 + 4 u 2 + 2 = 0 найдем с т аци о нарну ю т о чку . О на б у дет и мет ь ви д u * = (1,0). Со с т ави м мат ри цу и з вт о рых про и зво дных: ∂ 2 I( u ) ∂ 2 I( u ) ∂ 2 I( u ) ∂ 2 I( u ) = 2, = 2. = −1, = −1, ∂u1∂u 2 ∂u 2 ∂u1 ∂u12 ∂u 22 П о кр и т ери ю Си львес т р а о на б у дет по ло ж и т ельно о пределена, т ак как по с ледо ват ельные главные ми но ры эт о й мат ри цы с о о т вет с т венно равны ∆1 = 2, ∆ 2 = 3. Т аки м о б разо м, т о чка u * являет с я т о чко й ми ни му ма ф у нкци и I(u ) и значени е в эт о й т о чке равно I(u ) = −1. О с т ает с я про вер и т ь, како й ми ни му м р еали зу ет т о чка u * - ло кальный и ли гло б альный. Для эт о го р ас с мо т ри м пр о и зво льно е при ращени е в т о чке u * , т .е. введем в рас с мо т р ени е но ву ю т о чку u по прави лу u = (u * + h 1 , u * + h 2 ) = (1 + h 1 , h 2 ) и по с чи т аем в ней значени е целево й ф у нкци и I(u ) = (1 + h1 ) 2 − (1 + h1 )h 2 + h 22 − 2(1 + h1 ) + h 2 = −1 + h12 − h1h 2 + h 22 =

h2 h + ( 2 ) 2 ) = I( u * ) + Ω, h1 h1 где Ω - неко т о рая по ло ж и т ельная вели чи на. О т с юда с леду ет , что u * - эт о т о чка гло б ально го ми ни му ма. − 1 + h12 (1 −

П ример 2. М и ни ми зи ро ват ь ф у нкци ю I(u ) = u 12 − u 22 − 4u 1 + 6u 2 → inf . П о с чи т аем час т ные про и зво дные пер во го по рядка и при равняем и х кну лю ∂I(u ) ∂I(u ) = −2 u 2 + 6 = 0 . = 2u 1 − 4 = 0, ∂u 1 ∂u 2 Ст аци о нарная т о чка и меет ви д u1 = 2, u 2 = 3. Значени е ф у нкци и в эт о й т о чке равно I(u * ) = 5. В ычи с ли м значени я вт о рых про и зво дных ф у нкци и I(u ) в т о чке по до зри т ельно й на экс т рему м. П о лу чаем ∂ 2 I( u ) ∂ 2 I( u ) ∂ 2 I ( u ) ∂ 2 I( u ) = 2 , = = 0 , = −2. ∂u1∂u 2 ∂u 2 ∂u1 ∂u12 ∂ 22 Г лавный ми но р вт о р о го по р ядка ∆ 2 = −4. О т с юда с леду ет , что т о чка u * = ( 2,3) не являет с я т о чко й ми ни му ма. П о дт верди м эт о . В ведем в рас с мо т р ени е др у гу ю т о чку u = (2 + h 1 ,3 + h 2 ) и по с чи т аем в ней значени е ми ни ми зи р у емо й ф у нкци и . О но равно I( u ) = ( 2 + h1 ) 2 − (3 + h 2 ) 2 − 4( 2 + h1 ) + 6(3 + h 2 ) = h12 − h 22 + 5.

7

П о ло ж и м

h 2 = 2h 1 .

Т о гда

I( u ) = −3h 12 + 5 < I( u * ) .

Ес ли

1 3 I( u ) = (1 − ) h12 + 5 = h12 + 5 > I(u * ) . О т с юда с леду ет , что 4 4 т о чко й ло кально го ми ни му ма.

h2 =

h1 , 2

то

u * - не являет с я

П ример 3. М и ни ми зи ро ват ь ф у нкци ю I(u ) = u 14 + u 42 − ( u1 + u 2 ) 2 → inf . П о с чи т аем час т ные про и зво дные целево й ф у нкци и и при р авняем и х к ну лю. П о лу чи м ∂I(u ) ∂I(u ) = 4u 13 − 2( u 1 + u 2 ) = 0, = 4u 32 − 2(u 1 + u 2 ) = 0. ∂u 1 ∂u 2 Н айдем о т с юда кр и т и чес ки е т о чки . Их б у дет т ри и о ни и меют с леду ющи й ви д: u 1 = (0,0), u 2 = (1,1), u 3 = ( −1,−1). В ычи с ли м в эт и х т о чках вт о рые час т ные про и зво дные и с о с т ави м в каж до й и з ни х мат р и цу Я ко б и : ∂ 2 I( u ) ∂ 2 I ( u ) ∂ 2 I( u ) ∂ 2 I( u ) 2 = − = 12 u 2 ; = − = 12u 22 − 2. 2 ; 1 2 2 ∂u1∂u 2 ∂u 2 ∂u1 ∂u1 ∂u 2 П о с чи т аем значени е мат ри цы Я ко б и в каж до й и з найденных т о чек. О ни с о о т вет с т венно равны  − 2 − 2  , A ( 0, 0) =   − 2 − 2 у ко т о ро й первый главный ми но р о т ри цат ельный и р авный -2, а вт о ро й главный ми но р – ну лево й. Рас с мо т ри м по ведени е целево й ф у нкци и в о крес т но с т и т о чки (0,0). В о зьмем две др у ги е т о чки u = (h ,−h ) , ~ u = (h , h ) и по с чи т аем в ни х значени я ф у нкци и . О ни равны I( u ) = 2h 4 ≥ 0, I( ~ u ) = 2 h 4 − 4 h 2 = 2 h 2 ( h 2 − 2) < 0 . О т с юда с леду ет , что т о чка (0,0) не являет с я т о чко й экс т рему ма. М ат ри ца Я ко б и в т о чке (1,1) и меет ви д  10 − 2   . A (1,1) =   − 2 − 10  О б а по с ледо ват ельных главных ми но ра по ло ж и т ельны. Следо ват ельно , и с с леду емая т о чка являет с я т о чко й экс т рему ма. В ычи с ли м мат ри цу Я ко б и в по с ледней т о чке. О на р авна  10 − 2   . A ( −1, −1) =   − 2 10  О чеви дно , что т о чки (1,1) и (-1,-1) являют с я т о чками ло кально го ми ни му ма. П о с чи т аем в ни х значени е целево й ф у нкци и . О но р авно I ( u * ) = 1 + 1 − ( 2 2 ) = −2 .

8

За да ни я для са м ост оят ельной ра бот ы Н айт и вс е значени я парамет ра k, пр и ко т о рых т о чка (1,0) являет с я т о чко й экс т р ему ма для ф у нкци и a −3 I(u ) = k 3 u1e u 2 − k 2 a ln(u1 + u 2 ) + ((a + b − 1)k − b) u1 + kcu 2 + 2bu1u 2 a при у с ло ви ях: а) а=-2, b=2, с =8; б ) а=3/2, b=-1/2, c=-3/2.

ЗАД АЧ А Н А У С Л О В Н Ы Й Э К С Т Р Е МУ М Ф У Н К ЦИ И Н Е С К О Л Ь К И ХП Е Р Е МЕ Н Н Ы Х. МЕ Т О Д МН О Ж И Т Е Л Е Й Л АГ Р АН Ж А П редпо ло ж и м, что по с т авлена задача о б о т ыс кани и ми ни му ма ф у нкци и I(u) при у с ло ви и , что u при ни мает значени я в неко т о ро м мно ж ес т ве U ⊂ R n , т .е. I(u ) → inf, (6) u ∈U ⊂ Rn. Здес ь мно ж ес т во U мо ж ет задават ьс я р азли чными с по с о б ами . Н апри мер, U = u ∈ R n | g i (u ) = 0, i = 1,..., s , где g i ( u ) = g i (u 1 ,..., u n ), i = 1,..., s. Для р ешени я задачи (6)-(8) надо выпи с ат ь ф у нкци ю Л агранж а

{

}

s

L(λ 0 , λ1 ,..., λ n , u ) = λ 0 I(u ) + ∑ λ i g i (u ).

(7) (8)

(9)

i =1

Т еорем а : пу с т ь u * - т о чка ло кально го ми ни му ма в задаче (6)-(8) и в о крес т но с т и эт о й т о чки ф у нкци и I(u) и g i ( u ), i = 1,..., s являют с я непрер ывно ди ф ф ер енци р у емыми , т о гда и меют мес т о с леду ющи е с о о т но шени я: 1) с у щес т ву ет наб о р ко нс т ант λ*0 , λ*1 ,..., λ*s т аки х, что s

∑ | λ i |≠ 0 , *

i =0

2)

λ*0 I′(u * )

+

s

* ∑ g ′i ( u * )λ i i =1

= 0,

3) для т о го, что б ы λ*0 ≠ 0 до с т ат о чно , g 1′ u (u * ), g ′2 u (u * ),..., g′s u ( u * ) б ыли ли нейно незави с и мы.

что б ы

вект о ры

С П О С О Б Р Е Ш Е Н И Я ЗАД АЧ И Н А У С Л О В Н Ы Й Э К С Т Р Е МУ М 1. П о и с хо дно й задаче (6)-(8) нео б хо ди мо выпи с ат ь ф у нкци ю Л агранж а. 2. В ыпи с ат ь с и с т ему у р авнени й.

9

3. Рас с мо т р ев о т дельно

 ∂L  ∂u (λ 0 , λ, u ) = 0 . (10)  ∂L  ( λ 0 , λ, u ) = 0  ∂u два с лу чая: λ*0 = 1 (ес ли задача на ми ни му м),

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

Для задачс о грани чени ями т и па равенс т в, мо ж но не о б р ащат ь вни мани е на т и п экс т рему ма и , у б еди вши с ь, что λ 0 ≠ 0 , по лагат ь λ 0 равным люб о й ко нс т ант е. П ример 1. М и ни ми зи ро ват ь ф у нкци ю I(u ) = 4u 1 + 3u 2 → inf при о грани чени и u 12 + u 22 = 1. Со с т ави м ф у нкци ю Л агранж а. В данно м с лу чае о на и меет ви д L(λ 0 , λ1 , u1 , u 2 ) = λ 0 (4u1 + 3u 2 ) + λ1 ( u12 + u 22 − 1) . П о с чи т аем час т ные про и зво дные о т эт о й ф у нкци и по с о о т вет с т ву ющи м переменным: ∂L ∂L = 3λ 0 + 2λ1u 2 . = 4λ 0 + 2λ1u 1 ; ∂u 2 ∂u 1 Со с т ави м с и с т ему ви да (10), пр и пи с ав в нее о грани чени е и з у с ло ви я задачи  4λ 0 + 2λ1u1 = 0  3λ 0 + 2λ1u 2 = 0  u 2 + u 2 = 1. 2  1 П р едпо ло ж и м с начала, что λ 0 = 0. Из с и с т емы с разу с леду ет , что λ1 = 0 . Э т о нас не у с т раи вает . П о эт о му б у дем с чи т ат ь, что λ 0 = 1 . Т о гда с и с т ема при о б р ет ает ви д  4 + 2λ1u1 = 0  3 + 2λ1u 2 = 0 .  u2 + u2 =1 2  1

10

2 3 , u2 = − . П о дс т авляя и х в т рет ье у р авнени е с и с т емы, λ1 2λ1 4 9 нахо ди м мно ж и т ель Л агранж а и з у равнени я 2 + 2 = 1. О н при ни мает λ1 4λ1 5 5 два значени я λ1 = ± . Ес ли λ1 = − , т о т о чка по до зри т ельная на 2 2 4 3 экс т рему м и меет ви д uˆ 1* = , uˆ *2 = . Значени е ф у нкци и в эт о й т о чке равно 5 5 5 4 * 3 u1* = − , ~ u 2 = − .Значени е ф у нкци и в эт о й т о чке I(uˆ * )=5. Ес ли λ1 = , т о ~ 2 5 5 * ~ р авно I( u ) = −5. Рас с мо т р и м по ведени е ф у нкци и I(u) вб ли зи т о чки uˆ * . 4 3 П у с т ь u = ( + h1 , + h 2 ) при надлеж и т мно ж ес т ву U. П о дс т ави м ее в наше 5 5 4 3 о грани чени е ( + h1 ) 2 + ( + h 2 ) 2 = 1. О т с юда легко замет и т ь, что 5 5 5 ( 4h1 + 3h 2 ) = − ( h 12 + h 22 ). П о дс т ави м т о чку u в целеву ю ф у нкци ю. 2 П о лу чи м 4 3 5 I(u ) = 4( + h1 ) + 3( + h 2 ) = 5 + 4h1 + 3h 2 = I(uˆ * ) − ( h12 + h 22 ) ≤ I(uˆ * ). 5 5 2 * Следо ват ельно , т о чка uˆ до с т авляет наи б о льшее значени е ф у нкци и .

О т с юда

u1 = −

П ример 2. М и ни ми зи ро ват ь ф у нкци ю I(u ) = u 12 + u 22 → inf, при о грани чени и 3u 1 + 4u 2 = 1. Со с т ави м ф у нкци ю Л агранж а для по с т авленно й задачи . О на и меет ви д L(λ 0 , λ1 , u1 , u 2 ) = λ 0 ( u12 + u 22 ) + λ1 (3u1 + 4u 2 − 1). Ч ас т ные про и зво дные с о о т вет с т венно равны ∂L ∂L = 2λ 0 u1 + 3λ1 ; = 2λ 0 u 2 + 4λ1. ∂u1 ∂u 2 Со с т ави м с и с т ему у р авнени й для нахо ж дени я с т аци о нар ных т о чеки парамет ро в  2λ 0 u1 + 3λ1 = 0   2λ 0 u 2 + 4λ 1 = 0 .  3u + 4u = 1 1 2  Ес ли λ 0 = 0 , т о о чеви дно что λ1 = 0 . Э т о решени е нас не у с т р аи вает . П о эт о му б у дем по лагат ь λ 0 = 1. В эт о м с лу чае с и с т ема при о б р ет ает ви д

11

 2u1 + 3λ1 = 0  2u 2 + 4λ1 = 0 .  3u + 4u = 1 2  1 3 9 16 О т с юда легко по с чи т ат ь, что u1 = − λ1 , u 2 = −2λ1 ,− λ1 − λ1 = 1. 2 2 2 2 3 4 П о эт о му λ1 = − , u1 = , u 2 = и о пт и мальная т о чка и меет ви д 25 25 25 3 4 1 u * = ( , ) и значени е ф у нкци и в ней р авно I(u * ) = . П о каж ем, что 25 25 25 эт а т о чка являет с я т о чко й ми ни му ма. Для эт о го с о с т ави м пр и ращени е 3 4 u = ( + h1 , + h 2 ), у до влет во р яющу ю о грани чени ю 25 25 3 4 3( + h1 ) + 4( + h 2 ) = 1. О т с юда о чеви дно , что 3h1 + 4h 2 = 0 и 25 25 3 h 2 = − h1. П о с чи т аем значени е ф у нкци и 4 3 4 3 4 3 1 25 I( u ) = ( + h 1 ) 2 + ( + h 2 ) 2 = ( + h 1 ) 2 + ( − h 1 ) 2 = + h 12 > I(u * ). 25 25 25 25 4 125 16 П ример 3. М и ни ми зи ро ват ь ф у нкци ю I(u ) = e u1u 2 → inf при о грани чени и u1 + u 2 = 1. Со с т ави м ф у нкци ю Л агранж а L(λ 0 , λ1 , u1 , u 2 ) = λ 0 e u1u 2 + λ1 (u1 + u 2 − 1). Ч ас т ные про и зво дные и меют ви д ∂L ∂L = λ 0 e u1u 2 u1 + λ1. = λ 0 e u1u 2 u 2 + λ1 ; ∂u 1 ∂u 2 В ыпи шем с о о т вет с т ву ющу ю с и с т ему у р авнени й для о пр еделени я парамет ро в и о пт и мально й т о чки : λ 0 e u1u 2 u 2 + λ1 = 0  uu  λ 0 e 1 2 u 1 + λ1 = 0 .  u +u =0 2 2  Рас с мо т ри м с лу чай, ко гда λ 0 = 0 . Т о гда и λ1 = 0 . Н ас эт о не у с т раи вает . П у с т ь λ 0 = 1 . П о лу чаем с леду ющу ю с и с т ему :

12

e u1u 2 u 2 + λ1 = 0  u1u 2  e u 1 + λ1 = 0 ;  u +u =0 2  2

e u1u 2 (u 2 − u 1 ) = 0  u1u 2  e u 1 + λ1 = 0 ;  u +u =0 2 2 

u1 = u 2   u1u 2 e u 1 + λ1 = 0 .  u = u = 1/ 2 2  1

О т ку да: λ1 = −1 / 2e1 / 4 . Со о т вет с т венно : u ∗ = (1 / 2,1 / 2) , J (u ∗ ) = e1 / 4 . В о зьмем

пр о и зво льну ю

1 / 2 + h1 + 1 / 2 + h 2 = 1 ,

т о чку

т .е.

u = (1 / 2 + h 1 ,1 / 2 + h 2 )

h1 + h 2 = 0

и ли

т аку ю,

h 2 = −h 1 .

что

Значи т :

u = (1 / 2 + h 1 ,1 / 2 − h 1 ) . В ычи с ли м значени е целево й ф у нкци и в эт о й т о чке.

J( u ) = e (1 / 2 + h1 )(1 / 2− h1 ) = e1 / 4− h1 ≤ e1 / 4 = J (u ∗ ) . П о лу чаем, что 2

u ∗ до с т авляет

целево й ф у нкци и наи б о льшее значени е. За да ни я для са м ост оят ельной ра бот ы М и ни ми зи ро ват ь с леду ющи е ф у нкци и : 1) J ( u ) = u 12 + u 22 → inf u14 + u 42 = 1 .

2) J ( u ) = u 1u 22 u 33 → inf u 1 + u 2 + u 3 = 1.

3) J( u ) = u 1u 2 u 3 → inf u 12 + u 22 + u 32 = 1 , u 1 + u 2 + u 3 = 0 .

Д О С Т АТ О Ч Н О Е У С Л О В И Е Л О К АЛ Ь Н О Г О МИ Н И МУ МА В ЗАД АЧ АХС О Г РАН И Ч Е Н И ЯМИ Т И П А РАВ Е Н С Т В П ри ведем до с т ат о чные у с ло ви я ло кально го у с ло вно го ми ни му ма. Бу дем предпо лагат ь, что вект о ры g1′ u (u * ), g′2 u (u * ),..., g ′s u (u * ) являют с я ли нейно незави с и мыми в т о чке u * . П у с т ь ( u * , λ*0 , λ* ) - р ешени е с и с т емы  ∂L = 0, j = 1,..., n   ∂u j g i ( u ) = 0, i = 1,..., s.

(11)

13

В ект о р u р азо б ьем на две час т и . О дна являет с я (n-s) – мерным вект о р о м. В дальнейшем ее б у дем о б о значат ь через u ∈ R n−s , вт о рая являет с я s-мер ным вект о р о м, ее мы б у дем о б о значат ь чер ез v ∈ R s , т .е.  u1   v1      u =  ... , v =  ... . u  v   n −s   s Т аккаквект о р ы g iu (u * , v* ), i = 1,..., s пр едпо лагают с я ли нейно незави с и мыми , т о переменные v мо ж но выб рат ь т ак, что б ы в о крес т но с т и т о чки ( u * , v* ) выпо лняли с ь у с ло ви я т ео р емы о неявных ф у нкци ях, и с и с т ема у р авнени й g i (u , v) = 0, i = 1,..., s о пределяет неявные ф у нкци и v i ( u ), i = 1,..., s в о крес т но с т и т о чки ( u * , v* ). Задачу (6)-(7) мо ж но запи с ат ь в ви де I(u, v) → inf, (12) g i ( u , v) = 0, i = 1,..., s, u ∈ R n −s , v ∈ R s . П у с т ь ф у нкци и I, g i , i = 1,..., s дваж ды непрерывно ди ф ф ер енци р у емы. В ведем о б о значени я

L uu

L uv

 ∂ 2L  2  ∂u1 = ...  ∂ 2L   ∂u1∂u n −s   ∂ 2L   ∂v1∂u1 = ...  ∂ 2L   ∂v1∂u n −s 

 ∂ 2L ∂ 2L    ... 2 ∂u n −s ∂u1   ∂v1 , L vv =  ... ... ... 2  ∂ 2L ∂ L  ...    ∂v1∂v s ∂u 2n −s    ∂ 2L ∂ 2L    ... ∂v s ∂u1   ∂u1∂v1  ... ... , L vu =  ... 2   ∂ 2L ∂ L ...    ∂u1∂v s ∂v s ∂u n −s  

 ∂g1  g ( u , v )  1   ∂u1   g (u, v) =  ... , g u =  ...  ∂g s  g (u , v)   s   ∂u  1

∂2L   ... ∂v s ∂v1  ... ... , ∂2L  ...  ∂v s2  ∂ 2L   ∂u n −s ∂v1  , ... ... 2 ∂ L  ...  ∂u n −s ∂v s  ...

∂g1   ∂g1   ∂u n −s   ∂v1 ... ... , g v =  ... ∂g s   ∂g s ...  ∂v ∂u n −s   1 ...

∂g1   ∂v s  ... ... . ∂g s  ... ∂v s  ...

Т еорем а . П у с т ь выпо лняют с я у с ло ви я: 1. ( u * , v * , λ*0 , λ* ) – с т аци о нарная т о чка ф у нкци и Л агранж а. 2. Ф у нкци и I, g i , i = 1,..., s дваж ды непр ерывно ди ф ф еренци р у емы в неко т о ро й о кр ес т но с т и т о чки ( u * , v* ); 3. В т о чке ( u * , v * ) мат ри ца g v (u * , v * ) и меет о б рат ну ю.

(13)

14

4. М ат ри ца (размера (n-s)x(n-s)) D = L uu − L uv g −v1g u − g Tu (g Tv ) −1 L vu + g Tu (g Tv ) −1 L vv g −v1g u ,

(14)

вычи с ленная в т о чке ( u * , v * , λ*0 , λ* ) по ло ж и т ельно о пр еделенная. Т о гда т о чка ( u * , v* ) являет с я т о чко й ло кально го ми ни му ма задачи (6)(8). Со глас но кри т ери ю Си львес т ра, с и ммет ри чес кая мат ри ца являет с я по ло ж и т ельно о пределенно й т о гда и т о лько т о гда, ко гда вс е по с ледо ват ельные ми но ры на главно й ди агонали мат р и цы по ло ж и т ельны. Н Е К О Л Ь К О П РИ МЕ РО В Р Е Ш Е Н И Я ЗАД АЧ П ример 1. М и ни ми зи ро ват ь ф у нкци ю J( u ) = u 1u 2 u 3 → inf при о грани чени ях 2u 1u 2 + u 2 u 3 = 12 , 2u 1 − u 2 = 8 .

1. В ыпи шем ф у нкци ю Л агранж а L(u, λ 0 , λ) = λ 0 u 1u 2 u 3 + λ 1 (2u 1u 2 + u 2 u 3 − 12) + λ 2 (2u 1 − u 2 − 8) . 2. Н айдем час т ные про и зво дные ф у нкци и Л агранж а ∂L = λ 0 u 2 u 3 + 2λ1u 2 + 2λ 2 ∂u1 ∂L = λ 0 u1u 3 + 2λ1u1 + λ1u 3 − λ 2 ∂u 2 ∂L = λ 0 u 1u 2 + λ 1u 2 ∂u 3 3. Решаем с и с т ему  λ 0 u 2 u 3 + 2λ1u 2 + 2λ 2 = 0 λ u u + 2λ u + λ u − λ = 0 1 1 1 3 2  0 1 3 λ 0 u 1 u 2 + λ1 u 2 = 0   2u1u 2 + u 2 u 3 = 12   2u 1 − u 2 = 8 Рас с мо т ри м с лу чай λ 0 = 0 . Си с т ема при мет ви д:

15

 2λ1u 2 + 2λ 2 = 0 2λ u + λ u − λ = 0 1 3 2  1 1 . λ1 u 2 = 0   2u u + u u = 12 1 2 2 3   2u 1 − u 2 = 8 П о с ко льку u 2 ≠ 0 , т о λ1 = 0 , а с ледо ват ельно , и λ 2 = 0 . Э т о т с лу чай нас не у с т р аи вает . П о ло ж и м λ 0 = 1 . П о лу чи м с и с т ему :  u 2 u 3 + 2λ 1 u 2 + 2λ 2 = 0  u 2 u 3 + 2λ1u 2 + 2λ 2 = 0  u u + 2λ u + λ u − λ = 0  u u + 2λ u + λ u − λ = 0 1 1 1 3 2 1 1 1 3 2  1 3  1 3 ⇔  u 1 u 2 + λ 1u 2 = 0 u 2 (u 1 + λ1 ) = 0 .    2u 1u 2 + u 2 u 3 = 12 2u 1u 2 + u 2 u 3 = 12     2u 1 − u 2 = 8 2u 1 − u 2 = 8 Си с т ема экви валент на с леду ющи м дву м: u2 = 0   u 2 u 3 + 2λ1u 2 + 2λ 2 = 0   u u + 2λ u + λ u − λ = 0 λ2 = 0 1 1 1 3 2   1 3 . λ1 = −u 1 u 1u 3 + 2λ1 u 1 + u 3 = 0 и    0 = 12 2u 1u 2 + u 2 u 3 = 12     u1 = 4 2u 1 − u 2 = 8 П ервая с и с т ема нес о вмес т на, по эт о му решаем вт о р у ю. 12 − 2u 1u 2 − 2u 1u 2 + 2λ 2 = 0  u 2 u 3 − 2 u 1 u 2 + 2λ 2 = 0  u u − 2 u 2 − u u − λ = 0 − 2u 12 − λ 2 = 0 1 1 3 2   1 3 λ1 = −u 1 ⇔  ⇔ λ1 = −u 1    2u 1u 2 + u 2 u 3 = 12 2u 1u 2 + u 2 u 3 = 12     2u 1 − u 2 = 8 2u 1 − u 2 = 8 12 − 4u 1u 2 − 4u 12 = 0  2  − 2u 1 − λ 2 = 0 λ1 = −u 1   2u u + u u = 12 1 2 2 3   2u 1 − u 2 = 8

12 − 4u 1 (2u 1 − 8) − 4u 12 = 0  − 2u 12 − λ 2 = 0  ⇔  ⇔ λ1 = −u 1  2u 1 u 2 + u 2 u 3 = 12   2u 1 − u 2 = 8

16

12 − 8u12 + 32u1 − 4u12 = 0  − 2u12 − λ 2 = 0  ⇔ λ1 = − u 1   2u u + u u = 12 1 2 2 3   2u 1 − u 2 = 8

− 12u 12 + 32u 1 + 12 = 0  − 2u 12 − λ 2 = 0  . λ1 = −u 1   2u u + u u = 12 1 2 2 3   2u 1 − u 2 = 8

Решая пер во е у равнени е с и с т емы, нахо ди м u 1 = −1 / 3 и u 1 = 3 . П о лу чаем λ 0 = 1, u 1 = −1 / 3, u 2 = −26 / 3, u 3 = −28 / 39, λ1 = 1 / 3, λ 2 = −2 / 9 и λ 0 = 1, u 1 = 3, u 2 = −2, u 3 = −12, λ1 = −3, λ 2 = −18 . П ро вери м, выпо лнено ли до с т ат о чно е у с ло ви е для т о чки (3,−2,−12,−3,−18) . Бу дем с чи т ат ь u = u1 - незави с и мо й переменно й и v1 = u 2 , v 2 = u 3 - ф у нкци ями о т u 1 . В ыпи шем вс е мат ри цы, вхо дящи е в ф о рму лу для вычи с лени я мат ри цы D. L uu

∂2L = 2 = 0, ∂u 1

∂  ∂L   ∂ ∂L ∂ ∂L   = (u 3 + 2λ1 , u 2 ) , ,  = ∂v  ∂u   ∂u 2 ∂u 1 ∂u 3 ∂u 1   ∂ ∂L    ∂ ∂L  ∂u 1 ∂u 2   u 3 + 2λ 1  , = = = ∂u ∂v  ∂ ∂L   u 2   ∂u ∂u   1 3

L uv =

L vu

 ∂ 2L ∂2L    u 1 + λ1  ∂u 3 ∂u 2   0  ∂u 22  , L vv =  2 = 0  ∂ L ∂ 2 L   u 1 + λ1   2 u u ∂ ∂ u ∂ 3  2 3   ∂g1 ∂g1    − u2  ∂u 2 ∂u 3   2u 1 + u 3 u 2  −1 1  0   ,  , g v = gv = =   ∂g 2 ∂g 2   − 1 0 u 2  1 2u 1 + u 3   ∂u   2 ∂u 3   2u + u 3 g Tv =  1  u2

− 1  , g Tv 0

( )

−1

=

1  0  u 2  − u 2

П о с чи т аем про и зведени е L uv g −v1g u = (λ 0 u 3 + 2λ1 , λ 0 u 2 )

1 u2

 ∂g1    1  ∂u 1   2u 2    , gu = . =  ∂g 2   2  2u 1 + u 3   ∂u   1

− u 2  2u 2  0    = −4λ 1 + 2u 2 + 4u 1 ;  1 2u 1 + u 3  2 

17

( )

−1

L vu = (2u 2 ,2 )

( )

−1

L vv g −v1g u =

g Tu g Tv

g Tu g Tv

= (2u 2 ,2)

(

1  0  u 2  − u 2

1 u2

 0  − u2

 u 3 + 2λ1   = 2 u 2 − 4λ 1 + 4 u 1 ;  2u 1 + u 3  u 2  1

1  0  2u1 + u 3  u1 + λ1

u1 + λ1  0 − u 2  2u 2    = 0  1 2u1 + u 3  2 

)

4 − 2u1u 2 − 4u12 − 2u1u 3 − 2λ1u 2 − 4λ1u1 − 2λ1u 3 u2 П о дс т авляя значени я мат ри ц в ф о р му лу для вычи с лени я D, нахо ди м 4 D = 4λ 1 − 2 u 2 − 4 u 1 − 2 u 2 + 4λ 1 − 4 u 1 − 2u 1u 2 + 4u 12 + 2u1u 3 + 2λ1u 2 + 4λ1u 1 + 2λ1u 3 u2 112 . D (3, −2, −12, −3, −18 ) = −40 < 0 , D (−1 / 3, −26 / 3, −28 / 39,1 / 3, −2 / 9 ) = 3 Следо ват ельно , т о чка u ∗ = (3,−2,−12) не до с т авляет ми ни мально е значени е целево й ф у нкци и , а т о чка u ∗ = (− 1 / 3,−26 / 3,−28 / 39 ) до с т авляет ми ни мально е значени е целево й ф у нкци и пр и заданных о грани чени ях. =

(

П ример 2. М и ни ми зи ро ват ь ф у нкци ю J ( u ) = u 1u 2 u 3 → inf

при о грани чени ях u 12 + u 22 + u 32 = 1 , u 1 + u 2 + u 3 = 0 .

1. В ыпи шем ф у нкци ю Л агранж а L( u , λ 0 , λ) = λ 0 u 1u 2 u 3 + λ1 ( u 12 + u 22 + u 32 − 1) + λ 2 (u 1 + u 2 + u 3 ) .

2. Н айдем час т ные про и зво дные ф у нкци и Л агранж а ∂L = λ 0 u 2 u 3 + 2λ1u 2 + λ 2 ∂u1 ∂L = λ 0 u1u 3 + 2λ1u 2 + λ 2 ∂u 2 ∂L = λ 0 u1u 2 + 2λ1u 3 + λ 2 ∂u 3 3. Решаем с и с т ему

)

18

λ 0 u 2 u 3 + 2λ 1u 2 + λ 2 = 0  λ u u + 2λ u + λ = 0 1 2 2  0 1 3  λ 0 u 1 u 2 + 2λ 1 u 3 + λ 2 = 0  u 12 + u 22 + u 32 = 1   u1 + u 2 + u 3 = 0 Рас с мо т ри м с лу чай λ 0 = 0 .  2λ1u 2 + λ 2 = 0  2λ1u 2 + λ 2 = 0  2λ u + λ = 0  λ2 = 0 2  1 2   2λ1u 3 + λ 2 = 0 ⇔  2λ1u 3 + λ 2 = 0 ⇔ u 2 + u 2 + u 2 = 1 u 2 + u 2 + u 2 = 1 2 3 2 3  1  1 u 1 + u 2 + u 3 = 0 u 1 + u 2 + u 3 = 0

λ2 = 0   2λ u = 0 1 1   2λ1u 3 = 0 u 2 + u 2 + u 2 = 1 2 3  1 u 1 + u 2 + u 3 = 0

Э т а с и с т ема экви валент на с леду ющей с о во ку пно с т и с и с т ем λ2 = 0  λ2 = 0   u1 = 0   λ1 = 0  u3 = 0 . и   2 2 2 u u u 1 + + = 2 3 u 2 + u 2 + u 2 = 1  1 2 3 u 1 + u 2 + u 3 = 0  1 u 1 + u 2 + u 3 = 0 П ервая с и с т ема и меет решени е, но λ 0 = λ1 = λ 2 = 0 , чего б ыт ь не мо ж ет . В т о р ая с и с т ема экви валент на с леду ющей с и с т еме λ2 = 0   u1 = 0  u3 = 0 .  u 2 + u 2 + u 2 = 1 2 3  1  u2 = 0 Э т а с и с т ема нес о вмес т на. П о эт о му λ 0 ≠ 0 . П о ло ж и м λ 0 = 1 . Си с т ема при мет ви д u 2 u 3 + 2λ1 u 1 + λ 2 = 0 (u 2 − u 1 )(u 3 − 2λ1 ) = 0 u u + 2λ u + λ = 0 (u − u )(u − 2λ ) = 0 1 2 2 1 2 1  1 3  3  u 1u 2 + λ1 u 3 + λ 2 = 0 ⇔  u 2 u 3 + 2λ1 u 1 + λ 2 = 0  u2 + u2 + u2 = 1  u2 + u2 + u2 = 1 1 2 3 1 2 3    u 1 + u 2 + u 3 = 0  u 1 + u 2 + u 3 = 0 Си с т ема экви валент на с о во ку пно с т и чет ыр ех с и с т ем

19

u3 = u2   u λ1 = 2  2  2.u u + 2λ u + λ = 0 ; 2 3 1 1 2  2 2 2  u1 + u 2 + u 3 = 1  u 1 + u 2 + u 3 = 0 u1 = u 3 u1 = u 2     u u λ1 = 3 λ1 = 2   2 2   4.u u + 2λ u + λ = 0 . 3.u u + 2λ u + λ = 0 ; 2 3 1 1 2 2 3 1 1 2   2 2 2 2 2 2  u1 + u 2 + u 3 = 1  u1 + u 2 + u 3 = 1  u 1 + u 2 + u 3 = 0  u 1 + u 2 + u 3 = 0 Н ет р у дно ви дет ь, что пер вая с и с т ема нес о вмес т на, вт о р ая экви валент на с и с т еме u3 = u2   u 1 = −2u 2   6u 22 = 1 ,  u  λ1 = 2  2 λ 2 = − u 2 u 3 − 2λ1 u 1 решени ем ко т о ро й являет с я вект о р 2 1 1 1 u1 = ± ,u2 = u3 = ± λ1 = ± , λ 2 = . А нало ги чно по лу чаем, что 6 6 6, 2 6 решени ем с и с т емы 3 являет с я вект о р 1 1 2 1 1 u1 = ± ,u2 = ± u3 = ± λ1 = ± , λ 2 = , а с и с т емы 4 6 6 6, 6, 2 6 1 2 1 1 1 u1 = ± ,u2 = ± u3 = ± λ1 = ± ,λ2 = . 6 6 6, 6, 2 6 П ро вери м, выпо лнено ли до с т ат о чно е у с ло ви е для т о чки 2 1 1 1  1 ,− , , ,  . В ыдели м незави с и мые и зави с и мые переменные.  6 6 2 6 6  6 Бу дем с чи т ат ь u = u 1 - незави с и мо й переменно й и v1 = u 2 , v 2 = u 3 - ф у нкци ями о т u 1 . Для т о го что б ы выпи с ат ь вс е мат ри цы, вхо дящи е в ф о рму лу для вычи с лени я мат ри цы D (в данно м с лу чае мат ри ца выро ж дает с я в чи с ло ), по с чи т аем вт о рые час т ные про и зво дные ф у нкци и Л агранж а ∂2L ∂2L ∂ 2L = 2λ1 , = 2λ1 , = 2λ1 , ∂u 32 ∂u 12 ∂u 22 u 2 = u1   u 3 = u1  1.u 2 u 3 + 2λ1 u 1 + λ 2 = 0  u2 + u2 + u2 = 1 1 2 3   u 1 + u 2 + u 3 = 0

20

∂2L ∂ 2L ∂ 2L ∂ 2L ∂2L ∂2L = = u3 , = = u2 , = = u1 , ∂u 1∂u 2 ∂u 2 ∂u 1 ∂u 3 ∂u 1 ∂u 1∂u 3 ∂u 2 ∂u 3 ∂u 3 ∂u 2 (λ 0 = 1) . П о эт о му 1 1 (− 2,1) , L uu u * , λ* = 2λ1(u* ,λ* ) = , L uv u * , λ* = (u 2 , u 3 )(u* ,λ* ) = 6 6 u   2λ u  1 1 1 1  ,  (1,−2) , L vv u * , λ* =  1 1  L vu u * , λ* =  3  = = 6 6 1 1  u 2  (u* ,λ* )  u 1 λ1  (u* ,λ* )

(

(

(

)

(

)

)

(

)

2u 3   1  (u* ,λ* )

 2u g v u * , λ* =  2  1

(

2   2  1 −  1   −1 * * 6 , 6  , gv u ,λ = − 4   6  1   −1 −  6 

 4 − = 6  1 

 4  1 − 6 , g Tv u * , λ* =   2 1   6 

)

(

)

1  12 u ,λ = − 6 − 6 

( ) ( −1 g Tv

)

*

*

)

−1  4 , −  6

 2   2u 2   g u u , λ =  =  6  .  2  (u* ,λ* )  1  П о дс т авляя значени я мат ри ц в ф о рму лу для вычи с лени я D, нахо ди м 1 1 1 6 5 D= − − + = > 0. 6 6 6 6 6 2 1   1 ,− , Следо ват ельно , т о чка u * =   до с т авляет ми ни мально е 6 6  6

(

*

*

)

значени е целево й ф у нкци и при заданных о грани чени ях и эт о значени е равно −

3 . В о с т альных т о чках до с т ат о чно е у с ло ви е про веряет с я анало ги чно . 6 За да ни я для са м ост оят ельной ра бот ы 1. М и ни ми зи ро ват ь ф у нкци ю I(u ) = u1u 2 u 3 → inf при о грани чени ях u 12 + u 22 + u 32 = 1, u 1 + u 2 + u 3 ≤ 0. 2. М и ни ми зи ро ват ь ф у нкци ю

21

I(u ) = e u1 − u 2 − u 1 − u 2 → inf при о грани чени ях u1 + u 2 ≤ 1, u1 ≥ 0, u 2 ≥ 0.

ЗАД АЧ А Н А У С Л О В Н Ы Й Э К С Т Р Е МУ М С О Г РАН И Ч Е Н И ЯМИ Т И П А Р АВ Е Н С Т В И Н Е Р АВ Е Н С Т В П о с т авлена задача

I(u ) → min,

(15)

при у с ло ви и , что u ∈ U = {u ∈ R n | g i (u ) = 0, i = 1,..., s; h j ( u ) ≤ 0, j = s + 1,..., k}. Задачу (15),(16) мо ж но с вес т и кзадаче на у с ло вный экс т рему м с о грани чени ями т и па равенс т в. В ведем но вые переменные: w j , j = s + 1,..., k; w = ( w s+1 ,..., w k ). Т о гда задача при мет ви д I(u, w ) = I(u ) → min, g i (u ) = 0, i = 1,..., s,

(16)

(17) (18)

h j ( u ) + w 2j = 0, j = s + 1,..., k. (19) Задачи (15),(16) и (17)-(19) экви валент ны в с леду ющем с мыс ле: ес ли ( u * , w * ) являет с я т о чко й ло кально го экс т р ему ма для задачи (17)-(19), т о u * - т о чка ло кально го экс т р ему ма для задачи (15),(16). И нао б о ро т , ес ли u * - т о чка ло кально го экс т р ему ма для задачи (15),(16), т о с у щес т ву ет вект о р w * , т ако й что т о чка ( u * , w * ) - т о чка ло кально го экс т рему ма для задачи (17)-(19). АЛ Г О Р И Т М РЕ Ш Е Н И Я ЗАД АЧ И Со с т авляем ф у нкци ю Л агранж а s

s1

i =1

j=1

L = λ 0 I( u ) + ∑ λ i g i ( u ) + ∑ µ j h j ( u ) и по т реб у ем выпо лнени я cледу ющи х у с ло ви й: ∂L = 0 - нео б хо ди мо е у с ло ви е экс т рему ма; 1. ∂u 2. g i (u ) = 0, i = 1,..., s; 3. µ j h j (u ) = 0, j = 1,..., s1 - у с ло ви я до по лняющей неж ес т ко с т и , где µ j неко т о рые чи с ла;

4. λ 0 , µ j≥0 , j = 1,..., s1 .

22

П ример 1. М и ни ми зи ро ват ь ф у нкци ю I(u ) = u 12 + u 22 + u 32 → inf , при у с ло ви ях 2u1 − u 2 + u 3 ≤ 5 , u1 + u 2 + u 3 = 3. П о с т ро и м ф у нкци ю Л агранж а. О на и меет ви д L = λ 0 (u12 + u 22 + u 32 ) + λ1 ( u1 + u 2 + u 3 − 3) + µ1 ( 2u1 − u 2 + u 3 − 5). П о с чи т аем час т ные про и зво дные о т ф у нкци и Л агранж а по каж до й переменно й и при равняем и х кну лю. П о лу чи м ∂L ∂L = 2λ 0 u1+ λ1 + 2µ1 = 0 , = 2λ 0 u 2 + λ1 − µ1 = 0 , ∂u1 ∂u 2 ∂L = 2λ 0 u 3 + λ1 + µ1 = 0 . ∂u 3 П ри пи шем кни м о грани чени я u1 + u 2 + u 3 = 3, µ1 (2u1 − u 2 + u 3 − 5) = 0 и т ем с амым с ведем задачу с о грани чени ями т и па неравенс т в кзадаче с о грани чени ями т и па равенс т в. П редпо ло ж и м с начала, что λ 0 = 0 , т о гда по лу чи м с леду ющу ю с и с т ему для о пр еделени я парамет ро в и кри т и чес ки х т о чек λ1 + 2µ1 = 0   λ1 − µ1 = 0  λ1 + µ1 = 0   u1 + u 2 + u 3 = 0  µ1 (2u1 − u 2 + u 3 − 5) = 0. О т с юда, о чеви дно , выт екает , что λ1 = µ1 = 0 . Э т о т с лу чай нам не по дхо ди т . Бу дем предпо лагат ь т еперь для у до б с т ва, что λ 0 =12 . Т о гда с и с т ема при о б р ет ет ви д u1 + λ1 + 2µ1 = 0   u 2 + λ1 + µ1 = 0  u 3 + λ1 + µ1 = 0 .   u1 + u 2 + u 3 = 3  µ1 (2u1 − u 2 + u 3 − 5) = 0

23

В ырази м пер еменные u1 , u 2 , u 3 и по дс т ави м и х в чет верт о е и пят о е у р авнени я по с ледней с и с т емы. П о лу чи м u1 = −(λ1 + 2µ1 ), u 2 = −(λ1 − µ1 ), u 3 = −(λ1 + µ1 ). Т о гда 3λ1 + 2µ1 = −3   µ1 ( −2λ1 − 6µ1 − 5) = 0. П о с ледняя с и с т ема и меет два решени я. П ер во е: ес ли µ1 = 0, т о λ1 = −1   u1 = 1  u = 1.  2 Значени е ф у нкци о нала равно I(u ) = 3. В т о ро й с лу чай: ес ли значени е в с ко б ках р авно ну лю, т .е. 2λ1 + 6µ1 + 5 = 0, т о 4  λ = − 1  7  1 12 µ1 = (−3 + ) < 0. 2 7  Э т о т с лу чай нас не у с т раи вает . П ример 2. М и ни ми зи ро ват ь ф у нкци ю I(u ) = u 1u 2 u 3 → inf при о грани чени и u 12 + u 22 + u 32 ≤ 1 . Со с т ави м ф у нкци ю Л агранж а. О на и меет ви д L = λ 0 u1u 2 u 3 + µ1 (u12 + u 22 + u 32 − 1). П о с чи т аем час т ные про и зво дные по вс ем переменным. П о лу чи м ∂L = λ 0 u 2 u 3 + 2µ1u1 ∂u1 ∂L = λ 0 u1u 3 + 2µ1u 2 ∂u 2 ∂L = λ 0 u1u 2 + 2µ1u 3 ∂u 3 П ри р авняем по лу ченные про и зво дные кну лю и до б ави м кэт о й с и с т еме у с ло ви я до по лняющей неж ес т ко с т и

24

 λ 0 u 2 u 3 + 2µ1u1 = 0  λ u u + 2µ u = 0  0 1 3 1 2   λ 0 u1u 2 + 2µ1u 3 = 0 µ1 u12 + u 22 + u 32 − 1 = 0

(

)

Ес ли мно ж и т ель λ 0 = 0 , т о с и с т ема при о б рет ает ви д µ1u 1 = 0   µ1 u 2 = 0   µ1 u 3 = 0  µ1 (u 12 + u 22 + u 32 − 1) = 0. Ес ли µ1 = 0, т о о грани чени е не выпо лняет с я. Ес ли ж е µ1 ≠ 0 , т о Э т о нас не у с т р аи вает . П у с т ь т епер ь λ 0 = 1 , т о гда u 1 = u 2 = u 3 = 0. и с хо дная с и с т ема б у дет и мет ь ви д  u 2 u 3 + 2µ1u1 = 0  u u + 2µ u = 0  1 3 1 2   u 1u 2 + 2µ1u 3 = 0 µ1 u 12 + u 22 + u 32 − 1 = 0

(

)

Ес ли µ1 = 0 , т о u 1 = u 2 = u 3 = 0 и о грани чени е не выпо лнено . Рас с мат ри вая с лу чай µ1 ≠ 0 и р ешая с о о т вет с ву ющу ю с и с т ему , по лу чаем 1 1   1 ,± ,± т о чки ви да  ±  . П редлагаем про вери т ь эт о 3 3 3  с амо с т о ят ельно . За да ни я для са м ост оят ельной ра бот ы 1. М и ни ми зи ро ват ь ф у нкци ю I(u ) = u1u 2 u 3 → inf при о грани чени ях u 12 + u 22 + u 32 = 1, u1 + u 2 + u 3 = 0.

2. М и ни ми зи ро ват ь ф у нкци ю I(u ) = − u 12 u 32 u 34 → inf при о грани чени и u 1 + u 2 + u 3 = 18.

25

С П И С О К Л И Т Е Р АТ У Р Ы 1. Г аллеев Э .М . О пт и ми заци я: Т ео ри я . П р и меры. Задачи / Э .М . Г аллеев, В .М . Т и хо ми ро в. – М . : Э ди т о р и ал У РСС, 2000. – 317 с . 2. В ас и льев О .В . М ет о ды о пт и ми заци и в задачах и у пр аж нени ях / О .В . В ас и льев, А .В . А р гучи нцев. – М . : Ф и змат ли т , 1999. – 207 с . 3. К армано в В .Г . М ат емат и чес ко е про грамми ро вани е / В .Г . К ар мано в. – М . : Ф и змат ли т , 2000. – 263 с . 4. П о лакЭ . Ч и с ленные мет о ды о пт и ми заци и . Еди ный по дхо д / Э .П о лак. – М . : М и р, 1974. – 367 с .

26

Д Л Я ЗАМЕ Т О К

27

Со с т ави т ели : Бело у с о ва Елена П ет ро вна К о с т ру б Ир и на Дми т р и евна Редакт о р Т и хо ми ро ва О льга А лекс андро вна