Н.М. Новикова - Основы оптимизации (1125234), страница 11
Текст из файла (страница 11)
dRUGIE METODY SM. W [2,6].2. mETOD WETWEJ I GRANIC DLQ clp. rASSMATRIWAETSQ ZADA^Amax hc; zi;(1)z2Zn : AzbRE[ENIEM KOTOROJ QWLQETSQ CELO^ISLENNYJ WEKTOR z .w KORNEWOJ WER[INE METODA WMESTO ZADA^I (1) RE[AETSQ OZlpmax hc; xi;(2)x2Rn : AxbRE[ENIEM KOTOROJ QWLQETSQ WEKTOR x0 .
eSLI x0 OKAZALSQ CELO^ISLENNYM, TO z :=x0 | RE[ENIE ZADA^I (1) ZAKON^ENO. iNA^E 9x0j 62 Z IOSU]ESTWLQEM WETWLENIE PO j -J KOMPONENTE SLEDU@]IM OBRAZOM.iZ WER[INY WYHODQT DWE WETWI, I NA NOWOM QRUSE K OGRANI^ENIQMOZlp, RE[AEMOJ W POROVDA@]EJ WER[INE, DOBAWLQETSQ OGRANI^ENIE571-J WETWI ILI xj dx0j e DLQ 2-J WETWI. zNA^ENIEMAKSIMUMA W ISHODNOJ ZADA^E clp (1), O^EWIDNO, RAWNO MAKSIMALXNOMU IZ ZNA^ENIJ PODZADA^ clp NA KAVDOJ WETWI.
nO, KAK I RANEE,WMESTO PODZADA^I clp RASSMATRIWAETSQ PODZADA^A BEZ OGRANI^ENIQCELO^ISLENNOSTI. tAKAQ OZlp I RE[AETSQ W O^EREDNOJ POROVDENNOJWER[INE W SLU^AE EE RASKRYTIQ, OBOZNA^IM RE[ENIE ^EREZ xk .eSLI xk | CELO^ISLENNOE, TO WER[INA ZAKRYWAETSQ, A ZNA^ENIEhc; xk i FUNKCII CELI SRAWNIWAETSQ S REKORDOM DLQ EGO OBNOWLENIQILI, PO PERWOMU RAZU, PRISWAIWAETSQ REKORDU, I TO^KA xk | DOPUSTIMAQ TO^KA W ZADA^E (1) | ZAPOMINAETSQ. pOSLE POLU^ENIQ REKORDAMOVET BYTX ZAKRYTA L@BAQ RASKRYTAQ WER[INA, DLQ KOTOROJ OPTIMALXNOE ZNA^ENIE CELEWOJ FUNKCII OKAVETSQ MENX[E REKORDA. dEJSTWITELXNO, POSKOLXKU MAKSIMUM PO BOLX[EMU MNOVESTWU NE MENX[EMAKSIMUMA PO MENX[EMU, TO ZNA^ENIE OZlp DAET OCENKU SWERHU (GRANICU) ZNA^ENIQ SOOTWETSTWU@]EJ CELO^ISLENNOJ PODZADA^I, I KOGDAWERHNQQ OCENKA NE PREWY[AET REKORDA, BESSMYSLENNO PYTATXSQ UWELI^ITX REKORD NA DANNOJ WETWI.dRUGIM SLU^AEM ZAKRYTIQ WER[INY (OTSE^ENIQ WETWI) QWLQETSQNERAZRE[IMOSTX POSTAWLENNOJ OZlp I, SLEDOWATELXNO, TOJ VE PODZADA^I clp.eSLI xk | NECELO^ISLENNOE, TO 9xki 62 Z, I OSU]ESTWLQEM WETWLENIE PO i-J KOMPONENTE OPISANNYM WY[E SPOSOBOM.
pROCEDURAZAKAN^IWAETSQ POSLE ZAKRYTIQ WSEH WER[IN, TOGDA ZNA^ENIE (1) RAWNO TEKU]EMU REKORDU, LIBO REKORD OSTALSQ NEOPREDELENNYM I ZADA^A(1) NE IMEET RE[ENIQ.wYBOR STRATEGII WETWLENIQ W clp IGRAET NE MENX[U@ ROLX, ^EMW GLOBALXNOJ OPTIMIZACII. oTSUTSTWIE REKORDA PRIWODIT K LI[NEMU PEREBORU, NO PROCEDURA WETWLENIQ \W GLUBINU" MOVET WMESTOREKORDA DATX NESOWMESTNU@ SISTEMU OGRANI^ENIJ. kROME TOGO, DLQNESKOLXKIH NECELYH KOMPONENT xk NE PONQTNO, PO KAKOJ IZ NIH LU^[E OSU]ESTWLQTX WETWLENIE: PO NOWOJ, KOTORAQ NE RASSMATRIWALASXNA PREDYDU]IH QRUSAH, ILI SNA^ALA PEREBRATX WSE DOPUSTIMYE CELYE ZNA^ENIQ ODNOJ IZ KOMPONENT (PO ANALOGII S blp | SM. NIVE).pOSLEDNQQ STRATEGIQ IMEET SMYSL PRI NALI^II DWUSTORONNIH OGRANI^ENIJ NA PEREMENNYE.3.
mETOD WETWEJ I GRANIC DLQ blp. ~ASTNYM SLU^AEM ZADA^Ixj bx0j c DLQ58(1) clp QWLQETSQ ZADA^A blpmax hc; zi;z2Bn : Azb(3)RE[ENIE KOTOROJ | WEKTOR z0 IZ BULEWA KUBA.iZ REZULXTATOW x2 (UTWERVDENIQ 8) WYTEKAET NP-TRUDNOSTX blpI, SLEDOWATELXNO, PRAWOMERNOSTX ISPOLXZOWANIQ PEREBORNYH SHEMDLQ RE[ENIQ (3). w x12 BUDET POKAZANA SHEMA DINAMI^ESKOGO PROGRAMMIROWANIQ DLQ blp S NEOTRICATELXNYMI KO\FFICIENTAMI, ADLQ PROIZWOLXNYH ZADA^ (3) PRIMENIMA SHEMA PREDYDU]EGO PUNKTA,KOTORAQ NESKOLXKO UPRO]AETSQ ZA S^ET DOPOLNITELXNOGO OGRANI^ENIQ 0 zi 1, PREWRA]A@]EGO clp W blp.
a IMENNO, POSLEZAMENY Zn NA Bn , PRI WETWLENII W NOWYE PODZADA^I DOBAWLQETSQWMESTO OGRANI^ENIJ NERAWENSTW USLOWIE RAWENSTWA 0 (DLQ ODNOJ WETWI) ILI 1 (DLQ DRUGOJ) TOJ PEREMENNOJ, PO KOTOROJ OSU]ESTWLQETSQWETWLENIE. tAKIM OBRAZOM UKAZANNAQ PEREMENNAQ STANOWITSQ BULEWOJWO WSEH NIVNIH QRUSAH, T.E. PO NEJ NE PRIDETSQ WNOWX PROWODITX WETWLENIE, A ZNA^IT, NA n-M QRUSE RE[ENIE (3) BUDET ZAKON^ENO.
~ISLORASKRYWAEMYH WER[IN (ILI RE[ENIJ PODZADA^ lp) PRI \TOM NE PREWYSIT 2n+1 , ^TO, KONE^NO, TOVE NEMALO, NO ZAMETNO MENX[E, ^EM DLQclp (SRAWNIMO SO SLU^AEM, PREDUSMOTRENNYM UTWERVDENIEM 3).x12. mETOD DINAMI^ESKOGO PROGRAMMIROWANIQ (dp)tEORETI^ESKIE OSNOWY dp. oB]AQ SHEMA METODA. mETOD dp DLQblp S NEOTRICATELXNYMI KO\FFICIENTAMI. sWQZX S mwg.1.
e]E ODNOJ TRADICIONNO ISPOLXZUEMOJ SHEMOJ PEREBORA QWLQETSQ METOD DINAMI^ESKOGO PROGRAMMIROWANIQ (dp). oDIN PRIMERALGORITMA dp PRIWODILSQ W x4, GDE \TOD METOD POZWOLIL POSTROITXPSEWDOPOLINOMIALXNYJ ALGORITM RE[ENIQ ZADA^I O R@KZAKE. wOOB]EGOWORQ, PODOBNYE ALGORITMY I NADE@TSQ POLU^ITX PUTEM PRIMENENIQSHEMY dp. 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 f2 ,ESLI ONA RAZDELQEMA NA f1 , f2 I FUNKCIQ f1 MONOTONNO NE UBYWAET POPOSLEDNEMU ARGUMENTU.tEOREMA 1 (OPTIMALXNOSTI DLQ RAZLOVIMYH FUNKCIJ).min f (x; y) = minf (x; minf (y));x 1y 2I TO^NO TAK VE DLQ max.dOKAZATELXSTWO PROWEDEM DLQ SLU^AQ MINIMUMA.(rAWENSTWO BUDET WYTEKATX IZ PARY PROTIWOPOLOVNYH NERAWENSTW.)f (x; f2 (y)) f1 (x0 ; f2 (y0 )) 8x0 ; y0pO OPREDELENI@ MINIMUMA minx;y 1(x;y)f (y); x0 := arg minf (x; f2 (y0 ));I; SLEDOWATELXNO; DLQ y0 := arg miny 2x 1^TO DOKAZYWAET NERAWENSTWO \".
aNALOGI^NO, W SILU NEUBYWANIQ f1PO POSLEDNEMU ARGUMENTU, f1 (x0 ; miny f2 (y)) f1 (x0 ; f2 (y0 )) 8x0 ; y0 :f (x0 ; f2 (y)); x0 := arg minf (x; f2 (y))g:pOLOVIM y0 := arg minfminy 1xy 1pOSKOLXKU POWTORNYJ min RAWEN DWOJNOMU, W PRAWOJ ^ASTI POLU^ILIminx;y f (x; y), ^EM DOKAZALI I NERAWENSTWO \".dLQ ZADA^I USLOWNOJ OPTIMIZACII TEOREMA OPTIMALXNOSTI DLQRAZLOVIMYH FUNKCIJ PEREPISYWAETSQ SLEDU@]IM OBRAZOM:min f (x; y) = x: Yminf (x; min f (y));6 ; 1 y2Y (x) 2(x)=(x;y)2(5)GDE Y (x) = fyj (x; y) 2 g.
uKAZANNAQ TEOREMA ISPOLXZUETSQ DLQPONIVENIQ RAZMERNOSTI OPTIMIZACIONNYH ZADA^ I W METODE dp.dLQ NA^ALA RASSMOTRIM ZADA^U OPTIMIZACII, ZAPISANNU@ W WIDEf =min f (x; y); x 2 X Rn; y 2 Y (x) Rk: (6)g(x;y)2E RmTzDESX ET NAZYWAETSQ MNOVESTWOM TERMINALXNYH SOSTOQNIJ SISTEMYPO ASSOCIACII S DINAMI^ESKIMI SISTEMAMI UPRAWLENIQ, DLQ OPTIMIZACII KOTORYH BYLO IZOBRETENO dp. nAPRIMER, DLQ g = (g1 ; : : : ; gm ),60ESLI OGRANI^ENIQ ZADA^I ZADANY W FORME gi (x; y) 0 8i = 1; m, TOET = Rm . pUSTX f RAZLOVIMA (4), A g RAZDELQEMA:g(x; y) = 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 0 .
fUNKCII h1 ; h2 NAZYWA@TSQ FUNKCIQMI PEREHODA, WEKTORY E; E 0 | SOSTOQNIQMI SISTEMY. mNOVESTWO WSEH WOZMOVNYHSOSTOQNIJ SISTEMYOBOZNA^AETSQ E I FORMALXNO ZADAETSQ TAK:1) E h1(X ) =: fh1(x)j x 2 X g,2) 8E 2 h1(X ) fh2(y; E )jy 2 Y (X )g E(MNOVESTWO W KA^ESTWE ARGUMENTA OZNA^AET OB_EDINENIE PO WSEM ARGUMENTAM IZ \TOGO MNOVESTWA).rASSMOTRIM DLQ (6) SEMEJSTWO ZADA^ POISKAF2 (E ) =miny: h2 (y;E )2ETf2 (y);KOTORYE NUVNO RE[ATX 8E 2 E . pO TEOREME OPTIMALXNOSTIf = xminf (x; F2 (h1 (x))):2X 1w REZULXTATE ZADA^A (6) SWELASX K POSLEDOWATELXNOSTI jEj + 1 OPTIMIZACIONNYH ZADA^ MENX[EJ RAZMERNOSTI.w METODE dp DANNAQ PROCEDURA PRIMENQETSQ REKURSIWNO K ZADA^EF =ming(x1 ;:::;xn )2ET Rmf (x1 ; : : : ; xn )(7)DLQ SWEDENIQ K SEMEJSTWU ODNOMERNYH ZADA^ SLEDU@]IM OBRAZOM.pUSTX f POSLEDOWATELXNO RAZLOVIMA, T.E.f (x1 ; : : : ; xn ) =f^2 (x2 ; : : : ; xn ) =::::::::::::::::::f^n 1 (xn 1 ; xn ) =f1 (x1 ; f^2 (x2 ; : : : ; xn ));f2 (x2 ; f^3 (x3 ; : : : ; xn ));:::::::::::::::::::::fn 1 (xn 1 ; fn (xn ));I WSE fi MONOTONNO NE UBYWA@T PO 2-MU ARGUMENTU.
pUSTX g POSLEDOWATELXNO RAZDELQEMA, T.E. 9E Rm ; 9 FUNKCII PEREHODA h1 ; h2 ; : : : ; hn :618x 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 = 1; n 1.oBOZNA^IM 8i = 2; n 1; 8E 2 E ^EREZ h^ i (xi ; xi+1 ; : : : ; xn ; E )FUNKCI@, OPREDELQEMU@ REKURRENTNO RAWENSTWAMI: Ei0 = hi(xi; E ),:Ei0+1 = hi+1 (xi+1 ; Ei0 ); : : : ; En0 = hn (xn ; En0 1 ) = h^ i (xi ; xi+1 ; : : : ; xn ; E ).zAMETIM, ^TO W SLU^AE E = Ei 1 : h^ i (xi ; xi+1 ; : : : ; xn ; Ei 1) = g(x) IEj0 = Ej 8j i.
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).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
