Н.М. Новикова - Основы оптимизации (курс лекций) (1162379), страница 6
Текст из файла (страница 6)
oTS@DA DLQEWKLIDOWOJ NORMY x POLU^AEM TREBUEMU@ OCENKU. s U^ETOM CELO^ISLENNOSTI WEKTORA c ZNAMENATELX d MOVET BYTX WYBRAN RAWNYMZNAMENATEL@ xj 8j , I 2-E UTWERVDENIE TEOREMY SLEDUET IZ OPREDELENIQ (A) jdetAI j.oPREDELENIE 1. tO^KA x" NAZYWAETSQ "-PRIBLIVENNYM RE[ENI-EM SISTEMY LINEJNYH NERAWENSTW (1), ESLIhai ; x" i bi + " 8i = 1; m; GDE ai | i-Q STROKA MATRICY A,ILI W MATRI^NOJ ZAPISI, OBOZNA^AQ e | WEKTOR-STOLBEC IZ EDINIC,Ax" b + "e:(1")tEOREMA 2 (O MERE NESOWMESTNOSTI). eSLI SISTEMA ln (1) IMEET "1 -PRIBLIVENNOE RE[ENIE DLQ "1 =: 1=[(n +2)(A)], TO \TA SISTEMARAZRE[IMA, T.E.
IMEET TO^NOE RE[ENIE x0 .dOKAZATELXSTWO. oBOZNA^IM ^EREZ " MINIMALXNOE ", PRI KOTOROM SISTEMA (1" ) IMEET RE[ENIE (PO USLOWI@ " "1 ):" =:min(x;"): Axb+"e":dOPUSTIM, ^TO UTWERVDENIE TEOREMY NE WERNO, TOGDA " > 0. zADA^AOPREDELENIQ " QWLQETSQ (S U^ETOM RAWENSTWA min() = max( ))OZlp S CELEWYM WEKTOROM c = (0; : : : ; 0; 1); n +1 PEREMENNYMI (x; ")I OGRANI^ENIQMI Ax "e b. sLEDOWATELXNO, PO TEOREME 1 " MOVETBYTX PREDSTAWLENA W WIDE DROBI SO ZNAMENATELEM, NE PREWY[A@]IM([Aj e]) (n + 1)(A), T.E.
" 1=[(n + 1)(A)] > "1 | PRI[LIK PROTIWORE^I@ S OPREDELENIEM " .aNALOGI^NOE UTWERVDENIE SPRAWEDLIWO I DLQ OZlp.oPREDELENIE 2. tO^KA x" NAZYWAETSQ "-PRIBLIVENNYM RE[ENIEM OZlp (2), ESLI ONA QWLQETSQ "-PRIBLIVENNYM RE[ENIEM SISTEMY(1) I REALIZUET MAKSIMUMW (2) S "-TO^NOSTX@:hai ; x" i bi + " 8i = 1; m I hc; x" i d ".tEOREMA 2 (O MERE NESOWMESTNOSTI). eSLI OZlp (2) IMEET "2 PRIBLIVENNOE RE[ENIE DLQ "2 =: 1=(2n2 3 (A)), TO \TA ZADA^A IMEETTO^NOE RE[ENIE x .dOKAZATELXSTWO SM.
W [3, S. 21].29x6. mETOD \LLIPSOIDOWpOLINOMIALXNYJ ALGORITM OKRUGLENIQ "1 -PRIBLIVENNOGO RE[ENIQ SISTEMY LINEJNYH NERAWENSTW. mETOD \LLIPSOIDOW "2 PRIBLIVENNOGO RE[ENIQ OZlp. oCENKA SLOVNOSTI METODA \LLIPSOIDOW. pOLINOMIALXNOSTX lp.1. iMEQ "-PRIBLIVENNOE RE[ENIE (1) S " "1 , MOVNO (NA OSNOWANII TEOREMY 2, x5) BYTX UWERENNYM W SU]ESTWOWANII TO^NOGO RE[ENIQ SISTEMY LINEJNYH NERAWENSTW. oKAZYWATSQ, PROCEDURA POLU^ENIQ x0 IZ x" QWLQETSQ POLINOMIALXNOJ. sOOTWETSTWU@]IJ ALGORITM OKRUGLENIQ "1 -PRIBLIVENNOGO RE[ENIQ SISTEMY (1) DO TO^NOGOBYL UKAZAN l. g. hA^IQNOM I SOSTOIT W SLEDU@]EM.x1 := x" I PODSTAWIM x1 W (1). rAZOBXEM MNOVESTWOpRISWOIM:M = f1; : : : ; mg INDEKSOW :NERAWENSTW W SISTEME NA DWA PODMNOVESTWA11M (x1 ) = f: i : jhai ; x1 i bi j "1 g;M n M (x1 ) = fi : hai ; x1 i bi "1 g.nAJDEM RE[ENIE x01 SISTEMY RAWENSTW AM (x1 ) x = bM (x1 ) (SU]ESTWUET PO TEOREME 2).
pUSTX x01 NE QWLQETSQ TO^NYM RE[ENIEM (1), T.E. W x01 NE WYPOLNILOSX i-E NERAWENSTWO DLQ KAKOGO-LIBOi 62 M (x1 ). tOGDAWWEDEM MNOVESTWO INDEKSOW NEWYPOLNENNYH NERAWENSTW 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 ibi hai ; x i; i1 =: arg minmin011i2M hai ; x i hai ; x ii2M 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(n2r1) fQ + (n 1n+11)QT gZA 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 kARMARKARA/BEZ DOKAsLEDSTWIQ SISTEM ln. aFINNAQ LEMMA fARKA[AZATELXSTWA/. 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=Xi2Mi ai I L@BOGO ^ISLA d Xi2Mi bi ;^TO (4) BUDET SLEDSTWIEM (1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
