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

rANEE UVE OTME^ALOSX, ^TO S PRAKTI^ESKOJ TO^KI ZRENIQ RAZNICA MEVDU POLINOMIALXNYM ALGORITMOM (DLQ POLINOMOW WYSOKIHSTEPENEJ) I \KSPONENCIALXNYM WESXMA USLOWNA, A WSE DELO W WOZMOVNOSTI ILI NEWOZMOVNOSTI IZBEVATX POLNOGO PEREBORA. wOPROS, WSE LINP-POLNYE I NP-TRUDNYE ZADA^I TRUDNY DLQ PRAKTI^ESKOGO S^ETA,MY OBSUDIM NIVE W \TOM PARAGRAFE.rASSMOTRIM SAMU@ PROSTU@ (PO FORMULIROWKE) NP-TRUDNU@ ZADA^U | ZADA^U O R@KZAKE (zr), ZAKL@^A@]U@SQ W TOM, ^TOBY IZIME@]EGOSQ NABORA POLEZNYH WE]EJ SOBRATX R@KZAK OGRANI^ENNOGOOB_EMA S NAIBOLX[EJ POLXZOJ.

fORMALXNO TREBUETSQ NAJTInXfmaxz: zj 2f0;1g 8j =1;:::;nj =1cj zj j19nXj =1wj zj K g;GDE cj 2 Z+ | POLEZNOSTX (CENNOSTX), wj 2 Z+ | OB_EM (WES) j -JWE]I, A PEREMENNAQ zj OPREDELQET KLASTX ILI NE KLASTX EE W R@KZAK;MAKSIMALXNO WOZMOVNYJ OB_EM (WES) R@KZAKA ZADAETSQ PARAMETROMK 2 Z+ . sOOTWETSTWU@]AQ ZADA^A RASPOZNAWANIQ SWOJSTW | SU]ESTWUET LI BULEWO RE[ENIE SISTEMY DWUH LINEJNYH NERAWENSTWnXj =1nXcj zj B Ij =1wj zj KS NATURALXNYMI KO\FFICIENTAMI | NP-POLNA (DOKAZATELXSTWO NESLEDUET IZ UTWERVDENIQ 8, TAK KAK RASSMATRIWAETSQ ^ASTNYJ SLU^AJbln, PO\TOMU SM.

[1, S. 87 ILI 2, S. 386]). dLQ RE[ENIQ zr IZWESTENSLEDU@]IJ METOD (DINAMI^ESKOGO PROGRAMMIROWANIQ).pROIZWOLXNAQ INDIWIDUALXNAQ ZADA^A I2zr POGRUVAETSQ W SEMEJSTWO ZADA^ POISKAFi (E ) =:nXmaxfz: zj 2f0;1g 8j =i;:::;nj =icj zj jnXj =iwj zj K E g;F1 (0) | ZNA^ENIE zr. i RE[A@TSQ WSE ZADA^I DANNOGO SEMEJSTWA POREKURRENTNYMFORMULAM, GDE i UBYWAET S n DO 1. a IMENNO, POLOVIMFi (E ) =: 0 8E K; 8i. iMEEM 8E = 0; K 1 :Fn (E ) =0;cnE > K wn ;INA^E,I 8i = n 1; : : : ; 2: Fi (E ) = maxfFi+1 (E ); ci + Fi+1 (E + wi )g =:=: z maxfc z + Fi+1 (E + wi zi )g; F1 (0) = maxfF2 (0); c1 + F2 (w1 )g:2f0;1g i ii~ISLO ITERACIJ PREDLOVENNOGO ALGORITMA RAWNO nK I TOGO VE SLOVNOSTX.

oTMETIM, ^TO ALGORITM NEPORQDKA BUDET EGO WREMENNAQQWLQETSQ POLINOMIALXNYM, IBO DLQ ZAPISI ^ISLA K TREBUETSQ PORQDKA log2 K SIMWOLOW; ON TAKVE OKAZYWAETSQ PEREBORNYM | PEREBIRAETWSE WARIANTY ZAPOLNENNOSTI R@KZAKA. oDNAKO PRI NE O^ENX BOLX[IHOB_EMAH R@KZAKA MOVNO DOWOLXNO BYSTRO POLU^ITX RE[ENIE. dLQOBOB]ENIQ UKAZANNOGO SWOJSTWA DADIM20oPREDELENIE 8. oBOZNA^IM ^EREZ num(I) MAKSIMALXNOE PO MODUL@ CELOE ^ISLO (ILI 0), FIGURIRU@]EE PRI ZADANII^ISLOWYH PARAMETROW DLQ INDIWIDUALXNOJ ZADA^I I, I ^EREZ jIj =: je(I)j | DLINUZAPISI I. aLGORITM a RE[ENIQ MASSOWOJ ZADA^I p (NE OBQZATELXNO RASPOZNAWANIQ SWOJSTW) NAZYWAETSQ PSEWDOPOLINOMIALXNYM, ESLIDLQ NEKOTOROGO POLINOMA p(; ) WYPOLNENO tA (e(I)) < p(jIj,num(I))8I 2 p.pRIMEROM PSEWDOPOLINOMIALXNOGO ALGORITMA QWLQETSQ ALGORITMDINAMI^ESKOGO PROGRAMMIROWANIQ DLQ RE[ENIQ zr.

dLQ MNOGIH DRUGIH ZADA^ (W ^ASTNOSTI, km) PSEWDOPOLINOMIALXNYH ALGORITMOW NEIZWESTNO. ~TOBY WYDELITX KLASS TAKIH ZADA^, WWEDEM PONQTIE POLINOMIALXNOGO SUVENIQ MASSOWOJ ZADA^I p KAK MNOVESTWA TEH INDIWIDUALXNYH ZADA^, ^ISLOWYE PARAMETRY KOTORYH NE PREWOSHODQT,POLINOMA OT DLINY WHODApp() =: fI 2 pj num(I) < p(jIj)g:oPREDELENIE 9. mASSOWAQ ZADA^A p RASPOZNAWANIQ SWOJSTW NAZYWAETSQ SILXNO NP-POLNOJ, ESLI EE POLINOMIALXNOE SUVENIE NPPOLNO, T.E. 9p() | POLINOM: pp() 2 NPC.pRIMERAMI SILXNO NP-POLNYH ZADA^ QWLQ@TSQ wyp I 3-wyp(KAK SOWPADA@]IE SO SWOIMI POLINOMIALXNYMI SUVENIQMI), bln(POSKOLXKU wyp BYLA SWEDENA K EE POLINOMIALXNOMU SUVENI@, WKOTOROM MODULI PRAWYH ^ASTEJ NE PREWY[A@T n), cln (KAK OBOB]ENIE bln W OTLI^IE OT zr), A TAKVE km [1, S.

123-124].tEOREMA 4. eSLI P =6 NP, TO NI DLQ KAKOJ SILXNO NP-POLNOJZADA^I NE SU]ESTWUET PSEWDOPOLINOMIALXNOGO ALGORITMA RE[ENIQ.dOKAZATELXSTWO PROWEDEM OT PROTIWNOGO. pUSTX dmt a RE[AET SILXNO NP-POLNU@ ZADA^U p I 8I 2 p tA (e(I)) < p0 (jIj,num(I))DLQ POLINOMA p0 (; ). tOGDA 8I 2 pp() tA (e(I)) < p0 (jIj; p(jIj)) =p00 (jIj), T.E. pp() 2 P | PROTIWORE^IE S pp() 2 NPC ILI UTWERVDENIEM 6.sILXNO NP-POLNYE ZADA^I S^ITA@TSQ NAIBOLEE TRUDNYMI DLQS^ETA SREDI WSEH ZADA^ KLASSA NP.

dALEE MY POKAVEM, ^TO DLQ PODOBNYH ZADA^ W OPTIMIZACIONNOJ POSTANOWKE OTSUTSTWU@T \FFEKTIWNYE ALGORITMY POISKA DAVE PRIBLIVENNOGO RE[ENIQ. rEKOMENDUEMYM PODHODOM K IH RE[ENI@ QWLQETSQ RAZBIENIE NA PODZADA^I p0 :D(p0 ) D(p); Y(p0 ) = Y(p) \ D(p0 ), ANALIZ SLOVNOSTI PODZADA^21I RAZRABOTKA SHEM PEREBORA (SM. W xx10,12) DLQ p0 2 NPC. pRI \TOMDLQ SILXNO NP-POLNYH PODZADA^ NE UDAETSQ ISPOLXZOWATX METOD DINAMI^ESKOGO PROGRAMMIROWANIQ W KA^ESTWE SPOSOBA PEREBORA (IBO,PO-WIDIMOMU, REALIZU@]IE EGO ALGORITMY PSEWDOPOLINOMIALXNY) ISLEDUET ORIENTIROWATXSQ NA SHEMU METODA WETWEJ I GRANIC (xx10,11).x4. pRIBLIVENNOE RE[ENIE ZADA^KOMBINATORNOJ OPTIMIZACIIoPREDELENIE ZADA^I KOMBINATORNOJ OPTIMIZACII I PRIBLIVENNOGO ALGORITMA EE RE[ENIQ.

uTWERVDENIE O RAZNICE MEVDU PRIBLIVENNYM I TO^NYM OPTIMUMOM DLQ ZADA^I O R@KZAKE. oPREDELENIE "-PRIBLIVENNOGO ALGORITMA I POLNOSTX@ POLINOMIALXNOJ PRIBLIVENNOJ SHEMY (ppps). sWQZX MEVDU SU]ESTWOWANIEM ppps IPSEWDOPOLINOMIALXNOSTX@. tEOREMA OB OTSUTSTWII ppps DLQ ZADA^ OPTIMIZACII, SOOTWETSTWU@]IH SILXNO NP-POLNYM ZADA^AMRASPOZNAWANIQ SWOJSTW. pRIMER ZADA^I O KOMMIWOQVERE.wAVNYJ KLASS MASSOWYH ZADA^ OBRAZU@T ZADA^I DISKRETNOJ(KOMBINATORNOJ) OPTIMIZACII. dLQ OPTIMIZACIONNOJ POSTANOWKIZADA^I p RE[ENIEM KAVDOJ INDIWIDUALXNOJ ZADA^I I2p QWLQETSQPROIZWOLXNAQ REALIZACIQ OPTIMUMAOptp (I) =:maxz 2 S p ( I)fp (I; z );T.E. TAKAQ TO^KA z (I) 2 Sp (I), DLQ KOTOROJ fp (I; z (I)) = Optp (I).zDESX Sp (I) | OBLASTX DOPUSTIMYH ZNA^ENIJ DISKRETNOJ (CELO^ISLENNOJ) PEREMENNOJ z, fp (I; ) : Sp (I) ! Z | CELEWAQ FUNKCIQINDIWIDUALXNOJ ZADA^I I OPTIMIZACII, ZNAK max W POSTANOWKE ZADA^I MOVET BYTX ZAMENEN NA min.bUDEM OBOZNA^ATX S I f TE KOMPONENTY WHODNOGO SLOWA = e(I),OPREDELQ@]EGO PARAMETRY INDIWIDUALXNOJ ZADA^I I 2 p, KOTORYEZADA@T DOPUSTIMU@ OBLASTX (OGRANI^ENIQ ZADA^I) I FUNKCI@ CELI SOOTWETSTWENNO.

nAPRIMER, DLQ zr IMEEM fzr (; z) = hc; zi,Szr () = fz = (z1 ; : : : ; zn )jzj 2 f0; 1g 8j = 1; n I hw; z i K g,S = (n; w; K ) I f = c: zDESX I DALEE ZNAK h; i OBOZNA^AET SKALQRNOE PROIZWEDENIE WEKTOROW.22oPREDELENIE 10. aLGORITM a NAZYWAETSQ PRIBLIVENNYM ALGORITMOM RE[ENIQ MASSOWOJ ZADA^I p OPTIMIZACII, ESLI 8I 2 pON NAHODIT NEKOTORU@ TO^KU IZ DOPUSTIMOJ OBLASTI za (I) 2 Sp (I),PRINIMAEMU@ ZA PRIBLIVENNOE RE[ENIE. zNA^ENIE fp (I; za (I)) NAZYWAETSQ PRIBLIVENNYM ZNA^ENIEM OPTIMUMA I OBOZNA^AETSQ A(I).gOWORITX OB ABSOL@TNOJ POGRE[NOSTI PRIBLIVENNOGO ALGORITMA RE[ENIQ MASSOWOJ ZADA^I OPTIMIZACII (NA KLASSE WSEWOZMOVNYHINDIWIDUALXNYH ZADA^) NE IMEET BOLX[OGO SMYSLA, KAK POKAZYWAETuTWERVDENIE 11. eSLI P 6= NP, TO NI DLQ KAKOJ KONSTANTYC > 0 NE SU]ESTWUET POLINOMIALXNOGO PRIBLIVENNOGO ALGORITMA aRE[ENIQ zr S OCENKOJ jOptzr (I) A(I)j C 8I 2 zr.dOKAZATELXSTWO PROWEDEM OT PROTIWNOGO.

pUSTX NAJDENY TAKIE C I a. pOSTROIM ALGORITM a0 SLEDU@]IM OBRAZOM: 8I 2 zrDOMNOVIM WSE KO\FFICIENTY cj NA C + 1 | POLU^IM INDIWIDUALXNU@ ZADA^U I0 2 zr, K KOTOROJ PRIMENIM ALGORITM a I RAZDELIMPOLU^ENNYJ OTWET NA C + 1, T.E. A0 (I) = A(I0 )=(C + 1). o^EWIDNO, Optzr (I0 ) = (s + 1)Optzr (I) I IZ POLINOMIALXNOSTI ALGORITMA a WYTEKAET POLINOMIALXNOSTX a0 .

pRI \TOM EGO TO^NOSTX RAWNAjOptzr (I) A0 (I)j = jOptzr (I0 ) A(I0 )j=(C + 1) C=(C + 1) < 1,T.E. RAWNA NUL@ (TAK KAK WSE ZNA^ENIQ CELEWOJ FUNKCII CELYE). pOLU^ILI POLINOMIALXNYJ ALGORITM TO^NOGO RE[ENIQ zr. pROWERKAOptzr (I) B POLINOMIALXNA, ZNA^IT, POSTROILI I POLINOMIALXNYJ ALGORITM RE[ENIQ zr W POSTANOWKE RASPOZNAWANIQ SWOJSTW, ^TOS U^ETOM UNIWERSALXNOSTI POSLEDNEJ PROTIWORE^IT UTWERVDENI@ 6.oPREDELENIE 11. pRIBLIVENNYJ ALGORITM a RE[ENIQ MASSOWOJZADA^I p OPTIMIZACII NAZYWAETSQ "-PRIBLIVENNYM ALGORITMOM RE[ENIQ p DLQ NEKOTOROGO " > 0, ESLIjOptp (I) A(I)j < ";8I 2 pjOptp (I)jT.E. 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 ALGORITM SLOVNOSTX@ TA" (jIj) < p(jIj; 1="):A" RE[ENIQ p S WREMENNOJtEOREMA 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 IMEETSQeSLI DLQ p OPTIMIZACII SOOTWETSTWU@]AQ EJ ptEOREMARASPOZNAWANIQ 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.eSLI P 6= NP, TO NI DLQ KAKOGO " > 0 NEuTWERVDENIESU]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).6.12.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 .