Н.М. Новикова - Курс лекций (1125270), страница 11

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

Текст из файла (страница 11)

oDNAKO dp MOVNO ISPOLXZOWATX NE DLQ PROIZWOLXNYHOPTIMIZACIONNYH ZADA^. kLASS PODHODQ]IH ZADA^ OPI[EM DALEE.oPREDELENIE 2. fUNKCIQ f NAZYWAETSQ RAZDELQEMOJ NA f1 I f2,ESLI ONA PREDSTAWIMA W WIDEf x;y() =f1 x;f2 y :(59( ))(4)oPREDELENIE 3. fUNKCIQ f NAZYWAETSQ RAZLOVIMOJ NA f1 I f2ESLI ONA RAZDELQEMA NA f1 f2 I FUNKCIQ f1 MONOTONNO NE UBYWAET POPOSLEDNEMU ARGUMENTUtEOREMA 1 (OPTIMALXNOSTI DLQ RAZLOVIMYH FUNKCIJ),,..x f1 (x; miny f2 (y));x;y) f (x;y) = minmin(I TO^NO TAK VE DLQmax.dOKAZATELXSTWO PROWEDEM DLQ SLU^AQ MINIMUMA.rAWENSTWO BUDET WYTEKATX IZ PARY PROTIWOPOLOVNYH NERAWENSTWpO OPREDELENI@ MINIMUMA x;y f1 x;f2 y f1 x0 ;f2 y0 8x0 ;y0(.)min(( ))(())00I; SLEDOWATELXNO; DLQ y0y f2 y ; xx f1 x;f2 y ;^TO DOKAZYWAET NERAWENSTWO aNALOGI^NO W SILU NEUBYWANIQ f1PO POSLEDNEMU ARGUMENTU f1 x0 ; y f2 y f1 x0 ;f2 y0 8x0 ;y0 :00pOLOVIM y0y f1 x ;f2 y ; xx f y f1 x;f2 y g::= arg min\,:= arg min( ):= arg min".(((()),min( ))( ))((:= arg min min))(( ))pOSKOLXKU POWTORNYJ RAWEN DWOJNOMU W PRAWOJ ^ASTI POLU^ILIx;y f x;y ^EM DOKAZALI I NERAWENSTWO dLQ ZADA^I USLOWNOJ OPTIMIZACII TEOREMA OPTIMALXNOSTI DLQRAZLOVIMYH FUNKCIJ PEREPISYWAETSQ SLEDU@]IM OBRAZOMminmin(,),\".:(min f (x;y ) =f (x; min f (y));6 ; 1 y2Y (x) 2x;yx: Ymin)2(x)=(5)GDE Y xfyj x;y 2 g uKAZANNAQ TEOREMA ISPOLXZUETSQ DLQPONIVENIQ RAZMERNOSTI OPTIMIZACIONNYH ZADA^ I W METODE dpdLQ NA^ALA RASSMOTRIM ZADA^U OPTIMIZACII ZAPISANNU@ W WIDE() =() ..,f g(x;y)2ET Rm f x;y ; x 2 X Rn; y 2 Y x Rk:=min()()(6)zDESX ET NAZYWAETSQ MNOVESTWOM TERMINALXNYH SOSTOQNIJ SISTEMYPO ASSOCIACII S DINAMI^ESKIMI SISTEMAMI UPRAWLENIQ DLQ OPTIMIZACII KOTORYH BYLO IZOBRETENO dp nAPRIMER DLQ g g1 ;:::;gm,.60,= (-),ESLI OGRANI^ENIQ ZADA^I ZADANY W FORME gi x;y ET Rm pUSTX f RAZLOVIMA A g RAZDELQEMA(=.)(4),0:8i ;m= 1TO,h2 y;h1 x ; h1 Rn ! Rm; h2 Rk+m ! Rm;TOGDA WWEDEM 8x;y E h1 x ; E 0 h2 y;E I WY^ISLQEM g KAKg x;y E 00 fUNKCII h1; h2 NAZYWA@TSQ FUNKCIQMI PEREHODA WEKTORY E; E SOSTOQNIQMI SISTEMY mNOVESTWO WSEH WOZMOVNYHSOSTOQNIJ SISTEMYOBOZNA^AETSQ E I FORMALXNO ZADAETSQ TAKE h 1 X : f h1 x j x 2 X g8E 2 h1 X fh2 y;E jy 2 Y X g Eg x;y() =(())=() =:(:)=().,|-.:1)2)() =(())(,)()MNOVESTWO W KA^ESTWE ARGUMENTA OZNA^AET OB_EDINENIE PO WSEM ARGUMENTAM IZ \TOGO MNOVESTWArASSMOTRIM DLQ SEMEJSTWO ZADA^ POISKA(-).(6)F2 E() =f2(y);y: h2 min(y;E )2ETKOTORYE NUVNO RE[ATX 8E 2 E pO TEOREME OPTIMALXNOSTI.f x2X f1 x;F2 h1 x := min((()))w REZULXTATE ZADA^A SWELASX K POSLEDOWATELXNOSTI jEj OPTIMIZACIONNYH ZADA^ MENX[EJ RAZMERNOSTIw METODE dp DANNAQ PROCEDURA PRIMENQETSQ REKURSIWNO K ZADA^E(6)+ 1-.F g(x ;:::;xn)2ET Rm f x1;:::;xn=1min()(7)DLQ SWEDENIQ K SEMEJSTWU ODNOMERNYH ZADA^ SLEDU@]IM OBRAZOMpUSTX f POSLEDOWATELXNO RAZLOVIMA T E,f x1;:::;xnf x2;:::;xn::::::::::::::::::fn 1 xn 1;xn()=^(2^)=()=..

.f1 x1;f2 x2;:::;xn ;f2 x2;f3 x3;:::;xn ;:::::::::::::::::::::fn 1 xn 1;fn xn ;(^())(^())(())I WSE fi MONOTONNO NE UBYWA@T PO MU ARGUMENTU pUSTX g POSLEDOWATELXNO RAZDELQEMA T E 9E Rm ; 9 FUNKCII PEREHODA h1 ;h2 ;:::;hn2-,. .61.:8x 2 X Xi g x hn xn;En 1 En 1 hn 1 xn 1;En 2 ;:::E2 h2 x2;E1 E1 h1 x1 I Ei 2 E 8i ;noBOZNA^IM 8i;n ; 8E 2 E ^EREZ hi xi;xi+1;:::;xn;E0==(() =),=((),=)= 2(= 1),1.^ (1FUNKCI@ OPREDELQEMU@ REKURRENTNO RAWENSTWAMIEi:)hi xi;EEi0+1 hi+1 xi+1;Ei0 ; :::;En0 hn xn;En0 1 hi xi;xi+1;:::;xn;EzAMETIM ^TO W SLU^AE E Ei 1 hi xi ;xi+1 ;:::;xn ;Ei 1 g x IEj0 Ej 8j i w SDELANNYH OBOZNA^ENIQH SPRAWEDLIWO WOZWRATNOE,:=()=,==(),)= ^ ((:=^ ().)=().SOOTNO[ENIE DLQ OGRANI^ENIJhi xi;xi+1;:::;xn;E hi+1 xi+1;:::;xn;hi xi;E :^ ()= ^(())(8)tOGDA PO OPREDELENI@F x2X : h^ (x ;:::;x ;h (x ))2E f1 x1;f2 x2;:::;xn ;nT=min2^((21I PO TEOREME OPTIMALXNOSTI))1F x 2X f1 x1;F2 h1 x1 ;GDE 8E1 2 E F2 E1 :f2 x2;:::;xn^ (x ;:::;x ;h (x ))2E(x ;:::;x ): h=(min1) =(minn22n2()))11^((8))=minx ;:::;xn ): h^ 3 (x3 ;:::;xn ;h2 (x2 ;E1 ))2ET( 2=min22(((5)(^((== () =^(min)) =1 IMEEM)),+Fi E : h^ (x ;x ;:::;x ;E)2E fi xi;xi+1;:::;xn 8i;Ei i inT()=)))I T D POLAGAQ MINIMUM PO PUSTOMU MNOVESTWU RAWNYM.

