Н.М. Новикова - Основы оптимизации (курс лекций) (1162379), страница 7
Текст из файла (страница 7)
oKAZYWAETSQ, DRUGIH SLEDSTWIJ U lnNE BYWAET. a IMENNO SPRAWEDLIWA34lEMMA fARKA[A(AFINNAQ). lINEJNOE NERAWENSTWO (4) QWLQETSQSLEDSTWIEM RAZRE[IMOJ W WE]ESTWENNYH PEREMENNYH SISTEMY ln (1)TOGDA I TOLXKO TOGDA, KOGDA SU]ESTWUET WEKTOR 2 Rm :c=Xi2Mi ai ; d Xi2Mi bi ; i 0 8i 2 M:(5)(sHEMU DOKAZATELXSTWA SM. W [3, S.
18].)dLQ NERAZRE[IMOJ SISTEMY ln (1) MOVNO FORMALXNO S^ITATXSLEDSTWIEM (1) ZAWEDOMO NEWERNOE NERAWENSTWO h0; xi 1 I DALEEPOLXZOWATXSQ AFINNOJ LEMMOJ fARKA[A, KAK POKAZYWAETlEMMA fARKA[A O NERAZRE[IMOSTI. sISTEMA ln (1) NERAZRE[IMA TOGDA I TOLXKO TOGDA, KOGDA RAZRE[IMA SISTEMAi ai = 0;i bi 1; i 0 8i 2 M:(6)XXi2Mi2MdOKAZATELXSTWO. pUSTX (1) NERAZRE[IMA, TOGDA IZ RAZRE[IMOSTI SISTEMY hai ; xi + xn+1 bi 8i 2 M DOLVNO SLEDOWATX, ^TOxn+1 " < 0, T.E.
SLEDSTWIEM \TOJ SISTEMY QWLQETSQ NERAWENSTWOh(0; : : : ; 0; 1="); (x; xn+1 )i 1 IPIZ AFINNOJ LEMMY fARKA[A POLU^AEM (6) (A TAKVE W DOPOLNENIE i = 1="). eSLI VE (6) RAZRE[IMA,TO UKAZANNOE WY[E NERAWENSTWO h0; xi 1 OKAZYWAETSQ SLEDSTWIEM(1) I DOLVNO WYPOLNQTXSQ DLQ WSEH x, UDOWLETWORQ@]IH (1), ZNA^IT,TAKIH NE SU]ESTWUET.tEPERX MY MOVEM DOKAZATX OSNOWNOJ TEORETI^ESKIJ REZULXTATlp | TEOREMU DWOJSTWENNOSTI, NA KOTOROJ BAZIRU@TSQ KAK METODYRE[ENIQ ZADA^ lp, TAK I SPOSOBY ANALIZA RE[ENIQ, I KOTORAQ FAKTI^ESKI DAET NEOBHODIMYE I DOSTATO^NYE USLOWIQ OPTIMALXNOSTI Wlp. nALI^IE DWOJSTWENNOSTI, OBUSLOWIW HORO[U@ HARAKTERIZACI@ZADA^I ln, PREDOPREDELILO POLINOMIALXNOSTX lp.oPREDELENIE 4.
dWOJSTWENNOJ K ZADA^E lp NA MAKSIMUM S OGRANI^ENIQMI NERAWENSTWAMI W FORME OZlp (2) NAZYWAETSQ SLEDU@]AQZADA^A lp NA MINIMUM S OGRANI^ENIQMI W KANONI^ESKOJ FORME:min fXi2Mi bi jXi 2Mi ai = c; i 0 8i 2 M g; ILI W KRATKOJ ZAPISI35min h; bi:(7)dLQ TOGO, ^TOBY POSTROITX DWOJSTWENNU@ K PROIZWOLXNOJ ZADA^E lp,NADO PREDSTAWITX EE W FORME OZlp, PRIMENITX FORMULU (7), A ZATEMWERNUTXSQ K OBOZNA^ENIQM ISHODNOJ ZADA^I.upravnenie 7.
pOKAZATX, ^TO DWOJSTWENNAQ ZADA^AK DWOJSTWENNOJ ZADA^E lp SOWPADAET S PRQMOJ ZADA^EJ lp:PREDSTAWITX (7) W FORME OZlp (ANALOGI^NO UPRAVNENI@ 5), WYPISATXDWOJSTWENNU@ K POLU^ENNOJ ZADA^E I SWESTI EE K (2).tEOREMA (DWOJSTWENNOSTI lp). zADA^A lp RAZRE[IMA TOGDAI TOLXKO TOGDA, KOGDA RAZRE[IMA DWOJSTWENNAQ K NEJ. 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:P^ y = q;^ y 0;(9)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^ ^I^^OBOZNA^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 : : : x N: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)zDESX TREBUETSQ NAJTI arg xminf (x) 2 Arg xminf (x); T:E:2X2Xx 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.x 2X39dLQ zmp MINIMUM W (1) DOSTIGAETSQ W USLOWIQH TEOREMY wEJER[TRASSA (f NEPRERYWNA, X KOMPAKTNO ILI DLQ NEKOTOROGO x^ 2 Xx g).OGRANI^ENO MNOVESTWO lEBEGA FUNKCII f | fx 2 X jf (x) f (^)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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
