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

w SLU^AE RAZRE[IMOSTI OPTIMALXNYE ZNA^ENIQ CELEWYH FUNKCIJ W OBEIH ZADA^AHSOWPADA@T, T.E. d = d , GDE d | ZNA^ENIE (2), d | ZNA^ENIE (7).dOKAZATELXSTWO PROWEDEM DLQ SLU^AQ OZlp, POSKOLXKU L@BAQZADA^A lp ADEKWATNO PREDSTAWLQETSQ W TAKOJ FORME.pUSTX ZADA^A (2) RAZRE[IMA, TOGDA (4) QWLQETSQ SLEDSTWIEM (1)8d d I NE QWLQETSQ 8d < d , ^TO PO AFINNOJ LEMME fARKA[A\KWIWALENTNO RAZRE[IMOSTI (5) PRI d d I NERAZRE[IMOSTI (5)PRI d < d , T.E. d = minfdj (5)g, A \TO I ESTX ZNA^ENIE (7).i NAOBOROT, IZ RAZRE[IMOSTI (7) SLEDUET NERAZRE[IMOSTX (6),IBO W PROTIWNOM SLU^AE min W (7) OBRA]ALSQ BY W 1 (TAK KAKPRIBAWLENIE RE[ENIQ (6) K RE[ENI@ (7) DAET DOPUSTIMU@ TO^KU IUMENX[AET ZNA^ENIE CELEWOJ FUNKCII (7)).

oTS@DA POLU^AEM RAZRE[IMOSTX (1) PO LEMME fARKA[A O NERAZRE[IMOSTI. kROME TOGO,RAZRE[IMOSTX (7) OZNA^AET RAZRE[IMOSTX (5) DLQ L@BOGO d d ,TAK ^TO (4) OKAZYWAETSQ SLEDSTWIEM (1) DLQ d d , I PO\TOMU dOGRANI^IWAET SWERHU ZNA^ENIE (2), T.E. MAKSIMUM W (2) DOSTIGAETSQ.tAKIM OBRAZOM POLU^ILI RAZRE[IMOSTX ZADA^I (2) I MOVEM WERNUTXSQ K NA^ALU DOKAZATELXSTWA DLQ USTANOWLENIQ RAWENSTWA d = d .iZ TEOREMY 4 NEPOSREDSTWENNO POLU^AEMuTWERVDENIE zADA^A lp OPTIMIZACII \KWIWALENTNA RE[ENI@ SISTEMY LINEJNYH NERAWENSTW.dEJSTWITELXNO, OZlp (2) \KWIWALENTNA ZADA^E lp (7) I OBE ONI\KWIWALENTNY SISTEME ln OTNOSITELXNO NEIZWESTNYH (x; ):Ax b; hc; xi = hb; i; A = c; 0:(8)A=c; 043.36uTWERVDENIE 4. zADA^A lp OPTIMIZACII \KWIWALENTNA RE[ENI@ SISTEMY LINEJNYH URAWNENIJ W NEOTRICATELXNYH PEREMENNYH.dOKAZATELXSTWO. oT SISTEMY ln (8) PEREHODIM K OGRANI^ENIQM W KANONI^ESKOJ FORME ANALOGI^NO UPRAVNENIQM 5,7.uTWERVDENIE 5.

zADA^A lp \KWIWALENTNA POISKU NEOTRICATELXNOGO NENULEWOGO RE[ENIQ ODNORODNOJ SISTEMY LINEJNYH URAWNENIJ.dOKAZATELXSTWO. nA OSNOWANII UTWERVDENIQ 4 OZlp SWODITSQK NEKOTOROJ SISTEME ln (S CELYMI KO\FFICIENTAMI) OTNOSITELXNOWEKTORA WE]ESTWENNYH NEIZWESTNYH y:^ y 0;(9)P^ y = q;PUSTX P^ | MATRICA (K (N 1)). wWEDEM PARAMETR R^ , MAVORIRU@]IJ KOORDINATY KAKOGO-TO RE[ENIQ (9) (PO TEOREME O GRANICAHRE[ENIJ), ESLI SISTEMA (9) RAZRE[IMA. dOBAWIM K (9) NERAWENSTWO^hy; ei = y1 + : : : + yN 1 NR;KOTOROE PREWRATIM W RAWENSTWO S POMO]X@ DOPOLNITELXNOJ PEREMENNOJ yN : hy;^ ei = y1 + : : : + yN 1 + yN = NR^ , A (9) PEREPI[ETSQ KAK[P^ j0]^y = q;^ y^: 0.

tEPERX SDELAEM ZAMENU PEREMENNYH x := y=R^ ^IOBOZNA^IM P = NR^ [P^ j0] [^qjq^j : : : jq^]. pRIDEM K ODNORODNOJ SISTEMEP x = 0 S DOPOLNITELXNYMI OGRANI^ENIQMI x = (x1 ; : : : ; xN ) 0,hx; ei = N , ^TO SOOTWETSTWUET SISTEME P x = 0; x 0; hx; ei > 0 SRE[ENIQMI-LU^AMI tx0 8t > 0, L@BOE IZ KOTORYH PERES^ITYWAETSQW RE[ENIE ISHODNOJ SISTEMY.2. mETOD kARMARKARA (N. Karmarkar, 1984 G.). wOSPOLXZUEMSQUTWERVDENIEM 5 I: OBOZNA^ENIQMI, WWEDENNYMI PRI EGO DOKAZATELXSTWE. pUSTX p(x) = (hp1 ; xi)2 + : : : + (hpK ; xi)2 , GDE pi | STROKI P .tOGDA p(x) = 0 \KWIWALENTNO P x = 0.

wWEDEM FUNKCI@ kARMARKARAk(x) =:[p(x)]N=2x1 x2 : : : xN:pRIMENQQ TEOREMU 2 I ALGORITM OKRUGLENIQ K ZADA^E RE[ENIQ (9),MOVNO POKAZATX, ^TO DLQ TO^NOGO EE RE[ENIQ DOSTATO^NO NAJTI TAKOJx^ > 0, DLQ KOTOROGO k(^)x 1=[3((P^ ))N ] [3, S. 25{26].pOLINOMIALXNYJ ALGORITM POISKA NUVNOGO PRIBLIVENNOGO x^PRIWODITSQ W [3, S. 26{28], I MY NE BUDEM EGO OPISYWATX. oTMETIM37TOLXKO, ^TO ANALOGI^NYJ ALGORITM MOVET BYTX POSTROEN NA OSNOWANII PRIMENENIQ METODA nX@TONA (SM. W RAZD.3) K ZADA^E MINIMIZACII FUNKCII kARMARKARA ILI EJ PODOBNYH. w REZULXTATE POLU^AEMCELYJ KLASS POLINOMIALXNYH ALGORITMOW lp, KOTORYE NA PRAKTIKE OKAZYWA@TSQ SRAWNIMYMI S SIMPLEKS-METODOM, NE IMEQ TEORETI^ESKIH NEDOSTATKOW POSLEDNEGO.

pREDLOVENNYE ALGORITMY STROQTSQNA PRINCIPIALXNO NOWOJ IDEE: NE DISKRETNOJ, A NEPRERYWNOJ TRAKTOWKI ZADA^I lp, KOGDA WMESTO PEREBORA KONE^NOGO ^ISLA UGLOWYHTO^EK OSU]ESTWLQ@T POISK RE[ENIQ W ISHODNOM PROSTRANSTWE WE]ESTWENNYH PEREMENNYH, I TRAEKTORII ALGORITMOW NE PROHODQT ^EREZUGLOWYE TO^KI.

nAPOMNIM, ^TO METOD \LLIPSOIDOW TAKVE NE ORIENTIRUETSQ NA UGLOWYE TO^KI MNOGOGRANNIKA OGRANI^ENIJ. hARAKTERNO,^TO IMENNO TAKOJ UHOD OT DISKRETNOGO PROGRAMMIROWANIQ POZWOLILPOSTROITX POLINOMIALXNYE ALGORITMY lp. pO\TOMU DALEE BUDET DANNEKOTORYJ OBZOR OSNOWNYH PODHODOW K RE[ENI@ NEPRERYWNYH ZADA^OPTIMIZACII.zAME^ANIE. eSLI BY RE^X [LA O NEPOSREDSTWENNOM POISKE TO^NOGO RE[ENIQ ZADA^I lp UKAZANNYMI METODAMI, TO NELXZQ BYLO BY GARANTIROWATX KONE^NO[AGOWOSTX (NE TO, ^TO POLINOMIALXNOSTX) SOOTWETSTWU@]IH ALGORITMOW.

dLQ IH PRIMENENIQ SU]ESTWENNOJ QWLQETSQ WOZMOVNOSTX OSTANOWKI W PRIBLIVENNOM RE[ENII BLAGODARQ NALI^I@ POLINOMIALXNOGO ALGORITMA OKRUGLENIQ. nO POSKOLXKU DLQ EGORABOTY TREBUETSQ NA^ALXNOE PRIBLIVENIE IZ OPREDELENNOJ OKRESTNOSTI RE[ENIQ, ZAWISQ]EJ OT DLINY l ILI WYSOTY h, ILI DLINYWHODA L KONKRETNOJ ZADA^I lp, TO I ^ISLO ITERACIJ ALGORITMOW, BAZIRU@]IHSQ NA RASSMATRIWAEMOM PRINCIPE, ZAWISIT OT ^ISLA CIFR WZAPISI \LEMENTOW MATRICY OGRANI^ENIJ. tAK ^TO NE UDAETSQ ISPOLXZOWATX DANNU@ IDE@ DLQ POSTROENIQ SILXNOPOLINOMIALXNYH ALGORITMOW lp, KROME KAK W ^ASTNYH SLU^AQH OGRANI^ENNOSTI \LEMENTOWMATRICY (NAPRIMER, W ZADA^AH NA GRAFAH I SETQH, GDE aij = 0; 1).383.|lementy matemati~eskogoprogrammirowaniq (mp)lITERATURA:4.

kARMANOW w. g. mATEMATI^ESKOE PROGRAMMIROWANIE. m.: nAUKA,1986.5. sUHAREW a. g., tIMOHOW a. w., fEDOROW w. w. kURS METODOWOPTIMIZACII. m.: nAUKA, 1985.6. mINU m. mATEMATI^ESKOE PROGRAMMIROWANIE. m.: nAUKA, 1990.x8. OBZOR IDEJ mpkLASSIFIKACIQ ZADA^ mp. pREIMU]ESTWA WYPUKLOGO SLU^AQ.pONQTIE O GRADIENTNYH I nX@TONOWSKIH METODAH MINIMIZACII.uSLOWNAQ OPTIMIZACIQ, SPOSOBY OSWOBOVDENIQ OT OGRANI^ENIJ(METODY BARXEROW I [TRAFOW).1. zADA^A lp, KAK I ZADA^A MINIMIZACII FUNKCII kARMARKARA,QWLQETSQ ^ASTNYM SLU^AEM ZADA^I mr:min f (x):(1)f (x) 2 Arg xminf (x); T:E:zDESX TREBUETSQ NAJTI arg xmin2X2Xx 2 X =: fx 2 X j f (x ) f (x) 8x 2 X g; I f = f (x ): (2)l@BOJ TAKOJ x NAZYWAETSQ RE[ENIEM (1); f | ZNA^ENIE (1), ILIOPTIMALXNOE ZNA^ENIE CELEWOJ FUNKCII f W ZADA^E (1), X | MNOVESTWO OGRANI^ENIJ ILI DOPUSTIMOE MNOVESTWO.w ZAWISIMOSTI OT PRIRODY MNOVESTWA X ZADA^I OPTIMIZACIIKLASSIFICIRU@TSQ KAK: DISKRETNYE (KOMBINATORNYE) | X KONE^NO ILI S^ETNO, CELO^ISLENNYE | xj 2 Z, BULEWY | xj 2 B, WE]ESTWENNYE (NEPRERYWNYE) | X Rn , BESKONE^NOMERNYE ILI WFUNKCIONALXNOM PROSTRANSTWE, NAPRIMER, KOGDA X | PODMNOVESTWOGILXBERTOWA PROSTRANSTWA L2 , I T.P.

w DANNOM RAZDELE BUDEM PO PREIMU]ESTWU RASSMATRIWATX ZADA^I S WE]ESTWENNYMI PEREMENNYMI,KOTORYE SOBSTWENNO I NAZYWA@TSQ (TRADICIONNO) ZADA^AMI MATEMATI^ESKOGO PROGRAMMIROWANIQ (zmp). eSLI X Rn , TO GOWORIM OZADA^E USLOWNOJ OPTIMIZACII (PRI USLOWII x 2 X ), INA^E (X = Rn )POLU^AEM ZADA^U BEZUSLOWNOJ OPTIMIZACII.x2 X39dLQ zmp MINIMUM W (1) DOSTIGAETSQ W USLOWIQH TEOREMY wEJER[TRASSA (f NEPRERYWNA, X KOMPAKTNO ILI DLQ NEKOTOROGO x^ 2 XOGRANI^ENO MNOVESTWO lEBEGA FUNKCII f | fx 2 X jf (x) f (^)x g).kROME RAZDELENIQ NA USLOWNYE I BEZUSLOWNYE, zmp KLASSIFICIRU@TSQ PO SWOJSTWAM CELEWOJ FUNKCII I MNOVESTWA OGRANI^ENIJ SOOTWETSTWENNO NA ZADA^I lp, WYPUKLOGO PROGRAMMIROWANIQ, GLADKIEILI NEGLADKIE I DR. dLQ KAVDOGO IZ KLASSOW zmp RAZRABATYWA@TSQ SWOI ^ISLENNYE METODY IH RE[ENIQ. s TO^KI ZRENIQ ^ISLENNYHMETODOW SU]ESTWENNO TAKVE RAZDELENIE NA LOKALXNU@ I GLOBALXNU@OPTIMIZACI@. w OPREDELENII (2) RE^X IDET O GLOBALXNOM MINIMUME,KOTORYJ, ODNAKO, NAJTI NE PROSTO, I PO\TOMU ZADA^U STARA@TSQ SWESTI K DISKRETNOJ OPTIMIZACII NA MNOVESTWE LOKALXNYH MINIMUMOW.oPREDELENIE 1.

tO^KA x0 2 X NAZYWAETSQ TO^KOJ LOKALXNOGOMINIMUMA W zmp (1), ESLI 9" > 0 : f (x0 ) f (x) 8x 2 X \ O" (x0 ).zDESX I DALEE O" (x) OBOZNA^AET "-OKRESTNOSTX TO^KI x.dLQ POISKA LOKALXNOGO MINIMUMA PRIMENQ@TSQ SPECIALXNYE METODY, KOTORYE PRI OPREDELENNYH PREDPOLOVENIQH OKAZYWA@TSQ \FFEKTIWNYMI. tOGDA KAK OB]AQ ZADA^A GLOBALXNOJ OPTIMIZACII QWLQETSQ NP-TRUDNOJ.

dEJSTWITELXNO K NEJ SWODITSQ NP-POLNAQ.uTWERVDENIE 1. cln/zmp.dOKAZATELXSTWO. pOSKOLXKU ZADA^A ln QWLQETSQ ^ASTNYM SLU^AEM ZADA^I lp, TO DLQ SWEDENIQ cln K zmp DOSTATO^NO PREDSTAWITX USLOWIE CELO^ISLENNOSTI PEREMENNYH W WIDE OGRANI^ENIJ(NERAWENSTW) NA WE]ESTWENNYE PEREMENNYE, ^TO NETRUDNO SDELATX,NAPRIMER, TAK: fxj 2 Zg \KWIWALENTNO fxj 2 Rj sin2 (xj ) 0g.pO\TOMU METODY GLOBALXNOJ OPTIMIZACII BUDUT RASSMOTRENY WRAZD.4, A W DANNOM PARAGRAFE OSTANOWIMSQ NA POISKE LOKALXNOGO \KSTREMUMA. oTMETIM, ^TO DLQ RQDA \KSTREMALXNYH POSTANOWOK ZADA^FIZIKI TO^KI LOKALXNOGO \KSTREMUMA IME@T SAMOSTOQTELXNOE ZNA^ENIE. kROME TOGO, SU]ESTWUET CELYJ KLASS zmp, DLQ KOTOROGO LOKALXNYJ \KSTREMUM SOWPADAET S GLOBALXNYM MINIMUMOM, \TO | ZADA^IWYPUKLOGO PROGRAMMIROWANIQ.oPREDELENIE 2.