.,(9)Tf2 x2;f3 x3;:::;xnx 2X f2 x2 ;F3 h2 x2 ;E1POSLEDNEE RAWENSTWO SLEDUET IZ S x x2 ; y x3 ;:::;xnIZ(((1,)(10)+1|SEMEJSTWO ZADA^ W KOTOROE POGRUZILI,\" (7),fi(xi;Fi+1(hi(xi;Ei 1))) 8Ei 1 2 Exmini 2Xi| WOZWRATNOE (FUNKCIONALXNOE) URAWNENIE dp 8i = 2;n1,F i Ei(1) =Fn E() =fn(xn):xn 2Xn : hminn (xn ;E )2ET62(11)(12)aLGORITM dp:8E 2 E WY^ISLQEM Fn(E) IZ (12),POSLEDOWATELXNO DLQ i = n 1;:::; 2 OPREDELQEM Fi (E ) IZ (11),(10),ZATEM F IZ (9).~ISLO [AGOW ALGORITMA (RE[ENIJ ZADA^ ODNOMERNOJ MINIMIZACII)BUDET PORQDKA njEj.

tAKIM OBRAZOM METOD dp IMEET SMYSL PRIMENQTXDLQ ZADA^ S NE O^ENX BOLX[IM ^ISLOM SOSTOQNIJ (jEj MALO).2. pRIMERAMI RAZLOVIMYH FUNKCIJ MOGUT SLUVITX min, max,SUMMA, PROIZWEDENIE (S NEOTRICATELXNYMI KO\FFICIENTAMI) I T.P.iSHODNO METOD dp ISPOLXZOWALSQ DLQ OPTIMIZACII DINAMI^ESKIHSISTEM, ^TO NA[LO OTRAVENIE W PRIMENQEMOJ TERMINOLOGII. tAK, ESOOTWETSTWUET FIZI^ESKOMU PROSTRANSTWU SOSTOQNIJ (WOZMOVNYH KOORDINAT TRAEKTORII DWIVENIQ), xi | UPRAWLENI@ W MOMENT WREMENIti, WOZDEJSTWIE UPRAWLENIQ NA TRAEKTORI@ OPREDELQETSQ FUNKCIEJPEREHODA W SLEDU@]EE SOSTOQNIE, NA KONE^NOE SOSTOQNIE NALOVENYOGRANI^ENIQ PRINADLEVNOSTI K ET , NA^ALXNOE SOSTOQNIE FIKSIROWANO; fi (xi ;E ) | STOIMOSTX UPRAWLENIQ SISTEMOJ, NAHODQ]EJSQ WSOSTOQNII E , f | STOIMOSTX WSEJ TRAEKTORII E1 ;:::;En 1 .sOOTNO[ENIE (11) OZNA^AET MINIMIZACI@ STOIMOSTI \HWOSTA"TRAEKTORII W KAVDYJ MOMENT WREMENI, ^TO SOGLASUETSQ S PRINCIPOM OPTIMALXNOSTI, SFORMULIROWANNYM r.

b\LLMANOM: OPTIMALXNAQPOLITIKA UPRAWLENIQ TAKOWA, ^TO DLQ L@BOGO NA^ALXNOGO SOSTOQNIQI L@BYH RE[ENIJ (PO WYBORU UPRAWLENIQ), PRINQTYH NA NA^ALXNYH[AGAH, OSTAW[IESQ RE[ENIQ OBRAZU@T OPTIMALXNU@ POLITIKU, NA^INA@]U@SQ S SOSTOQNIQ, WOZNIK[EGO W REZULXTATE \TIH RE[ENIJ. (oTMETIM, ^TO W SLU^AE STROGOJ MONOTONNOSTI f TAKIM OBRAZOM MOVNOPOLU^ITX L@BOE RE[ENIE, W SLU^AE NESTROGOJ MONOTONNOSTI | HOTQBY ODNO).pROILL@STRIRUEM PRIMENENIE METODA dp NA PRIMERE RE[ENIQ ZADA^ blp S NEOTRICATELXNYMI KO\FFICIENTAMI (\LEMENTAMISIMPLEKS-TABLICY).

iTAK, WERNEMSQ K ZADA^E (3)F z2Bn: Azbhc;ziW PREDPOLOVENII aij ; bi ; cj 2 Z+ oBOZNA^IM ^EREZ aj j J STOLBEC=max.63-MATRICY A rASSMOTRIM SEMEJSTWO ZADA^ POISKA.nXFk E : z: zj 2f0;1g 8j=k;:::;n cj zjj=k() =maxnXaj zj b E;j=kGDE E 2 E =: fE 2 Zm+ j Ei bi 8i = 1;mg; k = 1;n.o^EWIDNO F,Fk E(=F1wOZWRATNOE URAWNENIE W DANNOM SLU^AE(0).:fFk+1 E ; ck Fk+1 E ak g;cn; E b an;Fn E) = max()+(+ )INA^EnAHODIM 8E 2 E Fn E I SOOTWETSTWU@]IE xn E ZATEM DLQ kn ;:::; OPREDELQEM Fk E I REALIZU@]IE IH xk E IZ WOZWRATNOGOURAWNENIQ WY^ISLQEM F1 ; x1 I DALEE x2 E 1 ;:::;xn E n 1 WZAWISIMOSTI OT TOGO KAKIE SOSTOQNIQ E 1 ;:::;E n 1 BYLI W KONE^NOMS^ETE ISPOLXZOWANY PRI WY^ISLENII F1 ESLI POSMOTRETX PO WSEM[AGAM ALGORITMA~ISLO [AGOW PREDLOVENNOGO ALGORITMA RAWNO n I NA n M [AGERASSMATRIWAETSQ f b1NA ::: bm ; n 1g nSOSTOQNIJn M MINIMUM IZ LEWOJ ^ASTI RAWNOJ jEj I 2 I T P tAK^TO PRI BOLX[IH b METOD dp RE[AET PRIMERNO STOLXKO VE ZADA^SKOLXKO mwg W HUD[EM SLU^AE ODNAKO RE[AEMYE ZADA^I ZDESX PRO]E PROWERKA OGRANI^ENIJ WMESTO lp pOD^ERKNEM ^TO PROCEDURA dp NE DAET SPOSOBOW SOKRA]ENIQ PEREBORA TOGDA KAK UDA^NYJWYBOR STRATEGII WETWLENIQ W mwg NAPRIMER NA OSNOWE IME@]EJSQ U WY^ISLITELQ DOPOLNITELXNOJ INFORMACII ILI \WRISTI^ESKIHSOOBRAVENIJ POZWOLQET HOTQ I NE GARANTIROWANNO RE[ATX ZADA^I BOLX[EJ RAZMERNOSTI oTMETIM TAKVE OTSUTSTWIE OGRANI^ENIQNEOTRICATELXNOSTI KO\FFICIENTOW DLQ RABOTY mwg w PRINCIPEWOZMOVNO KOMBINIROWANIE OBEIH SHEM SM((12) =0.)((,)),((0)(0)(=))(),(0),.-min ((1)-+ 1)(|+ 1)2(,)2.

.,,-().,-,(),(-)-..(64. [6]).,sODERVANIEwwedenie w teori` slovnostix pONQTIE O SLOVNOSTI RE[ENIQ ZADA^x POLNYE UNIWERSALXNYE ZADA^Ix kLASSY SLOVNOSTI sILXNAQ POLNOTAI PSEWDOPOLINOMIALXNOSTXx pRIBLIVENNOE RE[ENIE ZADA^ KOMBINATORNOJ1.1.2. NP3.(3).10NP-154.OPTIMIZACIIosnowy linejnogo programmirowaniqx pONQTIE O SLOVNOSTI ZADA^ILINEJNOGO PROGRAMMIROWANIQ lpx mETOD \LLIPSOIDOWx tEORIQ DWOJSTWENNOSTI lp iDEQ METODA kARMARKARA|lementy matemati~eskogoprogrammirowaniqx oBZOR IDEJ MATEMATI^ESKOGO PROGRAMMIROWANIQ mpx dWOJSTWENNOSTX W mpsposoby re{eniq perebornyh zada~x gLOBALXNAQ OPTIMIZACIQmETOD WETWEJ I GRANIC mwgx cELO^ISLENNOE LINEJNOE PROGRAMMIROWANIE clpx mETOD DINAMI^ESKOGO PROGRAMMIROWANIQ dp212.5.()6.7..2429333.8.()9.38454.10..()11.(12.(65))515458.

Характеристики

Список файлов лекций