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

pOLU^ITX TEOREMU DWOJSTWENNOSTIlp KAK SLEDSTWIE TEOREMY kUNA-tAKKERA (DLQ SLU^AQ OZlp).uSLOWIQ OPTIMALXNOSTI SLUVAT OSNOWNYM INSTRUMENTOM TEORETI^ESKOGO ISSLEDOWANIQ ZADA^ USLOWNOJ OPTIMIZACII. ~TOBY ^ISLENNO (PRIBLIVENNO) NAJTI USLOWNYJ \KSTREMUM S IH POMO]X@, PRIMENQ@T METODY BEZUSLOWNOJ OPTIMIZACII DLQ POISKA SEDLOWOJ TO^KIFUNKCII lAGRANVA ILI KOMBINIRU@T [TRAFNU@ FUNKCI@ S FUNKCIEJ lAGRANVA DLQ POLU^ENIQ TO^NOGO GLADKOGO [TRAFA. k SOVALENI@, WSE \TI METODY OSTANAWLIWA@TSQ W PERWOM POPAW[EMSQ LOKALXNOM \KSTREMUME. gLOBALXNYJ OPTIMUM MOVNO ISKATX, PEREBIRAQ LOKALXNYE OPTIMUMY, NO DLQ ZADA^ NEODNOMERNOJ MINIMIZACIINE PONQTNO, KAK NAHODITX WSE LOKALXNYE OPTIMUMY. nEKOTORYE IZSU]ESTWU@]IH PODHODOW K RE[ENI@ ZADA^ GLOBALXNOJ OPTIMIZACIIPRIWODQTSQ W SLEDU@]EM PARAGRAFE.51sposoby re{eniq perebornyh zada~lITERATURA:2.

pAPADIMITRIU h., sTAJGLIC k. kOMBINATORNAQ OPTIMIZACIQ.m.: mIR, 1985.6. mINU m. mATEMATI^ESKOE PROGRAMMIROWANIE. m.: nAUKA, 1990.x10. gLOBALXNAQ OPTIMIZACIQ. mETOD WETWEJ I GRANIC4.sLU^AJNYJ I POSLEDOWATELXNYJ PEREBOR. mETOD WETWEJ I GRANIC W GLOBALXNOJ OPTIMIZACII. oPISANIE I STRATEGII METODA.1.

kAK UVE OTME^ALOSX RANEE, ZADA^I GLOBALXNOJ OPTIMIZACII(T.E. W NEWYPUKLOM SLU^AE ZADA^I OPTIMIZACII WOOB]E) QWLQ@TSQPEREBORNYMI. pEREBORNYE ALGORITMY NE \FFEKTIWNY (W RAS^ETE NAHUD[U@ ZADA^U), PO\TOMU USPEH W RE[ENII KAVDOJ KONKRETNOJ ZADA^I SU]ESTWENNYM OBRAZOM ZAWISIT OT SPOSOBA ORGANIZACII PEREBORA.eSLI MY GOTOWY OSTAWITX WOZMOVNOSTX ILI NEWOZMOVNOSTX RE[ENIQNA[EJ ZADA^I NA WOL@ SLU^AQ, TO ESTESTWENNO ISPOLXZOWATX SLU^AJNYJ PEREBOR. |TOT SPOSOB PEREBORA OBY^NO QWLQETSQ SAMYM PROSTYMI, KAK PRAWILO, \KONOMIT PAMQTX.

dLQ ZADA^I POISKA GLOBALXNOGO MINIMUMA EMU SOOTWETSTWUET SLEDU@]IJ METOD mONTE-kARLO.pUSTX RE[AETSQ ZADA^A (1) IZ x8, GDE (DLQ UPRO]ENIQ IZLOVENIQ)MNOVESTWO OGRANI^ENIJ X | EDINI^NYJ n-MERNYJ KUB. wYBIRAEM WSOOTWETSTWII S RAWNOMERNYM RASPREDELENIEM NA X SLU^AJNYE TO^KIxt , W KOTORYH WY^ISLQEM ZNA^ENIE CELEWOJ FUNKCII, ZAPOMINAEM TEKU]EE NAIMENX[EE ZNA^ENIE | REKORD | I REALIZU@]U@ EGO TO^KU.tOGDA 8" > 0 WEROQTNOSTXP(j min f (xt )tf j > ") ! 0 PRI t ! 1:sHODIMOSTX TAKOGO METODA BUDET DOWOLXNO MEDLENNOJ. pRI \TOM NEIZWESTNO, NA KAKOM RASSTOQNII OT TO^KI MINIMUMA NAHODITSQ POLU^ENNAQ REALIZACIQ.sUZIM KLASS RASSMATRIWAEMYH ZADA^ (1), PREDPOLOVIW WDOBAWOKK PREDYDU]EMU, ^TO FUNKCIQ CELI LIP[ICEWA NA X S KONSTANTOJL: f 2Lip(X; L), T.E. jf (x) f (x0 )j Lkx x0 k 8x; x0 2 X .

i NERASS^ITYWAQ NAJTI TO^NOE RE[ENIE, ZADADIMSQ PODHODQ]IM " > 0 S52CELX@ POISKA "-PRIBLIVENNOGO RE[ENIQ x" : f (x" ) f (x ) + ". (nABLIZOSTX x" I x NIKAKIH USLOWIJ NE NAKLADYWAETSQ.)tEPERX MY MOVEM PRIMENQTX METODY DETERMINIROWANNOGO PEREBORA. pASSIWNYJ (NE ISPOLXZU@]IJ PRI WYBORE O^EREDNOJ TO^KIINFORMACI@, POLU^ENNU@ DLQ PREDYDU]IH) SPOSOB POISKA PRIWOX NA PODKUBY X j TAK, ^TOBYDIT K POLNOMU PEREBORU: RAZOBXEM:j008x; x 2 X : kx x k = "=L, W KAVDOM X j BEREM PROIZWOLXNU@TO^KU xj I POLAGAEM:f (x" ) = minf (xj ):jo^EWIDNO, x" I ESTX ISKOMOE "-PRIBLIVENNOE RE[ENIE.

(dEJSTWITELXNO, 8j; 8x 2 X j f (x" ) f (xj ) f (x) + " PO USLOWI@ lIP[ICA,I, W ^ASTNOSTI, DLQ x = x IMEEM f (x" ) f (x ) + " | SOOTWETSTWIEpS OPREDELENIEM.) oDNAKO STORONA KAVDOGO j -GO PODKUBA RAWNA"=(L n), A WSEGO PODKUBOW I, SLEDOWATELXNO, WY^ISLENIJ ZNA^ENIJ CELEWOJ FUNKCII BUDET (Lpn=")n W L@BOM SLU^AE, ^TO NE MYSLIMO DAVEDLQ DESQTKA PEREMENNYH. pO\TOMU RAZRABATYWA@TSQ METODY POSLEDOWATELXNOGO PEREBORA, POZWOLQ@]IE U^ITYWATX UVE WY^ISLENNYEZNA^ENIQ I ADAPTIROWATXSQ K NEHUD[EMU SLU^A@.pREDPOLOVIM, ^TO UVE WY^ISLENY ZNA^ENIQ FUNKCII W TO^KAHx1 ; : : : ; xj 1 I REKORDNYM OKAZALOSX ZNA^ENIE f (xr ) = R.

tOGDA, ESLIf (xj ) < f (xr ), TO OBNOWLQEM REKORD r := j; R := f (xj ), A ESLI f (xj ) >f (xr ), :TO MOVNO NE WY^ISLQTX ZNA^ENIJ FUNKCII NA MNOVESTWETj (R) = fx 2 X : kx xj k (f (xj ) R)=Lg, TAK KAK \TO NE DAST NOWOGO REKORDA (IBO 8x 2 Tr f (xj ) f (x) Lkx xj k f (xj ) f (xr ), T.E.f (x) f (xr ) = R, I ZNA^IT, SREDI NIH NET GLOBALXNO-OPTIMALXNOGORE[ENIQ). oBNOWLENIE REKORDA W PRINCIPE POZWOLQET \OTBROSITX"ANALOGI^NYE MNOVESTWA Ti (R) DLQ i = 1; : : : ; j 1.eSTESTWENNO, W Ti ; Tj MOGUT POPASTX I TO^KI xk S UVE WY^ISLENNYM ZNA^ENIEM f (xk ) (KOTORYE TAKIM OBRAZOM WY^ISLQLISX ZRQ). pO\TOMU HOTELOSX BY TAK ORGANIZOWATX PEREBOR, ^TOBY PO WOZMOVNOSTIUMENX[ITX ^ISLO PODOBNYH \ZRQ[NYH" WY^ISLENIJ. k SOVALENI@,OPTIMALXNOJ STRATEGII ORGANIZACII PEREBORA DLQ MNOGOMERNYH ZADA^ NET.

iSPOLXZOWANIE SLU^AJNYH TO^EK xi PRIWODIT K PROBLEMEHRANENIQ I OBNOWLENIQ SLOVNOGO MNOVESTWA [Ti (R) ZAWEDOMO NE OPTIMALXNYH TO^EK. mETOD POSLOJNOGO PEREBORA DAET WOZMOVNOSTX SOKRA]ENIQ LI[X PO ODNOJ PEREMENNOJ. dLQ ZADA^ BOLX[OJ RAZMERNOSTI53PREDLAGAETSQ (RAZLI^NYMI AWTORAMI) SLEDU@]IJ METOD PEREBORA POSHEME WETWEJ I GRANIC.2. mETOD WETWEJ I GRANIC (mwg) DLQ GLOBALXNOJ MINIMIZACII.pUSTX x1 | CENTR KUBA X . wY^ISLQEM f (x1 ) I PRISWAIWAEM \TO ZNA^ENIE REKORDU R := f (x1 ). rAZBIWAEM KUB NA 2n ODINAKOWYH PODKUBOW X 1i SO STORONOJ 1/2 I WY^ISLQEM ZNA^ENIQ CELEWOJ FUNKCIIW IH CENTRAH: f (x1i ); i = 1; : : : ; 2n , OBNOWLQQ PO HODU WY^ISLENIJZNA^ENIE REKORDA R := mini f (x1i ). pROWERQEM WYPOLNENIE USLOWIQX 1i T1i (R) DLQ i = 1; : : : ; 2n I OTBRASYWAEM SOOTWETSTWU@]IE PODKUBY.

kAVDYJ IZ OSTAW[IHSQ RAZBIWAEM NA 2n ODINAKOWYH PODKUBOWX 2ij SO STORONOJ 1/4 I POSTUPAEM, KAK PREVDE. nA L@BOM [AGE U NASFORMIRUETSQ MNOVESTWO K \KUBIKOW" SO STORONAMI 2 l ; l 2, CELOE.pRAWILO WYBORA O^EREDNOGO KUBIKA DLQ RAZBIENIQ NAZYWAETSQ PRAWIWARIANTY PRIWODQTSQ NIVE. kUBIKI SOLOM WETWLENIQ | WOZMOVNYESTORONOJ NE BOLX[E "=(Lpn) ISKL@^A@TSQ IZ MNOVESTWA K | DROBLENIE KUBIKA ZAKAN^IWAETSQ.

tAKVE ISKL@^A@TSQ KUBIKI, POPAW[IEW MNOVESTWO Tk (R) (S INDEKSOM k | NOMEROM KUBIKA) DLQ TEKU]EGOZNA^ENIQ REKORDA, | PRAWILO OTSE^ENIQ WETWEJ. rEKORD OBNOWLQETSQ PRI POLU^ENII MENX[EGO ZNA^ENIQ CELEWOJ FUNKCII (PRAWILOPOLU^ENIQ GRANIC, T.E. OCENOK). zNA^ENIQ CELEWOJ FUNKCII WY^ISLQ@TSQ W CENTRE KAVDOGO NOWOGO PODKUBIKA, WKL@^AEMOGO W K POSLERAZBIENIQ WYBRANNOGO DLQ \TOGO KUBIKA. aLGORITM OSTANAWLIWAETSQ,KOGDA K PUSTO.uKAZANNAQ TERMINOLOGIQ I NAZWANIE METODA OPREDELQ@TSQ TEM,^TO WIZUALXNO DANNAQ SHEMA PEREBORA PREDSTAWLQETSQ W WIDE GRAFADEREWA, KORNEWAQ WER[INA KOTOROGO SOOTWETSTWUET KUBU X , WER[INY PERWOGO QRUSA | PODKUBAM X 1i , WER[INY WTOROGO QRUSA | KUBIKAM X 2ij , PODSOEDINENNYM K SWOIM POROVDA@]IM WER[INAM X 1i 1-GOQRUSA, I T.D.

eSLI KUBIK ISKL@^AETSQ IZ K, EGO WER[INA ZAKRYWAETSQ | IZ NEE NE BUDUT IDTI WETWI NA SLEDU@]IJ QRUS. eSLI KUBIK E]ENE WKL@^EN W K, EGO WER[INA E]E NE RASKRYTA. pORQDOK ZAKRYTIQWER[INY OPREDELQETSQ PRAWILOM OTSE^ENIQ (SWOIM DLQ KAVDOJ MASSOWOJ ZADA^I | SM. TAKVE W x11), PORQDOK RASKRYTIQ | PRAWILOM WETWLENIQ (SWOIM DLQ KAVDOJ INDIWIDUALXNOJ ZADA^I). rAZLI^A@T DWAWIDA PRAWIL WETWLENIQ PO TIPU POSTROENIQ DEREWA RE[ENIJ (WYBORAWER[IN DLQ RASKRYTIQ): \W [IRINU", KOGDA SNA^ALA RASKRYWA@TSQ54WSE WER[INY ODNOGO QRUSA DO PEREHODA K SLEDU@]EMU, I \W GLUBINU"| WSQKIJ RAZ RASKRYWAETSQ LI[X ODNA (OBY^NO S LU^[IM ZNA^ENIEMREKORDA) WER[INA NA QRUSE DO KONCA WETWI.

nA PRAKTIKE REALIZU@TNEKOTORU@ SMESX, NAPRIMER, PERWOE PRAWILO, POKA HWATAET MA[INNOJPAMQTI (W K NE SLI[KOM MNOGO \LEMENTOW), ZATEM PEREKL@^AEMSQ NAWTOROE. pREDPO^TITELXNOSTX TOJ ILI INOJ STRATEGII WETWLENIQ OCENIWAETSQ KAVDYM WY^ISLITELEM PO-SWOEMU, ISHODQ IZ GLAWNOJ ZADA^IMETODA WETWEJ I GRANIC | BYSTREE POLU^ITX LU^[IJ REKORD, ^TOBYOTSE^X BOLX[E WETWEJ.w RASSMATRIWAEMOJ ZADA^E ESTX HORO[IJ SPOSOB ULU^[ENIQ REKORDA | LOKALXNAQ OPTIMIZACIQ (SM. W x8).

eE IMEET SMYSL PROWODITX IZ TEKU]EJ TO^KI, W KOTOROJ PROIZO[LO OBNOWLENIE REKORDA,NAPRIMER, DELAQ NESKOLXKO [AGOW GRADIENTNOGO METODA. pRI \TOMRASPOLOVENIE KUBIKOW MENQTX NE NADO, PROSTO UWELI^IWAETSQ [ANSSOKRA]ENIQ PEREBORA (OTBRASYWANIQ BOLX[IHKUBIKOW).oTMETIM, ^TO W HUD[EM SLU^AE f = const ([Ti = ;) | NE UDAETSQ OTBROSITX NI ODNOJ TO^KI x | I PRIHODIM K POLNOMU PEREBORU;T.E.

UKAZANNAQ W P.1 \KSPONENCIALXNAQ OCENKA TO^NA NA KLASSE WSEHLIP[ICEWYH FUNKCIJ.x11. cELO^ISLENNOE LINEJNOE PROGRAMMIROWANIE (clp)oTLI^IE ZADA^ clp I lp: SU]ESTWENNAQ NELINEJNOSTX OGRANI^ENIJ TIPA CELO^ISLENNOSTI. nE\FFEKTIWNOSTX OKRUGLENIQ RE[ENIQ lp DO BLIVAJ[EGO CELOGO. sLU^AJ WPOLNE UNIMODULQRNOJ MATRICY OGRANI^ENIJ. mwg W clp. mwg DLQ BULEWA LINEJNOGO PROGRAMMIROWANIQ (blp).1.

pO-WIDIMOMU, NAIBOLEE WAVNYM KLASSOM ZADA^ GLOBALXNOJOPTIMIZACII QWLQ@TSQ ZADA^I clp. |TI ZADA^I FORMULIRU@TSQ KAKZADA^I lp S DOPOLNITELXNYM OGRANI^ENIEM CELO^ISLENNOSTI PEREMENNYH. pOSLEDNEE OGRANI^ENIE, KAKIMI BY SPOSOBAMI OT NEGO NIIZBAWLQTXSQ, \PORTIT" SWOJSTWO WYPUKLOSTI (I POLINOMIALXNOSTI)ZADA^I lp.

nAPRIMER, WYRAZIW USLOWIE CELO^ISLENNOSTI W FORMEOGRANI^ENIJ NERAWENSTW, RASSMOTRENNOJ W DOKAZATELXSTWE UTWERVDENIQ 1 x8, I SNQW IH METODOM [TRAFOW, PRIDEM K ZADA^E GLOBALXNOJOPTIMIZACII, IME@]EJ NE MENX[E LOKALXNYH \KSTREMUMOW, ^EM WARIANTOW DLQ CELO^ISLENNYH PEREMENNYH W ISHODNOJ clp. pO\TOMU55NA PRAKTIKE UDAETSQ RE[ATX ZADA^I clp TOLXKO NEBOLX[OJ RAZMERNOSTI ILI S OGRANI^ENIQMI CELO^ISLENNOSTI NE NA WSE, A LI[X NANESKOLXKO PEREMENNYH.sU]ESTWUET ^ASTNYJ KLASS ZADA^ clp, W KOTORYH OGRANI^ENIECELO^ISLENNOSTI OKAZYWAETSQ NESU]ESTWENNYM.oPREDELENIE 1. mATRICA NAZYWAETSQ WPOLNE UNIMODULQRNOJ,ESLI OPREDELITELX L@BOJ EE NEWYROVDENNOJ KWADRATNOJ PODMATRICYRAWEN PO MODUL@ 1.uTWERVDENIE 1. eSLI MATRICA OGRANI^ENIJ RAZRE[IMOJ ZADA^I lp S CELYMI KO\FFICIENTAMI WPOLNE UNIMODULQRNA, TO U NEESU]ESTWUET CELO^ISLENNOE RE[ENIE.dOKAZATELXSTWO O^EWIDNO IZ PRINCIPA GRANI^NYH RE[ENIJ(x5) I PRAWILA kRAMERA (SM.

DOKAZATELXSTWO TEOREMY 1 x5).uTWERVDENIE 2. mATRICA A WPOLNE UNIMODULQRNA TOGDA I TOLXKO TOGDA, KOGDA DLQ L@BOGO CELO^ISLENNOGO WEKTORA b WSE WER[INYMNOGOGRANNIKA Ax b; x 0 QWLQ@TSQ CELO^ISLENNYMI.dOKAZATELXSTWO W ODNU STORONU ANALOGI^NO PREDYDU]EMU, WDRUGU@ STORONU SM. SSYLKU W [2, S. 333].tAKIM OBRAZOM, WPOLNE UNIMODULQRNYMI MATRICAMI OGRANI^ENIJ W PRINCIPE OGRANI^IWAETSQ KLASS ZADA^ clp, \KWIWALENTNYHlp I, SLEDOWATELXNO, DOPUSKA@]IH \FFEKTIWNOE RE[ENIE. oTMETIM,^TO UKAZANNYJ KLASS, HOTQ I ^REZWY^AJNO UZOK S FORMALXNOJ TO^KIZRENIQ (\LEMENTAMI MATRICY A MOGUT BYTX TOLXKO 0, 1 I -1, PRI^EMPO BOLX[EJ ^ASTI 0), SOOTWETSTWUET DOSTATO^NO [IROKOMU KLASSUPRAKTI^ESKIH ZADA^ OPTIMIZACII NA GRAFAH I SETQH (ODNO- I DWUHPRODUKTOWYE SETI, DWUDOLXNYE GRAFY I T.P.).pRIWEDEM BEZ DOKAZATELXSTWA E]E ODNO POLEZNOE UTWERVDENIE, POZWOLQ@]EE W NEKOTORYH SLU^AQH POLU^ATX PRIBLIVENNOE RE[ENIEclp PUTEM RE[ENIQ lp.uTWERVDENIE 3.