Н.М. Новикова - Курс лекций (1125270), страница 6
Текст из файла (страница 6)
21]).---(1,2,5).,,.1976{77.().....,-. = (),(3).|-vol.(1)-,-.( ),,( ) =0( )-,,E < e 1=(2n+2);EI E 0 MOVNO WY^ISLITX PO E g ZA O n2 ARIFMETI^ESKIH OPERACIJdOKAZATELXSTWO. pUSTX E EDINI^NYJ [AR S CENTROM W TO^KEf2Rn kxk g A E gExE \fxn g pOMESTIM CENTR1TOGDAE 0 W TO^KU 0 ;:::; ; n+1,vol( )vol( )().|0:=:1 ,= (00( ) =0 .),E 0 fxj x21 ::: x2n 1 = 2 xn n 2=2 g;= n < e 1=(n+1); 2 := n2 n <1 e1=(n1=(21)n:+2)GDE :oTNO[ENIE OB_EMOW RAWNO PROIZWEDENI@ POLUOSEJ < e== 1(1 (++)+(+ 1)1+1= 1+1 ()11)2OTS@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 g oBOZNA^IM : QT g=kQT gkGDE WERHNIJ INDEKS T ZNAK TRANSPONIROWANIQ tOGDA 0 I Q0 PREDSTAWLQ@]IE \LLIPSOID E 0 MINIMALXNOGO OB_EMA OPISANNYJ WOKRUG( ),,.,-(:=-=),+-1 .|=.,31,,-,POLU\LLIPSOIDA E g PERES^ITYWA@TSQ PO FORMULAM( ),0 = n1+1Q0 = pQ;(nn21)fQr+(nn1+11)QT gZA O n2 ARIFMETI^ESKIH OPERACIJ3 mETOD \LLIPSOIDOW POLU^ENIQ "-PRIBLIVENNOGO RE[ENIQ"2 : = n2 3 wWEDEM"OZlp.
pOLOVIM ": n1=MNOVESTWO2 S CENTROMRPRIBLIVENNYHRE[ENIJOZlpW[ARERADIUSAW X" : fxj hai ;xi bi " 8i ;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 gSM P GDE WEKTOR g OPREDELQETSQ SLEDU@]IM OBRAZOM tAK KAK 62 X0 " TO LIBO9i hai;i > bi " I TOGDA g ai LIBO0 hc; i < d"Ig cuBEDIMSQ ^TO PRI \TOM X" E 0 dEJSTWITELXNO DLQ WARIANTA 08x 2 X" ha0i;xi bi " < hai;i T E X" E \ fxj h0ai;x i gE ai E I ANALOGI^NO POLU^IM DLQ WARIANTA()..:==1 (2 ).-=0:=+= 1..,-.,,--,(.( ).2),.,1 ):+2 ),:=:=,.,.+,,1. .0=X" 0 E \ fxj hc;x i g E c E 0tEPERX S E E WOZWRA]AEMSQ K NA^ALU ITERACII NA NOWYJ [AGoCENIM ^ISLO ITERACIJ METODA: \LLIPSOIDOW pOKAVEM ^TO X"SODERVIT [AR RADIUSA r= 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[ENIQMIpOSKOLXKU 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= |TOT [AR I PRINADLEVIT X" tAKIM OBRAZOM OB_EM X" BOLX[E OB_EMA n MERNOGO();20=():=.()..2,).=(,)(|.=,,.
.-.,(,. .,),.-2.,--32[ARA RADIUSA r= 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 POLU^AEM DLQ k SOOTNO[ENIE2.,,,--,.1-r n X" E k < e k=(2n+2);RE1E1IZ KOTOROGO k PO OPREDELENI@ r;R;";h I NE PREWOSHODITn2 Rnh=" < n2 n3:5 5 < n2 nupravnenie 6. oCENITX PO PORQDKU BITOWU@ DLINUL WHODA OZlp: DOKAZATX, ^TO L > O nsLEDOWATELXNO ^ISLO ITERACIJ METODA \LLIPSOIDOW k < O n2 LI 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 DO2volvolvolvol(2)ln()2ln(2 )10(ln(ln().)).,(+())(,-(+))-,-.-TO^NOGO \TOJ OCENKI NE PORTIT SM SmOVNO 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 S^TO NE WLIQET NAPORQDOK OCENKI DLQ OB]EGO ^ISLA ITERACIJ w REZULXTATE WREMENNAQSLOVNOSTX 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 WREMQsLEDSTWIEM DANNOJ TEOREMY QWLQETSQ(.[3,. 21]).,-,().,(),(\[3,")-. 24],..uTWERVDENIE 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 INDIWIDUALXNYH,,--(-),33ZADA^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 \LLIPSOIDOWI 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 PROGRAMMIROWANIQMETODY 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 NERAWENSTWOhc;xi d(4)QWLQETSQ SLEDSTWIEM RAZRE[IMOJ SISTEMY LINEJNYH NERAWENSTWESLI DLQ L@BOGO x UDOWLETWORQ@]EGO WYPOLNENOsPOSOB POLU^ENIQ NERAWENSTW SLEDSTWIJ DOWOLXNO PROST WYBEREMPROIZWOLXNYE i 8i 2 M DOMNOVIM NA i KAVDOE i E NERAWENSTWOSISTEMY I SLOVIM POLU^IM DLQ WEKTORA(1),,(1),(4).-0(1):,-;c=Xi 2Miai I L@BOGO ^ISLA d Xi2Mibi;^TO BUDET SLEDSTWIEMoKAZYWAETSQ DRUGIH SLEDSTWIJ U lnNE BYWAET a IMENNO SPRAWEDLIWA(4)(1).,.34lEMMA fARKA[A(AFINNAQ) lINEJNOE NERAWENSTWOQWLQETSQSLEDSTWIEM RAZRE[IMOJ W WE]ESTWENNYH PEREMENNYH SISTEMY lnTOGDA I TOLXKO TOGDA KOGDA SU]ESTWUET WEKTOR 2 Rm.(4)(1),c=Xi 2M:iai; d Xi2Mibi; i 8i 2 M:0(5)sHEMU DOKAZATELXSTWA SM W SdLQ NERAZRE[IMOJ SISTEMY ln MOVNO FORMALXNO S^ITATXSLEDSTWIEM ZAWEDOMO NEWERNOE NERAWENSTWO h ;xi I DALEEPOLXZOWATXSQ AFINNOJ LEMMOJ fARKA[A KAK POKAZYWAETlEMMA fARKA[A O NERAZRE[IMOSTI sISTEMA ln NERAZRE[IMA TOGDA I TOLXKO TOGDA KOGDA RAZRE[IMA SISTEMA(.[3,.
18].)(1)0(1)1,.(1)-,Xi 2Miai= 0;Xi2Mibi ; i 8i 2 M:10(6)dOKAZATELXSTWO. pUSTX NERAZRE[IMA TOGDA IZ RAZRE[IMOSTI SISTEMY hai ;xi xn+1 bi 8i 2 M DOLVNO SLEDOWATX ^TOxn+1 " < T E SLEDSTWIEM \TOJ SISTEMY QWLQETSQ NERAWENSTWOh ;:::; ; =" ; x;xn+1 i IPIZ AFINNOJ LEMMY fARKA[A POLU^AEMA TAKVE W DOPOLNENIE i =" eSLI VE RAZRE[IMATO UKAZANNOE WY[E NERAWENSTWO h ;xi OKAZYWAETSQ SLEDSTWIEMI DOLVNO WYPOLNQTXSQ DLQ WSEH x UDOWLETWORQ@]IH ZNA^ITTAKIH NE SU]ESTWUETtEPERX 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 lpoPREDELENIE 4.
dWOJSTWENNOJ K ZADA^E lp NA MAKSIMUM S OGRANI^ENIQMI NERAWENSTWAMI W FORME OZlp NAZYWAETSQ SLEDU@]AQZADA^A lp NA MINIMUM S OGRANI^ENIQMI W KANONI^ESKOJ FORME(1),-+0,(00 1,. .) ()1-(6) (= 10(1)).(6),1,(1),,.|,,,.-,,.-(2):minf X ibij X iai c; i 8i 2 M g;i2Mi2M=035ILI W KRATKOJ ZAPISIA=c; 0minh;bi:(7)dLQ TOGO ^TOBY POSTROITX DWOJSTWENNU@ K PROIZWOLXNOJ ZADA^E lpNADO PREDSTAWITX EE W FORME OZlp PRIMENITX FORMULU A ZATEMWERNUTXSQ K OBOZNA^ENIQM ISHODNOJ ZADA^I,,,(7),.upravnenie 7. pOKAZATX, ^TO DWOJSTWENNAQ ZADA^AK DWOJSTWENNOJ ZADA^E lp SOWPADAET S PRQMOJ ZADA^EJ lp:PREDSTAWITX W FORME OZlp ANALOGI^NO UPRAVNENI@ WYPISATXDWOJSTWENNU@ K POLU^ENNOJ ZADA^E I SWESTI EE KtEOREMA 4 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^AHd ZNA^ENIESOWPADA@T T E d d GDE d ZNA^ENIEdOKAZATELXSTWO PROWEDEM DLQ SLU^AQ OZlp POSKOLXKU L@BAQZADA^A lp ADEKWATNO PREDSTAWLQETSQ W TAKOJ FORMEpUSTX ZADA^A RAZRE[IMA TOGDA QWLQETSQ SLEDSTWIEM8d d I NE QWLQETSQ 8d < d ^TO PO AFINNOJLEMME fARKA[A\KWIWALENTNO RAZRE[IMOSTI PRI d d I NERAZRE[IMOSTIPRI d < d T E dfdj g A \TO I ESTX ZNA^ENIEi NAOBOROT IZ RAZRE[IMOSTI SLEDUET NERAZRE[IMOSTXIBO W PROTIWNOM SLU^AEWOBRA]ALSQ BY W 1 TAK KAKPRIBAWLENIE RE[ENIQ K RE[ENI@ DAET DOPUSTIMU@ TO^KU IUMENX[AET ZNA^ENIE CELEWOJ FUNKCIIoTS@DA POLU^AEM RAZRE[IMOSTX PO LEMME fARKA[A O NERAZRE[IMOSTI kROME TOGORAZRE[IMOSTX OZNA^AET RAZRE[IMOSTX DLQ L@BOGO d dTAK ^TO OKAZYWAETSQ SLEDSTWIEM DLQ d d I PO\TOMU dOGRANI^IWAET SWERHU ZNA^ENIET E MAKSIMUM W DOSTIGAETSQtAKIM OBRAZOM POLU^ILI RAZRE[IMOSTX ZADA^I I MOVEM WERNUTXSQ K NA^ALU DOKAZATELXSTWA DLQ USTANOWLENIQ RAWENSTWA d diZ TEOREMY NEPOSREDSTWENNO POLU^AEMuTWERVDENIE 3.
zADA^A lp OPTIMIZACII \KWIWALENTNA RE[ENI@ SISTEMY LINEJNYH NERAWENSTWdEJSTWITELXNO OZlp \KWIWALENTNA ZADA^E lp I OBE ONI\KWIWALENTNY SISTEME ln OTNOSITELXNO NEIZWESTNYH x;(7)(5),(2).().,,.. .=,|(2),-|(7).,.(2),(4)(1),(5),. .= min(5)(5) ,(7).,(7)min(6),(7)(6)((7)(7)).-(1).(7),(5)(4),(1)(2),,. .(2).(2)-=.4-.,(2)(7)(Ax b; hc;xi hb;i; A c; :==360):(8)uTWERVDENIE 4. zADA^A lp OPTIMIZACII \KWIWALENTNA RE[ENI@ SISTEMY LINEJNYH URAWNENIJ W NEOTRICATELXNYH PEREMENNYHdOKAZATELXSTWO.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
