[учебник] Основы оптимизации. Новикова (1998) ([учебник] Основы оптимизации. Новикова (1998).pdf), страница 11

eSLI WSE \LEMENTY SIMPLEKS-TABLICY aij ; bi ; cjNATURALXNYE ^ISLA, TO DLQ L@BOGO RE[ENIQ x0 ZADA^I lpmax hc; xiAxb; x0WEKTOR bx0 c, SOSTAWLENNYJ IZ KOMPONENT bx0j c, BUDET DOPUSTIMYM WDANNOJ ZADA^E. pRI \TOM DLQ RE[ENIQ x SOOTWETSTWU@]EJ ZADA^I56clpmax hc; xiAxb; x2Zn+O^EWIDNA OCENKA jhc; bx0 ci hc; x ij hc; 1i.uSLOWIE POLOVITELXNOSTI ISHODNYH DANNYH WYPOLNQETSQ DLQ NEKOTORYH \KONOMI^ESKIH ZADA^. tAKOJ VE REZULXTAT MOVNO POLU^ITXDLQ RQDA MNOGOPRODUKTOWYH POTOKOWYH ZADA^ NA SETQH I DRUGIH LINEJNYH ZADA^ MAKSIMIZACII S POLOVITELXNYM c, W KOTORYH DOPUSTIMOE MNOVESTWO WMESTE S L@BOJ TO^KOJ x SODERVIT I WSE x0 S KOMPONENTAMI x0j 2 [0; xj ]. oDNAKO POISK x PO bx0 c MOVET POTREBOWATXPEREBORA 2n WARIANTOW OKRUGLENIQ KOMPONENT x0 .k SOVALENI@, W OB]EM SLU^AE I PEREBORA WSEH WOZMOVNYH WARIANTOW OKRUGLENIQ KOMPONENT RE[ENIQ NEPRERYWNOJ ZADA^I lp OKAZYWAETSQ NEDOSTATO^NO DLQ POLU^ENIQ RE[ENIQ clp (NAPRIMER, PRIn = 2, ESLI DLQ POLOVITELXNOGO c RASSMOTRETX SISTEMU OGRANI^ENIJ9x1 + 10x2 0; 8x1 + 10x2 1).

tAKIM OBRAZOM, POISK RE[ENIQclp MOVET POTREBOWATX O^ENX BOLX[OGO PEREBORA CELO^ISLENNYHTO^EK, I WOZNIKAET TA VE, ^TO I W x10, ZADA^A ORGANIZACII PEREBORAS CELX@ POPYTATXSQ EGO SOKRATITX W SLU^AE NE SAMOJ PLOHOJ ZADA^I.oDNIM IZ DOSTATO^NO UPOTREBITELXNYH METODOW PEREBORA ZDESX QWLQETSQ METOD WETWEJ I GRANIC, KOTORYJ DLQ clp BUDET RASSMOTREN WP.2.

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.