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

oSNOWNAQ ZADA^A lp (OZlp) SOSTOIT W(1), KOTOROE MAKSIMIZIRUET ZADANNU@NAHOVDENII TAKOGO RE[ENIQLINEJNU@ FUNKCI@ hc; xi =: c1 x1 + c2 x2 + : : : + cn xn WEKTORA NEIZWESTNYH x PO WSEM WE]ESTWENNYM x, UDOWLETWORQ@]IM SISTEME (1):max hc; xi;(2)x2Rn : AxbOZlp (2) S n NEIZWESTNYMI I m OGRANI^ENIQMI NAZYWAETSQ ZADA^EJRAZMERNOSTI (n; m) I ZADAETSQ ^ISLOWOJ TABLICEJ a11 a12 : : : a1n b1 a21 a22 : : : a2n b2 :::: : : : : : : : : : : : (3) aa:::ab12mmmnm cc 2 : : : cn 0 1925SWOIH KO\FFICIENTOW.

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