wyk-optym-ogr-row-2011.pdf

(183 KB) Pobierz
Optymalizacjazograniczeniamir ó wno–ciowymi
Wielezagadnie«optymalizacyjnychposiadaograniczeniar ó wno–ciowe:
g(x)=0:
(1)
Problemyoptymalizacyjnezograniczeniamir ó wno–ciowymirozwi¡zujemyprzypo-
mocymetodymno»nik ó wLagrange’a.Metodatapozwalazamienia¢problemyop-
tymalizacjiwarunkowej(zograniczeniami)naproblemyoptymalizacjibezwarunkowej
(bezogranicze«).
Kluczow¡rolƒwteoriimno»nik ó wLagrange’aodgrywaTwierdzenieofunkcjiuwik“anej.
Twierdzenie1(ofunkcjiuwik“anej).NiechG R
n+m bƒdziezbioremotwartym
m
bƒdziefunkcj¡klasyC 1 naG.Oznaczmy
orazniechF=(F 1 ;:::;F m ):G !R
S=f(x 1 ;:::;x n+m )2 G:F(x)=0 R m g:
Za“ ó »my,»ex ? 2 Soraz
W:=det h (F i ) x n+j (x ? ) i
1i;jm 6=0:
W ó wczasistniej¡zbi ó rotwartyU Gtaki,»ex ? 2 U, oto cze ni eV-x ? =(x ? 1 ;:::;x ? n )
ifunkcja'=(' 1 ;:::;' m ):V !R m klasyC 1 taka,»e(x ? ;'(x ? ))=x ? oraz
S\U=f(x;'(x))=(x 1 ;:::;x n ;' 1 (x 1 ;:::;x n );:::;' m (x 1 ;:::;x n )):(x 1 ;:::;x n )2 Vg:
Uwaga1.ZTwierdzeniaofunkcjiuwik“anejwynika,»eje»elispe“niones¡za“o»enia,
tegotwierdzenia,to
x n+1 =' 1 (x 1 ;:::;x n )::: x n+m =' m (x 1 ;:::;x n ); (x 1 ;:::;x n )2 V:
Wniosek1.Je»elispe“niones¡wszystkieza“o»eniaTwierdzenia1-ofunkcjiuwik“anej
orazdodatkowofunkcjaFjestklasyC k ,k 2N,tofunkcjauwik“ana'jestklasyC k .
Przejd„mydosformu“owaniaproblemu,kt ó rybƒdziemyrozwa»a¢wtejczƒ–ciwyk“adu.
NiechU R
zbi ó rotwarty,f;g 1 ;:::;g m :U !RfunkcjeklasyC 1 .Bƒdziemy
chcielirozwi¡za¢problemoptymalizacjizograniczeniamir ó wno–ciowymipostaci
8
<
n+m
f(x)=f(x 1 ;:::;x n ;x n+1 ;:::;x n+m )!min(max)
przyograniczeniach
g 1 (x)=g 1 (x 1 ;:::;x n ;x n+1 ;:::;x n+m )=0;
. . .
g m (x)=g m (x 1 ;:::;x n ;x n+1 ;:::;x n+m )=0;
x=(x 1 ;:::;x n ;x n+1 ;:::;x n+m )2 U:
(P)
:
Uwaga2.Zauwa»my,»ewproblemie(P)ilo–¢funkcjiograniczaj¡cychjestmniejsza
ni»ilo–¢zmiennychfunkcjiceluiograniczaj¡cych.
1
1092455750.016.png 1092455750.017.png
n+m
zbi ó rotwarty,f;g 1 ;:::;g m :U !RfunkcjeklasyC 1 .
De nicja1.NiechU R
Oznaczamy
D:=fx=(x 1 ;:::;x n ;x n+1 ;:::;x n+m )2 U:g j (x)=0; j=1;:::;mg:
Je»elidlapunktux ? 2 D d \Dzachodzijedenznastƒpuj¡cychwarunk ó w
9r >08x 2 D\K(x ? ;r)f(x) f(x ? ); (2)
9r >08x 2 D\K(x ? ;r)f(x) f(x ? ); (3)
tom ó wimy,»efunkcjafosi¡gawx ? minimumwarunkoweprzywarunkach
g 1 (x)=0;:::;g m (x)=0,gdyzachodziwarunek(2)orazm ó wimy,»efunkcjafos-
i¡gawx ? maksimumwarunkoweprzywarunkachg 1 (x)=0;:::;g m (x)=0,
gdyzachodziwarunek(3).Je»eliwpunkciex ? funkcjafosi¡gaminimumlubmaksi-
mumwarunkoweprzywarunkachg 1 (x)=0;:::;g m (x)=0,tom ó wimy,»efunkcjaf
osi¡gawx ? ekstremumwarunkoweprzywarunkachg 1 (x)=0;:::;g m (x)=0.
Punktx 2 Dnazywamypunktemregularnym(regularpoint)dlaproblemu
(P),je»elizbi ó rwektor ó wfrg j (x):j=1;:::;mgjestliniowoniezale»ny,gdym >1
lubgdyrg 1 (x)6=0 R n+1 ,gdym=1.
Dlaproblemu(P)de niujemyfunkcjƒLangrange’a(lagran»jan)nastƒpuj¡co
X
m
n+m R
m U R
m !R; L(x;)=f(x)+
L:R
j g j (x):
j=1
Wsp ó “rzƒdnewektoranazywamymno»nikamiLagrange’aproblemu(P).
Twierdzenie2(warunekkoniecznyistnieniaekstremumwarunkowego).Niech
U R
n+m zbi ó rotwarty, f;g 1 ;:::;g m :U !RfunkcjeklasyC 1 .Je»elifunkcja
fosi¡gawpunkcieregularnymdlaproblemu(P)-x ? ekstremumwarunkoweprzy
warunkachg 1 (x)=0;:::;g m (x)=0,toistnieje ? 2R
m taka,»e
rL(x ? ; ? )=0 R n+2m ;
cojestr ó wnowa»nezwarunkami
X
m
rf(x ? )+
? j rg j (x ? )=0 R n+m ; g 1 (x ? )=0; :::; g m (x ? )=0:
j=1
Dow ó d.Dow ó dprzeprowadzonynawyk“adzie.
Powy»szetwierdzenie2,towarunekkoniecznyistnieniaekstremumwarunkowego,
czyliekstremumlokalnego.U»ywaj¡ctegotwierdzeniawpewnychprzypadkachmo»emy
znale„¢rozwi¡zanieproblemu(P),czyliwyznaczy¢ekstremaglobalnefunkcji fna
zbiorzeogranicze«.Prze–led„mytonaprzyk“adzie.
2
1092455750.018.png 1092455750.019.png 1092455750.001.png
 
Przyk“ad1.Rozwa»myproblem
8
<
x 2 +y 2 +z 2 !ext
przyograniczeniu
x 2 + y 2
(P) 1
:
4 + z 2
9 =1:
Funkcjef(x;y;z)=x 2 +y 2 +z 2 ,g(x;y;z)=x 2 + y 2
4 + z 2
9 1s¡funkcjamiklasyC 1
naR
3 .Poniewa»zbi ó r
3 :x 2 + y 2
4 + z 2
3 :g(x;y;z)=0g=f(x;y;z)2R
S=f(x;y;z)2R
9 =1g6=;
jestzbioremzwartym,zatemfunkcjafosi¡gaswojekresynatymzbiorze(kt ó ry
jestelipsoid¡),czyliproblem(P) 1 marozwi¡zanie.Rozwi¡zanieproblemu(P) 1 wyz-
naczamyzTwierdzenia2.Zauwa»my,»eka»dypunktle»¡cynaelispoidziejestregu-
larny,poniewa»
rg(x;y;z)=[2x; y 2 ; 2z 9 ]=[0;0;0] ,(x;y;z)=(0;0;0)2 S:
FunkcjaLagrange’adlaproblmu(P) 1 maposta¢
L(x;y;z;)=f(x;y;z)+g(x;y;z)=x 2 +y 2 +z 2 +(x 2 + y 2
4 + z 2
9 1):
Rozwi¡zanieproblemu(P) 1 musiby¢punktemkrytycznymlagran»janu,czyli
rL(x;y;z;)=[0;0;0;0] , [2x+2x;2y+2 y 4 ;2z+2 z 9 ;x 2 + y 2
4 + z 2
9 1]=[0;0;0;0] ,
<
x(1+)=0
y(4+)=0
z(9+2)=0
x 2 + y 2
,(x;y;z;)2f(1;0;0;1);(0;2;0;4);(0;0;3; 9 2 )g:
,
:
4 + z 2
9 1=0
Poniewa»f(1;0;0)=1,f(0;2;0)=4,f(0;0;3)=9,st¡dpunkty(1;0;0)s¡
punktami,wkt ó rychfunkcjafosi¡gaminimumglobalneprzywarunkug(x;y;z)=0,
apunkty(0;0;3)s¡punktami,wkt ó rychfunkcjafosi¡gamaksimumglobalne
przywarunkug(x;y;z)=0.St¡dwynika,»epunkty(1;0;0)s¡punktami,w
kt ó rychfunkcjafosi¡gaminimumwarunkoweprzywarunkug(x;y;z)=0,apunkty
(0;0;3)s¡punktami,wkt ó rychfunkcjafosi¡gamaksimumwarunkoweprzywarunku
g(x;y;z)=0.
Zauwa»my,»ewpunktach(0;2;0)funkcjafnieosi¡gaekstremumwarunkowegoprzy
warunkug(x;y;z)=0.Poka»emy,todla(0;2;0)dla(0;2;0)pokazujesiƒanalog-
icznie.Poka»emy,»e
8" >09(x " ;y " ;z " );(x 0 " ;y 0 " ;z 0 " )2 S\K((0;2;0);") f(x " ;y " ;z " )< f(0;2;0)< f(x 0 " ;y 0 " ;z 0 " ):
Wystarczywykaza¢powy»szywarunekdla" 2(0;1).Niech" 2(0;1).Rozwa»my
3
q
q
1 " 2
1 " 2
( " 4 ;2
16 ; 3" 4 )2 S.Ponadto
16 ;0),(0;2
q
q
1 " 2
16 ;0)(0;2;0)k 2 = " 2
16 +4(1 " 2
1 " 2
k( " 4 ;2
16 2
16 +1)=
q
p 5"
= 3" 2
16 + " 2
2(1+
3" 2
16 + " 2
2 = 5" 2
1 " 2
16 ) k( " 4 ;2
16 ;0)(0;2;0)k
4 < "
r
1 " 2
16 )
q
q
1 " 2
16 ; 3" 4 )(0;2;0)k 2 = 9" 2
16 +4(1 " 2
1 " 2
k(0;2
16 2
16 +1)=
q
p 13"
= 5" 2
16 + " 2
2(1+
5" 2
16 + " 2
2 = 13" 2
1 " 2
16 ; 3" 4 )(0;2;0)k
16 ) k(0;2
4 < "
r
1 " 2
16 )
q
1 " 2
f( " 4 ;2
16 ;0)= " 2
16 +4(1 " 2
16 )=4 3" 2
16 <4=f(0;2;0)
q
1 " 2
16 ; 3" 4 )= 9" 2
16 +4(1 " 2
16 )=4+ 5" 2
16 >4=f(0;2;0):
Poniewa»wpunktach(0;2;0)funkcjafnieosi¡gaekstremumwarunkowegoprzy
warunkug(x;y;z)=0,tonieka»dypunktkrtytycznyfunkcjiLagrange’adlaproblemu
(P) 1 jestpunktem,wkt ó rymfunkcjafosi¡gaekstremumwarunkoweprzywarunku
g(x;y;z)=0,cooznacza,»etwierdzenieodwrotnedowarunkukoniecznegoistnienia
ekstremumwarunkowegoniejestprawdziwe.
Przejd„mydoprezentacjiwarunkudostatecznegoistnieniaekstremuwarunkowego
wprzypadku,gdyjestjednoograniczenieorazfunkcjeceluiograniczaj¡cas¡okre–lone
napodzbiorzeotwartymR
f(0;2
2 .
Twierdzenie3(warunekdostatecznyistnieniaekstremumwarunkowego).
NiechU R
2 zbi ó rotwarty,f;g:U !RfunkcjeklasyC 2 .Niechpunkt(x ? ;y ? )2 U
bƒdziepunktemregularnymdlaproblemu
8
<
f(x;y)!ext
przyograniczeniu
g(x;y)=0:
(P) 2
:
Je»elipunkt(x ? ;y ? ; ? )jestpunktemstacjonarnymdlafunkcjiLagrange’a-L(;;)dla
problemu(P) 2 oraz
L xx (x ? ;y ? ; ? ) L xy (x ? ;y ? ; ? ) g x (x ? ;y ? ; ? )
L yx (x ? ;y ? ; ? ) L yy (x ? ;y ? ; ? ) g y (x ? ;y ? ; ? )
g x (x ? ;y ? ; ? ) g y (x ? ;y ? ; ? ) 0
detHL(x ? ;y ? ; ? ):=
6=0; (4)
tofunkcjafosi¡gawpunkcie(x ? ;y ? )ekstremumwarunkoweprzywarunkug(x;y)=0.
Ponadto,
(i)je»elidetHL(x ? ;y ? ; ? )>0,tofunkcjafosi¡gawpunkcie(x ? ;y ? )maksimum
warunkoweprzywarunkug(x;y)=0,
(ii)je»elidetHL(x ? ;y ? ; ? )<0,tofunkcjafosi¡gawpunkcie(x ? ;y ? )minimum
warunkoweprzywarunkug(x;y)=0.
Dow ó d.Dow ó dprzeprowadzonynawyk“adzie.
4
1092455750.002.png 1092455750.003.png 1092455750.004.png 1092455750.005.png 1092455750.006.png 1092455750.007.png 1092455750.008.png 1092455750.009.png 1092455750.010.png 1092455750.011.png 1092455750.012.png 1092455750.013.png 1092455750.014.png 1092455750.015.png
 

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin