Н.М. Новикова - Основы оптимизации (1125234), страница 5
Текст из файла (страница 5)
w ^ASTNOM SLU^AE c = 0 ZADA^A (2) \KWIWALENTNA (1), TAK ^TO UMENIE RE[ATX OZlp PREDPOLAGAET UMENIE RE[ATXSISTEMY LINEJNYH NERAWENSTW (ln). w x7 BUDET POKAZANO OBRATNOESWEDENIE. wOOB]E GOWORQ, W FORME (2) MOVET BYTX PREDSTAWLENA L@BAQ ZADA^A lp S OGRANI^ENIQMI RAWENSTWAMI I NERAWENSTWAMI, W TOM^ISLE KANONI^ESKAQ ZADA^A lpmax hc; xi:Ax=b; x0(zDESX I DALEE ^ERTA SWERHU BUDET ISPOLXZOWATXSQ DLQ WYDELENIQWEKTORA W OTLI^IE OT POHOVEGO ^ISLA.)upravnenie 5. pREDSTAWITX KANONI^ESKU@ ZADA^Ulp W FORME OZlp.nESMOTRQ NA TO, ^TO FORMALXNO ZADA^I lp NE QWLQ@TSQ DISKRETNYMI (x 2 Rn ), IH RE[ENIE NETRUDNO SWESTI K PEREBORU KONE^NOGO^ISLA UGLOWYH TO^EK (WER[IN POLI\DRA (1), ZADA@]EGO OGRANI^ENIQ)NA OSNOWANII PRINCIPA GRANI^NYH RE[ENIJ:ESLI ZADA^A (2) IMEET RE[ENIE, TO NAJDETSQ TAKAQ PODMATRICA AIMATRICY A, ^TO L@BOE RE[ENIE SISTEMY URAWNENIJ AI x = bI , T.E.fai1 x1 + ai2 x2 + : : : + ain xn = bi j i 2 I g,REALIZUET MAKSIMUM W (2).oTMETIM, ^TO DLQ NEWYROVDENNYH AI RE[ENIE SOOTWETSTWU@]EJSISTEMY URAWNENIJ AI x = bI , UDOWLETWORQ@]EE OGRANI^ENIQM (1),QWLQETSQ UGLOWOJ TO^KOJ (1).
iZ PRINCIPA GRANI^NYH RE[ENIJ SLEDUET, ^TO ESLI UGLOWAQ TO^KA (1) SU]ESTWUET, TO RAZRE[IMAQ ZADA^A (2)IMEET RE[ENIE I W UGLOWOJ TO^KE (1), T.E. ONA \KWIWALENTNA MAKSIMIZACII hc; xi NA KONE^NOM MNOVESTWE WER[IN POLI\DRA (1). pROCEDURARE[ENIQ SISTEMY LINEJNYH URAWNENIJ METODOM gAUSSA TREBUET NEBOLEE POLINOMA 3-J STEPENI OT m; n (TO^NEE, max(m; n)[min(m; n)]2 )ARIFMETI^ESKIH OPERACIJ S \LEMENTAMI A I b.
oDNAKO ^ISLO WOZMOVNYH PODMATRIC MATRICY A \KSPONENCIALXNO, I METOD POLNOGOIH PEREBORA NE \FFEKTIWEN.w 1820-H GG. v. fURXE I ZATEM W 1947 G. dV. dANCIG PREDLOVILI METOD NAPRAWLENNOGO PEREBORA SMEVNYH WER[IN (1) | W NAPRAWLENII WOZRASTANIQ CELEWOJ FUNKCII (2) | SIMPLEKS-METOD.
hOTQKAVDYJ [AG SIMPLEKS-METODA (PREDSTAWLQ@]IJ SOBOJ OPREDELENNU@26PROCEDURU PERES^ETA \LEMENTOW SIMPLEKS-TABLICY (3)) OGRANI^EN POPORQDKU ^ISLOM mn ARIFMETI^ESKIH OPERACIJ, W NASTOQ]EE WREMQDLQ WSEH IZWESTNYH WARIANTOW SIMPLEKS-METODA PRIWEDENY PRIMERY, \KSPONENCIALXNYE PO ^ISLU ITERACIJ, KOGDA PEREBIRAETSQ BOLEE2min(n;m=2) WER[IN, NO DOKAZATELXSTWO NEWOZMOVNOSTI POSTROITX POLINOMIALXNYJ SIMPLEKS-METOD TAKVE OTSUTSTWUET. pOD^ERKNEM, ^TONA PRAKTIKE SIMPLEKS-METOD NE POKAZYWAET DANNOJ OCENKI (\PLOHIE"PRIMERY DOWOLXNO REDKI).
mOVNO POSTROITX ALGORITM RE[ENIQ ZADA^I lp S OCENKOJ f (n)m ARIFMETI^ESKIH OPERACIJ (NAD ^ISLAMI,ZAPISANNYMI W (3)), GDE f () RASTET BYSTREE \KSPONENTY. aLGORITM SPOLINOMIALXNOJ OCENKOJ ODNOWREMENNO PO n I m NE IZWESTEN I WRQDLI BUDET POSTROEN.tEPERX ZAMETIM, ^TO FUNKCIQ, OCENIWA@]AQ ^ISLO ARIFMETI^ESKIH OPERACIJ W ZAWISIMOSTI OT n I m, NE U^ITYWAET DLINU KODA\LEMENTOW (3), A TOLXKO IH KOLI^ESTWO I PO\TOMU NE QWLQETSQ WRE SLOVNOSTX@ ALGORITMA. uKAZANNAQ FUNKCIQ NOSIT NAZWANIEMENNOJALGEBRAI^ESKOJ SLOVNOSTI W OTLI^IE OT BITOWOJ SLOVNOSTI |FUNKCII, OCENIWA@]EJ ^ISLO ARIFMETI^ESKIH OPERACIJ S BITAMI(ILI S KONE^NYMI PORCIQMI | PO RAZMERU MA[INNOGO REGISTRA)CIFROWOJ ZAPISI PARAMETROW INDIWIDUALXNOJ ZADA^I lp W ZAWISIMOSTI OT DLINY WHODNOGO SLOWA, T.E.
OT n, m I DLIN l KODOW ^ISELW SIMPLEKS-TABLICE. o^EWIDNO, BITOWAQ SLOVNOSTX ALGORITMA SOOT SLOVNOSTI (SM. x1). wHODNYE KO\FFICIENTYWETSTWUET EGO WREMENNOJZADA^I lp OBY^NO RACIONALXNY, PO\TOMU DALEE USLOWIMSQ S^ITATXIH CELYMI, TOGDA l | DLINA ZAPISI MAKSIMALXNOGO KO\FFICIENTAW (3) | KONE^NA. nABOR (n, m, l) NAZYWAETSQ BITOWOJ RAZMERNOSTX@ZADA^I lp. wOPROS O SU]ESTWOWANII ALGORITMA lp S POLINOMIALXNOJ BITOWOJ SLOVNOSTX@ BYL RE[EN l.
g. hA^IQNOM W 1978 G., I TEMSAMYM BYLA DOKAZANA POLINOMIALXNOSTX ZADA^ lp. oSNOWNYE MOMENTY \TOGO DOKAZATELXSTWA IZLAGA@TSQ W SLEDU@]EM PUNKTE I x6.zDESX VE UKAVEM NA OTLI^IE KLASSOW SLOVNOSTI ZADA^I lp I DRUGIHLINEJNYH ZADA^.mETOD gAUSSA RE[ENIQ SISTEMY LINEJNYH ALGEBRAI^ESKIH URAWNENIJ IMEET POLINOMIALXNU@ ALGEBRAI^ESKU@ SLOVNOSTX, T.E. QWLQETSQ SILXNOPOLINOMIALXNYM. dLQ lp WOPROS O SU]ESTWOWANII SILXNOPOLINOMIALXNOGO ALGORITMA OTKRYT. kROME TOGO, ZADA^A RE[ENIQ27SISTEMY LINEJNYH URAWNENIJ PRINADLEVIT KLASSU NC, A ANALOGI^NYJ REZULXTAT DLQ lp OZNA^AL BY RAWENSTWO NC=P, OVIDATX KOTOROE NET OSNOWANIJ.iZ POLINOMIALXNOSTI lp WYTEKAET POLINOMIALXNOSTX ZADA^Iln (SU]ESTWUET LI RE[ENIE SISTEMY ln): ln 2 P.
aNALOGI^NYE ZADA^I S DOPOLNITELXNYM OGRANI^ENIEM CELO^ISLENNOSTI ILIBULEWOSTI RE[ENIQ NP-POLNY: cln; bln 2 NPC (SM. x2), T.E.POLINOMIALXNYE ALGORITMY DLQ NIH WRQD LI BUDUT POSTROENY.sU]ESTWUET NEPOLINOMIALXNOE OBOB]ENIE lp | ZADA^A PROWERKIISTINNOSTI WYSKAZYWANIJ WIDAQ1 x1 : : : Qn xn F(ha1 ; xi b1 ; : : : ; ham ; xi bm );GDE Qi 2 f8; 9g, A F(; : : : ; ) | PREDLOVENIE, SOSTAWLENNOE IZ LINEJNYH NERAWENSTW S POMO]X@ SWQZOK &; _; : (I, ILI, OTRICANIE).dOKAZANO, ^TO L@BOJ ALGORITM, RE[A@]IJ \TU MASSOWU@ ZADA^U,IMEET NE MENEE ^EM \KSPONENCIALXNU@ SLOVNOSTX.
tOT VE REZULXTAT BUDET I PRI ZAMENE RAWENSTWAMI WSEH NERAWENSTW W POSTANOWKEZADA^I.2. rASSMOTRIM NEKOTORYE SWOJSTWA ZADA^ lp S CELYMI KO\FFICIENTAMI. dLQ L@BOJ CELO^ISLENNOJ MATRICY D WWEDEM PARAMETR(D) =: fD0 KWADRATNAQmaxPODMATRICA Dg jdetD0j:bUDEM OBOZNA^ATX ^EREZ [Ajb] MATRICU, SOSTAWLENNU@ IZ A I WEKTORASTOLBCA b 2 Zm , DOPISANNOGO SPRAWA. zDESX I DALEE Zm | m-MERNOEPROSTRANSTWO CELO^ISLENNYH WEKTOROW, Zm+ | EGO NEOTRICATELXNYJORTANT.tEOREMA 1 (O GRANICAH RE[ENIJ).
eSLI OZlp (2) RAZMERNOSTI(n; m) S CELYMI KO\FFICIENTAMIRAZRE[IMA, TO U NEE SU]ESTWUETRACIONALXNOE: RE[ENIE x W [ARE kxk n1=2 ([Ajb]) I ZNA^ENIEMOZlp (2) d = hc; x i QWLQETSQ RACIONALXNOE ^ISLO t=s SO ZNAMENATELEM, OGRANI^ENNYM WELI^INOJ (A).dOKAZATELXSTWO. nA OSNOWANII PRINCIPA GRANI^NYH RE[ENIJ9AI A: PO PRAWILU kRAMERA jxj j = jdetAjI =detAI j ([Ajb]), IBOjdetAI j 1, A OPREDELITELX MATRICY AjI , POLU^ENNOJ IZ AI ZAMENOJ28j -GO STOLBCA NA bI , NE PREWY[AET PO MODUL@ ([Ajb]). 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.pRISWOIMx1 := x" I PODSTAWIM x1 W (1). rAZOBXEM MNOVESTWO: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-LIBOWWEDEM MNOVESTWO INDEKSOW NEWYPOLNENNYH NERAi 62 M (x1 ).
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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
