Н.М. Новикова - Основы оптимизации (курс лекций) (1162379), страница 5
Текст из файла (страница 5)
EGO OTNOSITELXNAQ POGRE[NOSTX NE PREWOSHODIT ".dLQ "-PRIBLIVENNYH ALGORITMOW PRIWEDEM SLEDU@]IJ REZULXTAT[2, S. 439], DOKAZATELXSTWO KOTOROGO OSNOWANO NA METODE DINAMI^ESKOGO PROGRAMMIROWANIQ I W DANNOM KURSE OPUSKAETSQ.tEOREMA 5. pUSTX DLQ ZADA^I p OPTIMIZACII1) SU]ESTWUET PSEWDOPOLINOMIALXNYJ ALGORITM EE RE[ENIQ;2) 8I 2 p jOptp(I)j < p1(jIj; num(I)) I num(I) < p2(jIj; Optp(I))23DLQ NEKOTORYH POLINOMOW p1 (; ); p2 (; );3) 8 = e(I); I 2 p: PARAMETRY S , ZADA@]IE OGRANI^ENIQ, I f ,ZADA@]IE CELEWU@ FUNKCI@, NE PERESEKA@TSQ, I 8z 2 Sp () FUNKCIQCELI fp (; z) LINEJNO ZAWISIT OT PARAMETROW f ;TOGDA 9p(; ) | POLINOM: 8" > 0 9 "-PRIBLIVENNYJ ALGORITMA" RE[ENIQ p S WREMENNOJ SLOVNOSTX@ TA" (jIj) < p(jIj; 1="):tEOREMA 5 SPRAWEDLIWA, NAPRIMER, DLQ zr (SRAWNITE REZULXTATS UTWERVDENIEM 11). nABOR ALGORITMOW fA" g, OPREDELENNYJ W TEOREME 5, NAZYWAETSQ POLNOSTX@ POLINOMIALXNOJ PRIBLIVENNOJ SHEMOJ(ppps) RE[ENIQ ZADA^I p OPTIMIZACII.
nALI^IE ppps | LU^[EE,^EGO MOVNO OVIDATX PRI RE[ENII NP-TRUDNYH ZADA^. k SOVALENI@,W CELOM RQDE SLU^AEW NA \TO NELXZQ RASS^ITYWATX, TAK KAK IMEETSQtEOREMA 6. eSLI DLQ p OPTIMIZACII SOOTWETSTWU@]AQ EJ pRASPOZNAWANIQ SWOJSTW QWLQETSQ SILXNO NP-POLNOJ I 9p0 () | POLINOM: jOptp (I)j < p0 (num(I)) 8I 2 p, TO PRI USLOWII, ^TO P 6= NP,DLQ p NE SU]ESTWUET ppps.dOKAZATELXSTWO PROWEDEM OT PROTIWNOGO. pUSTX ppps SU]ESTWUET. pOSTROIM ALGORITM A0 SLEDU@]IM OBRAZOM. dLQ L@BOJ INDIWIDUALXNOJ ZADA^I I A0 WYZYWAET A" S " = 1=(p0 (num(I))+1).tOGDA PO OPREDELENI@ "-PRIBLIVENNOGO ALGORITMA A" jOptp (I)A0 (I)j < jOptp (I)j=(p0 (num(I)) + 1) < p0 (num(I))=(p0 (num(I)) + 1) POUSLOWI@ TEOREMY.
nO W LEWOJ ^ASTI POLU^ENNOGO NERAWENSTWA BYLO CELOE ^ISLO, KOTOROE OKAZYWAETSQ RAWNYM NUL@ KAK NEOTRICATELXNOE, MENX[EE 1. tAKIM OBRAZOM, ALGORITM A0 TO^EN, PRI^EMTA0 (jIj) = TA" (jIj) < p(jIj; p0 (num(I)) + 1) PO OPREDELENI@ ppps.sLEDOWATELXNO, ALGORITM A0 PSEWDOPOLINOMIALEN, ^TO PROTIWORE^ITTEOREME 4.uTWERVDENIE 12.
eSLI P 6= NP, TO NI DLQ KAKOGO " > 0 NESU]ESTWUET POLINOMIALXNOGO "-PRIBLIVENNOGO ALGORITMA RE[ENIQOPTIMIZACIONNOJ POSTANOWKI ZADA^I KOMMIWOQVERA.dOKAZATELXSTWO SM. W [2, S. 440{441].dLQ ^ASTNOGO SLU^AQ km, W KOTOROM FUNKCIQ d(; ) RASSTOQNIQ MEVDU GORODAMI UDOWLETWORQET NERAWENSTWU TREUGOLXNIKA, IZWESTEN 0.5-PRIBLIVENNYJ POLINOMIALXNYJ ALGORITM kRISTOFIDESA[2, S. 429{432] (RE[ENIQ km OPTIMIZACII).242.osnowy linejnogo programmirowaniqlITERATURA:3.
hA^IQN l. g. sLOVNOSTX ZADA^ LINEJNOGO PROGRAMMIROWANIQ.m.: zNANIE, 1987, N 10.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 :a11 x1 + a12 x2 + : : : + a1n xn b1 >>a21 x1 + a22 x2 + : : : + a2n xn b2 =(1)::::::::::::::::::::::::::: ::: >>;am1 x1 + am2 x2 + : : : + amn xn bmILI W SOKRA]ENNOJ ZAPISI Ax b.
s^ITAEM, ^TO MATRICA A NE SODERVIT NULEWYH STROK ai . 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:::abm2mn m m1 cc2 : : : 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]).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
