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

tOGDAWENSTW M + =: fij hai ; x01 i > bi g M n M (x1 ) I RASSMOTRIM NA OTREZKE[x1; x01] BLIVAJ[U@+K x01 1TO^KU, W KOTOROJ E]E WYPOLNENY WSE NERAWENSTWA DLQ i 2 M (W x ONI WYPOLNENY S "1 -ZAPASOM). a IMENNOOPREDELIMbi hai ; x imin bi hai; x i ; i1 =: arg imini2M hai ; x01 i hai ; x1 i2M hai ; x01 i hai ; x1 iI PRISWOIM x2 := (1 )x1 + x01 .

iMEEM M (x2 ) M (x1 ) [ fi1 g, IBONERAWENSTWA S INDEKSAMI IZ M (x1 ) "1 -PRIBLIVENNO WYPOLNQLISXKAK RAWENSTWA NA WSEM OTREZKE [x1 ; x01 ], A NERAWENSTWO S INDEKSOMi1 2 M + , NE WYPOLNENNOE W TO^KE x01 , WYPOLNQETSQ W x2 KAK RAWENSTWOPO POSTROENI@. tAKIM OBRAZOM, M (x2 ) M (x1 ), NO jM (x)j m,PO\TOMU, POWTORQQ UKAZANNU@ PROCEDURU S ZAMENOJ x1 NA x2 I T.D.,PRIDEM NE BOLEE ^EM ^EREZ max(n; m) [AGOW K TOMU, ^TO RE[ENIE x0SOOTWETSTWU@]EJ SISTEMY RAWENSTW OKAVETSQ x0 | RE[ENIEM (1).s U^ETOM POLINOMIALXNOSTI ZADA^I RE[ENIQ SISTEM URAWNENIJPREDLOVENNYJ ALGORITM OKRUGLENIQ POLINOMIALEN.

=:11++30aNALOGI^NYJ ALGORITM IMEETSQ I DLQ OKRUGLENIQ "2 -PRIBLIVENNOGO RE[ENIQ OZlp x" DO TO^NOGO x (SM. [3, S. 21]). pO\TOMU DLQ POSTROENIQ POLINOMIALXNOGO ALGORITMA RE[ENIQ OZlp OSTALOSX UKAZATX POLINOMIALXNYJ ALGORITM POISKA "2 -PRIBLIVENNOGO RE[ENIQOZlp W [ARE kxk n1=2 ILI UDOSTOWERENIQ, ^TO TAKOGO RE[ENIQNET (PO TEOREMAM 1,2 IZ x5). tREBUEMYJ ALGORITM, OSNOWANNYJ NAMETODE \LLIPSOIDOW, KOTORYJ PREDLOVILI W 1976{77 GG. d.

b. `DINI a. s. nEMIROWSKIJ I (NEZAWISIMO) n. z. {OR, PRIWODITSQ W SLEDU@]IH PUNKTAH.zDESX I DALEE =: (D), GDE MATRICA D ZADAETSQ TABLICEJ (3).2. pUSTX E | PROIZWOLXNYJ \LLIPSOID W Rn S CENTROM I NENULEWOGO OB_EMA volE . rASSMOTRIM (n 1)-MERNU@ PLOSKOSTX, ZADANNU@ WEKTOROM g NORMALI I PROHODQ]U@ ^EREZ CENTR \LLIPSOIDA E .oBOZNA^IM ^EREZ E (g) ODIN IZ DWUH POLU\LLIPSOIDOW, NA KOTORYERAZBIWAET E DANNAQ PLOSKOSTX, E (g) = E \ fxj hg; x i 0g:uTWERVDENIE 1. pOLU\LLIPSOID E (g) \LLIPSOIDA E MOVNO CELIKOM ZAKL@^ITX W NOWYJ \LLIPSOID E 0 , IME@]IJ OB_EM, STROGOMENX[IJ E ,volE 0 < e 1=(2n+2);()volEI E 0 MOVNO WY^ISLITX PO E (g) ZA O(n2 ) ARIFMETI^ESKIH OPERACIJ.dOKAZATELXSTWO.

pUSTX E | EDINI^NYJ [AR S CENTROM W TO^KE0: E = fx 2 Rn : kxk 1g, A E (g) = E \fxn 0g. pOMESTIM CENTR1 ), TOGDAE 0 W TO^KU 0 = (0; : : : ; 0; n+121E 0 = fxj (x21 + : : : + x2n 1 )= 2 + (xn)2=2 1g;n+1GDE =: 1 1=(n + 1) < e 1=(n+1) ; 2 =: 1 + 1=(n2 1) < e1=(n2 1) :oTNO[ENIE OB_EMOW RAWNO PROIZWEDENI@ POLUOSEJ n 1 < e 1=(2n+2) ,OTS@DA POLU^AEM (), IBO L@BOJ \LLIPSOID MOVNO PREWRATITX W [ARAFINNYM PREOBRAZOWANIEM KOORDINAT, SOHRANQ@]IM OB_EM. dEJSTWITELXNO, BUDEM PREDSTAWLQTX PROIZWOLXNYJ \LLIPSOID E S POMO]X@ EGO CENTRA I MATRICY Q (n n), ZADA@]EJ UKAZANNOEPREOBRAZOWANIE: E = fxj x = + Qy; kyk 1g.

oBOZNA^IM =: QT g=kQT gk,GDE WERHNIJ INDEKS T | ZNAK TRANSPONIROWANIQ. tOGDA 0 I Q0 , PREDSTAWLQ@]IE \LLIPSOID E 0 MINIMALXNOGO OB_EMA, OPISANNYJ WOKRUG31POLU\LLIPSOIDA E (g), PERES^ITYWA@TSQ PO FORMULAM0 = 1 Q;n+1Q0 =np(n2fQ + ( nn + 11 1)QT g1)rZA O(n2 ) ARIFMETI^ESKIH OPERACIJ.3. mETOD \LLIPSOIDOW POLU^ENIQ "-PRIBLIVENNOGO RE[ENIQ"OZlp. pOLOVIM " := "2 =: 1=(2n2 3 ). wWEDEM: n1=MNOVESTWO2 S CENTROMR=PRIBLIVENNYHRE[ENIJOZlpW[ARERADIUSAW 0: X" =: fxj hai ; xi bi + " 8i = 1; m; hc; xi d "; kxk Rg:wYBEREM UKAZANNYJ WY[E [AR W KA^ESTWE NA^ALXNOJ ITERACII DLQ\LLIPSOIDA E X" . rASSMOTRIM PROIZWOLXNU@ ITERACI@.pROWERQEM, QWLQETSQ LI CENTR \LLIPSOIDA E "-PRIBLIVENNYMRE[ENIEM.

eSLI DA, TO ALGORITM ZAKAN^IWAET SWO@ RABOTU, W PROTIWNOM SLU^AE STROIM \LLIPSOID E 0 DLQ O^EREDNOJ ITERACII KAK MINIMALXNYJ PO OB_EMU \LLIPSOID, SODERVA]IJ POLU\LLIPSOID E (g)(SM. P.2), GDE WEKTOR g OPREDELQETSQ SLEDU@]IM OBRAZOM. tAK KAK 62 X" , TO LIBO100) 9i : hai; i > bi + ", I TOGDA g := ai, LIBO2 ) hc; i < d " I g := c.uBEDIMSQ, ^TO PRI \TOM X" E 0 . dEJSTWITELXNO, DLQ WARIANTA 108x 2 X" hai ; xi bi + " < hai ; i, T.E. X" E \ fxj hai ; x i 0g =E (ai ) E 0 ; I ANALOGI^NO POLU^IM DLQ WARIANTA 20X" E \ fxj hc; x i 0g = E ( c) E 0 .tEPERX S E := E 0 WOZWRA]AEMSQ K NA^ALU ITERACII (NA NOWYJ [AG).oCENIM ^ISLO ITERACIJ METODA: \LLIPSOIDOW.

pOKAVEM, ^TO X"SODERVIT [AR RADIUSA r=2, GDE r = "=(hn1=2 ) < R; h jaij j; jcj j (hWYSOTA ZADA^I). pUSTX x | TO^NOE RE[ENIE W X" . iZ kx xk rSLEDUET jhai ; xi hai ; x ij kai k kx xk hn1=2 r = " 8i 2 MI jhc; xi hc; x ij kck kx xk hn1=2 r, T.E. UKAZANNYJ WYBOR rGARANTIRUET, ^TO WSE TAKIE x BUDUT "-PRIBLIVENNYMI RE[ENIQMI.pOSKOLXKU kx k R, TO MNOVESTWO TEH IZ RASSMATRIWAEMYH x, DLQKOTORYH kxk R (T.E. PERESE^ENIE [AROW RADIUSA r I R, WKL@^A@]EE CENTR PERWOGO), SODERVIT [AR RADIUSA r=2.

|TOT [AR I PRINADLEVIT X" . tAKIM OBRAZOM, OB_EM X" BOLX[E OB_EMA n-MERNOGO32[ARA RADIUSA r=2. zNA^IT, OB_EM \LLIPSOIDA, POSTROENNOGO POSLEDNIM, NAPRIMER E k DLQ k-J ITERACII, NE DOLVEN OKAZATXSQ MENX[EOB_EMA \TOGO [ARA. oTS@DA I IZ UTWERVDENIQ 1 POLU^AEM DLQ k SOOTNO[ENIEvolX" volE k < e k=(2n+2);volE 1 volE 1IZ KOTOROGO k (PO OPREDELENI@ r; R; "; h I ) NE PREWOSHODIT2n2 ln(Rnh=") < 2n2 ln(2n3:55) < 10n2 ln(n).upravnenie 6.

oCENITX PO PORQDKU BITOWU@ DLINUL WHODA OZlp: DOKAZATX, ^TO L > O(ln(n)).sLEDOWATELXNO, ^ISLO ITERACIJ METODA \LLIPSOIDOW k < O(n2 )L,I S U^ETOM O(n2 + nm) ARIFMETI^ESKIH OPERACIJ DLQ KAVDOJ ITERACII POLU^IM OCENKU O(n3 (n+m)L) DLQ ^ISLA ARIFMETI^ESKIH OPERACIJ, DOSTATO^NOGO METODU \LLIPSOIDOW PRI POISKE "2 -PRIBLIVENNOGORE[ENIQ OZlp. aLGORITM OKRUGLENIQ "2 -PRIBLIVENNOGO RE[ENIQ DOTO^NOGO \TOJ OCENKI NE PORTIT (SM.[3, S.

21]). mOVNO TAKVE POKAZATX,^TO PRI REALIZACII METODA \LLIPSOIDOW I ALGORITMA OKRUGLENIQ WSEARIFMETI^ESKIE OPERACII DOSTATO^NO PROWODITX S ^ISLAMI DWOI^NOJ DLINY, OGRANI^ENNOJ O(L). pRI \TOM O[IBKI, WOZNIKA@]IE ZAS^ET KONE^NOSTI ^ISLA RAZRQDOW (O[IBKI OKRUGLENIJ), POGLO]A@TSQPUTEM NEKOTOROGO DOPOLNITELXNOGO UWELI^ENIQ (\RAZDUTIQ") OPISANNOGO \LLIPSOIDA E 0 NA KAVDOJ ITERACII [3, S. 24], ^TO NE WLIQET NAPORQDOK OCENKI DLQ OB]EGO ^ISLA ITERACIJ. w REZULXTATE WREMENNAQr n2R SLOVNOSTX TAKOJ PROCEDURY RE[ENIQ OZlp OKAZYWAETSQ POLINOMOMOT DLINY WHODA I SPRAWEDLIWAtEOREMA 3. zADA^A lp S CELYMI KO\FFICIENTAMI RAZRE[IMA ZAPOLINOMIALXNOE OT DLINY WHODA WREMQ.sLEDSTWIEM DANNOJ TEOREMY QWLQETSQuTWERVDENIE 2.

ln 2 P.pOD^ERKNEM, ^TO NESMOTRQ NA DOKAZANNU@ POLINOMIALXNOSTX, METOD \LLIPSOIDOW NE MOVET KONKURIROWATX S SIMPLEKS-METODOM PRIPRAKTI^ESKOM RE[ENII ZADA^ lp (REALXNO ON PRIMENQETSQ W WYPUKLOM KWADRATI^NOM PROGRAMMIROWANII), POSKOLXKU POLU^ENNAQOCENKA ^ISLA EGO ITERACIJ DOSTIGAETSQ NA L@BYH INDIWIDUALXNYH33ZADA^AH, DAVE ESLI W KA^ESTWE NA^ALXNOGO PRIBLIVENIQ WZQTX RE[ENIE.

tOGDA KAK SIMPLEKS-METOD DLQ \HORO[IH" (NEWYROVDENNYH) ZADA^ DAET OCENKU O(n3 ), NA PORQDOK MENX[U@, ^EM METOD \LLIPSOIDOW,I ZA ODNU ITERACI@ MOVET PODTWERDITX, ^TO NA^ALXNOE PRIBLIVENIEQWLQETSQ RE[ENIEM. tEM NE MENEE SAM FAKT POLINOMIALXNOSTI lpINICIIROWAL POISK NOWYH METODOW lp, ^TO PRIWELO K SOZDANI@ CELOGO KLASSA \FFEKTIWNYH METODOW MATEMATI^ESKOGO PROGRAMMIROWANIQ| METODY WNUTRENNEJ TO^KI | I POZWOLILO POSTROITX KONKURENTOSPOSOBNYE POLINOMIALXNYE ALGORITMY lp. iDEQ IH POSTROENIQBUDET IZLOVENA W SLEDU@]EM PARAGRAFE, GDE TAKVE PRIWODQTSQ NEOBHODIMYE SWEDENIQ PO TEORII lp, NA^INAQ S ln.x7. tEORIQ DWOJSTWENNOSTI lp.

iDEQ METODA kARMARKARAsLEDSTWIQ SISTEM ln. aFINNAQ LEMMA fARKA[A/BEZ DOKAZATELXSTWA/. lEMMA fARKA[A O NERAZRE[IMOSTI. tEOREMA DWOJSTWENNOSTI lp. sWEDENIE OZlp K ODNORODNOJ SISTEME URAWNENIJS OGRANI^ENIEM POLOVITELXNOSTI. iDEQ METODA kARMARKARA I EGOOTLI^IE OT SIMPLEKS-METODA.1. sISTEMA ln (1) NAZYWAETSQ RAZRE[IMOJ, ESLI 9x: Ax b, INERAZRE[IMOJ | W PROTIWNOM SLU^AE.

oZlp (2) RAZRE[IMA, KOGDARAZRE[IMA SISTEMA (1) I MAKSIMUM W (2) DOSTIGAETSQ.oPREDELENIE 3. lINEJNOE NERAWENSTWO(4)hc; xi dQWLQETSQ SLEDSTWIEM RAZRE[IMOJ SISTEMY LINEJNYH NERAWENSTW (1),ESLI DLQ L@BOGO x, UDOWLETWORQ@]EGO (1), WYPOLNENO (4).sPOSOB POLU^ENIQ NERAWENSTW-SLEDSTWIJ DOWOLXNO PROST: WYBEREMPROIZWOLXNYE i 0 8i 2 M , DOMNOVIM NA i KAVDOE i-E NERAWENSTWOSISTEMY (1) I SLOVIM; POLU^IM DLQ WEKTORAc=Xi 2Mi ai I L@BOGO ^ISLA d Xi2Mi bi ;^TO (4) BUDET SLEDSTWIEM (1). 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=Xi 2Mi 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 SISTEMA(6)i ai = 0;i bi 1; i 0 8i 2 M:XXi 2Mi2MdOKAZATELXSTWO.

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 jXi2Mi 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.