Н.М. Новикова - Курс лекций (1125270), страница 5
Текст из файла (страница 5)
440{441].,()-,0.5-[2,. 429{432] ().24-2.osnowy linejnogo programmirowaniqlITERATURA:hA^IQN l. g. sLOVNOSTX ZADA^ LINEJNOGO PROGRAMMIROWANIQ.m.: zNANIE, 1987, N 10.3.x5. pONQTIE O SLOVNOSTI ZADA^ILINEJNOGO PROGRAMMIROWANIQ (lp)oPREDELENIE OSNOWNOJ ZADA^I lp (OZlp). pRINCIP GRANI^NYHRE[ENIJ I GEOMETRI^ESKOE OPISANIE SIMPLEKS-METODA.
aLGEBRAI^ESKAQ I BITOWAQ SLOVNOSTX METODOW lp. rEZULXTATY PO SLOVNOSTI ZADA^, BLIZKIH K lp. tEOREMA O GRANICAH RE[ENIJ ZADA^ lp SCELYMI KO\FFICIENTAMI. tEOREMA O MERE NESOWMESTNOSTI SISTEMLINEJNYH NERAWENSTW S CELYMI KO\FFICIENTAMI.1. sOGLASNO [3] LINEJNOE PROGRAMMIROWANIE | \TO RAZDEL PRIKLADNOJ MATEMATIKI, IZU^A@]IJ TEORI@, PRILOVENIQ I METODY RE[ENIQ KONE^NYH SISTEM LINEJNYH NERAWENSTW S KONE^NYM ^ISLOMWE]ESTWENNYH NEIZWESTNYH x1 ;:::;xn :a11x1 + a12x2 + ::: + a1nxn b1 9>=a21x1 + a22x2 + ::: + a2nxn b2 >(1)::::::::::::::::::::::::::: ::: >;am1x1 am2x2 ::: amnxn bm >ILI W SOKRA]ENNOJ ZAPISI Ax b s^ITAEM ^TO MATRICA A NE SODERVIT NULEWYH STROK ai oSNOWNAQ ZADA^A lp OZlp SOSTOIT WNAHOVDENII TAKOGO RE[ENIQKOTOROE MAKSIMIZIRUET ZADANNU@LINEJNU@ FUNKCI@ hc;xi : c1 x1 c2 x2 ::: cn xn WEKTORA NEIZWESTNYH x PO WSEM WE]ESTWENNYM x UDOWLETWORQ@]IM SISTEMEx2Rn : Axbhc;xiOZlp S n NEIZWESTNYMI I m OGRANI^ENIQMI NAZYWAETSQ ZADA^EJRAZMERNOSTI n;m I ZADAETSQ ^ISLOWOJ TABLICEJ a11 a12 ::: a1n b1 a21 a22 ::: a2n b2 ::: ::: ::: ::: ::: am1 am2 ::: amn bm c1c2 ::: cn+++.,-(.)(1),=+++,-(1):max;(2)(2)()(3)025SWOIH KO\FFICIENTOW w ^ASTNOM SLU^AE c ZADA^A \KWIWALENTNATAK ^TO UMENIE RE[ATX OZlp PREDPOLAGAET UMENIE RE[ATXSISTEMY LINEJNYH NERAWENSTW ln w x BUDET POKAZANO OBRATNOESWEDENIE wOOB]E GOWORQ W FORME MOVET BYTX PREDSTAWLENA L@BAQ ZADA^A lp S OGRANI^ENIQMI RAWENSTWAMI I NERAWENSTWAMI W TOM^ISLE KANONI^ESKAQ ZADA^A lp= 0.(2)-(1),(.).,7(2)-,Ax=b; x0maxhc;xi:zDESX I DALEE ^ERTA SWERHU BUDET ISPOLXZOWATXSQ DLQ WYDELENIQWEKTORA W OTLI^IE OT POHOVEGO ^ISLA(upravnenielp W FORME OZlp..)pREDSTAWITX KANONI^ESKU@ ZADA^U5.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 ZADA@]EGO OGRANI^ENIQNA OSNOWANII PRINCIPA GRANI^NYH RE[ENIJESLI ZADA^A IMEET RE[ENIE TO NAJDETSQ TAKAQ PODMATRICA AIMATRICY A ^TO L@BOE RE[ENIE SISTEMY URAWNENIJ AI x bI T E,(-),((1),):(2),fai1x1 ai2x2 ::: ainxn bij i 2 I g,+++==,.
.,REALIZUET MAKSIMUM WoTMETIM ^TO DLQ NEWYROVDENNYH AI RE[ENIE SOOTWETSTWU@]EJSISTEMY URAWNENIJ AI x bI UDOWLETWORQ@]EE OGRANI^ENIQMQWLQETSQ UGLOWOJ TO^KOJ iZ PRINCIPA GRANI^NYH RE[ENIJ SLEDUET ^TO ESLI UGLOWAQ TO^KA SU]ESTWUET TO RAZRE[IMAQ ZADA^AIMEET RE[ENIE I W UGLOWOJ TO^KE T E ONA \KWIWALENTNA MAKSIMIZACII hc;xi NA KONE^NOM MNOVESTWE WER[IN POLI\DRA pROCEDURARE[ENIQ SISTEMY LINEJNYH URAWNENIJ METODOM gAUSSA TREBUET NEBOLEE POLINOMA J STEPENI OT m;n TO^NEEm;nm;n 2ARIFMETI^ESKIH OPERACIJ S \LEMENTAMI A I b oDNAKO ^ISLO WOZMOVNYH PODMATRIC MATRICY A \KSPONENCIALXNO I METOD POLNOGOIH PEREBORA NE \FFEKTIWENwH GG v fURXE I ZATEM WG dV dANCIG PREDLOVILI METOD NAPRAWLENNOGO PEREBORA SMEVNYH WER[INW NAPRAWLENII WOZRASTANIQ CELEWOJ FUNKCIISIMPLEKS-METOD hOTQKAVDYJ [AG SIMPLEKS METODA PREDSTAWLQ@]IJ SOBOJ OPREDELENNU@(2).,=,(1),(1).,-(1),(1),(2).
.-(1).3-(, max()[min()] ).-,.1820-..1947..-(1) |(2) |-(26-.PROCEDURU PERES^ETA \LEMENTOW SIMPLEKS TABLICY 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 BOLEEmin(n;m=2) WER[IN NO DOKAZATELXSTWO NEWOZMOVNOSTI POSTROITX POLINOMIALXNYJ SIMPLEKS METOD TAKVE OTSUTSTWUET pOD^ERKNEM ^TONA PRAKTIKE SIMPLEKS METOD NE POKAZYWAET DANNOJ OCENKI PLOHIEPRIMERY DOWOLXNO REDKI mOVNO POSTROITX ALGORITM RE[ENIQ ZADA^I lp S OCENKOJ f n m ARIFMETI^ESKIH OPERACIJ NAD ^ISLAMIZAPISANNYMI WGDE f RASTET BYSTREE \KSPONENTY aLGORITM SPOLINOMIALXNOJ OCENKOJ ODNOWREMENNO PO n I m NE IZWESTEN I WRQDLI BUDET POSTROENtEPERX ZAMETIM ^TO FUNKCIQ OCENIWA@]AQ ^ISLO ARIFMETI^ESKIH OPERACIJ W ZAWISIMOSTI OT n I m NE U^ITYWAET DLINU KODA\LEMENTOWA TOLXKO IH KOLI^ESTWO I PO\TOMU NE QWLQETSQ WREMENNOJ SLOVNOSTX@ ALGORITMA uKAZANNAQ FUNKCIQ NOSIT NAZWANIEALGEBRAI^ESKOJ SLOVNOSTI W OTLI^IE OT BITOWOJ SLOVNOSTIFUNKCII OCENIWA@]EJ ^ISLO ARIFMETI^ESKIH OPERACIJ S BITAMIILI S KONE^NYMI PORCIQMI PO RAZMERU MA[INNOGO REGISTRACIFROWOJ 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 SOOTWETSTWUET EGO WREMENNOJ SLOVNOSTI SM x wHODNYE KO\FFICIENTYZADA^I lp OBY^NO RACIONALXNY PO\TOMU DALEE USLOWIMSQ S^ITATXIH CELYMI TOGDA l DLINA ZAPISI MAKSIMALXNOGO KO\FFICIENTAWKONE^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 WG I TEMSAMYM BYLA DOKAZANA POLINOMIALXNOSTX ZADA^ lp oSNOWNYE MOMENTY \TOGO DOKAZATELXSTWA IZLAGA@TSQ W SLEDU@]EM PUNKTE I xzDESX 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[ENIQ-(3)),-,-,2,--.,-(\").(-)((3)),( ),..,,-,(3),-.|,(|)-,-..
.,,-(.1).,,(3) ||.(,,).-..1978.,.-6..-,.. .--.27,SISTEMY LINEJNYH URAWNENIJ PRINADLEVIT KLASSU NC A ANALOGI^NYJ REZULXTAT DLQ lp OZNA^AL BY RAWENSTWO NC P OVIDATX KOTOROE NET OSNOWANIJiZ 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 x T EPOLINOMIALXNYE ALGORITMY DLQ NIH WRQD LI BUDUT POSTROENYsU]ESTWUET NEPOLINOMIALXNOE OBOB]ENIE lp ZADA^A PROWERKIISTINNOSTI WYSKAZYWANIJ WIDA,=-,-.():-.:(-.2),. ..|x ::: Qnxn 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 OTRICANIEQ1 1(,()) |,&( ,,-).dOKAZANO ^TO L@BOJ ALGORITM RE[A@]IJ \TU MASSOWU@ ZADA^UIMEET NE MENEE ^EM \KSPONENCIALXNU@ SLOVNOSTX tOT VE REZULXTAT BUDET I PRI ZAMENE RAWENSTWAMI WSEH NERAWENSTW W POSTANOWKEZADA^I2.
rASSMOTRIM NEKOTORYE SWOJSTWA ZADA^ lp S CELYMI KO\FFICIENTAMI dLQ L@BOJ CELO^ISLENNOJ MATRICY D WWEDEM PARAMETR,,.,-.-.D : fD0() =maxKWADRATNAQ PODMATRICADg jdetD j:0bUDEM 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 NEOTRICATELXNYJORTANTtEOREMA 1 (O GRANICAH RE[ENIJ) eSLI OZlp RAZMERNOSTIRAZRE[IMA TO U NEE SU]ESTWUETn;m S CELYMI KO\FFICIENTAMIRACIONALXNOE: RE[ENIE x W [ARE kxk n1=2 Ajb I ZNA^ENIEMOZlp d hc;x i QWLQETSQ RACIONALXNOE ^ISLO t=s SO ZNAMENATELEM OGRANI^ENNYM WELI^INOJ AdOKAZATELXSTWO. nA OSNOWANII PRINCIPA GRANI^NYH RE[ENIJ9AI A PO PRAWILU kRAMERA jxjj j j AjI = AI j Ajb IBOj AI j A OPREDELITELX MATRICY AI POLU^ENNOJ IZ AI ZAMENOJ[],,-.|,-|..((2)),([(2),-(:det])=).=1,det,28det([]),j 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 E UTWERVDENIE TEOREMY SLEDUET IZ OPREDELENIQ A j AI joPREDELENIE 1.
tO^KA x" NAZYWAETSQ " PRIBLIVENNYM RE[ENIEM SISTEMY LINEJNYH NERAWENSTW ESLIhai;x"i bi " 8i ;m; GDE ai i Q STROKA MATRICY A-,([])..,()det-2--.--(1),+= 1ILI W MATRI^NOJ ZAPISI OBOZNA^AQ e,|-|,WEKTOR STOLBEC IZ EDINIC-Ax" b "e:,"+(1 )tEOREMA 2 (O MERE NESOWMESTNOSTI) eSLI SISTEMA ln IMEA TO \TA SISTEMAET "1 PRIBLIVENNOE RE[ENIE DLQ "1 : = nRAZRE[IMA T E IMEET TO^NOE RE[ENIE x0" PRI KOdOKAZATELXSTWO. oBOZNA^IM ^EREZ " MINIMALXNOETOROM SISTEMA " IMEET RE[ENIE PO USLOWI@ " "1.-= 1 [(,. .(1)+2)(-)],.,(1 )(" : (x;"): Axb+"e ":=-):mindOPUSTIM ^TO UTWERVDENIE TEOREMY NE WERNO TOGDA " > zADA^AOPREDELENIQ " QWLQETSQ S U^ETOM RAWENSTWAOZlp S CELEWYM WEKTOROM c ;:::; ; ; n PEREMENNYMI x;"I OGRANI^ENIQMI Ax "e b sLEDOWATELXNO PO TEOREME " MOVETBYTX PREDSTAWLENA W WIDE DROBI SO ZNAMENATELEM NE PREWY[A@]IMAj e nA T E " = nA > "1 PRI[LIK PROTIWORE^I@ S OPREDELENIEM "aNALOGI^NOE UTWERVDENIE SPRAWEDLIWO I DLQ OZlpoPREDELENIE 2.
tO^KA x" NAZYWAETSQ " PRIBLIVENNYM RE[ENIEM OZlp ESLI ONA QWLQETSQ " PRIBLIVENNYM RE[ENIEM SISTEMYI REALIZUET MAKSIMUM W S " TO^NOSTX@hai;x"i bi " 8i ;m I hc;x"i d "IMEET "2) eSLI OZlptEOREMA 2 (O MERE NESOWMESTNOSTIPRIBLIVENNOE RE[ENIE DLQ "2 : = n2 3 A TO \TA ZADA^A IMEETTO^NOE RE[ENIE xdOKAZATELXSTWO SM W S,,(0.min( ) == (001)max())()+1.,1,([])(+ 1)(),. .1 [(+ 1)()]|..-(2),--(1)(2)+-:= 1..= 1 (2..[3,. 21].29 ((2))),-x6.
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"1 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"1 I PODSTAWIM x1 W (1). rAZOBXEM MNOVESTWO:NERAWENSTW W SISTEME NA DWA PODMNOVESTWAM = f1;:::;mg INDEKSOWM (x1) 1=: f: i : jhai;x1i1 bij "1g;M n M (x ) = fi : hai;x i bi "1g.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 OTREZKE1 0101 TO^KU, W KOTOROJ E]E WYPOLNENY WSE NERA[x ;x ] BLIVAJ[U@ K x+WENSTWA DLQ i 2 M (W x1 ONI WYPOLNENY S "1 -ZAPASOM).
a IMENNOOPREDELIMbi hai;x1i ; i1 =: arg min bi hai;x1i =: 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 INDEKSOMW x2 KAK RAWENSTWOi1 2 M +, NE WYPOLNENNOE W TO^KE x01, WYPOLNQETSQ21PO POSTROENI@.
tAKIM OBRAZOM, M (x ) M (x ), 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.30aNALOGI^NYJ ALGORITM IMEETSQ I DLQ OKRUGLENIQ "2 PRIBLIVENNOGO RE[ENIQ OZlp x"2 DO TO^NOGO x SM SpO\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 IZ x tREBUEMYJ ALGORITM OSNOWANNYJ NAMETODE \LLIPSOIDOW KOTORYJ PREDLOVILI WGG d b `DINI a s nEMIROWSKIJ I NEZAWISIMO n z {OR PRIWODITSQ W SLEDU@]IH PUNKTAHzDESX I DALEE : D GDE MATRICA D ZADAETSQ TABLICEJPROIZWOLXNYJ \LLIPSOID W Rn S CENTROM I NE2.
pUSTX ENULEWOGO OB_EMA E rASSMOTRIM nMERNU@ PLOSKOSTX ZADANNU@ WEKTOROM g NORMALI I PROHODQ]U@ ^EREZ CENTR \LLIPSOIDA EoBOZNA^IM ^EREZ E g ODIN IZ DWUH POLU\LLIPSOIDOW NA KOTORYERAZBIWAET E DANNAQ PLOSKOSTX E g E \ fxj hg;x i g:uTWERVDENIE 1. pOLU\LLIPSOID E g \LLIPSOIDA E MOVNO CELIKOM ZAKL@^ITX W NOWYJ \LLIPSOID E 0 IME@]IJ OB_EM STROGOMENX[IJ E0-(. [3,-.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
