[учебник] Основы оптимизации. Новикова (1998) (1186147), страница 12
Текст из файла (страница 12)
w SDELANNYH OBOZNA^ENIQH SPRAWEDLIWO WOZWRATNOESOOTNO[ENIE DLQ OGRANI^ENIJh^ i (xi ; xi+1 ; : : : ; xn ; E )= h^ i+1 (xi+1 ; : : : ; xn ; hi (xi ; E )):(8)tOGDA PO OPREDELENI@F =minf1 (x1 ; f^2 (x2 ; : : : ; xn ));x2X : h^ 2 (x2 ;:::;xn ;h1 (x1 ))2ETI PO TEOREME OPTIMALXNOSTIF = xminf (x ; F (h (x )));2X 1 1 2 1 11GDE 8E1 2 E F2 (E1 ) =:1min(x2 ;:::;xn ): h^ 2 (x2 ;:::;xn ;h1 (x1 ))2ET(9)f^2 (x2 ; : : : ; xn ) =(IZ (8)) = (x ;:::;x ): h^ (x minf2 (x2 ; f^3 (x3 ; : : : ; xn )) =;:::;xn ;h (x ;E ))2ETn= xminf (x ; F (h (x ; E )))2X 2 2 3 2 2 1(POSLEDNEE RAWENSTWO SLEDUET IZ (5) S x = x2; y = (x3; : : : ; xn)),I T.D., POLAGAQ MINIMUM PO PUSTOMU MNOVESTWU RAWNYM +1, IMEEMFi (E ) =:minf^i (xi ; xi+1 ; : : : ; xn ) 8i; E(10)h^ (x ;x ;:::;x ;E )2E232iii+132212nT| SEMEJSTWO ZADA^, W KOTOROE \POGRUZILI" (7),Fi (Ei 1 ) = xminfi (xi ; Fi+1 (hi (xi ; Ei 1 ))) 8Ei 1 2 Ei 2Xi(11)| WOZWRATNOE (FUNKCIONALXNOE) URAWNENIE dp 8i = 2; n 1,Fn ( E ) =minfn (xn ):(12)xn 2Xn : hn (xn ;E )2ET62aLGORITM 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 =max hc; ziz2Bn : AzbW PREDPOLOVENII aij ; bi ; cj 2 Z+ . oBOZNA^IM ^EREZ aj j -J STOLBEC63MATRICY A. rASSMOTRIM SEMEJSTWO ZADA^ POISKAFk (E ) =:maxz: zj 2f0;1g 8j =k;:::;nnXj =knXj =kcj zjaj zj b E;GDE E 2 E =: fE 2 Zm+ j Ei bi 8i = 1; mg; k = 1; n.o^EWIDNO, F = F1 (0). wOZWRATNOE URAWNENIE W DANNOM SLU^AE:Fk (E ) = maxfFk+1 (E ); ck + Fk+1 (E + ak )g;an ;Fn (E ) = c0n ; E bINA^E.nAHODIM 8E 2 E Fn (E ) I SOOTWETSTWU@]IE xn (E ), ZATEM DLQ k =n 1; : : : ; 2 OPREDELQEM Fk (E ) I REALIZU@]IE IH xk (E ) IZ WOZWRATNOGOURAWNENIQ, WY^ISLQEM F1 (0); x1 (0) 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 (0), ESLI POSMOTRETX PO WSEM[AGAM ALGORITMA.~ISLO [AGOW PREDLOVENNOGO ALGORITMA RAWNO n I NA n-M [AGERASSMATRIWAETSQ minf(b1 + 1) : : : (bm + 1); 2n 1 g SOSTOQNIJ, NA(n 1)-M | MINIMUM IZ LEWOJ ^ASTI (RAWNOJ jEj) I 2n 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 PRINCIPE,WOZMOVNO KOMBINIROWANIE OBEIH SHEM (SM. [6]).64sODERVANIE1. wwedenie w teori` slovnostix1. pONQTIE O SLOVNOSTI RE[ENIQ ZADA^x2. NP-POLNYE (UNIWERSALXNYE) ZADA^Ix3. kLASSY SLOVNOSTI. sILXNAQ NP-POLNOTAI PSEWDOPOLINOMIALXNOSTXx4.
pRIBLIVENNOE RE[ENIE ZADA^ KOMBINATORNOJOPTIMIZACII2. osnowy linejnogo programmirowaniqx5. pONQTIE O SLOVNOSTI ZADA^ILINEJNOGO PROGRAMMIROWANIQ (lp)x6. mETOD \LLIPSOIDOWx7. tEORIQ DWOJSTWENNOSTI lp. iDEQ METODA kARMARKARA3. |lementy matemati~eskogoprogrammirowaniqx8. oBZOR IDEJ MATEMATI^ESKOGO PROGRAMMIROWANIQ (mp)x9. dWOJSTWENNOSTX W mp4. sposoby re{eniq perebornyh zada~x10. gLOBALXNAQ OPTIMIZACIQ.mETOD WETWEJ I GRANIC (mwg)x11.
cELO^ISLENNOE LINEJNOE PROGRAMMIROWANIE (clp)x12. mETOD DINAMI^ESKOGO PROGRAMMIROWANIQ (dp)6531015212429333845515458.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
