n m nOWIKOWA .
.
osnowy optimizacii (KURS LEKCIJ)
moskwa 1
1998
oTWETSTWENNYJ REDAKTOR AKADEMIK ran p s kRASNO]EKOW w SVATOJ FORME DAETSQ IZLOVENIE OSNOW TEORII SLOVNOSTI LINEJNOGO PROGRAMMIROWANIQ lp S OPISANIEM POLINOMIALX NYH ALGORITMOW CELO^ISLENNOGO lp MATEMATI^ESKOGO PROGRAM MIROWANIQ NEOBHODIMYE USLOWIQ \KSTREMUMA PRI OGRANI^ENIQH NERAWENSTWAH LOKALXNYE METODY BEZUSLOWNOJ OPTIMIZACII METOD [TRAFOW IDEI GLOBALXNOJ OPTIMIZACII SHEM METODOW DINAMI^E SKOGO PROGRAMMIROWANIQ I WETWEJ I GRANIC rABOTA NAPISANA NA BAZE SEMESTROWOGO KURSA LEKCIJ ^ITAEMOGO AWTOROM STUDENTAM GO KURSA PROGRAMMISTSKOGO POTOKA FAKULXTETA wmIk mgu S U^ETOM DOPOLNENIJ I ZAME^ANIJ UKAZANNYH STUDEN TAMI aWTOR BLAGODARIT WSEH STUDENTOW SODEJSTWOWAW[IH IZDANI@ \TOGO KURSA I PREDLOVIW[IH ISPRAWLENIQ SPOSOBSTWU@]IE EGO ULU^ [ENI@ W TOM ^ISLE lASKAWOGO sERGEQ sANNIKOWA aNDREQ I sWAHINA nIKOLAQ zAME^ENNYE OPE^ATKI I NETO^NOSTI PROSXBA SOOB]ATX AW TORU PO ADRESU rABOTA ^ASTI^NO PODDERVANA GRANTOM rffi .
.
,
(
) |
,
-
,
-
(
-
,
,
,
),
-
.
,
4-
,
,
.
-
,
,
,
,
-
,
.
-
[email protected]
No.96-01-00786.
rECENZENTY s k zAWRIEW a w lOTOW :
.
.
.
.
,
2
n m c
.
.
nOWIKOWA
3
~ASTX 1. wwedenie w teori` slovnosti
lITERATURA: 1. g\RI m., dVONSON d. wY^ISLITELXNYE MA[INY I TRUDNORE[AEMYE ZADA^I. m.: mIR, 1982. 2. pAPADIMITRIU h., sTAJGLIC k. kOMBINATORNAQ OPTIMIZACIQ. m.: mIR, 1985.
x1. pONQTIE O SLOVNOSTI RE[ENIQ ZADA^
oSNOWNYE OPREDELENIQ: INDIWIDUALXNAQ I MASSOWAQ ZADA^I, KODI ROWKA, ALGORITM RE[ENIQ MASSOWOJ ZADA^I, WREMENNAQ SLOVNOSTX ALGORITMA. kLASSY P I NP (FORMALXNYE OPREDELENIQ, PRIMERY). 1. nA WOPROS, DLQ ^EGO NADO IMETX PREDSTAWLENIE O SLOVNOSTI RE[AEMYH ZADA^, NAIBOLEE NAGLQDNYJ OTWET DAN WO WWEDENII K KNIGE [1]. w \TOJ KNIGE TAKVE PRIWODITSQ BOLEE 500 ZADA^ (IZ SAMYH RAZNYH OBLASTEJ, WKL@^AQ TEORI@ GRAFOW I SETEJ, TEORI@ RASPISANIJ, TEORI@ AWTOMATOW I QZYKOW, OPTIMIZACI@ PROGRAMM, BAZY DANNYH, IGRY I GOLOWOLOMKI I T.P.), DLQ KOTORYH W NASTOQ]EE WREMQ NET OSNOWANIJ NADEQTXSQ POSTROITX \FFEKTIWNYE ALGORITMY IH RE[ENIQ. ~TO \TO ZNA^IT FORMALXNO, BUDET RASSKAZANO W DANNOM RAZDELE (xx1{4), A SOOTWETSTWU@]IE PRAKTI^ESKIE WYWODY KAVDYJ ^ELOWEK, TAK ILI INA^E SWQZANNYJ S RAZRABOTKOJ ALGORITMOW I PROGRAMM, DELAET DLQ SEBQ SAM. kROME TOGO, TEORIQ SLOVNOSTI | NOWAQ, MODNAQ, INTENSIWNO RAZWIWA@]AQSQ OBLASTX MATEMATIKI I KIBERNETIKI, EE TERMINOLOGIQ [IROKO RASPROSTRANENA W SOWREMENNOJ NAU^NOJ LITERATURE I TREBUET OPREDELENNOGO S NEJ ZNAKOMSTWA. pOQWLENIE WY^ISLITELXNOJ TEHNIKI PRIWELO K TOMU, ^TO WSE REVE PRIHODITSQ RE[ATX OTDELXNU@ KONKRETNU@ ZADA^U, A WSE BOLX[E PISATX PROGRAMMY, RASS^ITANNYE NA CELYJ KLASS ZADA^, POLU^A@]IHSQ ODNA IZ DRUGOJ ZAMENOJ RQDA ISHODNYH DANNYH. pO\TOMU IMEET SMYSL GOWORITX O SLOVNOSTI NE DLQ ODNOJ INDIWIDUALXNOJ ZADA^I I, A DLQ MASSOWOJ ZADA^I, ILI PROBLEMY p, SOOTWETSTWU@]EJ MNOVESTWU INDIWIDUALXNYH ZADA^. fORMALXNO MASSOWAQ ZADA^A p OPREDELQETSQ 0 OB]IM SPISKOM WSEH PARAMETROW ZADA^I (SWOBODNYH PARAME1 TROW, ZNA^ENIQ KOTORYH NE ZADANY), 4
0 FORMULIROWKOJ SWOJSTW KOTORYM DOLVEN UDOWLETWORQTX OTWET RE[ENIE ZADA^I iNDIWIDUALXNAQ ZADA^A I 2 p POLU^AETSQ IZ p ESLI WSEM PARA METRAM PRISWOITX KONKRETNYE ZNA^ENIQ dLQ PRIMERA RASSMOTRIM ZADA^U KOMMIWOQVERA NAJTI MINI MALXNYJ MAR[RUT OBHODA GRUPPY OB_EKTOW USLOWNO GOWORQ GORODOW S WOZWRATOM W NA^ALXNU@ TO^KU dLQ p KOMMIWOQVERA WWEDEM 0 WHODNYE PARAMETRY ^ISLO GORODOW m ILI MNOVESTWO GORODOW C fc1;:::;cmg I NABOR RASSTOQNIJ MEVDU GORODAMI 2
,
(
).
,
-
.
:
-
(
,
)
.
1
=
:
fd ci;cj >
ci;cj 2 C; i 6 j g 0 TREBOWANIQ K RE[ENI@ c(1);:::;c(m) REALIZUET (
2
)
0 : :
min
"m 1 X
=
[
;
]
#
d c(i);c(i+1) d c(m);c(1) ; (
i=1
)+
(
)
GDE MINIMUM BERETSQ PO WSEM WOZMOVNYM PERESTANOWKAM NA MNOVE STWE INDEKSOW GORODOW kONKRETIZIRUEM PARAMETRY 0 ^TOBY POLU ^ITX INDIWIDUALXNU@ ZADA^U I KOMMIWOQVERA m d c1;c2
-
.
d c1;c3 d ci;cj
1 ,
:
= 4,
(
-
) = 10,
d c1;c4 d c2;c4 d c3;c4 d c3;c2 d cj ;ci tOGDA W ZADA^E I OPTIMALXNYM OKAZYWAETSQ MAR[RUT c1 ;c2 ;c4 ;c3 REALIZU@]IJ PUTX MINIMALXNOJ DLINY kROME PERWI^NYH PONQTIJ MASSOWOJ I INDIWIDUALXNOJ ZADA^I p I I MY BUDEM ISPOLXZOWATX TERMIN ALGORITM I OBOZNA^ENIE a DLQ PO[AGOWOJ PROCEDURY RE[ENIQ ZADA^I W ^ASTNOSTI MA[INY tX@ RINGA ILI PROGRAMMY DLQ |wm bUDEM GOWORITX ^TO ALGORITM a RE[AET MASSOWU@ ZADA^U p ESLI DLQ L@BOJ INDIWIDUALXNOJ ZADA^I I 2 p ALGORITM a PRIMENIM K I T E OSTANAWLIWAETSQ ZA KONE^NOE ^ISLO [AGOW I 8I 2 p ALGORITM a DAET RE[ENIE ZADA^I I nAPRI MER DLQ p KOMMIWOQVERA SU]ESTWUET ALGORITM KOTORYJ RE[AET EE NA OSNOWE POLNOGO PEREBORA WSEH MAR[RUTOW PERESTANOWOK (
) = 5,
(
)
=
(
[
(
) = 9,
(
) = 9,
(
) = 3,
(
) = 6,
).
],
27. (
)
(
),
-
.
,
,
(
. .
)
.
,
-
,
(
).
bOLX[INSTWO DISKRETNYH I KOMBINATORNYH ZADA^ DOPUSKAET RE [ENIE S POMO]X@ NEKOTOROGO PROCESSA PEREBORA WARIANTOW ODNAKO ^ISLO WOZMOVNYH WARIANTOW RASTET \KSPONENCIALXNO W ZAWISIMOSTI OT RAZMEROW ZADA^I TAK W ZADA^E KOMMIWOQVERA m MAR[RUTOW -
,
(
,
!
5
).
pO\TOMU PEREBORNYE ALGORITMY RE[ENIQ MASSOWYH ZADA^ S^ITA@T SQ NE\FFEKTIWNYMI MOGUT RE[ATX LI[X NEBOLX[IE INDIWIDUALX NYE ZADA^I w OTLI^IE OT NIH \FFEKTIWNYMI NAZYWA@TSQ POLINOMIALXNYE ALGORITMY RE[ENIQ MASSOWOJ ZADA^I T E TAKIE KOTORYE RE[A@T PROIZWOLXNU@ I 2 p ZA WREMQ OGRANI^ENNOE POLINOMOM OT RAZMERA I nESMOTRQ NA OPREDELENNU@ USLOWNOSTX \TOGO RAZDELE NIQ S TO^KI ZRENIQ PRAKTI^ESKOGO S^ETA ONO OB_QSNQETSQ PREVDE WSEGO TEM ^TO CENTRALXNYM DLQ DISKRETNOJ OPTIMIZACII QWLQET SQ WOPROS MOVNO LI POSTROITX ALGORITM RE[ENIQ MASSOWOJ ZADA^I T E L@BOJ INDIWIDUALXNOJ NE PEREBIRA@]IJ WSEH ILI PO^TI WSEH WARIANTOW EE RE[ENIQ eSLI DLQ MASSOWOJ ZADA^I p SU]ESTWUET PO LINOMIALXNYJ ALGORITM EE RE[A@]IJ ZNA^IT EE MOVNO RE[ITX NE PUTEM PEREBORA \FFEKTIWNO uKAZANNYE ZADA^I p NAZYWA@TSQ POLINOMIALXNYMI pEREJDEM K IH FORMALXNOMU OPREDELENI@ 2 fORMALIZACIQ PROWODITSQ DLQ ZADA^ RASPOZNAWANIQ SWOJSTW |TO MASSOWYE ZADA^I PREDPOLAGA@]IE OTWET DA ILI NET W KA^ESTWE RE[ENIQ tAKIM OBRAZOM W P 0 OPREDELENIQ p RASPOZNA WANIQ SWOJSTW STOIT NEKOTORYJ ALXTERNATIWNYJ WOPROS I RE[ENIEM KAVDOJ INDIWIDUALXNOJ ZADA^I I 2 p QWLQETSQ PRAWILXNOE RASPO ZNAWANIE PRINADLEVIT LI ONA K ZADA^AM S OTWETOM DA pOSLEDNEE PODMNOVESTWO MNOVESTWA INDIWIDUALXNYH ZADA^ BUDEM OBOZNA^ATX Y tEPERX WWEDEM OBOZNA^ENIE D DLQ MNOVESTWA WSEH WOZMOVNYH ZNA^ENIJ PARAMETROW ZADANNYH W P 0 OPREDELENIQ p o^EWIDNO ^TO NABOR D(p) Y(p) POLNOSTX@ HARAKTERIZUET SOOTWETSTWU@ ]U@ MASSOWU@ ZADA^U p RASPOZNAWANIQ SWOJSTW nESMOTRQ NA SPE CIFI^NOSTX POSTANOWKI KLASS ZADA^ RASPOZNAWANIQ SWOJSTW QWLQET SQ DOSTATO^NO [IROKIM PO KRAJNEJ MERE DLQ L@BOJ ZADA^I DIS KRETNOJ OPTIMIZACII MOVNO UKAZATX ANALOGI^NU@ p RASPOZNAWANIQ SWOJSTW w ^ASTNOSTI DLQ p KOMMIWOQVERA ESLI WWESTI W P 0 E]E ODIN PARAMETR B DLINU MAR[RUTA TO WOPROS W P 0 SU]ESTWU ET LI MAR[RUT DLINY NE PREWY[A@]EJ B DAET EE PEREFORMULI ROWKU KAK ZADA^I RASPOZNAWANIQ SWOJSTW pOLU^ENNAQ p KOMMIWO QVERA IMEET W LITERATURE OBOZNA^ENIE km ILI zk DLQ NEE -
(
-
).
,
. .
,
,
\
"
.
-
,
,
-
,
(
. .
),
.
-
,
,
|
,
.
.
.
.
.
|
,
\
.
,
"
\
"
.2
-
-
,
\
".
.
,
[
.1
,
.
,
]
-
.
-
,
-
:
.
,
,
-
,
|
.1
,
.2
,
\
-
?"
-
.
-
km fC; fd ci;cj 2 Z+j ci;cj 2 C; i < j g; B 2 Z+g: (
D(
) =
(
[2]),
)
zDESX I DALEE Z+ MNOVESTWO NATURALXNYH ^ISEL Z CELYH dLQ FORMALIZACII RAZMERA INDIWIDUALXNOJ ZADA^I SWQVEM S |
,
\
"
6
|
.
KAVDOJ PROBLEMOJ p OPREDELENNU@ SHEMU KODIROWANIQ (KODIROWKU). wWEDEM KONE^NOE MNOVESTWO | ALFAWIT = fi g, NAPRIMER = f0; 1g, A TAKVE MNOVESTWO SLOW NAD ALFAWITOM | PROIZWOLXNYH KONE^NYH POSLEDOWATELXNOSTEJ, SOSTAWLENNYH IZ SIMWOLOW ALFAWITA, WOZMOVNO POWTORQ@]IHSQ, = i1 i2 :::in ; ij 2 8ij ; NAPRIMER, PUSTOE MNOVESTWO ; ILI 011000. ~ISLO n NAZYWAETSQ DLINOJ SLOWA I OBOZNA^AETSQ ZNAKOM MODULQ, n = jj. kODIROWKOJ ZADA^I p NAZOWEM TAKOE OTOBRAVENIE e: p! , STAWQ]EE W SOOTWETSTWIE L@BOJ INDIWIDUALXNOJ ZADA^E I 2 p EE KOD e(I) = 2 (SLOWO IZ ALFAWITA ), ^TO 1 WOZMOVNO ODNOZNA^NOE DEKODIROWANIE: 8I1 6= I2 e(I1 ) 6= e(I2 ); 1 POLINOMIALXNO WY^ISLIMY: SU]ESTWUET ALGORITM, REA2 e; e LIZU@]IJ e; e 1 , I POLINOM p(), DLQ KOTOROGO 8I 2 p WREMQ OPREDELENIQ e(I) I e 1 (e(I)) NE PREWOSHODIT p(je(I)j); 0 3 KODIROWKA NEIZBYTO^NA: DLQ L@BOJ DRUGOJ KODIROWKI e , UDO 0 WLETWORQ@]EJ USLOWIQM 1 ,2 , NAJDETSQ POLINOM p () TAKOJ, ^TO 8I 2 p je(I)j < p0(je0(I)j). nAPRIMER, DLQ ZAPISI CELYH ^ISEL NEIZBYTO^NOJ QWLQETSQ L@BAQ k-I^NAQ SISTEMA S^ISLENIQ S k > 1, KODIROWKA ^ISEL TEM VE KOLI^ESTWOM PALO^EK (SLU^AJ k = 1) IZBYTO^NA.
upravnenie 1. pREDLOVITX NEIZBYTO^NU@ KODIROWKU I OCENITX PO PORQDKU DLINU WHODA ZADA^I KOMMIWOQVERA, SRAWNITX POLU^ENNU@ OCENKU S UKAZANNOJ W [1] NA S. 35: m d 2 Be fd 2 d ci;cj ej ci;cj 2 C g zDESX I DALEE ZNAKOM de OBOZNA^AETSQ BLIVAJ[EE CELOE SWERHU K ^ISLU W SKOBKAH A bc CELAQ ^ASTX ^ISLA nA^INAQ S \TOGO MOMENTA W xx MY BUDEM KAK PRAWILO RASSMA TRIWATX p RASPOZNAWANIQ SWOJSTW OGOWARIWAQ DRUGIE SLU^AI OSOBO pOSLE TOGO KAK DLQ MASSOWOJ ZADA^I p WWEDENA KODIROWKA S L@ BOJ INDIWIDUALXNOJ ZADA^EJ I 2 p BUDET SWQZANO NEKOTOROE SLOWO W ALFAWITE \TOJ KODIROWKI sLOWA KOTORYE SOOTWETSTWU@T INDI WIDUALXNYM ZADA^AM RASPOZNAWANIQ SWOJSTW IME@]IM OTWET DA USLOWIMSQ S^ITATX PRAWILXNYMI I MNOVESTWO PRAWILXNYH SLOW W NAZOWEM QZYKOM fORMALXNO QZYK L p e : e Y(p) : : f 2 j ALFAWIT e; e I ; I 2 Y p g: s ALGORITMOM a RE[ENIQ ZADA^I p RASPOZNAWANIQ SWOJSTW BU DEM ASSOCIIROWATX MA[INU tX@RINGA PROGRAMMU DLQ DETERMINI +
log
,
+ max
log
,
1{3
(
)
|
.
.
,
,
-
,
.
,
.
,
-
,
\
\
",
"
.
=
-
,
(
|
=
, ) = ( )
(
)=
(
)
-
(
7
-
ROWANNOJ MA[INY tX@RINGA S WHODNYM ALFAWITOM I KONE^NYMI SOSTOQNIQMI qY DA I qN NET I ANALOGI^NO NAZOWEM QZYKOM ALGORITMA a MNOVESTWO SLOW PRINIMAEMYH a S KOTORYMI NA WHODE W SOSTOQNII qY DA a OSTANAWLIWAETSQ ALFAWIT a I a qY g: L a : f 2 j oPREDELENIE 1. aLGORITM a RE[AET MASSOWU@ ZADA^U p S KO DIROWKOJ e ESLI L a L p e I 8 2 a OSTANAWLIWAETSQ oBOZNA^IM ta WREMQ RABOTY NAD SLOWOM 2 ^ISLO [AGOW ALGORITMA a DO OSTANOWKI wREMENNOJ SLOVNOSTX@ ALGORITMA a RE[ENIQ MASSOWOJ ZADA^I p NAZOWEM FUNKCI@ Ta OPREDELQEMU@ KAK )
(\
")
(\
")
,
(
| \
(
) =
"),
|
,
(
) =
-
,
(
(
) =
(
, )
.
)
(
)
.
( ),
Ta n 2: jj
) =
max
(
)
tAKIM OBRAZOM PRI OCENKE WREMENNOJ SLOVNOSTI ALGORITMOW MY RASS^ITYWAEM NA HUD[U@ IZ WOZMOVNYH INDIWIDUALXNYH ZADA^ DANNOGO RAZMERA POSKOLXKU ZARANEE NE IZWESTNO S KAKOJ KONKRET NOJ ZADA^EJ PRIDETSQ RABOTATX ,
\
(
"
),
,
-
.
upravnenie 2. dATX ALGORITM RASPOZNAWANIQ PROSTOTY ^ISLA, OCENITX WREMENNU@ SLOVNOSTX ALGORITMA. oPREDELENIE 2. kLASS POLINOMIALXNO RAZRE[IMYH ZADA^ : fL p e j 9a RE[A@]IJ p S KODIROWKOJ e; 9p POLINOM P Ta n < p n 8n 2 Z+g: eSLI DLQ ZADA^I p SU]ESTWUET TAKAQ KODIROWKA e ^TO L p e 2 P TO BUDEM NAZYWATX ZAD ^U p POLINOMIALXNO RAZRE[IMOJ ILI PROSTO POLINOMIALXNOJ I POLXZOWATXSQ OBOZNA^ENIEM p2P OTOVDE STWLQQ MASSOWU@ ZADA^U I QZYK s U^ETOM USLOWIQ NEIZBYTO^NOSTI KODA UKAZANNAQ PROCEDURA KORREKTNA IBO DLQ POLINOMIALXNOJ p PO LU^AEM L p e 2 P 8e = (
(
)
, )
(
,
( ) |
:
)
,
,
(
, )
a
,
-
. (
,
(
, )
-
.)
pRIMEROM POLINOMIALXNOJ ZADA^I QWLQETSQ RASPOZNAWANIE ^ET NOSTI CELOGO ^ISLA s E]E ODNOJ POLINOMIALXNOJ ZADA^EJ MY WSTRE TIMSQ W RAZD dLQ ZADA^I RASPOZNAWANIQ PROSTOTY ^ISLA p~ WOPROS O EE POLINOMIALXNOSTI POKA OTKRYT dLQ RQDA DRUGIH ZADA^ UDAETSQ DOKAZATX IH NEPOLINOMIALXNOSTX tAK IZWESTNY ALGORITMI^ESKI NERAZRE[IMYE ZADA^I KOGDA NE SU]ESTWUET ALGORITMA RE[A@]EGO L@BU@ INDIWIDUALXNU@ ZADA^U T E 8a 9I 2 p a NE PRIMENIM K I W ^ASTNOSTI tA e I 1 NAPRI MER Q PROBLEMA gILXBERTA PO DANNOMU MNOGO^LENU g S CELYMI
-
. (
-
.2.)
(
)
.
.
,
1)
,
,
:
, 10-
,
,
:
8
,
. .
( ( )) =
;
-
KO\FFICIENTAMI WYQSNITX IMEET LI URAWNENIE g CELO^ISLENNOE RE[ENIE NERAZRE[IMOSTX DOKAZAL ` m mATIQSEWI^ W G ZADA^I NE QWLQ@]IESQ ZADA^AMI RASPOZNAWANIQ SWOJSTW DLQ KOTORYH DLINA ZAPISI RE[ENIQ PREWOSHODIT L@BOJ NAPERED ZADAN NYJ POLINOM OT DLINY WHODA NAPRIMER W ZADA^E KOMMIWOQVERA ESLI TREBUETSQ NAJTI WSE MAR[RUTY IH \KSPONENCIALXNOE ^ISLO W OSTALXNYH SLU^AQH FORMALXNO IMEEM 8a RE[A@]EGO p S KODIROWKOJ e; 8p 9I 2 p ta e I > p je I j zDESX I DALEE p WOZMOVNO S INDEKSAMI SLUVIT DLQ OBOZNA^ENIQ POLINOMOW w NASTOQ]EE WREMQ DLQ L@BOJ MASSOWOJ ZADA^I p DLQ KOTOROJ DOKAZANO POSLEDNEE USLOWIE POLU^EN I BOLEE SILXNYJ REZULXTAT OT SUTSTWIE POLINOMIALXNOGO ALGORITMA ISPOLXZU@]EGO PROIZWOLXNOE PUSTX BESKONE^NOE ^ISLO PARALLELXNYH PROCESSOROW wOPROS SU ]ESTWU@T LI NEPOLINOMIALXNYE ZADA^I p RASPOZNAWANIQ SWOJSTW KOTORYE OKAZYWA@TSQ POLINOMIALXNO RAZRE[IMYMI PRI WOZMOVNO STI RASPARALLELIWANIQ WY^ISLENIJ QWLQETSQ OSNOWNOJ METODOLOGI ^ESKOJ PROBLEMOJ TEORII SLOVNOSTI OBUSLOWIW[EJ EE FORMIROWANIE KAK SAMOSTOQTELXNOJ NAU^NOJ DISCIPLINY oTWET PO WIDIMOMU DOLVEN BYTX POLOVITELXNYM I UVE UKAZAN BOLX[OJ KLASS MASSO WYH ZADA^ W KA^ESTWE KANDIDATOW SM KLASS NPC W x NO DOKAZATX ILI OPROWERGNUTX \TU GIPOTEZU W DANNYJ MOMENT PREDSTAWLQETSQ NEREALXNYM dLQ EE FORMALIZACII WWODITSQ OB_EML@]IJ P KLASS NEDETERMINIROWANNO POLINOMIALXNYH ZADA^ NP 3 oPREDELIM NEDETERMINIROWANNU@ MA[INU tX@RINGA ndmt ^ KAK NABOR OBY^NYH DETERMINIROWANNYH MA[IN tX@RINGA A dmt A S S ALFAWITOM GDE S PROBEGAET WSE MNOVESTWO SLOW IZ ,
= 0
(
.
2)
.
1970
(
.);
),
-
,
,
(
);
3)
,
( )
:
( ( ))
(
( ) ).
( ),
,
.
,
,
:
-
,
-
,
(
)
.
,
-
,
-
(
).
,
-
,
,
-
(
.
2),
.
|
.
.
(
|
(
)
(
)
,
:
)
|
^ A
: fA S gS2 :
=
(
)
ndmt a^ OSTANAWLIWAETSQ KOGDA OSTANAWLIWAETSQ PERWAQ IZ dmt a S PRINIMA@]AQ WHODNOE SLOWO sOOTWETSTWU@]IM KONE^NYM SO STOQNIEM BUDET qY qZYK ndmt MNOVESTWO SLOW PRINIMAEMYH HOTQ BY ODNOJ dmt: A S IZ A^ ,
(
),
.
.
L a^ f 2 j 9S 2 (
^(
-
|
) =
)
:
,
:
2L a S g (
(
)) .
(
)
sLOWA S W OPREDELENII ndmt MOVNO PROINTERPRETIROWATX KAK PODSKAZKI K RE[ENI@ DOGADKI TOGDA dmt a S PROWERQET DLQ (
),
9
WHODNOGO SLOWA PODSKAZKU S I W SLU^AE PRAWILXNOSTI OSTANAWLI WAETSQ W SOSTOQNII qY ndmt A^ PROWERQET DLQ WHODNOGO SLOWA WSE WOZMOVNYE PODSKAZKI I ESLI HOTX ODNA PRAWILXNAQ DOGADKA SU ]ESTWUET TO ndmt OSTANAWLIWAETSQ S OTWETOM DA w SILU BES KONE^NOSTI ^ISLA DOGADOK W SOSTOQNII qN ndmt OSTANOWITXSQ NE MOVET oPREDELENIE 3. ndmt a^ RE[AET MASSOWU@ ZADA^U p S KODI ROWKOJ e ESLI L p e L a^ T E QZYKI ndmt I ZADA^I SOWPADA@T 8 2 L p e 9S 2 dmt a S OSTANAWLIWAETSQ W SOSTOQNII qY I 8 2 n L p e ; 8S 2 dmt a S NE PRINIMAET NE OSTA NAWLIWAETSQ ILI OSTANAWLIWAETSQ W SOSTOQNII qN oPREDELIM 8 2 L a^ WREMQ RABOTY ndmt a^ NAD SLOWOM KAK MINIMALXNOE IZ WREMEN RABOTY NAD WHODOM dmt a S PRINIMA @]IH S U^ETOM WREMENI PRO^TENIQ SLOWA S T E EGO DLINY
-
.
,
-
,
\
". (
-
,
.)
-
,
(
, ) = ^(
(
, )
),
:
(
. .
(
, )
:
)
,
(
)
(
-
).
^(
)
(
,
(
),
. .
-
):
tA^ : fSj 2LA S gfjS j tA(S) g: wREMENNOJ SLOVNOSTX@ ndmt a^ RE[ENIQ MASSOWOJ ZADA^I p NA ZOWEM FUNKCI@ TA^ 8n 2 Z+ TA^ n 2L^ (a^ ): jj
) =
min
+
( )
(
)
-
^
^
(
) =
( ) :
^ (
max
) =
max
min
( )
+
(
)
pOD^ERKNEM RAZNICU S OPREDELENIEM WREMENNOJ SLOVNOSTI dmt DLQ ndmt RASSMATRIWA@TSQ LI[X SLOWA IZ QZYKA SOOTWETSTWU@]IE IN DIWIDUALXNYM ZADA^AM S OTWETOM DA oPREDELENIE 4. kLASS NEDETERMINIROWANNO POLINOMIALXNYH ndmt RE[A@]AQ p S KODIROWKOJ ZADA^ NP : fL p e j 9a^ e; 9p POLINOM TA^ n < p n 8n 2 Z+g: eSLI DLQ ZADA ^I p SU]ESTWUET TAKAQ KODIROWKA e ^TO L p e 2 NP TO BUDEM NAZYWATX ZADA^U p NEDETERMINIROWANNO POLINOMIALXNOJ I POLXZO WATXSQ OBOZNA^ENIEM p2NP KAK I DLQ KLASSA P KORREKTNYM pRIMEROM NEDETERMINIROWANNO POLINOMIALXNOJ ZADA^I QWLQETSQ km IBO W KA^ESTWE DOGADKI MOVNO ISPOLXZOWATX MAR[RUT I PRO WERKA EGO DOPUSTIMOSTI POLINOMIALXNA oTMETIM ^TO POLINOMIALXNOSTX PROWERKI GARANTIRUETSQ TOLXKO DLQ INDIWIDUALXNYH ZADA^ S OTWETOM DA I WOZMOVNO LI[X PRI
:
(
\
=
( ) |
(
, ) :
|
^
(
-
").
,
)
(
)
-
,
(
, )
,
-
(
,
).
,
-
.
,
\
10
" (
,
EDINSTWENNOJ PODSKAZKE A DLQ I 2 D p n Y p ndmt PROSTO NE OSTANOWITSQ w \TOM SU]ESTWENNOE OTLI^IE KLASSOW P I NP nEPOSREDSTWENNO IZ OPREDELENIJ SLEDUET ),
.
uTWERVDENIE 1.
(
)
(
)
|
P
NP
.
.
wOPROS O NALI^II STROGOGO WKL@^ENIQ I QWLQETSQ FORMALIZACIEJ OSNOWNOJ PROBLEMY TEORII SLOVNOSTI .
x2. NP-POLNYE (UNIWERSALXNYE) ZADA^I
tEOREMA OB \KSPONENCIALXNOJ OCENKE WREMENNOJ SLOVNOSTI DLQ ZADA^ IZ KLASSA NP. kLASS SO-Nr. zADA^I, IME@]IE HORO[U@ HARAKTERIZACI@. oPREDELENIE POLINOMIALXNOJ SWODIMOSTI. kLASS NPC. tEOREMA kUKA (BEZ DOKAZATELXSTWA). kRITERIJ NPPOLNOTY. dOKAZATELXSTWO NP-POLNOTY ZADA^I blH (BULEWY LINEJNYE NERAWENSTWA). 1. rASSMOTRIM PODROBNEE KLASS NP. tEOREMA 1. dLQ L@BOJ NEDETERMINIROWANNO POLINOMIALXNOJ ZADA^I SU]ESTWUET dmt, RE[A@]AQ EE S \KSPONENCIALXNOJ WREMENNOJ SLOVNOSTX@, T.E. 8p2NP 9p() | POLINOM | I dmt a: a RE[AET p I Ta(n) < 2p(n) 8n 2 Z+: dOKAZATELXSTWO. tAK KAK p2NP, TO DLQ L@BOGO SLOWA IZ QZYKA ZADA^I p SU]ESTWUET PRAWILXNAQ DOGADKA S POLINOMIALXNOJ DLINY: jS j < p1 (jj); p1 () | POLINOM, I SU]ESTWUET dmt a(S ) : ta(S)() < p2(jj); p2() | POLINOM. pOSTROIM dmt a, KOTORAQ RABOTAET NAD L@BYM WHODNYM SLOWOM 2 (S L@BOJ INDIWIDUALXNOJ ZADA^EJ I 2 p) SLEDU@]IM OBRAZOM: RASSMATRIWA@TSQ WSE SLOWA S IZ DLINY MENX[E p1 (jj) I DELAETSQ NE BOLEE p2 (jj) [AGOW S KAVDOJ dmt a(S ). eSLI O^EREDNAQ dmt OSTANAWLIWAETSQ W SOSTOQNII qY (T.E. SOOTWETSTWU@]AQ DOGADKA OKAZALASX PRAWILXNOJ), S^ITAEM SLOWO PRINQTYM I RABOTU dmt a ZAKON^ENNOJ; ESLI NI ODNA IZ dmt a(S ) NE OSTANOWILASX ZA OTWEDENNOE WREMQ ILI OSTANOWILASX W SOSTOQNII qN , TO ZAKAN^IWAEM RABOTU dmt a I PRIPISYWAEM EJ KONE^NOE SOSTOQNIE qN . w POSLEDNEM SLU^AE dmt a DELAET NAIBOLX[EE ^ISLO [AGOW, I \TO ^ISLO MENX[E p2 (jj)jjp1 (jj) (WTOROJ SOMNOVITELX RAWEN ^ISLU PROWERQEMYH DOGADOK, jj | ^ISLO SIMWOLOW W ALFAWITE ). oTS@DA UVE NETRUDNO POLU^ITX UTWERVDENIE TEOREMY. 11
dLQ TOGO ^TOBY LU^[E PO^UWSTWOWATX RAZLI^IE KLASSOW P I NP WWEDEM PONQTIE DOPOLNITELXNOJ K p MASSOWOJ ZADA^I p POLU^A @]EJSQ IZ p RASPOZNAWANIQ SWOJSTW ZAMENOJ ALXTERNATIWNOGO WO PROSA OPREDELQ@]EGO OTWET W ZADA^E SM P 0 OPREDELENIQ p W x EGO OTRICANIEM NAPRIMER WOPROSOM W km PRAWDA LI ^TO NE SU]ESTWUET MAR[RUTA DLINY NE PREWOSHODQ]EJ B fORMALXNO ,
,
-
-
,
(
1)
.
.2
,
p
p;
\
p
p nY p ,
,
?".
oPREDELIM KLASSY DOPOLNITELXNYH ZADA^ co-P : fpj p 2 Pg I : co-NP fpj p 2 NPg iZ OPREDELENIJ O^EWIDNO ^TO ESLI dmt a RE[AET p TO dmt a RE[AET p GDE PROGRAMMA dmt a POLU^ENA IZ PROGRAMMY dmt a PROSTOJ ZAMENOJ KONE^NYH SOSTOQNIJ qY I qN DRUG NA DRUGA tAKIM OBRAZOM SPRAWEDLIWO D(
) =
D(
)
Y(
) =
=
D(
)
(
).
=
.
,
,
,
,
.
,
uTWERVDENIE 2.
co-P
P.
=
aNALOGI^NOE UTWERVDENIE DLQ KLASSA NP DO SIH POR NE UDAETSQ NI DOKAZATX NI OPROWERGNUTX PRIWEDENNOE WY[E DLQ dmt RASSU VDENIE NELXZQ OBOB]ITX NA ndmt IBO DLQ INDIWIDUALXNYH ZADA^ I S OTWETOM NET T E I 62 Y p ILI I 2 Y p ndmt NE OSTA NAWLIWAETSQ ZA WREMQ OGRANI^ENNOE POLINOMOM OT DLINY WHODA I w ^ASTNOSTI NE IZWESTNA ndmt RE[A@]AQ km ZA POLINOMIALX NOE WREMQ TAK KAK DLQ NEE NE PRIDUMANO PODSKAZKI POLINOMIALXNOJ DLINY ESTESTWENNYJ WARIANT POKAZATX WSE MAR[RUTY NE PO LINOMIALEN WKL@^ENIE km 2 NP NE DOKAZANO I NE OPROWERGNUTO :
-
,
\
" (
. .
(
),
(
))
-
,
.
,
,
-
,
(
|
|
-
);
.
upravnenie 3. dOKAZATX, ^TO ZADA^A RASPOZNAWANIQ PROSTOTY ^ISLA PRINADLEVIT KLASSU SO-Nr, T.E. p~ 2 NP oPREDELENIE 5. mASSOWAQ ZADA^A RASPOZNAWANIQ SWOJSTW NAZY WAETSQ IME@]EJ HORO[U@ HARAKTERIZACI@ ESLI DLQ NEE WYPOLNENO p 2 NP\co-NP .
-
,
iZ UTWERVDENIQ SLEDUET ^TO P NP\co-NP sOWREMENNAQ GI POTEZA SOSTOIT W RAWENSTWE \TIH KLASSOW oTS@DA I TERMIN HORO[AQ HARAKTERIZACIQ TAK KAK DLQ PODOBNYH ZADA^ ESTX OSNOWANIQ NADE QTXSQ NA WOZMOVNOSTX POSTROENIQ POLINOMIALXNYH ALGORITMOW SM ZADA^U ln LINEJNYE NERAWENSTWA W RAZD oDNAKO DLQ ZADA^I p~ OBLADA@]EJ HORO[EJ HARAKTERIZACIEJ DLQ DOKAZATELXSTWA TO GO ^TO p~ 2 NP SM S DETERMINIROWANNOGO POLINOMIALX NOGO ALGORITMA POKA NE NAJDENO NESMOTRQ NA EE NEPOSREDSTWENNU@ PRAKTI^ESKU@ ZNA^IMOSTX .
2
,
.
.
-
\
",
-
(
|
|
,
,
(
,
. [2,
. 414]),
.
.2).
-
-
,
.
12
BOLX[OE RAZNOOBRAZIE I DLQ 2 zADA^ RASPOZNAWANIQ SWOJSTW TEORII PREDSTAWLQET INTERES NE TOLXKO WOZMOVNOSTX IH KLASSIFI KACII NO I SPOSOBY OPREDELENIQ KLASSA SLOVNOSTI ODNIH ZADA^ NA OSNOWE IZWESTNOGO KLASSA SLOVNOSTI DRUGIH pO\TOMU WWODITSQ BAZO WOE DLQ TEORII SLOVNOSTI PONQTIE POLINOMIALXNOJ SWODIMOSTI oPREDELENIE 6. bUDEM GOWORITX ^TO MASSOWAQ ZADA^A RASPOZNA WANIQ SWOJSTW p0 S KODIROWKOJ e0 POLINOMIALXNO SWODITSQ K ZADA^E p S KODIROWKOJ e ESLI L@BAQ INDIWIDUALXNAQ ZADA^A I0 2 p0 MO VET BYTX SWEDENA ZA POLINOMIALXNOE OT EE DLINY WREMQ K NEKOTOROJ I 2 p S SOHRANENIEM OTWETA fORMALXNO SU]ESTWUET FUNKCIQ SWODIMOSTI f e0 D p0 ! e D p TAKAQ ^TO f e0 Y p0 e Y p 00T E 80 2 e0 Y p0 f 0 2 e Y p 00 0 0 I 8 2 e D p n Y p f 2 e D p n Y p I SU]ESTWUET dmt Af ; REALIZU@]AQ f ZA POLINOMIALXNOE WREMQ T E 9pf POLINOM 8 2 e0 D p0 TAf jj < pf jj : w SLU^AE KOGDA SOOTWETSTWU@]IE KODIROWKI NE IZBYTO^NY BUDEM ISPOLXZOWATX TERMIN POLINOMIALXNOJ SWODIMOSTI PO OTNO[ENI@ K SAMIM ZADA^AM BEZ UKAZANIQ KODIROWOK I PRIMENQTX OBOZNA^ENIE .
|
,
-
,
.
-
.
,
-
,
-
.
:
(
(
(
))) =
(
(
)
(
(
(
))
)),
(
(
. .
)
(
(
(
(
)
))
(
(
))
(
)),
(
(
)),
)
(
(
))
,
. .
( ) |
:
(
(
))
(
)
(
)
,
,
(
)
p0 / p:
kORREKTNOSTX UPRO]ENIQ WYTEKAET IZ POLINOMIALXNOJ SWODIMOSTI ZADA^I K SAMOJ SEBE NO S DRUGOJ NEIZBYTO^NOJ KODIROWKOJ I SLEDU @]EGO O^EWIDNOGO UTWERVDENIQ TRANZITIWNOSTI OTNO[ENIQ / uTWERVDENIE 3. eSLI p1 / p2 I p2 / p3; TO p1 / p3 sU]ESTWENNYM DLQ TEORII SLOVNOSTI QWLQETSQ uTWERVDENIE 4. eSLI p0 / p I p 2 P; TO I p0 2 P dOKAZATELXSTWO. oBOZNA^IM a dmt RE[A@]U@ p S POLI NOMIALXNOJ WREMENNOJ SLOVNOSTX@ I POSTROIM dmt A0 RE[A@ ]U@ p0 S POLINOMIALXNOJ WREMENNOJ SLOVNOSTX@ KAK SUPERPOZCI@ dmt A I Af A0 A Af ; T E SNA^ALA K L@BOMU WHODNOMU SLOWU 0 2 e0 D p0 0 PRIMENQETSQ Af ; A0 POTOM K POLU^IW[EMUSQ SLO WU f DLINOJ NE BOLEE pf j j PRIMENQETSQ A wREMENNAQ SLOVNOSTX A0 TA0 TAf TA pf POLINOM aNALOGI^NO DOKAZYWAETSQ PRI ZAMENE SLOWA dmt NA ndmt uTWERVDENIE 5. eSLI p0 / p I p 2 NP; TO I p0 2 NP (
,
,
-
|
.)
.
.
,
-
,
,
-
,
:
(
=
(
(
=
. .
))
)
-
(
|
(
( )
( )+
))
(
.
( )) |
.
(
)
.
13
oPREDELENIE 7. mASSOWAQ ZADA^A p NAZYWAETSQ NP-POLNOJ ILI UNIWERSALXNOJ, ESLI p 2 NP I 8p0 2 NP p0 / p (T.E. L@BAQ NEDETERMINIROWANNO POLINOMIALXNAQ ZADA^A POLINOMIALXNO SWODITSQ K p). kLASS WSEH NP-POLNYH ZADA^ (RASPOZNAWANIQ SWOJSTW) OBOZNA^AETSQ NPC (NP-complete). nEPUSTOTU KLASSA NPC DOKAZAL s. a. kUK W 1971 G. iM BYLA RASSMOTRENA ZADA^A O WYPOLNIMOSTI (wyp): WYQSNITX WYPOLNIMOSTX KON_@NKTIWNOJ NORMALXNOJ FORMY (knf) | KON_@NKCII KONE^NOGO ^ISLA DIZ_@NKTIWNYH FUNKCIJ, T.E. DIZ_@NKCIJ BULEWYH PEREMENNYH zi ILI IH OTRICANIJ zi . a IMENNO, W ZADA^E wyp TREBUETSQ RASPOZNATX DLQ knf NA WHODE, SU]ESTWUET LI WYPOLNQ@]IJ NABOR z0 (DLQ KOTOROGO ZNA^ENIE knf RAWNO 1). tEOREMA 2 wyp 2 NPC dOKAZATELXSTWO POLINOMIALXNOJ SWODIMOSTI K wyp L@BOJ NEDETERMINIROWANNO POLINOMIALXNOJ ZADA^I OSNOWANO NA FORMALX NOJ ZAPISI USLOWIQ PRINADLEVNOSTI SLOWA QZYKU IZ KLASSA NP TO GO ^TO PRINIMAETSQ NEKOTOROJ ndmt A ZNA^IT I KAKOJ TO dmt (S. A. Cook).
.
-
(
,
,
,
-
-
)
W WIDE NABORA DIZ_@NKTIWNYH FUNKCIJ OT SPECIALXNO WWODIMYH BU LEWYH PEREMENNYH SWQZANNYH S SOSTOQNIQMI dmt W RAZLI^NYE MO MENTY WREMENI I QWLQETSQ NEDOSTATO^NO PROSTYM DLQ WWODNOGO KUR SA SM pO\TOMU MY LI[X UBEDIMSQ W TOM ^TO wyp 2 NP dEJSTWITELXNO WHODNOE SLOWO PARAMETRY OPREDELQ@]IE INDIWI DUALXNU@ ZADA^U WYPOLNIMOSTI SODERVIT ^ISLO DIZ_@NKTIWNYH FUNKCIJ W knf I UKAZANIE DLQ KAVDOJ IZ NIH KAKIE PEREMENNYE WHODQT S OTRICANIEM A KAKIE NE WHODQT WOOB]E dLINU TAKOGO SLOWA MOVNO OGRANI^ITX SNIZU SUMMOJ DLIN DIZ_@NKTIWNYH FUNKCIJ PO NIMAQ POD DLINOJ FUNKCII ^ISLO EE PEREMENNYH ILI ^ISLO ZNAKOW DIZ_@NKCII eSLI TEPERX W KA^ESTWE PODSKAZKI DLQ OPREDELQ EMOJ WHODNYM SLOWOM knf WZQTX z0 WYPOLNQ@]IJ EE NABOR TO WY^ISLENIE NA NEM ZNA^ENIQ knf PROWERKA WYPOLNIMOSTI POTRE BUET TAKOGO VE PO PORQDKU ^ISLA [AGOW iZ OPREDELENIQ NP POLNOTY NEPOSREDSTWENNO SLEDUET uTWERVDENIE 6. eSLI P \ NPC 6 ; TO P NP a ESLI NPC \ NP n P 6 ; TO NPC NP n P tAKIM OBRAZOM ESLI BY UDALOSX NAJTI POLINOMIALXNYJ ALGO RITM RE[ENIQ HOTX ODNOJ NP POLNOJ ZADA^I TO BYLI BY POSTROENY -
,
-
,
(
-
. [1,2]).
,
,
(
.
,
-
)
,
,
.
,
-
(
+ 1).
-
|
,
(
)
-
.
-
=
(
) =
,
,
=
.
.
,
-
-
,
14
POLINOMIALXNYE ALGORITMY RE[ENIQ WSEH NP POLNYH ZADA^ I WSEH ZADA^ IZ KLASSA NP A ESLI DLQ KAKOJ LIBO NP POLNOJ ZADA^I DO KAZATX OTSUTSTWIE POLINOMIALXNOGO ALGORITMA EE RE[ENIQ TO \TO NE TOLXKO DAET STROGOE WKL@^ENIE P NP T E OTWET K OSNOWNOJ PROBLEME TEORII SLOVNOSTI NO I WLE^ET ZA SOBOJ DOKAZATELXSTWO NE WOZMOVNOSTI POSTROENIQ POLINOMIALXNOGO ALGORITMA RE[ENIQ L@ BOJ ZADA^I IZ KLASSA NPC pOSKOLXKU NI TOGO NI DRUGOGO POKA NE SDELANO S^ITAETSQ ^TO ZADA^I IZ NPC OTWE^A@T VITEJSKOMU PRED STAWLENI@ O TRUDNOJ ZADA^E I WRQD LI DOPUSKA@T \FFEKTIWNOE RE [ENIE pO\TOMU ESLI WSTRE^AETSQ ZADA^A DLQ KOTOROJ NA PRAKTIKE NE UDAETSQ PRIDUMATX NEPEREBORNYJ ALGORITM TO IMEET SMYSL PO PYTATXSQ DOKAZATX EE NP POLNOTU ^TOBY OPRAWDATX PRIMENENIE K NEJ TEH ILI INYH PEREBORNYH SHEM 3 pOSLE TOGO KAK BYLA USTANOWLENA NEPUSTOTA KLASSA NPC TE OREMOJ kUKA POQWILASX WOZMOVNOSTX DOKAZATELXSTWA NP POLNOTY MASSOWOJ ZADA^I p PUTEM POLINOMIALXNOGO SWEDENIQ K p ODNOJ IZ IZWESTNYH NP POLNYH ZADA^ SOOTWETSTWU@]IJ SPISOK SM W dEJSTWITELXNO IZ UTWERVDENIQ SLEDUET tEOREMA 3 KRITERIJ NP-POLNOTY mASSOWAQ ZADA^A p RAS POZNAWANIQ SWOJSTW NP POLNA TOGDA I TOLXKO TOGDA KOGDA ONA PRI NADLEVIT KLASSU NP I K NEJ POLINOMIALXNO SWODITSQ KAKAQ LIBO NP POLNAQ ZADA^A fp 2 NPCg () fp 2 NP I 9p0 2 NPC p0 / pg: pOLXZUQSX TEOREMOJ MOVNO POKAZATX NP POLNOTU ZADA^I O SU ]ESTWOWANII CELO^ISLENNOGO RE[ENIQ SISTEMY LINEJNYH NERAWENSTW S CELYMI KO\FFICIENTAMI cln -
,
-
-
-
,
(
. .
),
-
-
.
,
,
,
-
-
.
,
,
,
-
-
,
.
.
(
),
-
-
-
(
,
.
[1]).
3
(
).
-
-
,
-
-
-
:
:
3,
-
-
uTWERVDENIE 7. cln 2 NPC dOKAZATELXSTWO. cln 2 NP TAK KAK PODSKAZKOJ MOVET (
).
.
1)
,
SLUVITX RE[ENIE SISTEMY A EGO PROWERKA SWODITSQ K UMNOVENI@ NA ZADANNYE KO\FFICIENTY I SLOVENI@ ^TO NE PREWOSHODIT POLINOMA OT DLINY ZAPISI WSEH KO\FFICIENTOW DOKAZATELXSTWO POLINOMIALX NOSTI DLINY ZAPISI RE[ENIQ SM W S wyp / cln oB]IJ WID SISTEMY LINEJNYH NERAWENSTW ,
,
(
.
2)
[2,
-
. 330]).
aj1z1 aj2z2 ::: ajnzn bj ; j .
+
+
+
;:::;m:
= 1
nETRUDNO PREDSTAWITX W PODOBNOJ FORME USLOWIE ISTINNOSTI DIZ_ @NKTIWNOJ FUNKCII dLQ \TOGO ZAMENIM W KAVDOJ j J FUNKCII ZNAKI .
-
-
15
DIZ_@NKCII ZNAKAMI SUMMY A OTRICANIQ PEREMENNYH zi NA zi I NAPI[EM DLQ POLU^IW[EJSQ LINEJNOJ FUNKCII USLOWIE DOBA WIW OGRANI^ENIQ zi I zi NA WSE PEREMENNYE cELO^ISLENNOE RE[ENIE z0 fzi0g SISTEMY WSEH POSTROENNYH NERAWENSTW QWLQET SQ WYPOLNQ@]IM NABOROM DLQ ISHODNOJ knf TAK KAK ISTINNOSTX knf \KWIWALENTNA ISTINNOSTI WSEH OBRAZU@]IH EE DIZ_@NKTIWNYH FUNKCIJ tAKIM SPOSOBOM RE[ENIE L@BOJ INDIWIDUALXNOJ ZADA^I O WYPOLNIMOSTI SWODITSQ K RE[ENI@ NEKOTOROJ INDIWIDUALXNOJ ZA DA^I I 2 cln pOLINOMIALXNOSTX SWEDENIQ O^EWIDNA zAMETIM ^TO FAKTI^ESKI W P DANNOGO DOKAZATELXSTWA DOKAZAN BOLEE SILXNYJ REZULXTAT O SWEDENII wyp K PODZADA^E cln ZA DA^E O SU]ESTWOWANII BULEWA RE[ENIQ SISTEMY LINEJNYH NERAWENSTW S CELYMI KO\FFICIENTAMI bln dOKAZATELXSTWO PRINADLEVNOSTI bln KLASSU NEDETERMINIROWANNO POLINOMIALXNYH ZADA^ POWTORQET P DANNOGO DOKAZATELXSTWA BEZ SSYLKI NA TAK KAK POLINOMIALX NOSTX DLINY BULEWA RE[ENIQ O^EWIDNA TEM SAMYM POLU^ENO I ,
|
(1
1,
0
1
)
-
.
=
-
(
).
-
.
.
,
.2
|
(
-
).
.1
[2] (
uTWERVDENIE 8. bln 2 NPC x3. kLASSY SLOVNOSTI. sILXNAQ NP-POLNOTA I PSEWDOPOLINOMIALXNOSTX
-
),
.
dOKAZATELXSTWO NP-POLNOTY ZADA^I O 3-WYPOLNIMOSTI. wZAIMOOTNO[ENIE KLASSOW r, Nr I Nrs, Nr I SO-Nr. NP-TRUDNYE ZADA^I. kLASS rSrase. pSEWDOPOLINOMIALXNYE ALGORITMY. pRIMER DLQ ZADA^I O R@KZAKE. sILXNAQ NP-POLNOTA. tEOREMA O SWQZI SILXNOJ NP-POLNOTY ZADA^I S SU]ESTWOWANIEM PSEWDOPOLINOMIALXNOGO ALGORITMA EE RE[ENIQ. 1. kROME ZADA^I O WYPOLNIMOSTI, NP-POLNOTA WSEH OSTALXNYH IZWESTNYH ZADA^ IZ KLASSA NPs (W TOM ^ISLE I km) BYLA DOKAZANA NA OSNOWE TEOREMY 3 S POMO]X@ POLINOMIALXNOGO SWEDENIQ. oB]IE RECEPTY DOKAZATELXSTWA POLINOMIALXNOJ SWODIMOSTI (SM. W [1]) LEGKO ISPOLXZOWATX LI[X W PROSTEJ[IH SLU^AQH. ~TOBY NAU^ITXSQ IH PRIMENQTX, NADO RAZOBRATX BOLX[OE ^ISLO PRIMEROW (W ^ASTNOSTI, IME@]IESQ W [1,2]), NA ^TO U NAS W RAMKAH DANNOJ RABOTY NET WOZMOVNOSTI. oDNAKO, E]E ODIN PRIMER BUDET DALEE PRIWEDEN S CELX@ POKAZATX, ^TO NE TOLXKO L@BAQ PODZADA^A SWODITSQ K SOOTWETSTWU@]EJ ZADA^E (AWTOMATI^ESKI), NO WOZMOVNO I OBRATNOE SWEDENIE. 16
rASSMOTRIM ^ASTNYJ SLU^AJ ZADA^I O WYPOLNIMOSTI KOGDA W knf MOGUT WHODITX LI[X DIZ_@NKTIWNYE FUNKCII TREH PEREMEN NYH 3-wyp pOSKOLXKU D(3-wyp)D(wyp) TO PO OPREDELE NI@ 3-wyp/wyp tAK ^TO 3-wyp2NP PO UTWERVDENI@ nO EE NP POLNOTA TREBUET SPECIALXNOGO DOKAZATELXSTWA IBO ^ASTNYE MASSOWYE ZADA^I SODERVAT MENX[E INDIWIDUALXNYH ZADA^ I MOGUT OKAZATXSQ PRO]E NAPRIMER ANALOGI^NAQ ZADA^A 2-wyp POLINOMI ALXNA dLQ POLU^ENIQ REZULXTATA 3-wyp 2 NPs DOKAVEM ^TO NP POLNAQ ZADA^A O WYPOLNIMOSTI SWODITSQ K SWOEJ PODZADA^E ^ASTNOMU SLU^A@ 3-wyp ,
-
(
).
,
.
-
(
5).
-
,
;
,
-
.
,
-
(
uTWERVDENIE 9. wyp / 3-wyp dOKAZATELXSTWO. pOKAVEM ^TO PROIZWOLXNU@ DIZ_@NKTIWNU@ FUNKCI@ f j zj k PEREMENNYH MOVNO PREDSTAWITX W WIDE KON_@NK CII DIZ_@NKTIWNYH FUNKCIJ OT TREH PEREMENNYH ZA S^ET WWEDENIQj DOPOLNITELXNYH PEREMENNYH uj oBOZNA^IM ^EREZ yi PEREMENNU@ zi ILI zji W ZAWISIMOSTI OT TOGO KAK i Q KOMPONENTA zj WHODIT W RAS SMATRIWAEMU@ DIZ_@NKTIWNU@ FUNKCI@ TOGDA POSLEDN@@ MOVNO ZAPISATX KAK y1 _ y2 _ ::: _ yk I PRI k > ZAMENITX NA knf y1 _ y2 _ uj1 y3 _ uj1 _ uj2 y4 _ uj2 _ uj3 ::: ::: yk 2 _ ujk 4 _ ujk 3 yk 1 _ yk _ ujk 3 )
.
.
,
(
)
-
(
).
,
-
-
;
3
(
)&(
)&(
:
)&
&(
)&(
).
oTMETIM ^TO DANNAQ ZAMENA NE QWLQETSQ \KWIWALENTNOJ dEJ STWITELXNO ESLI ISHODNAQ DIZ_@NKTIWNAQ FUNKCIQ RAWNQLASX NU L@ TO POSTROENNAQ knf RAWNA NUL@ PRI WSEH ZNA^ENIQH u NO ESLI ISHODNAQ DIZ_@NKTIWNAQ FUNKCIQ RAWNQLASX TO NAJDETSQ TAKOE ZNA^ENIE u ^TOBY knf RAWNQLASX |TOGO ODNAKO DOSTATO^NO DLQ SOHRANENIQ OTWETA NA WOPROS O SU]ESTWOWANII WYPOLNQ@]EGO NABO RA ,
.
-
,
-
,
,
1,
,
1.
,
,
-
.
upravnenie 4. zAWER[ITX DOKAZATELXSTWO Nr-POLNOTY ZADA^I 3-wyp (RASSMOTRETX SLU^AI k < ). 2. uNIWERSALXNOSTX ZADA^ IZ KLASSA NPs NP POLNYH ZADA^ SO 3
(
-
)
-
STOIT W TOM ^TO OSNOWNYE NERE[ENNYE WOPROSY DLQ KLASSA NP NEDE TERMINIROWANNO POLINOMIALXNYH ZADA^ DOSTATO^NO RAZRE[ITX HO TQ BY DLQ ODNOJ NP POLNOJ ZADA^I ^TOBY POLU^ITX OTWET DLQ WSEGO KLASSA NP kROME UTWERVDENIQ ZDESX TAKVE WAVNO uTWERVDENIE 10. eSLI DLQ NEKOTOROJ NP POLNOJ ZADA^I p DO POLNITELXNAQ K NEJ p PRINADLEVIT KLASSU NP TO NP co-NP ,
(
-
)
-
.
-
,
6
-
-
,
17
=
.
dOKAZATELXSTWO . tAK KAK p 2 NPC TO 8p0 2 NP p0 / p 0 OTS@DA I p / p POLINOMIALXNOE SWEDENIE OSU]ESTWLQETSQ0 TOJ VE FUNKCIEJ SM OPREDELENIE nO p 2 NP ZNA^IT p 2 NP PO UTWERVDENI@ s U^ETOM PROIZWOLXNOSTI p0 2 NP POLU^ILI ,
,
(
|
.
6).
,
,
^TO co-NP NP oBRATNOE WKL@^ENIE DOKAZYWAETSQ NA OSNOWANII O^EWIDNOGO RAWENSTWA p p nAPOMNIM ^TO GIPOTEZA NP co-NP W NASTOQ]EE WREMQ KA VETSQ NEREALXNOJ REALXNAQ GIPOTEZA P NP\co-NP I WRQD LI DLQ KAKOJ LIBO NP POLNOJ ZADA^I UDASTSQ DOKAZATX PRINADLEVNOSTX KLASSU co-NP pO\TOMU DLQ KONKRETNOJ NEDERMINIROWANNO POLINO MIALXNOJ MASSOWOJ ZADA^I p2NP ESLI EE RE[ENIE PREDSTAWLQET INTERES IMEET SMYSL POPYTATXSQ DOKAZATX WKL@^ENIE p 2 NP T E EE HORO[U@ HARAKTERIZACI@ I ZATEM POSTROITX POLINOMIALXNYJ ALGORITM RE[ENIQ LIBO KOGDA UKAZANNOE WKL@^ENIE NE DOKAZYWAET SQ NADO POPROBOWATX POLINOMIALXNO SWESTI K p ODNU IZ IZWESTNYH NP POLNYH ZADA^ T E POKAZATX NP POLNOTU p I W SLU^AE USPEHA PODYSKIWATX PEREBORNU@ SHEMU RE[ENIQ U^ITYWAQ OGRANI^ENIQ NA RAZMERNOSTX PRAKTI^ESKI RE[AEMYH INDIWIDUALXNYH ZADA^ dOKAZATELXSTWO UNIWERSALXNOSTI p T E WKL@^ENIQ p2NPC UDAETSQ NE WSEGDA I W TEORII SLOVNOSTI BYL WWEDEN OB_EML@]IJ NPC KLASS NP TRUDNYH ZADA^ SODERVA]IJ p RASPOZNAWANIQ SWOJSTW DLQ KOTORYH DOKAZANO ^TO p0 / p 0 DLQ p 2 NPC NO NE POKAZANO ^TO p 2 NP W ^ASTNOSTI \TO ZADA^I 5.
,
.
=
.
,
=
-
(
-
=
),
-
.
-
,
,
(
. .
)
,
,
-
,
-
(
. .
-
)
(
).
,
. .
,
,
-
,
1)
,
,
p2co-NPC p OPTIMIZACII DLQ KOTORYH SOOTWETSTWU@]IE p RASPOZNA ,
,
(
,
);
2)
WANIQ SWOJSTW
x
,
POLNY NAPRIMER ZADA^A KOMMIWOQVERA IZ P
NP-
(
,
-
.1
1);
I OSTALXNYE MASSOWYE ZADA^I NE OBQZATELXNO RASPOZNAWANIQ SWOJSTW K KOTORYM SWODQTSQ PO tX@RINGU KAKIE LIBO NP POLNYE ZADA^I p0 2 NPC GDE SWODIMOSTX PO tX@RINGU p0 /T p OZNA ^AET ^TO IZ SU]ESTWOWANIQ POLINOMIALXNOGO ALGORITMA RE[ENIQ p SLEDUET SU]ESTWOWANIE POLINOMIALXNOGO ALGORITMA I DLQ p0 zADA^I p NE OBQZATELXNO RASPOZNAWANIQ SWOJSTW DLQ KOTORYH 9p0 2 NPC p0 /T p I 9p00 2 NP p /T p00 NAZYWA@TSQ ZADA^A MI IZ KLASSA NP \KWIWALENTNYH 3)
(
),
-
,
-
|
|
-
,
.
(
),
:
:
-
.
18
,
-
wSE RASSMOTRENNYE NAMI KLASSY ZADA^ p KLASSY SLOVNOSTI WKL@^A@TSQ W OB]IJ KLASS PSPACE MASSOWYH ZADA^ NE OBQZA TELXNO RASPOZNAWANIQ SWOJSTW DLQ RE[ENIQ KOTORYH SU]ESTWU@T ALGORITMY TREBU@]IE NE BOLEE ^EM POLINOMIALXNOJ PAMQTI wO PROS O RAWENSTWE P I PSPACE QWLQETSQ OTKRYTYM rABO^AQ GI POTEZA SOSTOIT W NALI^II STROGOGO WKL@^ENIQ PPSPACE PRI \TOM NP POLNYE NP TRUDNYE I NP \KWIWALENTNYE ZADA^I DOLVNY WKL@^ATXSQ W PSPACE n P sOOTWETSTWU@]U@ DIAGRAMMU WZAIMO SWQZI KLASSOW SLOVNOSTI SM W S zAMETIM ^TO TEORETI^ESKI RASSMOTRENNU@ SHEMU POSTROENIQ KLASSOW SLOVNOSTI MOVNO PRIMENQTX I DLQ DRUGIH SHEM KLASSIFIKA CII W ^ASTNOSTI WWODQT TAKVE KLASS PSPACE POLNYH ZADA^ K KO TORYM POLINOMIALXNO SWODITSQ L@BAQ ZADA^A IZ KLASSA PSPACE kROME POLINOMIALXNOJ SWODIMOSTI MOVNO ANALOGI^NO GOWORITX O LOGARIFMI^ESKOJ SWODIMOSTI O ZADA^AH TREBU@]IH LOGARIFMI^E SKOJ PAMQTI I T P w NASTOQ]EE WREMQ NAIBOLEE INTENSIWNO IZU^A EMYM ZDESX OKAZYWAETSQ KLASS NC AWTOR ZADA^ RE[AEMYH ZA WREMQ OGRANI^ENNOE POLINOMOM OT LOGARIFMA DLINY WHODA I TREBU@]IH POLINOMIALXNOJ PAMQTI LOGARIFMI^E SKOE WREMQ PRI WOZMOVNOSTI POLINOMIALXNOGO ^ISLA PROCESSOROW k SOVALENI@ IZLOVENIE POLU^ENNYH DLQ NC REZULXTATOW WYHODIT ZA RAMKI WWEDENIQ W TEORI@ SLOVNOSTI 3 rANEE UVE OTME^ALOSX ^TO S PRAKTI^ESKOJ TO^KI ZRENIQ RAZ NICA MEVDU POLINOMIALXNYM ALGORITMOM DLQ POLINOMOW WYSOKIH STEPENEJ I \KSPONENCIALXNYM WESXMA USLOWNA A WSE DELO W WOZMOV NOSTI ILI NEWOZMOVNOSTI IZBEVATX POLNOGO PEREBORA wOPROS WSE LI NP 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@ ZA DA^U ZADA^U O R@KZAKE zr ZAKL@^A@]U@SQ W TOM ^TOBY IZ IME@]EGOSQ NABORA POLEZNYH WE]EJ SOBRATX R@KZAK OGRANI^ENNOGO OB_EMA S NAIBOLX[EJ POLXZOJ fORMALXNO TREBUETSQ NAJTI |
(
-
),
,
.
.
-
-
,
-
,
-
-
. (
-
.
[2,
. 412].)
,
-
;
,
-
(
-
).
,
,
-
. .
-
(Nick Class,
,
N. Pippenger)
,
,
(
-
).
,
.
.
,
-
(
)
,
-
.
-
,
-
,
.
(
|
(
)
),
n
n
j=1
j=1
X X f j c z wj zj K g; j j z: zj 2f0;1g 8j=1;:::;n
19
-
,
.
max
-
GDE cj 2 Z+ POLEZNOSTX CENNOSTX wj 2 Z+ OB_EM WES j J WE]I A PEREMENNAQ zj OPREDELQET KLASTX ILI NE KLASTX EE W R@KZAK MAKSIMALXNO WOZMOVNYJ OB_EM WES R@KZAKA ZADAETSQ PARAMETROM K 2 Z+ sOOTWETSTWU@]AQ ZADA^A RASPOZNAWANIQ SWOJSTW SU]E STWUET LI BULEWO RE[ENIE SISTEMY DWUH LINEJNYH NERAWENSTW |
(
),
|
(
)
-
,
;
(
)
.
|
n X j=1
n X
cj zj B I
j=1
-
wj zj K
S NATURALXNYMI KO\FFICIENTAMI NP POLNA DOKAZATELXSTWO NE SLEDUET IZ UTWERVDENIQ TAK KAK RASSMATRIWAETSQ ^ASTNYJ SLU^AJ bln PO\TOMU SM S ILI S dLQ RE[ENIQ zr IZWESTEN SLEDU@]IJ METOD DINAMI^ESKOGO PROGRAMMIROWANIQ pROIZWOLXNAQ INDIWIDUALXNAQ ZADA^A I2zr POGRUVAETSQ W SE MEJSTWO ZADA^ POISKA |
-
(
8,
,
. [1,
. 87
2,
. 386]).
(
).
-
n n X X Fi E : z: zj 2f0;1g 8j=i;:::;nf cj zj j wj zj K E g; j=i j =i F1 ZNA^ENIE zr i RE[A@TSQ WSE ZADA^I DANNOGO SEMEJSTWA PO REKURRENTNYM FORMULAM GDE i UBYWAET S n DO a IMENNO POLOVIM Fi E : 8E K; 8i iMEEM 8E ;K ; E > K wn; Fn E cn INA^E I 8i n ;:::; Fi E fFi+1 E ; ci Fi+1 E wi g : : fF2 ; c1 F2 w1 g: zi 2f0;1gfci zi Fi+1 E wi zi g F1 (
)
=
max
(0) |
.
,
(
) = 0
= 0
(
=
=
max
1.
.
1
2:
+
) =
(
(
0
,
) = max
+
,
1 :
) ;
(
)
+
(0) = max
(
+
(0)
+
)
=
(
)
~ISLO ITERACIJ PREDLOVENNOGO ALGORITMA RAWNO nK I TOGO VE PORQDKA BUDET EGO WREMENNAQ SLOVNOSTX oTMETIM ^TO ALGORITM NE QWLQETSQ POLINOMIALXNYM IBO DLQ ZAPISI ^ISLA K TREBUETSQ PORQD KA 2 K SIMWOLOW ON TAKVE OKAZYWAETSQ PEREBORNYM PEREBIRAET WSE WARIANTY ZAPOLNENNOSTI R@KZAKA oDNAKO PRI NE O^ENX BOLX[IH OB_EMAH R@KZAKA MOVNO DOWOLXNO BYSTRO POLU^ITX RE[ENIE dLQ OBOB]ENIQ UKAZANNOGO SWOJSTWA DADIM
.
,
,
log
-
;
|
.
.
20
oPREDELENIE 8. oBOZNA^IM ^EREZ I MAKSIMALXNOE PO MO DUL@ CELOE ^ISLO ILI FIGURIRU@]EE PRI ZADANII ^ISLOWYH PA RAMETROW DLQ INDIWIDUALXNOJ ZADA^I I I ^EREZ jIj : je I j DLINU ZAPISI I aLGORITM a RE[ENIQ MASSOWOJ ZADA^I p NE OBQZATELX NO RASPOZNAWANIQ SWOJSTW NAZYWAETSQ PSEWDOPOLINOMIALXNYM ESLI DLQ NEKOTOROGO POLINOMA p ; WYPOLNENO tA e I < p jIj I num( )
(
-
0),
-
,
=
.
( )
|
(
-
)
8I 2 p
,
(
)
( ( ))
(
,num( ))
.
pRIMEROM PSEWDOPOLINOMIALXNOGO ALGORITMA QWLQETSQ ALGORITM DINAMI^ESKOGO PROGRAMMIROWANIQ DLQ RE[ENIQ zr dLQ MNOGIH DRU GIH ZADA^ W ^ASTNOSTI km PSEWDOPOLINOMIALXNYH ALGORITMOW NE IZWESTNO ~TOBY WYDELITX KLASS TAKIH ZADA^ WWEDEM PONQTIE POLINOMIALXNOGO SUVENIQ MASSOWOJ ZADA^I p KAK MNOVESTWA TEH IN DIWIDUALXNYH ZADA^ ^ISLOWYE PARAMETRY KOTORYH NE PREWOSHODQT POLINOMA OT DLINY WHODA : .
(
,
-
)
.
,
-
,
pp() fI 2 pj
I < p jIj g: oPREDELENIE 9. mASSOWAQ ZADA^A p RASPOZNAWANIQ SWOJSTW NA ZYWAETSQ SILXNO NP POLNOJ ESLI EE POLINOMIALXNOE SUVENIE NP POLNO 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@ W KOTOROM MODULI PRAWYH ^ASTEJ NE PREWY[A@T n cln KAK OBOB ]ENIE bln W OTLI^IE OT zr A TAKVE km S tEOREMA 4. eSLI P 6 NP TO NI DLQ KAKOJ SILXNO NP POLNOJ ZADA^I NE SU]ESTWUET PSEWDOPOLINOMIALXNOGO ALGORITMA RE[ENIQ dOKAZATELXSTWO PROWEDEM OT PROTIWNOGO pUSTX dmt a RE[A ET SILXNO NP POLNU@ ZADA^U p I 8I 2 p tA e I < p0 jIj 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 UTWERVDE ,
=
-
,
. .
num( )
(
)
-
,
( ) |
-
:
.
-
(
),
(
,
),
),
=
[1,
(
-
. 123-124].
,
-
.
.
-
(
(
),
-
( ( ))
).
. .
(
( ( ))
(
|
,num( )) (
)) =
-
NIEM sILXNO NP POLNYE ZADA^I S^ITA@TSQ NAIBOLEE TRUDNYMI DLQ S^ETA SREDI WSEH ZADA^ KLASSA NP dALEE MY POKAVEM ^TO DLQ PO DOBNYH ZADA^ W OPTIMIZACIONNOJ POSTANOWKE OTSUTSTWU@T \FFEKTIW NYE ALGORITMY POISKA DAVE PRIBLIVENNOGO RE[ENIQ rEKOMENDUE MYM PODHODOM K IH RE[ENI@ QWLQETSQ RAZBIENIE NA PODZADA^I p0 D p0 D p ; Y p0 Y p \ D p0 ANALIZ SLOVNOSTI PODZADA^ 6.
-
.
,
-
.
-
:
(
)
(
)
(
) =
(
)
(
21
),
I RAZRABOTKA SHEM PEREBORA SM W xx DLQ p0 2 NPC pRI \TOM DLQ SILXNO NP POLNYH PODZADA^ NE UDAETSQ ISPOLXZOWATX METOD DI NAMI^ESKOGO PROGRAMMIROWANIQ W KA^ESTWE SPOSOBA PEREBORA IBO PO WIDIMOMU REALIZU@]IE EGO ALGORITMY PSEWDOPOLINOMIALXNY I SLEDUET ORIENTIROWATXSQ NA SHEMU METODA WETWEJ I GRANIC xx (
.
10,12)
.
-
-
(
-
,
,
)
(
10,11).
x4. pRIBLIVENNOE RE[ENIE ZADA^ KOMBINATORNOJ OPTIMIZACII
oPREDELENIE 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 I PSEWDOPOLINOMIALXNOSTX@. tEOREMA OB OTSUTSTWII ppps DLQ ZADA^ OPTIMIZACII, SOOTWETSTWU@]IH SILXNO NP-POLNYM ZADA^AM RASPOZNAWANIQ SWOJSTW. pRIMER ZADA^I O KOMMIWOQVERE. wAVNYJ KLASS MASSOWYH ZADA^ OBRAZU@T ZADA^I DISKRETNOJ (KOMBINATORNOJ) OPTIMIZACII. dLQ OPTIMIZACIONNOJ POSTANOWKI ZADA^I p RE[ENIEM KAVDOJ INDIWIDUALXNOJ ZADA^I I2p QWLQETSQ PROIZWOLXNAQ REALIZACIQ OPTIMUMA
Optp I : z2Sp(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^I SLENNOJ PEREMENNOJ z fp I; Sp I ! Z CELEWAQ FUNKCIQ ( ) =
. .
( )
max
(
)
( ),
(
( )) =
( ) |
( ).
(
)
,
(
) :
( )
|
,
max
-
INDIWIDUALXNOJ ZADA^I I OPTIMIZACII ZNAK W POSTANOWKE ZA DA^I MOVET BYTX ZAMENEN NA bUDEM OBOZNA^ATX S I f TE KOMPONENTY WHODNOGO SLOWA e I OPREDELQ@]EGO PARAMETRY INDIWIDUALXNOJ ZADA^I I 2 p KOTORYE ZADA@T DOPUSTIMU@ OBLASTX OGRANI^ENIQ ZADA^I I FUNKCI@ CE hc;zi LI SOOTWETSTWENNO nAPRIMER DLQ zr IMEEM fzr ;z Szr fz z1;:::;zn jzj 2 f ; g 8j ;n I hw;zi K g S n;w;K I f c: zDESX I DALEE ZNAK h; i OBOZNA^AET SKALQR NOE PROIZWEDENIE WEKTOROW -
min.
=
( ),
,
(
.
(
) =
= (
= (
)
)
,
)
-
(
0 1
=
= 1
)
=
,
,
-
.
22
oPREDELENIE 10. aLGORITM a NAZYWAETSQ PRIBLIVENNYM ALGORITMOM RE[ENIQ MASSOWOJ ZADA^I p OPTIMIZACII, ESLI 8I 2 p ON 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 WSEWOZMOVNYH INDIWIDUALXNYH ZADA^) NE IMEET BOLX[OGO SMYSLA, KAK POKAZYWAET uTWERVDENIE 11. eSLI P 6= NP, TO NI DLQ KAKOJ KONSTANTY C > 0 NE SU]ESTWUET POLINOMIALXNOGO PRIBLIVENNOGO ALGORITMA a RE[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 zr DOMNOVIM WSE KO\FFICIENTY cj NA C + 1 | POLU^IM INDIWIDUALXNU@ ZADA^U I0 2 zr, K KOTOROJ PRIMENIM ALGORITM a I RAZDELIM POLU^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 RAWNA
jOptzr 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 pO LU^ILI POLINOMIALXNYJ ALGORITM TO^NOGO RE[ENIQ zr pROWERKA Optzr I B POLINOMIALXNA ZNA^IT POSTROILI I POLINOMIALX NYJ ALGORITM RE[ENIQ zr W POSTANOWKE RASPOZNAWANIQ SWOJSTW ^TO S U^ETOM UNIWERSALXNOSTI POSLEDNEJ PROTIWORE^IT UTWERVDENI@ oPREDELENIE 11. pRIBLIVENNYJ ALGORITM a RE[ENIQ MASSOWOJ ZADA^I p OPTIMIZACII NAZYWAETSQ " PRIBLIVENNYM ALGORITMOM RE [ENIQ p DLQ NEKOTOROGO " > ESLI . .
(
).
-
.
( )
,
,
-
,
6.
-
-
0,
jOptp I A I j < "; jOptp I j
8I 2 p
( )
( )
( )
T E EGO OTNOSITELXNAQ POGRE[NOSTX NE PREWOSHODIT " dLQ " PRIBLIVENNYH ALGORITMOW PRIWEDEM SLEDU@]IJ REZULXTAT S DOKAZATELXSTWO KOTOROGO OSNOWANO NA METODE DINAMI^ESKO GO PROGRAMMIROWANIQ I W DANNOM KURSE OPUSKAETSQ tEOREMA 5. pUSTX DLQ ZADA^I p OPTIMIZACII SU]ESTWUET PSEWDOPOLINOMIALXNYJ ALGORITM EE RE[ENIQ 8I 2 p jOptp I j < p1 jIj; I I I < p2 jIj;Optp I . .
.
-
[2,
. 439],
-
.
1) 2)
;
( )
(
num( ))
23
num( )
(
( ))
DLQ NEKOTORYH POLINOMOW p1 ; ; p2 ; 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 FUNKCIQ CELI fp ;z LINEJNO ZAWISIT OT PARAMETROW f TOGDA 9p ; POLINOM 8" > 9 " PRIBLIVENNYJ ALGORITM A" RE[ENIQ p S WREMENNOJ SLOVNOSTX@ TA" jIj < p jIj; =" : tEOREMA SPRAWEDLIWA NAPRIMER DLQ zr SRAWNITE REZULXTAT S UTWERVDENIEM nABOR ALGORITMOW fA" g OPREDELENNYJ W TEORE ME 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 IMEETSQ tEOREMA 6. eSLI DLQ p OPTIMIZACII SOOTWETSTWU@]AQ EJ p RASPOZNAWANIQ SWOJSTW QWLQETSQ SILXNO NP POLNOJ I 9p0 PO LINOM jOptp I j < p0 I 8I 2 p TO PRI USLOWII ^TO P 6 NP DLQ p NE SU]ESTWUET ppps dOKAZATELXSTWO PROWEDEM OT PROTIWNOGO pUSTX ppps SU]E STWUET pOSTROIM ALGORITM A0 SLEDU@]IM OBRAZOM dLQ L@BOJ IN DIWIDUALXNOJ ZADA^I I A0 WYZYWAET A" S " = p0 I tOGDA PO OPREDELENI@ " PRIBLIVENNOGO ALGORITMA A" jOptp I A0 I j < jOptp I j= p0 < p0 PO I I = p0 I USLOWI@ TEOREMY nO W LEWOJ ^ASTI POLU^ENNOGO NERAWENSTWA BY LO CELOE ^ISLO KOTOROE OKAZYWAETSQ RAWNYM NUL@ KAK NEOTRICA TELXNOE MENX[EE tAKIM OBRAZOM ALGORITM A0 TO^EN PRI^EM TA0 jIj TA" jIj < p jIj;p0 0 PO OPREDELENI@ ppps I sLEDOWATELXNO ALGORITM A PSEWDOPOLINOMIALEN ^TO PROTIWORE^IT TEOREME uTWERVDENIE 12. eSLI P 6 NP TO NI DLQ KAKOGO " > NE SU]ESTWUET POLINOMIALXNOGO " PRIBLIVENNOGO ALGORITMA RE[ENIQ OPTIMIZACIONNOJ POSTANOWKI ZADA^I KOMMIWOQVERA dOKAZATELXSTWO SM W S dLQ ^ASTNOGO SLU^AQ km W KOTOROM FUNKCIQ d ; RASSTOQ NIQ MEVDU GORODAMI UDOWLETWORQET NERAWENSTWU TREUGOLXNIKA IZ WESTEN PRIBLIVENNYJ POLINOMIALXNYJ ALGORITM kRISTOFIDESA S RE[ENIQ km OPTIMIZACII (
3)
=
( )
)
(
:
);
,
,
,
(
,
(
)
,
)
;
(
) |
:
0
-
5
(
,
,
)
(
1
)
(
11).
,
-
5,
(
)
.
|
-
,
.
,
,
-
:
( )
(num( ))
( ) |
,
,
=
-
,
.
.
-
.
.
-
= 1 (
(num( ))+1).
-
( )
( )
(
( )
(num( )) + 1)
(num( )) (
(num( )) + 1)
.
-
,
-
,
(
1.
) =
(
)
,
(
,
(num( )) + 1)
,
.
,
4.
=
,
0
-
.
.
[2,
. 440{441].
,
(
)
-
,
0.5-
[2,
. 429{432] (
).
24
-
2.
osnowy linejnogo programmirowaniq
lITERATURA: hA^IQN l. g. sLOVNOSTX ZADA^ LINEJNOGO PROGRAMMIROWANIQ. m.: zNANIE, 1987, N 10. 3.
x5. pONQTIE O SLOVNOSTI ZADA^I LINEJNOGO PROGRAMMIROWANIQ (lp)
oPREDELENIE OSNOWNOJ ZADA^I lp (OZlp). pRINCIP GRANI^NYH RE[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 S CELYMI KO\FFICIENTAMI. tEOREMA O MERE NESOWMESTNOSTI SISTEM LINEJNYH 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 ^ISLOM WE]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 SO DERVIT NULEWYH STROK ai oSNOWNAQ ZADA^A lp OZlp SOSTOIT W NAHOVDENII TAKOGO RE[ENIQ KOTOROE MAKSIMIZIRUET ZADANNU@ LINEJNU@ FUNKCI@ hc;xi : c1 x1 c2 x2 ::: cn xn WEKTORA NEIZWEST NYH x PO WSEM WE]ESTWENNYM x UDOWLETWORQ@]IM SISTEME x2Rn : Axbhc;xi OZlp S n NEIZWESTNYMI I m OGRANI^ENIQMI NAZYWAETSQ ZADA^EJ RAZMERNOSTI n;m I ZADAETSQ ^ISLOWOJ TABLICEJ a11 a12 ::: a1n b1 a21 a22 ::: a2n b2 ::: ::: ::: ::: ::: am1 am2 ::: amn bm c1 c2 ::: cn +
+
+
.
,
-
(
.
)
(1),
=
+
+
+
,
-
(1):
max
;
(2)
(2)
(
)
(3)
0
25
SWOIH KO\FFICIENTOW w ^ASTNOM SLU^AE c ZADA^A \KWIWALENT NA TAK ^TO UMENIE RE[ATX OZlp PREDPOLAGAET UMENIE RE[ATX SISTEMY LINEJNYH NERAWENSTW ln w x BUDET POKAZANO OBRATNOE SWEDENIE 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; x0 max
hc;xi:
zDESX I DALEE ^ERTA SWERHU BUDET ISPOLXZOWATXSQ DLQ WYDELENIQ WEKTORA W OTLI^IE OT POHOVEGO ^ISLA
(
upravnenie lp W FORME OZlp.
.)
pREDSTAWITX KANONI^ESKU@ ZADA^U
5.
nESMOTRQ NA TO ^TO FORMALXNO ZADA^I lp NE QWLQ@TSQ DISKRET NYMI x 2 Rn IH RE[ENIE NETRUDNO SWESTI K PEREBORU KONE^NOGO ^ISLA UGLOWYH TO^EK WER[IN POLI\DRA ZADA@]EGO OGRANI^ENIQ NA OSNOWANII PRINCIPA GRANI^NYH RE[ENIJ ESLI ZADA^A IMEET RE[ENIE TO NAJDETSQ TAKAQ PODMATRICA AI MATRICY 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 W oTMETIM ^TO DLQ NEWYROVDENNYH AI RE[ENIE SOOTWETSTWU@]EJ SISTEMY URAWNENIJ AI x bI UDOWLETWORQ@]EE OGRANI^ENIQM QWLQETSQ UGLOWOJ TO^KOJ iZ PRINCIPA GRANI^NYH RE[ENIJ SLEDU ET ^TO ESLI UGLOWAQ TO^KA SU]ESTWUET TO RAZRE[IMAQ ZADA^A IMEET RE[ENIE I W UGLOWOJ TO^KE T E ONA \KWIWALENTNA MAKSIMI ZACII hc;xi NA KONE^NOM MNOVESTWE WER[IN POLI\DRA pROCEDURA RE[ENIQ SISTEMY LINEJNYH URAWNENIJ METODOM gAUSSA TREBUET NE BOLEE POLINOMA J STEPENI OT m;n TO^NEE m;n m;n 2 ARIFMETI^ESKIH OPERACIJ S \LEMENTAMI A I b oDNAKO ^ISLO WOZ MOVNYH PODMATRIC MATRICY A \KSPONENCIALXNO I METOD POLNOGO IH PEREBORA NE \FFEKTIWEN w H GG v fURXE I ZATEM W G dV dANCIG PREDLOVI LI METOD NAPRAWLENNOGO PEREBORA SMEVNYH WER[IN W NAPRA WLENII WOZRASTANIQ CELEWOJ FUNKCII SIMPLEKS-METOD hOTQ KAVDYJ [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 PO PORQDKU ^ISLOM mn ARIFMETI^ESKIH OPERACIJ W NASTOQ]EE WREMQ DLQ WSEH IZWESTNYH WARIANTOW SIMPLEKS METODA PRIWEDENY PRIME RY \KSPONENCIALXNYE PO ^ISLU ITERACIJ KOGDA PEREBIRAETSQ BOLEE min(n;m=2) WER[IN NO DOKAZATELXSTWO NEWOZMOVNOSTI POSTROITX PO LINOMIALXNYJ SIMPLEKS METOD TAKVE OTSUTSTWUET pOD^ERKNEM ^TO NA PRAKTIKE SIMPLEKS METOD NE POKAZYWAET DANNOJ OCENKI PLOHIE PRIMERY DOWOLXNO REDKI mOVNO POSTROITX ALGORITM RE[ENIQ ZA DA^I lp S OCENKOJ f n m ARIFMETI^ESKIH OPERACIJ NAD ^ISLAMI ZAPISANNYMI W GDE f RASTET BYSTREE \KSPONENTY aLGORITM S POLINOMIALXNOJ OCENKOJ ODNOWREMENNO PO n I m NE IZWESTEN I WRQD LI BUDET POSTROEN tEPERX ZAMETIM ^TO FUNKCIQ OCENIWA@]AQ ^ISLO ARIFMETI^E SKIH OPERACIJ W ZAWISIMOSTI OT n I m NE U^ITYWAET DLINU KODA \LEMENTOW A TOLXKO IH KOLI^ESTWO I PO\TOMU NE QWLQETSQ WRE MENNOJ SLOVNOSTX@ ALGORITMA uKAZANNAQ FUNKCIQ NOSIT NAZWANIE ALGEBRAI^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 ZAWISI MOSTI OT DLINY WHODNOGO SLOWA T E OT n m I DLIN l KODOW ^ISEL W SIMPLEKS TABLICE o^EWIDNO BITOWAQ SLOVNOSTX ALGORITMA SOOT WETSTWUET EGO WREMENNOJ SLOVNOSTI SM x wHODNYE KO\FFICIENTY ZADA^I lp OBY^NO RACIONALXNY PO\TOMU DALEE USLOWIMSQ S^ITATX IH CELYMI TOGDA l DLINA ZAPISI MAKSIMALXNOGO KO\FFICIENTA W KONE^NA nABOR n m l NAZYWAETSQ BITOWOJ RAZMERNOSTX@ ZADA^I lp wOPROS O SU]ESTWOWANII ALGORITMA lp S POLINOMIALX NOJ BITOWOJ SLOVNOSTX@ BYL RE[EN l g hA^IQNOM W G I TEM SAMYM BYLA DOKAZANA POLINOMIALXNOSTX ZADA^ lp oSNOWNYE MO MENTY \TOGO DOKAZATELXSTWA IZLAGA@TSQ W SLEDU@]EM PUNKTE I x zDESX VE UKAVEM NA OTLI^IE KLASSOW SLOVNOSTI ZADA^I lp I DRUGIH LINEJNYH ZADA^ mETOD gAUSSA RE[ENIQ SISTEMY LINEJNYH ALGEBRAI^ESKIH URAW NENIJ IMEET POLINOMIALXNU@ ALGEBRAI^ESKU@ SLOVNOSTX T E QWLQ ETSQ SILXNOPOLINOMIALXNYM dLQ lp WOPROS O SU]ESTWOWANII SILX NOPOLINOMIALXNOGO 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 KOTO ROE NET OSNOWANIJ iZ POLINOMIALXNOSTI lp WYTEKAET POLINOMIALXNOSTX ZADA^I ln SU]ESTWUET LI RE[ENIE SISTEMY ln ln 2 P aNALOGI^ NYE ZADA^I S DOPOLNITELXNYM OGRANI^ENIEM CELO^ISLENNOSTI ILI BULEWOSTI RE[ENIQ NP POLNY cln; bln 2 NPC SM x T E POLINOMIALXNYE ALGORITMY DLQ NIH WRQD LI BUDUT POSTROENY sU]ESTWUET NEPOLINOMIALXNOE OBOB]ENIE lp ZADA^A PROWERKI ISTINNOSTI WYSKAZYWANIJ WIDA ,
=
-
,
-
.
(
):
-
.
:
(
-
.
2),
. .
.
|
x ::: Qnxn F ha1;xi b1;:::; ham;xi bm ; GDE Qi 2 f8; 9g A F ;:::; PREDLOVENIE SOSTAWLENNOE IZ LI NEJNYH NERAWENSTW S POMO]X@ SWQZOK ; _; : I ILI OTRICANIE Q1 1
(
,
(
)
) |
,
&
( ,
,
-
).
dOKAZANO ^TO L@BOJ ALGORITM RE[A@]IJ \TU MASSOWU@ ZADA^U IMEET NE MENEE ^EM \KSPONENCIALXNU@ SLOVNOSTX tOT VE REZULX TAT BUDET I PRI ZAMENE RAWENSTWAMI WSEH NERAWENSTW W POSTANOWKE ZADA^I 2. rASSMOTRIM NEKOTORYE SWOJSTWA ZADA^ lp S CELYMI KO\FFI CIENTAMI dLQ L@BOJ CELO^ISLENNOJ MATRICY D WWEDEM PARAMETR ,
,
.
,
-
.
-
.
D : fD0
(
) =
max
KWADRATNAQ PODMATRICA
Dg jdetD j: 0
bUDEM OBOZNA^ATX ^EREZ Ajb MATRICU SOSTAWLENNU@ IZ A I WEKTORA STOLBCA b 2 Zm DOPISANNOGO SPRAWA zDESX I DALEE Zm m MERNOE PROSTRANSTWO CELO^ISLENNYH WEKTOROW Zm+ EGO NEOTRICATELXNYJ ORTANT tEOREMA 1 (O GRANICAH RE[ENIJ) eSLI OZlp RAZMERNOSTI RAZRE[IMA TO U NEE SU]ESTWUET n;m S CELYMI KO\FFICIENTAMI RACIONALXNOE: RE[ENIE x W [ARE kxk n1=2 Ajb I ZNA^ENIEM OZlp d hc;x i QWLQETSQ RACIONALXNOE ^ISLO t=s SO ZNAMENATE LEM OGRANI^ENNYM WELI^INOJ A dOKAZATELXSTWO. nA OSNOWANII PRINCIPA GRANI^NYH RE[ENIJ 9AI A PO PRAWILU kRAMERA jxjj j j AjI = AI j Ajb IBO j AI j A OPREDELITELX MATRICY AI POLU^ENNOJ IZ AI ZAMENOJ [
]
,
,
-
.
|
,
-
|
.
.
(
(2)
)
,
([
(2)
,
-
(
:
det
])
=
).
=
1,
det ,
28
det
([
]),
j GO STOLBCA NA bI NE PREWY[AET PO MODUL@ Ajb oTS@DA DLQ EWKLIDOWOJ NORMY x POLU^AEM TREBUEMU@ OCENKU s U^ETOM CELO ^ISLENNOSTI WEKTORA c ZNAMENATELX d MOVET BYTX WYBRAN RAWNYM ZNAMENATEL@ xj 8j I E UTWERVDENIE TEOREMY SLEDUET IZ OPREDELE NIQ A j AI j oPREDELENIE 1. tO^KA x" NAZYWAETSQ " PRIBLIVENNYM RE[ENI EM SISTEMY LINEJNYH NERAWENSTW ESLI hai;x"i bi " 8i ;m; GDE ai i Q STROKA MATRICY A -
,
([
]).
.
,
(
)
det
-
2-
-
.
-
-
(1),
+
= 1
ILI W MATRI^NOJ ZAPISI OBOZNA^AQ e ,
|
-
|
,
WEKTOR STOLBEC IZ EDINIC -
Ax" b "e:
,
"
+
(1 )
tEOREMA 2 (O MERE NESOWMESTNOSTI) eSLI SISTEMA ln IME A TO \TA SISTEMA ET "1 PRIBLIVENNOE RE[ENIE DLQ "1 : = n RAZRE[IMA T E IMEET TO^NOE RE[ENIE x0 " PRI KO dOKAZATELXSTWO. oBOZNA^IM ^EREZ " MINIMALXNOE TOROM SISTEMA " IMEET RE[ENIE PO USLOWI@ " "1 .
-
= 1 [(
,
. .
(1)
+2)(
-
)],
.
,
(1 )
(
" : (x;"): Axb+"e ": =
-
):
min
dOPUSTIM ^TO UTWERVDENIE TEOREMY NE WERNO TOGDA " > zADA^A OPREDELENIQ " QWLQETSQ S U^ETOM RAWENSTWA OZlp S CELEWYM WEKTOROM c ;:::; ; ; n PEREMENNYMI x;" I OGRANI^ENIQMI Ax "e b sLEDOWATELXNO PO TEOREME " MOVET BYTX PREDSTAWLENA W WIDE DROBI SO ZNAMENATELEM NE PREWY[A@]IM Aj e n A T E " = n A > "1 PRI[LI K PROTIWORE^I@ S OPREDELENIEM " aNALOGI^NOE UTWERVDENIE SPRAWEDLIWO I DLQ OZlp oPREDELENIE 2. tO^KA x" NAZYWAETSQ " PRIBLIVENNYM RE[ENI EM OZlp ESLI ONA QWLQETSQ " PRIBLIVENNYM RE[ENIEM SISTEMY I REALIZUET MAKSIMUM W S " TO^NOSTX@ hai;x"i bi " 8i ;m I hc;x"i d " IMEET "2 ) eSLI OZlp tEOREMA 2 (O MERE NESOWMESTNOSTI PRIBLIVENNOE RE[ENIE DLQ "2 : = n2 3 A TO \TA ZADA^A IMEET TO^NOE RE[ENIE x dOKAZATELXSTWO SM W S ,
,
(
0.
min( ) =
= (0
0
1)
max(
))
(
)
+1
.
,
1
,
([
])
(
+ 1)(
),
. .
1 [(
+ 1)(
)]
|
.
.
-
(2),
-
-
(1)
(2)
+
-
:
= 1
.
.
= 1 (2
.
.
[3,
. 21].
29
(
(2)
)),
-
x6. mETOD \LLIPSOIDOW
pOLINOMIALXNYJ 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^NOGO BYL UKAZAN l. g. hA^IQNOM I SOSTOIT W SLEDU@]EM. pRISWOIM x1 := x"1 I PODSTAWIM x1 W (1). rAZOBXEM MNOVESTWO : NERAWENSTW W SISTEME NA DWA PODMNOVESTWA M = f1;:::;mg INDEKSOW M (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-LIBO WWEDEM MNOVESTWO INDEKSOW NEWYPOLNENNYH NERAi 62 M (x1).+ tOGDA WENSTW M =: fij hai ;x01 i > bi g M n M (x1 ) I RASSMOTRIM NA OTREZKE 1 01 01 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 IMENNO OPREDELIM bi hai;x1i ; i1 =: arg min bi hai;x1i =: imin i2M + hai ;x01 i hai ;x1 i 2M + hai ;x01 i hai ;x1 i I PRISWOIM x2 := (1 )x1 + x01 . iMEEM M (x2 ) M (x1 ) [ fi1 g, IBO NERAWENSTWA S INDEKSAMI IZ M (x1 ) "1 -PRIBLIVENNO WYPOLNQLISX KAK RAWENSTWA NA WSEM OTREZKE [x1 ;x01 ], A NERAWENSTWO S INDEKSOM W x2 KAK RAWENSTWO i1 2 M +, NE WYPOLNENNOE W TO^KE x01, WYPOLNQETSQ 2 1 PO 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 x0 SOOTWETSTWU@]EJ SISTEMY RAWENSTW OKAVETSQ x0 | RE[ENIEM (1). s U^ETOM POLINOMIALXNOSTI ZADA^I RE[ENIQ SISTEM URAWNENIJ PREDLOVENNYJ ALGORITM OKRUGLENIQ POLINOMIALEN. 30
aNALOGI^NYJ ALGORITM IMEETSQ I DLQ OKRUGLENIQ "2 PRIBLIVEN NOGO RE[ENIQ OZlp x"2 DO TO^NOGO x SM S pO\TOMU DLQ PO STROENIQ POLINOMIALXNOGO ALGORITMA RE[ENIQ OZlp OSTALOSX UKA ZATX POLINOMIALXNYJ ALGORITM POISKA "2 PRIBLIVENNOGO RE[ENIQ OZlp W [ARE kxk n1=2 ILI UDOSTOWERENIQ ^TO TAKOGO RE[ENIQ NET PO TEOREMAM IZ x tREBUEMYJ ALGORITM OSNOWANNYJ NA METODE \LLIPSOIDOW KOTORYJ PREDLOVILI W GG d b `DIN I a s nEMIROWSKIJ I NEZAWISIMO n z {OR PRIWODITSQ W SLEDU @]IH PUNKTAH zDESX I DALEE : D GDE MATRICA D ZADAETSQ TABLICEJ PROIZWOLXNYJ \LLIPSOID W Rn S CENTROM I NE 2. pUSTX E NULEWOGO OB_EMA E rASSMOTRIM n MERNU@ PLOSKOSTX ZADAN NU@ WEKTOROM g NORMALI I PROHODQ]U@ ^EREZ CENTR \LLIPSOIDA E oBOZNA^IM ^EREZ E g ODIN IZ DWUH POLU\LLIPSOIDOW NA KOTORYE RAZBIWAET E DANNAQ PLOSKOSTX E g E \ fxj hg;x i g: uTWERVDENIE 1. pOLU\LLIPSOID E g \LLIPSOIDA E MOVNO CE LIKOM ZAKL@^ITX W NOWYJ \LLIPSOID E 0 IME@]IJ OB_EM STROGO MENX[IJ E 0 -
(
. [3,
-
. 21]).
-
-
-
(
1,2
,
5).
,
,
.
1976{77
.
(
)
.
.
.
.
.
,
-
.
= (
),
(3).
|
-
vol
.
(
1)-
,
-
.
( )
,
,
( ) =
0
( )
-
,
,
E < e 1=(2n+2); E I E 0 MOVNO WY^ISLITX PO E g ZA O n2 ARIFMETI^ESKIH OPERACIJ dOKAZATELXSTWO . pUSTX E EDINI^NYJ [AR S CENTROM W TO^KE f 2 Rn kxk g A E g E x E \fxn g pOMESTIM CENTR 1 TOGDA E 0 W TO^KU 0 ;:::; ; n+1 ,
vol
( )
vol
( )
(
)
.
|
0:
=
:
1 ,
= (0
0
( ) =
0 .
),
E 0 fxj x21 ::: x2n 1 = 2 xn n 2= 2 g; = n < e 1=(n+1); 2 : = n2 n <1 e1=(n1=(21)n:+2) GDE : oTNO[ENIE OB_EMOW RAWNO PROIZWEDENI@ POLUOSEJ < e =
= 1
(
1 (
+
+
)
+(
+ 1)
1
+1
= 1+1 (
)
1
1)
2
OTS@DA POLU^AEM IBO L@BOJ \LLIPSOID MOVNO PREWRATITX W [AR AFINNYM PREOBRAZOWANIEM KOORDINAT SOHRANQ@]IM OB_EM dEJ STWITELXNO BUDEM PREDSTAWLQTX PROIZWOLXNYJ \LLIPSOID E S POMO ]X@ EGO CENTRA I MATRICY Q n n ZADA@]EJ UKAZANNOE PREOBRA ZOWANIE E fxj x Qy; kyk g oBOZNA^IM : QT g=kQT gk GDE WERHNIJ INDEKS T ZNAK TRANSPONIROWANIQ tOGDA 0 I Q0 PRED STAWLQ@]IE \LLIPSOID E 0 MINIMALXNOGO OB_EMA OPISANNYJ WOKRUG ( ),
,
.
,
-
(
:
=
-
=
),
+
-
1 .
|
=
.
,
31
,
,
-
,
POLU\LLIPSOIDA E g PERES^ITYWA@TSQ PO FORMULAM ( ),
0 =
n
1 +1
Q0 = p
Q;
(
n n2
1)
fQ
r
+(
n n
1 +1
1)
QT g
ZA O n2 ARIFMETI^ESKIH OPERACIJ 3 mETOD \LLIPSOIDOW POLU^ENIQ "-PRIBLIVENNOGO RE[ENIQ "2 : = n2 3 wWEDEM " OZlp. pOLOVIM " : n1=MNOVESTWO 2 S CENTROM R PRIBLIVENNYH RE[ENIJ OZlp W [ARE RADIUSA W X" : fxj hai ;xi bi " 8i ;m; hc;xi d "; kxk Rg: wYBEREM UKAZANNYJ WY[E [AR W KA^ESTWE NA^ALXNOJ ITERACII DLQ \LLIPSOIDA E X" rASSMOTRIM PROIZWOLXNU@ ITERACI@ pROWERQEM QWLQETSQ LI CENTR \LLIPSOIDA E " PRIBLIVENNYM RE[ENIEM eSLI DA TO ALGORITM ZAKAN^IWAET SWO@ RABOTU W PROTIW NOM SLU^AE STROIM \LLIPSOID E 0 DLQ O^EREDNOJ ITERACII KAK MINI MALXNYJ PO OB_EMU \LLIPSOID SODERVA]IJ POLU\LLIPSOID E g SM P GDE WEKTOR g OPREDELQETSQ SLEDU@]IM OBRAZOM tAK KAK 62 X0 " TO LIBO 9i hai;i > bi " I TOGDA g ai LIBO 0 hc; i < d "Ig c uBEDIMSQ ^TO PRI \TOM X" E 0 dEJSTWITELXNO DLQ WARIANTA 0 8x 2 X" ha0i;xi bi " < hai;i T E X" E \ fxj h0ai;x i g E ai E I ANALOGI^NO POLU^IM DLQ WARIANTA (
)
.
.
:=
=
1 (2
).
-
=
0:
=
+
= 1
.
.
,
-
.
,
,
-
-
,
(
.
( )
.2),
.
,
1 )
:
+
2 )
,
:=
:=
,
.
,
.
+
,
,
1
. .
0
=
X" 0 E \ fxj hc;x i g E c E 0 tEPERX S E E WOZWRA]AEMSQ K NA^ALU ITERACII NA NOWYJ [AG oCENIM ^ISLO ITERACIJ METODA: \LLIPSOIDOW pOKAVEM ^TO X" SODERVIT [AR RADIUSA r= GDE r "= hn1=2 < R; h jaij j; jcj j h WYSOTA ZADA^I pUSTX x TO^NOE RE[ENIE W X" iZ kx xk r SLEDUET jhai ;xi hai ;x ij kai k kx xk hn1=2 r " 8i 2 M I jhc;xi hc;x ij kck kx xk hn1=2 r T E UKAZANNYJ WYBOR r GARANTIRUET ^TO WSE TAKIE x BUDUT " PRIBLIVENNYMI RE[ENIQMI pOSKOLXKU kx k R TO MNOVESTWO TEH IZ RASSMATRIWAEMYH x DLQ KOTORYH kxk R T E PERESE^ENIE [AROW RADIUSA r I R WKL@^A @]EE CENTR PERWOGO SODERVIT [AR RADIUSA r= |TOT [AR I PRI NADLEVIT X" tAKIM OBRAZOM OB_EM X" BOLX[E OB_EMA n MERNOGO (
)
;
2
0
=
(
)
:=
.
(
).
.
2,
).
=
(
,
)
(
|
.
=
,
,
. .
-
.
,
(
,
. .
,
),
.
-
2.
,
-
-
32
[ARA RADIUSA r= zNA^IT OB_EM \LLIPSOIDA POSTROENNOGO POSLED NIM NAPRIMER E k DLQ k J ITERACII NE DOLVEN OKAZATXSQ MENX[E OB_EMA \TOGO [ARA oTS@DA I IZ UTWERVDENIQ POLU^AEM DLQ k SO OTNO[ENIE 2.
,
,
,
-
-
,
.
1
-
r n X" E k < e k=(2n+2); R E1 E1 IZ KOTOROGO k PO OPREDELENI@ r;R;";h I NE PREWOSHODIT n2 Rnh=" < n2 n3:5 5 < n2 n upravnenie 6. oCENITX PO PORQDKU BITOWU@ DLINU L WHODA OZlp: DOKAZATX, ^TO L > O n sLEDOWATELXNO ^ISLO ITERACIJ METODA \LLIPSOIDOW k < O n2 L I S U^ETOM O n2 nm ARIFMETI^ESKIH OPERACIJ DLQ KAVDOJ ITERA CII POLU^IM OCENKU O n3 n m L DLQ ^ISLA ARIFMETI^ESKIH OPERA CIJ DOSTATO^NOGO METODU \LLIPSOIDOW PRI POISKE "2 PRIBLIVENNOGO RE[ENIQ OZlp aLGORITM OKRUGLENIQ "2 PRIBLIVENNOGO RE[ENIQ DO
2
vol
vol
vol
vol
(
2
)
ln(
)
2
ln(2
)
10
(ln(
ln(
).
)).
,
(
+
(
)
)
(
,
-
(
+
)
)
-
,
-
.
-
TO^NOGO \TOJ OCENKI NE PORTIT SM S mOVNO TAKVE POKAZATX ^TO PRI REALIZACII METODA \LLIPSOIDOW I ALGORITMA OKRUGLENIQ WSE ARIFMETI^ESKIE OPERACII DOSTATO^NO PROWODITX S ^ISLAMI DWOI^ NOJ DLINY OGRANI^ENNOJ O L pRI \TOM O[IBKI WOZNIKA@]IE ZA S^ET KONE^NOSTI ^ISLA RAZRQDOW O[IBKI OKRUGLENIJ POGLO]A@TSQ PUTEM NEKOTOROGO DOPOLNITELXNOGO UWELI^ENIQ RAZDUTIQ OPISAN NOGO \LLIPSOIDA E 0 NA KAVDOJ ITERACII S ^TO NE WLIQET NA PORQDOK OCENKI DLQ OB]EGO ^ISLA ITERACIJ w REZULXTATE WREMENNAQ SLOVNOSTX TAKOJ PROCEDURY RE[ENIQ OZlp OKAZYWAETSQ POLINOMOM OT DLINY WHODA I SPRAWEDLIWA tEOREMA 3. zADA^A lp S CELYMI KO\FFICIENTAMI RAZRE[IMA ZA POLINOMIALXNOE OT DLINY WHODA WREMQ sLEDSTWIEM DANNOJ TEOREMY QWLQETSQ (
.[3,
. 21]).
,
-
,
(
).
,
(
),
(\
[3,
")
-
. 24],
.
.
uTWERVDENIE 2. ln 2 P
.
pOD^ERKNEM ^TO NESMOTRQ NA DOKAZANNU@ POLINOMIALXNOSTX ME TOD \LLIPSOIDOW NE MOVET KONKURIROWATX S SIMPLEKS METODOM PRI PRAKTI^ESKOM RE[ENII ZADA^ lp REALXNO ON PRIMENQETSQ W WY PUKLOM KWADRATI^NOM PROGRAMMIROWANII POSKOLXKU POLU^ENNAQ OCENKA ^ISLA EGO ITERACIJ DOSTIGAETSQ NA L@BYH INDIWIDUALXNYH ,
,
-
-
(
-
),
33
ZADA^AH DAVE ESLI W KA^ESTWE NA^ALXNOGO PRIBLIVENIQ WZQTX RE[E NIE tOGDA KAK SIMPLEKS METOD DLQ HORO[IH NEWYROVDENNYH ZA DA^ DAET OCENKU O n3 NA PORQDOK MENX[U@ ^EM METOD \LLIPSOIDOW I ZA ODNU ITERACI@ MOVET PODTWERDITX ^TO NA^ALXNOE PRIBLIVENIE QWLQETSQ RE[ENIEM tEM NE MENEE SAM FAKT POLINOMIALXNOSTI lp INICIIROWAL POISK NOWYH METODOW lp ^TO PRIWELO K SOZDANI@ CELO GO KLASSA \FFEKTIWNYH METODOW MATEMATI^ESKOGO PROGRAMMIROWANIQ METODY WNUTRENNEJ TO^KI I POZWOLILO POSTROITX KONKUREN TOSPOSOBNYE POLINOMIALXNYE ALGORITMY lp iDEQ IH POSTROENIQ BUDET IZLOVENA W SLEDU@]EM PARAGRAFE GDE TAKVE PRIWODQTSQ NE OBHODIMYE SWEDENIQ PO TEORII lp NA^INAQ S ln ,
-
.
-
(
\
" (
),
)
-
,
,
,
.
,
|
-
|
-
.
,
-
,
.
x7. tEORIQ DWOJSTWENNOSTI lp. iDEQ METODA kARMARKARA
sLEDSTWIQ SISTEM ln. aFINNAQ LEMMA fARKA[A /BEZ DOKAZATELXSTWA/. lEMMA fARKA[A O NERAZRE[IMOSTI. tEOREMA DWOJSTWENNOSTI lp. sWEDENIE OZlp K ODNORODNOJ SISTEME URAWNENIJ S OGRANI^ENIEM POLOVITELXNOSTI. iDEQ METODA kARMARKARA I EGO OTLI^IE OT SIMPLEKS-METODA. 1. sISTEMA ln (1) NAZYWAETSQ RAZRE[IMOJ, ESLI 9x: Ax b, I NERAZRE[IMOJ | W PROTIWNOM SLU^AE. oZlp (2) RAZRE[IMA, KOGDA RAZRE[IMA SISTEMA (1) I MAKSIMUM W (2) DOSTIGAETSQ. oPREDELENIE 3. lINEJNOE NERAWENSTWO
hc;xi d
(4)
QWLQETSQ SLEDSTWIEM RAZRE[IMOJ SISTEMY LINEJNYH NERAWENSTW ESLI DLQ L@BOGO x UDOWLETWORQ@]EGO WYPOLNENO sPOSOB POLU^ENIQ NERAWENSTW SLEDSTWIJ DOWOLXNO PROST WYBEREM PROIZWOLXNYE i 8i 2 M DOMNOVIM NA i KAVDOE i E NERAWENSTWO SISTEMY I SLOVIM POLU^IM DLQ WEKTORA
(1),
,
(1),
(4).
-
0
(1)
:
,
-
;
c
=
X
i 2M
iai I L@BOGO ^ISLA d
X
i2M
ibi;
^TO BUDET SLEDSTWIEM oKAZYWAETSQ DRUGIH SLEDSTWIJ U ln NE BYWAET a IMENNO SPRAWEDLIWA (4)
(1).
,
.
34
lEMMA fARKA[A (AFINNAQ) lINEJNOE NERAWENSTWO QWLQETSQ SLEDSTWIEM RAZRE[IMOJ W WE]ESTWENNYH PEREMENNYH SISTEMY ln TOGDA I TOLXKO TOGDA KOGDA SU]ESTWUET WEKTOR 2 Rm .
(4)
(1)
,
c
=
X
i 2M
:
iai; d
X
i2M
ibi; i 8i 2 M: 0
(5)
sHEMU DOKAZATELXSTWA SM W S dLQ NERAZRE[IMOJ SISTEMY ln MOVNO FORMALXNO S^ITATX SLEDSTWIEM ZAWEDOMO NEWERNOE NERAWENSTWO h ;xi I DALEE POLXZOWATXSQ AFINNOJ LEMMOJ fARKA[A KAK POKAZYWAET lEMMA fARKA[A O NERAZRE[IMOSTI sISTEMA ln NERAZRE [IMA TOGDA I TOLXKO TOGDA KOGDA RAZRE[IMA SISTEMA
(
.
[3,
. 18].)
(1)
0
(1)
1
,
.
(1)
-
,
X
i 2M
iai
= 0
;
X
i2M
ibi ; i 8i 2 M: 1
0
(6)
dOKAZATELXSTWO. pUSTX NERAZRE[IMA TOGDA IZ RAZRE[I MOSTI SISTEMY hai ;xi xn+1 bi 8i 2 M DOLVNO SLEDOWATX ^TO xn+1 " < T E SLEDSTWIEM \TOJ SISTEMY QWLQETSQ NERAWENSTWO h ;:::; ; =" ; x;xn+1 i IPIZ AFINNOJ LEMMY fARKA[A POLU ^AEM A TAKVE W DOPOLNENIE i =" eSLI VE RAZRE[IMA TO UKAZANNOE WY[E NERAWENSTWO h ;xi OKAZYWAETSQ SLEDSTWIEM I DOLVNO WYPOLNQTXSQ DLQ WSEH x UDOWLETWORQ@]IH ZNA^IT TAKIH NE SU]ESTWUET tEPERX MY MOVEM DOKAZATX OSNOWNOJ TEORETI^ESKIJ REZULXTAT lp TEOREMU DWOJSTWENNOSTI NA KOTOROJ BAZIRU@TSQ KAK METODY RE[ENIQ ZADA^ lp TAK I SPOSOBY ANALIZA RE[ENIQ I KOTORAQ FAK TI^ESKI DAET NEOBHODIMYE I DOSTATO^NYE USLOWIQ OPTIMALXNOSTI W lp nALI^IE DWOJSTWENNOSTI OBUSLOWIW HORO[U@ HARAKTERIZACI@ ZADA^I ln PREDOPREDELILO POLINOMIALXNOSTX lp oPREDELENIE 4. dWOJSTWENNOJ K ZADA^E lp NA MAKSIMUM S OGRA NI^ENIQMI NERAWENSTWAMI W FORME OZlp NAZYWAETSQ SLEDU@]AQ ZADA^A lp NA MINIMUM S OGRANI^ENIQMI W KANONI^ESKOJ FORME (1)
,
-
+
0,
(0
0 1
,
. .
) (
)
1
-
(6) (
= 1
0
(1)
).
(6)
,
1
,
(1),
,
.
|
,
,
,
.
-
,
,
.
-
(2)
:
min
f X ibij X iai c; i 8i 2 M g; i2M
i2M
=
0
35
ILI W KRATKOJ ZAPISI
A=c; 0 min
h;bi:
(7)
dLQ TOGO ^TOBY POSTROITX DWOJSTWENNU@ K PROIZWOLXNOJ ZADA^E lp NADO PREDSTAWITX EE W FORME OZlp PRIMENITX FORMULU A ZATEM WERNUTXSQ K OBOZNA^ENIQM ISHODNOJ ZADA^I ,
,
,
(7),
.
upravnenie 7. pOKAZATX, ^TO DWOJSTWENNAQ ZADA^A K DWOJSTWENNOJ ZADA^E lp SOWPADAET S PRQMOJ ZADA^EJ lp :
PREDSTAWITX W FORME OZlp ANALOGI^NO UPRAVNENI@ WYPISATX DWOJSTWENNU@ K POLU^ENNOJ ZADA^E I SWESTI EE K tEOREMA 4 DWOJSTWENNOSTI lp zADA^A lp RAZRE[IMA TOGDA I TOLXKO TOGDA KOGDA RAZRE[IMA DWOJSTWENNAQ K NEJ w SLU^AE RAZ RE[IMOSTI OPTIMALXNYE ZNA^ENIQ CELEWYH FUNKCIJ W OBEIH ZADA^AH d ZNA^ENIE SOWPADA@T T E d d GDE d ZNA^ENIE dOKAZATELXSTWO PROWEDEM DLQ SLU^AQ OZlp POSKOLXKU L@BAQ ZADA^A lp ADEKWATNO PREDSTAWLQETSQ W TAKOJ FORME pUSTX ZADA^A RAZRE[IMA TOGDA QWLQETSQ SLEDSTWIEM 8d d I NE QWLQETSQ 8d < d ^TO PO AFINNOJ LEMME fARKA[A \KWIWALENTNO RAZRE[IMOSTI PRI d d I NERAZRE[IMOSTI PRI d < d T E d fdj g A \TO I ESTX ZNA^ENIE i NAOBOROT IZ RAZRE[IMOSTI SLEDUET NERAZRE[IMOSTX IBO W PROTIWNOM SLU^AE W OBRA]ALSQ BY W 1 TAK KAK PRIBAWLENIE RE[ENIQ K RE[ENI@ DAET DOPUSTIMU@ TO^KU I UMENX[AET ZNA^ENIE CELEWOJ FUNKCII oTS@DA POLU^AEM RAZ RE[IMOSTX PO LEMME fARKA[A O NERAZRE[IMOSTI kROME TOGO RAZRE[IMOSTX OZNA^AET RAZRE[IMOSTX DLQ L@BOGO d d TAK ^TO OKAZYWAETSQ SLEDSTWIEM DLQ d d I PO\TOMU d OGRANI^IWAET SWERHU ZNA^ENIE T E MAKSIMUM W DOSTIGAETSQ tAKIM OBRAZOM POLU^ILI RAZRE[IMOSTX ZADA^I I MOVEM WERNUTX SQ K NA^ALU DOKAZATELXSTWA DLQ USTANOWLENIQ RAWENSTWA d d iZ TEOREMY NEPOSREDSTWENNO POLU^AEM uTWERVDENIE 3. zADA^A lp OPTIMIZACII \KWIWALENTNA RE[E NI@ SISTEMY LINEJNYH NERAWENSTW dEJSTWITELXNO OZlp \KWIWALENTNA ZADA^E lp I OBE ONI \KWIWALENTNY SISTEME ln OTNOSITELXNO NEIZWESTNYH x; (7)
(
5),
(2).
(
).
,
,
.
. .
=
,
|
(2),
-
|
(7).
,
.
(2)
,
(4)
(1)
,
(5)
,
. .
= min
(5)
(5) ,
(7).
,
(7)
min
(6),
(7)
(6)
(
(7)
(7)).
-
(1)
.
(7)
,
(5)
(4)
,
(1)
(2),
,
. .
(2)
.
(2)
-
=
.
4
-
.
,
(2)
(7)
(
Ax b; hc;xi hb;i; A c; : =
=
36
0
):
(8)
uTWERVDENIE 4. zADA^A lp OPTIMIZACII \KWIWALENTNA RE[E NI@ SISTEMY LINEJNYH URAWNENIJ W NEOTRICATELXNYH PEREMENNYH dOKAZATELXSTWO. oT SISTEMY ln PEREHODIM K OGRANI^ENI QM W KANONI^ESKOJ FORME ANALOGI^NO UPRAVNENIQM uTWERVDENIE 5. zADA^A lp \KWIWALENTNA POISKU NEOTRICATELX NOGO NENULEWOGO RE[ENIQ ODNORODNOJ SISTEMY LINEJNYH URAWNENIJ dOKAZATELXSTWO. nA OSNOWANII UTWERVDENIQ OZlp SWODITSQ K NEKOTOROJ SISTEME ln S CELYMI KO\FFICIENTAMI OTNOSITELXNO WEKTORA WE]ESTWENNYH NEIZWESTNYH y -
.
(8)
-
5,7.
-
.
4
(
)
:
Py q; y ; MATRICA K N wWEDEM PARAMETR R MAVORI ^
0
= ^
(9)
PUSTX P RU@]IJ KOORDINATY KAKOGO TO RE[ENIQ PO TEOREME O GRANICAH RE[ENIJ ESLI SISTEMA RAZRE[IMA dOBAWIM K NERAWENSTWO ^ |
(
(
^,
1)).
-
hy; ei y1 ::: yN 1 NR;
),
(9)
.
=
-
(9) (
+
(9)
^
+
KOTOROE PREWRATIM W RAWENSTWO S POMO]X@ DOPOLNITELXNOJ PEREMEN NOJ yN hy; ei y1 ::: yN 1 yN NR A PEREPI[ETSQ KAK P j y q; y tEPERX SDELAEM ZAMENU PEREMENNYH x y=R I OBOZNA^IM P : NR P j qjqj ::: jq pRIDEM K ODNORODNOJ SISTEME S DOPOLNITELXNYMI OGRANI^ENIQMI x x1 ;:::;xN Px hx; ei N ^TO SOOTWETSTWUET SISTEME Px ; x ; hx; ei > S RE[ENIQMI LU^AMI tx0 8t > L@BOE IZ KOTORYH PERES^ITYWAETSQ W RE[ENIE ISHODNOJ SISTEMY G wOSPOLXZUEMSQ 2 mETOD kARMARKARA UTWERVDENIEM I: OBOZNA^ENIQMI WWEDENNYMI PRI EGO DOKAZATELX STWE pUSTX p x hp1;xi 2 ::: hpK ;xi 2 GDE pi STROKI P tOGDA p x \KWIWALENTNO Px wWEDEM FUNKCI@ kARMARKARA :
^
=
[^ 0] ^ = ^
+
+
+
=
^,
0.
^
:= ^
^[ ^ 0]
=
[^ ^
= (
= 0
,
-
^
^].
= 0 =
-
(9)
0,
)
0
0
0,
.
.
(N. Karmarkar, 1984
5
.
(
(
.).
,
) = (
)
+
-
+ (
) ,
|
.
= 0.
) = 0
N=2 k x : x1xp2 x ::: xN : (
) =
[ (
)]
pRIMENQQ TEOREMU I ALGORITM OKRUGLENIQ K ZADA^E RE[ENIQ MOVNO POKAZATX ^TO DLQ TO^NOGO EE RE[ENIQ DOSTATO^NO NAJTI TAKOJ x > DLQ KOTOROGO k x = P N S pOLINOMIALXNYJ ALGORITM POISKA NUVNOGO PRIBLIVENNOGO x PRIWODITSQ W S I MY NE BUDEM EGO OPISYWATX oTMETIM 2
(9),
,
^
0,
( ^)
1 [3(( ^ ))
] [3,
. 25{26].
^
[3,
. 26{28],
.
37
TOLXKO ^TO ANALOGI^NYJ ALGORITM MOVET BYTX POSTROEN NA OSNOWA NII PRIMENENIQ METODA nX@TONA SM W RAZD K ZADA^E MINIMIZA CII FUNKCII kARMARKARA ILI EJ PODOBNYH w REZULXTATE POLU^AEM CELYJ KLASS POLINOMIALXNYH ALGORITMOW lp KOTORYE NA PRAKTI KE OKAZYWA@TSQ SRAWNIMYMI S SIMPLEKS METODOM NE IMEQ TEORETI ^ESKIH NEDOSTATKOW POSLEDNEGO pREDLOVENNYE ALGORITMY STROQTSQ NA PRINCIPIALXNO NOWOJ IDEE NE DISKRETNOJ A NEPRERYWNOJ TRAK TOWKI ZADA^I lp KOGDA WMESTO PEREBORA KONE^NOGO ^ISLA UGLOWYH TO^EK OSU]ESTWLQ@T POISK RE[ENIQ W ISHODNOM PROSTRANSTWE WE]E STWENNYH PEREMENNYH I TRAEKTORII ALGORITMOW NE PROHODQT ^EREZ UGLOWYE TO^KI nAPOMNIM ^TO METOD \LLIPSOIDOW TAKVE NE ORIENTI RUETSQ NA UGLOWYE TO^KI MNOGOGRANNIKA OGRANI^ENIJ hARAKTERNO ^TO IMENNO TAKOJ UHOD OT DISKRETNOGO PROGRAMMIROWANIQ POZWOLIL POSTROITX POLINOMIALXNYE ALGORITMY lp pO\TOMU DALEE BUDET DAN NEKOTORYJ OBZOR OSNOWNYH PODHODOW K RE[ENI@ NEPRERYWNYH ZADA^ OPTIMIZACII zAME^ANIE. eSLI BY RE^X [LA O NEPOSREDSTWENNOM POISKE TO^NO GO RE[ENIQ ZADA^I lp UKAZANNYMI METODAMI TO NELXZQ BYLO BY GA RANTIROWATX KONE^NO[AGOWOSTX NE TO ^TO POLINOMIALXNOSTX SOOT WETSTWU@]IH ALGORITMOW dLQ IH PRIMENENIQ SU]ESTWENNOJ QWLQET SQ WOZMOVNOSTX OSTANOWKI W PRIBLIVENNOM RE[ENII BLAGODARQ NALI ^I@ POLINOMIALXNOGO ALGORITMA OKRUGLENIQ nO POSKOLXKU DLQ EGO RABOTY TREBUETSQ NA^ALXNOE PRIBLIVENIE IZ OPREDELENNOJ OKREST NOSTI RE[ENIQ ZAWISQ]EJ OT DLINY l ILI WYSOTY h ILI DLINY WHODA L KONKRETNOJ ZADA^I lp TO I ^ISLO ITERACIJ ALGORITMOW BA ZIRU@]IHSQ NA RASSMATRIWAEMOM PRINCIPE ZAWISIT OT ^ISLA CIFR W ZAPISI \LEMENTOW MATRICY OGRANI^ENIJ tAK ^TO NE UDAETSQ ISPOLX ZOWATX DANNU@ IDE@ DLQ POSTROENIQ SILXNOPOLINOMIALXNYH ALGO RITMOW lp KROME KAK W ^ASTNYH SLU^AQH OGRANI^ENNOSTI \LEMENTOW MATRICY NAPRIMER W ZADA^AH NA GRAFAH I SETQH GDE aij ; ,
-
(
.
.3)
-
.
,
-
-
,
-
.
:
,
-
,
-
,
.
,
-
.
,
.
.
-
,
(
-
,
)
-
.
-
-
.
-
,
,
,
,
-
,
.
-
-
,
(
,
,
38
= 0
1).
3.
|lementy matemati~eskogo programmirowaniq (mp)
lITERATURA: 4. kARMANOW w. g. mATEMATI^ESKOE PROGRAMMIROWANIE. m.: nAUKA, 1986.
sUHAREW a g tIMOHOW a w fEDOROW w w kURS METODOW OPTIMIZACII m nAUKA mINU m mATEMATI^ESKOE PROGRAMMIROWANIE m nAUKA 5.
.
.
6.
.,
.
.:
.
.,
.
.
, 1985.
.
x8. OBZOR IDEJ mp
.:
, 1990.
kLASSIFIKACIQ ZADA^ mp. pREIMU]ESTWA WYPUKLOGO SLU^AQ. pONQTIE O GRADIENTNYH I nX@TONOWSKIH METODAH MINIMIZACII. uSLOWNAQ OPTIMIZACIQ, SPOSOBY OSWOBOVDENIQ OT OGRANI^ENIJ (METODY BARXEROW I [TRAFOW). 1. zADA^A lp, KAK I ZADA^A MINIMIZACII FUNKCII kARMARKARA, QWLQETSQ ^ASTNYM SLU^AEM ZADA^I mr:
zDESX TREBUETSQ NAJTI
f (x): xmin 2X
(1)
f (x); T:E: x2X f (x) 2 Arg xmin 2X
arg min
x 2 X : fx 2 X j f x f x 8x 2 X g; I f f x : f ZNA^ENIE ILI l@BOJ TAKOJ x NAZYWAETSQ RE[ENIEM X MNO OPTIMALXNOE ZNA^ENIE CELEWOJ FUNKCII f W ZADA^E VESTWO OGRANI^ENIJ ILI DOPUSTIMOE MNOVESTWO w ZAWISIMOSTI OT PRIRODY MNOVESTWA X ZADA^I OPTIMIZACII X KONE^ KLASSIFICIRU@TSQ KAK DISKRETNYE KOMBINATORNYE NO ILI S^ETNO CELO^ISLENNYE xj 2 Z BULEWY xj 2 B WE X Rn BESKONE^NOMERNYE ILI W ]ESTWENNYE NEPRERYWNYE FUNKCIONALXNOM PROSTRANSTWE NAPRIMER KOGDA X PODMNOVESTWO =
(
)
(
)
=
(1);
(
)
|
(2)
(1),
(1),
-
|
.
:
(
,
(
) |
|
,
) |
-
|
,
-
,
,
,
|
GILXBERTOWA PROSTRANSTWA L2 I T P w DANNOM RAZDELE BUDEM PO PRE IMU]ESTWU RASSMATRIWATX ZADA^I S WE]ESTWENNYMI PEREMENNYMI KOTORYE SOBSTWENNO I NAZYWA@TSQ TRADICIONNO ZADA^AMI MATEMATI^ESKOGO PROGRAMMIROWANIQ (zmp) eSLI X Rn TO GOWORIM O ZADA^E USLOWNOJ OPTIMIZACII PRI USLOWII x 2 X INA^E X Rn POLU^AEM ZADA^U BEZUSLOWNOJ OPTIMIZACII ,
. .
,
(
)
.
,
(
),
.
39
(
=
)
dLQ zmp MINIMUM W DOSTIGAETSQ W USLOWIQH TEOREMY wEJ ER[TRASSA f NEPRERYWNA X KOMPAKTNO ILI DLQ NEKOTOROGO x 2 X OGRANI^ENO MNOVESTWO lEBEGA FUNKCII f fx 2 X jf x f x g kROME RAZDELENIQ NA USLOWNYE I BEZUSLOWNYE zmp KLASSIFICI RU@TSQ PO SWOJSTWAM CELEWOJ FUNKCII I MNOVESTWA OGRANI^ENIJ SO OTWETSTWENNO NA ZADA^I lp WYPUKLOGO PROGRAMMIROWANIQ GLADKIE ILI NEGLADKIE I DR dLQ KAVDOGO IZ KLASSOW zmp RAZRABATYWA@T SQ SWOI ^ISLENNYE METODY IH RE[ENIQ s TO^KI ZRENIQ ^ISLENNYH METODOW SU]ESTWENNO TAKVE RAZDELENIE NA LOKALXNU@ I GLOBALXNU@ OPTIMIZACI@ w OPREDELENII RE^X IDET O GLOBALXNOM MINIMUME KOTORYJ ODNAKO NAJTI NE PROSTO I PO\TOMU ZADA^U STARA@TSQ SWE STI K DISKRETNOJ OPTIMIZACII NA MNOVESTWE LOKALXNYH MINIMUMOW TO^KOJ LOKALXNOGO oPREDELENIE 1. tO^KA x0 2 X NAZYWAETSQ MINIMUMA W zmp ESLI 9" > f x0 f x 8x 2 X \ O" x0 zDESX I DALEE O" x OBOZNA^AET " OKRESTNOSTX TO^KI x dLQ POISKA LOKALXNOGO MINIMUMA PRIMENQ@TSQ SPECIALXNYE ME TODY KOTORYE PRI OPREDELENNYH PREDPOLOVENIQH OKAZYWA@TSQ \F FEKTIWNYMI tOGDA KAK OB]AQ ZADA^A GLOBALXNOJ OPTIMIZACII QWLQ ETSQ NP TRUDNOJ dEJSTWITELXNO K NEJ SWODITSQ NP POLNAQ uTWERVDENIE 1. cln/zmp dOKAZATELXSTWO. pOSKOLXKU ZADA^A ln QWLQETSQ ^ASTNYM SLU ^AEM ZADA^I lp TO DLQ SWEDENIQ cln K zmp DOSTATO^NO PRED STAWITX USLOWIE CELO^ISLENNOSTI PEREMENNYH W WIDE OGRANI^ENIJ NERAWENSTW NA WE]ESTWENNYE PEREMENNYE ^TO NETRUDNO SDELATX NAPRIMER TAK fxj 2 Zg \KWIWALENTNO fxj 2 Rj 2 xj g pO\TOMU METODY GLOBALXNOJ OPTIMIZACII BUDUT RASSMOTRENY W RAZD A W DANNOM PARAGRAFE OSTANOWIMSQ NA POISKE LOKALXNOGO \KS TREMUMA oTMETIM ^TO DLQ RQDA \KSTREMALXNYH POSTANOWOK ZADA^ FIZIKI TO^KI LOKALXNOGO \KSTREMUMA IME@T SAMOSTOQTELXNOE ZNA^E NIE kROME TOGO SU]ESTWUET CELYJ KLASS zmp DLQ KOTOROGO LOKALX NYJ \KSTREMUM SOWPADAET S GLOBALXNYM MINIMUMOM \TO ZADA^I WYPUKLOGO PROGRAMMIROWANIQ f NAZYWAETSQ WYPUKLOJ NA X ESLI EE oPREDELENIE 2. fUNKCIQ : NADGRAFIK X f f x;y j y f x ; x 2 X g WYPUKLOE MNOVE STWO fUNKCIQ WYPUKLAQ NA WSEJ OBLASTI OPREDELENIQ NAZYWAETSQ WYPUKLOJ mNOVESTWO NAZYWAETSQ WYPUKLYM ESLI WMESTE S L@BYMI (1)
(
-
,
^
|
(
)
( ^) ).
,
-
-
,
,
.
-
.
.
(2)
,
,
,
,
-
.
(1),
(
0 :
)
(
)
(
)
(
-
).
.
-
,
-
.
-
-
.
-
.
.
-
,
(
-
)
,
,
,
:
sin (
)
0 .
.4,
-
.
,
-
.
,
,
-
,
|
.
,
epigraf
.
=
(
)
(
)
|
,
-
,
.
,
40
DWUMQ SWOIMI TO^KAMI ONO SODERVIT OTREZOK IH SOEDINQ@]IJ uTWERVDENIE 2. l@BAQ TO^KA LOKALXNOGO MINIMUMA WYPUKLOJ FUNKCII QWLQETSQ TO^KOJ EE GLOBALXNOGO MINIMUMA dOKAZATELXSTWO. pUSTX f0 x0 > f x tOGDA f x0 > f x DLQ WSEH TO^EK x POLUINTERWALA x ;x PO OPREDELENI@ A ZNA^IT I W NEKOTOROJ OKRESTNOSTI x0 PROTIWORE^IE S OPREDELENIEM dLQ RE[ENIQ ZADA^ WYPUKLOGO PROGRAMMIROWANIQ PRIMENIM ME TOD \LLIPSOIDOW PRI^EM W GLADKOM SLU^AE OTSE^ENIE POLU\LLIPSO IDA PROWODITSQ NA OSNOWE GRADIENTA NEWYPOLNENNOGO OGRANI^ENIQ W POLNOJ ANALOGII S ALGORITMOM IZ x pO\TOMU ZADA^A POISKA " PRIBLIVENNOGO RE[ENIQ ZADA^I WYPUKLOGO PROGRAMMIROWANIQ OKA ZYWAETSQ POLINOMIALXNO RAZRE[IMOJ dLQ OSTRYH ZADA^ WYPUKLOGO PROGRAMMIROWANIQ KOGDA FUNKCIQ CELI UBYWAET W OKRESTNOSTI MINIMUMA NE MEDLENNEE NEKOTOROJ LINEJNOJ FUNKCII MOVNO PO LU^ITX I TO^NOE RE[ENIE 2. oB]IMI METODAMI LOKALXNOJ OPTIMIZACII DLQ PROIZWOLXNO GO NE OBQZATELXNO WYPUKLOGO SLU^AQ QWLQ@TSQ METODY LOKALXNOGO SPUSKA oPREDELENIE 3. wEKTOR h 2 Rn NAZYWAETSQ NAPRAWLENIEM UBYWANIQ FUNKCII f W TO^KE x ESLI f x h < f x DLQ WSEH DOSTATO^NO MALYH > uTWERVDENIE 3. pUSTX f DIFFERENCIRUEMA W TO^KE x tOGDA ESLI h f x ;hi < TO h NAPRAWLENIE UBYWANIQ FUNKCII f W TO^KE x A ESLI h NAPRAWLENIE UBYWANIQ FUNKCII f W TO^KE x TO ,
.
.
(
)
(
(
]
).
(
(
)
(
)
2),
,
|
1.
-
,
-
6.
-
-
.
|
|
-
.
(
,
,
-
)
.
,
(
+
)
(
)
0.
.
grad
(
)
h f x ;hi
0,
,
grad
(
)
,
|
|
,
0.
dOKAZATELXSTWO. iZ USLOWIQ DIFFERENCIRUEMOSTI f IMEEM DLQ f x h f x h f x ; hi o fh f x ;hi o = g o^EWIDNO POSLEDNQQ DOBAWKA NE IZMENIT
DOSTATO^NO MALYH > grad
(
)
+
(
0:
)
(
+
)
.
(
) =
grad
(
)
+
(
) =
,
ZNAKA WYRAVENIQ W FIGURNYH SKOBKAH ESLI SKALQRNOE PROIZWEDENIE STROGO OTRICATELXNO ILI STROGO POLOVITELXNO oTS@DA AWTOMATI ^ESKI WYTEKAET TREBUEMOE UTWERVDENIE tAKIM OBRAZOM NAPRAWLENIE LOKALXNOGO UBYWANIQ DIFFERENCI RUEMOJ FUNKCII DOLVNO SOSTAWLQTX OSTRYJ UGOL S EE ANTIGRADIEN TOM KOTORYJ QWLQETSQ W SMYSLE LINEJNOGO PRIBLIVENIQ NAILU^[IM NAPRAWLENIEM UBYWANIQ dLQ MNEMONIKI PRIWEDEM \PIGRAF K GLAWE POSWQ]ENNOJ GRADIENTNYM METODAM MINIMIZACII IZ GO IZDANIQ ,
.
-
.
,
-
-
,
.
,
,
41
1-
KNIGI f. p. wASILXEWA ~ISLENNYE METODY RE[ENIQ \KSTREMALXNYH ZADA^: \wOT KTO-TO S GORO^KI SPUSTILSQ | ANTIGRADIENT!" eSLI gradf (x) = 0, TO x BUDET STACIONARNOJ TO^KOJ. oTMETIM, ^TO W USLOWNOJ OPTIMIZACII RAWENSTWO NUL@ GRADIENTA UVE NE QWLQETSQ NEOBHODIMYM USLOWIEM MINIMUMA (SOOTWETSTWU@]IE USLOWIQ BUDUT RASSMOTRENY W x9). nO W BOLEE PROSTOM SLU^AE X = Rn MOVNO, DWIGAQSX NEBOLX[IMI [AGAMI W NAPRAWLENII ANTIGRADIENTA FUNKCII f W TEKU]EJ TO^KE, PRIJTI W STACIONARNU@ TO^KU, KAK PRAWILO, LOKALXNOGO MINIMUMA. tAK MY POLU^AEM IDE@ GRADIENTNOGO METODA BEZUSLOWNOJ MINIMIZACII, ZADAWAEMOGO ITERATIWNOJ PROCEDUROJ xt+1 = xt tgradf (xt); t = 1; 2;:::; 8x1 2 Rn: pARAMETR t NAZYWAETSQ [AGOWYM MNOVITELEM I MOVET WYBIRATXSQ, ISHODQ IZ RAZLI^NYH SOOBRAVENIJ, RAZNYMI SPOSOBAMI. 1) pASSIWNYE SPOSOBY | f t g WYBIRAETSQ ZARANEE. pOSTOQNNYJ [AG | t = 0 DLQ DOSTATO^NO MALYH 0 . uBYWA@]IJ [AG (ESLI 0 NE IZWESTNO ILI PRI NALI^II POMEH) | t # 0; P t = 1; P 2t < 1, NAPRIMER t = 1=t. t 2) aDAPTIWNYE SPOSOBY | f t g ZAWISIT OT REALIZU@]EJSQ fx g. t t mETOD SKOREJ[EGO SPUSKA | t 2 Arg min >0 f (x gradf (x )): mETOD DROBLENIQ [AGA (DELENIQ POPOLAM) | ESLI f (xt+1 ) > f (xt ), TO WOZWRAT K t-J ITERACII S t := t =2. (wOZMOVNO I UWELI^ENIE [AGA PRI STABILXNOM UBYWANII f , T.E. PRIBLIVENNYJ SKOREJ[IJ SPUSK.) pRAWILO aRMIHO | PUTEM DROBLENIQ [AGA DOBIWAEMSQ DLQ t WYPOLNENIQ USLOWIQ f (xt t gradf (xt )) f (xt ) " t kgradf (xt )k2 . w OB]EM SLU^AE DIFFERENCIRUEMOJ, OGRANI^ENNOJ SNIZU f MOVNO POLU^ITX SHODIMOSTX GRADIENTNOGO METODA K MNOVESTWU STACIONARNYH TO^EK, A PRI DOPOLNITELXNYH PREDPOLOVENIQH DOKAZYWAETSQ (ZA ISKL@^ENIEM WARIANTA S UBYWA@]IM [AGOM) LINEJNAQ SKOROSTX SHODIMOSTI, KOTORAQ W WYPUKLYH ZADA^AH OZNA^AET kxt+1 x k qkxt xk DLQ NEKOTOROGO 0 < q < 1. uKAZANNAQ LINEJNAQ OCENKA OB_QSNQETSQ TEM, ^TO W PROCESSE MINIMIZACII GRADIENTNYM METODOM ISPOLXZUETSQ LINEJNAQ APPROKSIMACIQ CELEWOJ FUNKCII NA KAVDOM [AGE. bOLEE WYSOKU@ SKOROSTX SHODIMOSTI POLU^A@T DLQ METODOW, OSNOWANNYH NA KWADRATI^NOJ APPROKSIMACII, W PREDPOLOVENII DWAVDY DIFFERENCIRUEMOSTI f . tIPI^NYM PRIMEROM ZDESX QWLQETSQ METOD nX@TONA. 42
pUSTX f 2 C2 Rn RAZLOVIM FUNKCI@ f W RQD tEJLORA W OKREST NOSTI TEKU]EJ TO^KI xt (
),
-
:
f x f xt h f xt ;x xti hf 00 xt x xt ;x xti o kx xtk2 : wYBEREM xt+1 IZ USLOWIQ MINIMIZACII KWADRATI^NOJ APPROKSIMA CII f x W TO^KE xt T E KWADRATI^NOJ ^ASTI PRIRA]ENIQ f x f xt (
)
(
) =
grad
(
)
+
1
(
2
)(
)
+ (
)
-
(
)
,
. .
POLU^IM METOD nX@TONA
(
)
(
),
:
xt+1 xt f 00 xt 1 f xt ; t ; ;:::; GDE NA^ALXNOE PRIBLIVENIE x1 DOLVNO NAHODITXSQ DOSTATO^NO BLIZ KO K TO^KE OPTIMUMA x w TAKOM SLU^AE I PRI DOPOLNITELXNYH =
(
(
))
grad
(
)
= 1 2
-
.
(
PREDPOLOVENIQH BOLEE SILXNYH ^EM DLQ PRIWEDENNOJ RANEE OCEN KI SKOROSTI SHODIMOSTI GRADIENTNOGO METODA DLQ METODA nX@TONA BUDET SPRAWEDLIWA KWADRATI^NAQ SKOROSTX SHODIMOSTI ,
,
-
)
kxt+1 xk Qkxt xk2; T:E: kxt+1 xk Q Qkx1 xk 2t ; ^TO PREDPOLAGAET kx1 x k < =Q OCENKU DLQ Q SM NAPRIMER 1
1
(
(
)
.,
,
W S e]E RAZ POD^ERKNEM ^TO GRADIENTNYJ METOD W OTLI ^IE OT NX@TONOWSKOGO SHODITSQ PRI L@BOM NA^ALXNOM PRIBLIVENII iZ OPREDELENIQ METODA nX@TONA TAKVE SLEDUET TREBOWANIE NEWYRO VDENNOSTI MATRICY WTORYH PROIZWODNYH GESSIANA FUNKCII f nETRUDNO WIDETX ^TO POLU^ENNAQ FORMULA METODA nX@TONA RE [ENIQ ZADA^ BEZUSLOWNOJ MINIMIZACII SOWPADAET S FORMULOJ METODA nX@TONA RE[ENIQ SISTEMY URAWNENIJ fx SOOTWETSTWU@ ]EJ NEOBHODIMYM USLOWIQM \KSTREMUMA 2 3: dLQ ZADA^ USLOWNOJ MINIMIZACII; NAPRIMER x2[1;2] x ; [5,
. 192]).
,
.
-
(
)
.
,
-
grad
(
) = 0,
-
.
min
PREDLOVENNYE METODY NUVDA@TSQ W MODIFIKACII w ^ASTNOSTI DLQ PRIWEDENNOGO PRIMERA KOGDA MNOVESTWO X IMEET DOSTATO^NO PRO STU@ STRUKTURU UKAZANNYE WY[E FORMULY SOWME]A@TSQ S PROCEDU ROJ PROEKTIROWANIQ NA X NA KAVDOM [AGE METODA tAK PRIHODIM K METODU PROEKCII GRADIENTA .
,
,
-
,
-
.
xt+1
X fxt
= Pr
t
f xt g; t
grad
(
)
43
; ;:::; 8x1 2 Rn:
= 1 2
dLQ BOLEE SLOVNYH MNOVESTW X DOPUSTIM ZADAWAEMYH OGRANI^E NIQMI NERAWENSTWAMI ,
,
X : fx 2 Rnj gi x 8i 2 M g; =
(
)
0
-
(3)
UNIWERSALXNYM SPOSOBOM OSWOBOVDENIQ OT OGRANI^ENIJ QWLQETSQ IH [TRAFOWANIE a IMENNO DLQ DOSTATO^NO BOLX[OJ KONSTANTY C > WMESTO ZADA^I USLOWNOJ MINIMIZACII RASSMATRIWA@T ZADA^U BEZUSLOWNOJ MINIMIZACII O[TRAFOWANNOJ CELEWOJ FUNKCII X + p X + p f x C g x ; gi x GDE f g i n x2R .
0
(1),(3)
min
(
) +
[
(
)]
[
(
)]
i2M i2M \TO FUNKCIQ [TRAFA ([TRAFNAQ FUNKCIQ) DLQ OGRANI^ENIJ NERAWENSTW, g+ () =: max[0;g()] | SREZKA g, PARAMETR [TRAFA p 1.
dRUGIE WIDY FUNKCIJ [TRAFA SM W w USLOWIQH NEPRERYWNO STI FUNKCIJ f; gi NEPUSTOTY X I OGRANI^ENNOSTI MNOVESTWA lEBEGA FUNKCII f MOVNO DOKAZATX ^TO S ROSTOM KONSTANTY [TRAFA
(
.
[4,5].)
-
,
,
X + p f (x) + C [gi (x)] g = f : f n x R 2 C "1 i2M lim min
(4)
eSLI p FUNKCIQ SREZKA I SLEDOWATELXNO [TRAFNAQ FUNKCIQ QWLQETSQ OSTROJ TO 9C ff x C Pi2M gi+ x g f SU]E STWUET TO^NYJ [TRAF oDNAKO PRI p > GLADKIJ [TRAF PO DOBNOE RAWENSTWO OZNA^ALO BY NESU]ESTWENNOSTX OGRANI^ENIJ x 2 X TO^KA BEZUSLOWNOGO MINIMUMA I TAK NAHODITSQ W X 1 n uTWERVDENIE 4. pUSTX P +f;gip2 C R WYPUKLY p > I 9C : C x ff x C gi x g 2 X TOGDA xC 2 x2Rn f x ; T:E: x2Rn f x x2X f x : = 1 (
-
,
),
:
,
min
(
)+
(
).
)
=
(
1 |
-
-
(
).
(
= arg min
(
)+
[
Arg min
(
(
)]
),
,
1
:
,
)
min
(
) = min
(
)
dOKAZATELXSTWO. tAK KAK xC TO^KA BEZUSLOWNOGO \KSTREMUMA DIFFERENCIRUEMOJ FUNKCII TO GRADIENT O[TRAFOWANNOJ FUNKCII C C p P gi+ xC p 1 gi xC f x CELI W NEJ RAWEN NUL@ nO IZ USLOWIQ xC 2 X WSE WYRAVENIQ W KWADRATNYH SKOBKAH A ZNA ^IT I WTOROE SLAGAEMOE RAWNY NUL@ oTS@DA SLEDUET f xC T E NEOBHODIMOE USLOWIE \KSTREMALXNOSTI TO^KI xC DLQ ZADA^I BEZ |
,
: grad
(
)+
[
(
)]
grad
(
) = 0.
,
,
.
. .
grad
(
-
) = 0, -
USLOWNOJ OPTIMIZACII KOTOROE W WYPUKLOM SLU^AE OKAZYWAETSQ I ,
44
DOSTATO^NYM SM UTWERVDENIE pO\TOMU xC TO^KA BEZUSLOW NOGO MINIMUMA f nO xC 2 X TAK ^TO xC I TO^KA USLOWNOGO MINIMUMA f NA X IBO BEZUSLOWNYJ MINIMUM NE PREWY[AET USLOW NOGO uTWERVDENIE DOKAZANO tAKIM OBRAZOM DLQ GLADKOGO [TRAFA NE UDAETSQ SWESTI ZADA^U USLOWNOJ MINIMIZACII K BEZUSLOWNOJ TEM NE MENEE FORMULA PO ZWOLQET ITERATIWNO KOMBINIROWATX METOD [TRAFOW I GRADIENTNYJ METOD W SLEDU@]EJ PROCEDURE 8x1 2 Rn (
.
2).
.
|
,
-
|
,
-
.
.
,
,
xt+1 xt tf =
grad
f xt C t p (
)+
:
X
i 2M
[
(4)
gi+ xt p (
)]
1
grad
gi xt g; t (
)
-
; ;:::;
= 1 2
KOTORAQ SHODITSQ PRI OPREDELENNYH SOOTNO[ENIQH P 2 2MEVDU f t g I t Ct < 1 NAPRI W ^ASTNOSTI DLQ UBYWA@]EGO [AGA PRI p MER t =t; Ct < t uTWERVDENIE POKAZYWAET ^TO TRAEKTORII METODA [TRAFA PRO HODQT WOOB]E GOWORQ WNE MNOVESTWA OGRANI^ENIJ X HOTQ I SHODQT SQ K DANNOMU MNOVESTWU iZ ZA \TOGO RASSMOTRENNYJ METOD INOGDA TAKVE NAZYWA@T METODOM WNE[NIH [TRAFOW W OTLI^IE OT METODOW WNUTRENNEJ TO^KI ILI BARXEROW tIPI^NYM PRIMEROM PRIMENENIQ METODA BARXEROW QWLQETSQ OPISANNYJ W x METOD kARMARKARA KOGDA ZADA^A \KWIWALENTNAQ ZADA^E USLOWNOJ MINIMIZACII
fC t g
,
(
,
= 1
-
).
4
,
,
-
,
,
.
-
-
,
.
7
(9),
x0; P xj =N min
,
px; (
)
SWODITSQ K BEZUSLOWNOJ MINIMIZACII SPECIALXNOJ BARXERNOJ FUNK CII k x NE POZWOLQ@]EJ METODU nX@TONA WYJTI ZA OGRANI^ENIQ x > ESLI W \TIH OGRANI^ENIQH WYBRANO NA^ALXNOE PRIBLIVENIE rAZLI^NYE WIDY BARXERNYH FUNKCIJ SM W DLQ NIH HARAKTER NO BYSTROE WOZRASTANIE PRI PRIBLIVENII IZNUTRI K GRANICE MNOVE STWA OGRANI^ENIJ TOGDA KAK [TRAFNAQ FUNKCIQ STREMITSQ K NUL@ PRI PRIBLIVENII K MNOVESTWU OGRANI^ENIJ IZWNE dLQ RE[E NIQ OB]EJ ZADA^I mp S OGRANI^ENIQMI NERAWENSTWAMI METO DU kARMARKARA SOOTWETSTWUET ISPOLXZOWANIE WMESTO RASSMOTRENNOJ WY[E [TRAFNOJ FUNKCII OSNOWANNOJ NA SREZKE LOGARIFMI^ESKOJ BARXERNOJ FUNKCII RAWNOJ
-
(
),
0,
.
.
[4,5] |
-
-
(
|
).
(1),(3)
-
,
,
,
1
-
X
C i2M
ln[
45
gi x (
)]
PRI gi x < 8i 2 M I 1 W PROTIWNOM SLU^AE |TA FUNKCIQ TAKVE PRIBAWLQETSQ K CELEWOJ I SPRAWEDLIWO SOOTNO[ENIE ANALOGI^NOE (
)
0
+
.
,
,
(4).
dRUGIE SPOSOBY SWEDENIQ ZADA^ USLOWNOJ OPTIMIZACII K BEZUSLOW NOJ OSNOWANNYE NA METODE MNOVITELEJ lAGRANVA BUDUT WYTEKATX IZ REZULXTATOW SLEDU@]EGO PARAGRAFA -
,
,
.
x9. dWOJSTWENNOSTX W mp
nEOBHODIMYE USLOWIQ LOKALXNOGO MINIMUMA OBOB]ENNO DIFFERENCIRUEMYH FUNKCIJ PRI OGRANI^ENIQH NERAWENSTWAH. tEOREMA kUNA-tAKKERA. pONQTIE O REGULQRNOSTI OGRANI^ENIJ NERAWENSTW W ZADA^E mp. mETOD MNOVITELEJ lAGRANVA. 1. w \TOM PARAGRAFE BUDEM RASSMATRIWATX ZADA^U USLOWNOJ OPTIMIZACII (1) S X Rn ; X = 6 ;, PO PREIMU]ESTWU, S OGRANI^ENIQMI NERAWENSTWAMI (3). kAK UVE OTME^ALOSX, USLOWIE RAWENSTWA NUL@ GRADIENTA DLQ TAKIH ZADA^ MOVET NE IMETX NIKAKOGO OTNO[ENIQ K TO^KAM USLOWNOGO \KSTREMUMA. pO\TOMU WYWEDEM SOOTWETSTWU@]IE NEOBHODIMYE USLOWIQ DLQ RASSMATRIWAEMOGO SLU^AQ. wNA^ALE ONI BUDUT DANY W DOSTATO^NO OB]EJ FORME, DOPUSKA@]EJ PRIMENENIE DLQ [IROKOGO KLASSA ZADA^ mp (KUSO^NO-GLADKIH I PRI PROIZWOLXNYM OBRAZOM ZADANNYH OGRANI^ENIQH, A TAKVE NE OBQZATELXNO KONE^NOMERNYH). zATEM PROWEDEM KONKRETIZACI@ DLQ OGRANI^ENIJ (3). dLQ OBY^NYH ZADA^ mp (KONE^NOMERNYH, S NEPRERYWNO DIFFERENCIRUEMYMI FUNKCIQMI) SPRAWEDLIWY WSE DALXNEJ[IE POSTROENIQ I WYWODY PRI ZAMENE ZNAKA r OBY^NYM GRADIENTOM. tAKIM OBRAZOM, OSNOWOJ OBOB]ENIQ QWLQETSQ SLEDU@]EE oPREDELENIE 4. fUNKCIQ f NAZYWAETSQ DIFFERENCIRUEMOJ PO aDAMARU W TO^KE x 2 Rn , ESLI SU]ESTWUET WEKTOR rf (x) 2 Rn , TAKOJ ^TO 8y 2 Rn WYPOLNENO:
f x y0 f x hrf x ;yi: ( ;y !(+0;y ) dLQ BESKONE^NOMERNYH ZADA^ KOGDA f FUNKCIONAL E ! R1 GDE E NEKOTOROE FUNKCIONALXNOE PROSTRANSTWO TREBUETSQ rf x 2 E 0 DLQ PROSTRANSTWA E 0 SOPRQVENNOGO K E I x;y 2 E w GLADKOM SLU^AE f x I MOVNO POLOVITX y0 TOVDESTWENNO RAWNYM y rf x lim
(
+
)
(
)
0)
,
=
(
|
:
,
,
(
) = grad
(
,
)
)
:
,
(
)
.
.
46
w BEZUSLOWNOJ OPTIMIZACII SU]ESTWENNU@ ROLX IGRALI NAPRAWLE NIQ SPUSKA UBYWANIQ CELEWOJ FUNKCII w USLOWNOJ OPTIMIZACII KROME UBYWANIQ CELEWOJ FUNKCII TREBUETSQ OTSLEVIWATX E]E I NE WYHOD ZA OGRANI^ENIQ pO\TOMU WWODITSQ PONQTIE WOZMOVNOGO ILI DOPUSTIMOGO NAPRAWLENIQ W TO^KE x 2 X DLQ MNOVESTWA OGRANI^E NIJ X KAK TAKOGO WEKTORA y DLQ KOTOROGO 9 0 > x y 2 X 8 2 ; 0 zAMYKANIE MNOVESTWA WSEH DOPUSTIMYH NAPRAWLENIJ W TO^KE x DLQ X DAET SLEDU@]EE oPREDELENIE 5. kONTINGENTNYM KONUSOM K MNOVESTWU X W TO^ KE x NAZYWAETSQ MNOVESTWO WEKTOROW -
(
).
,
,
-
.
-
,
[0
0 :
+
].
-
K X;x : fyj 9 f t;yt gt1=1 t;yt ! ;y ; x tyt 2 X 8tg: o^EWIDNO DLQ x 62 X K X; x ; A DLQ x0 2 X K X;x0 n R dLQ x 2 @X W SLU^AE GLADKOJ GRANICY KONUS K X;x NAZY (
) =
(
,
)
: (
^
)
(
^) =
(+0
)
+
,
int
.
(
(
) =
)
-
WAETSQ TAKVE KONUSOM KASATELXNYH I SOOTWETSTWUET KASATELXNYM NAPRAWLENIQM DLQ OGRANI^ENIJ RAWENSTW tEOREMA 1 OB]IJ WID NEOBHODIMYH USLOWIJ LOKALXNOGO MINIMUMA W ZADA^E (1) pUSTX FUNKCIQ f DIFFERENCIRUEMA PO aDAMARU LOKALXNOGO MINIMUMA f W ZADA^E X Rn; X 6 ;; 0x0 TO^KA TOGDA 8y 2 K X;x hrf x0 ;yi : dOKAZATELXSTWO. wYBEREMt y 2 K X;x0 0 dLQ tSOOTWETSTWU@ ]IH EMU PO OPREDELENI@ f t ;y g WYPOLNENO x t y 2 X I NA^I NAQ S DOSTATO^NO BOLX[OGO t; x0 t yt 2 X \ O" x0 IBO t ! SLEDOWATELXNO PO OPREDELENI@ f x0 t yt f x0 w PREDELE POLU^IM -
.
(
).
,
=
|
(
)
(1),
(
)
0
(
).
5
+
,
1
f x0 y0 f x0 ( ;y !(+0;y ) lim
0)
(
+
)
(
-
+
)
=
,
(
(
;y
+
lim
)
,
-
) (
(
0),
).
f x0 tyt f x0 ; t ;y
( t t )!(+0 )
(
+
)
(
)
0
I TREBUEMOE SOOTNO[ENIE WYTEKAET IZ OPREDELENIQ sODERVATELXNO DANNYE USLOWIQ OZNA^A@T ^TO SREDI DOPUSTIMYH NAPRAWLENIJ W TO^KE LOKALXNOGO MINIMUMA NE DOLVNO BYTX NAPRA WLENIJ UBYWANIQ CELEWOJ FUNKCII SM UTWERVDENIE x oDNAKO W TAKOM OB]EM WIDE \TIMI USLOWIQMI NEUDOBNO POLXZOWATXSQ kONKRETIZIRUEM POLU^ENNYE USLOWIQ DLQ OGRANI^ENIJ NERA WENSTW KOGDA X ZADAETSQ FORMULOJ wWEDEM 8x 2 X MNOVESTWO 4.
,
-
(
.
3
8).
.
-
,
(3).
47
INDEKSOW J x fi 2 M j gi x g AKTIWNYH OGRANI^ENIJ W TO^KE x T E TAKIH NERAWENSTW IZ KOTORYE W \TOJ TO^KE WYPOLNENY KAK (
,
) =
(
) = 0
. .
|
(3),
RAWENSTWA i OPREDELIM MNOVESTWO KONUS .
(
)
)
0
G x : fy 2 Rnj hrgj x ;yi 8j 2 J x g: oPREDELENIE 6. mNOVESTWO X DLQ OGRANI^ENIJ NERAWENSTW NAZYWAETSQ REGULQRNYM W TO^KE x 2 X ESLI G x K X;x tEOREMA 2 NEOBHODIMYE USLOWIQ LOKALXNOGO MINIMUMA S OGRA NI^ENIQMI NERAWENSTWAMI pUSTX FUNKCII f; gi 8i 2 M DIFFEREN CIRUEMY PO aDAMARU X 6 ;; x0 TO^KA LOKALXNOGO MINIMUMA f W ZADA^E I MNOVESTWO X REGULQRNO W TO^KE x0 tOGDA 9j rff x0 X j gj x0 g : (
) =
(
(
)
(3)
,
(
)
(
).
(
-
).
,
-
=
|
(1),(3)
.
0 :
(
)+
(
j2J (x0 )
)
= 0
(5)
dOKAZATELXSTWO. pO TEOREME I IZ OPREDELENIQ REGULQRNOSTI X W x0 SLEDUET 0 ^TO hrf x0 ;yi 0 DLQ WSEH y UDOWLETWORQ@]IH USLOWI@ hrgj x ;yi 8j 2 J x zNA^IT PO OPREDELENI@ x LINEJNOE NERAWENSTWO hrf x0 ;yi QWLQETSQ SLEDSTWIEM SISTE MY LINEJNYH NERAWENSTW fhrgj x0 ;yi 8j 2 J x0 g pRIWEDQ \TO NERAWENSTWO K STANDARTNOMU WIDU h rf x0 ;yi I PRIMENIW 1
,
(
(
)
)
0
0
(
(
)
9j
,
3
-
)
0
(
x POLU^IM ^TO rf x0 X j rgj x0 : (
( 7),
0 :
(
7,
0
(
AFINNU@ LEMMU fARKA[A
,
).
)
) .
0
,
) =
(
j2J (x0 )
)
tAKIM OBRAZOM DLQ REGULQRNYH OGRANI^ENIJ NEOBHODIMYM USLO WIEM LOKALXNOGO MINIMUMA W GLADKOJ ZADA^E QWLQETSQ RAWEN STWO NUL@ DIFFERENCIALA FUNKCII W FIGURNYH SKOBKAH W DLQ HOTX KAKIH NIBUDX j ~TOBY NE ZAPISYWATX W QWNOM WIDE MNO VESTWO AKTIWNYH OGRANI^ENIJ WWODQT FUNKCI@ lAGRANVA ,
-
(1),(3)
-
(5)
-
0.
L ;x : f x (
) =
(
-
,
)+
j gj x : f x h;g x0 i j 2M GDE WEKTOR FUNKCIQ g : gj j j 2 M X
(
) =
(
)+
(
)
REGULQRNOJ ZADA^I iZ TEOREMY SLEDUET ^TO RAWENSTWO NUL@ DIFFERENCIALA FUNK CII lAGRANVA DLQ j TAKVE QWLQETSQ NEOBHODIMYM USLOWIEM
(
)
(1),(3),
2
,
-
0
48
( ) = (
( )
). -
LOKALXNOGO MINIMUMA W REGULQRNOJ ZADA^E IBO MNOVITELI lAGRANVA j SOOTWETSTWU@]IE NEAKTIWNYM OGRANI^ENIQM MOVNO WZQTX RAWNYMI NUL@ pOSLEDNEE USLOWIE ZAPISYWAETSQ KAK (1),(3),
,
,
.
h;g x0 i (
)
= 0
(6)
I NAZYWAETSQ USLOWIEM DOPOLNQ@]EJ NEVESTKOSTI iTAK DOKAZANA tEOREMA 3 (PRINCIP OPTIMALXNOSTI lAGRANVA) w PREDPOLO VENIQH TEOREMY DLQ ZADA^I SU]ESTWUET NEOTRICATELXNYJ WEKTOR MNOVITELEJ lAGRANVA TAKOJ ^TO DLQ x0 WYPOLNENY USLOWIQ OPTIMALXNOSTI rx L x0 ; I dLQ WYPUKLYH ZADA^ DANNYE NEOBHODIMYE USLOWIQ QWLQ @TSQ W REGULQRNOM SLU^AE I DOSTATO^NYMI I MOVET BYTX DOKAZANA FUNKCII tEOREMA 4 kUNA, tAKKERA eSLI W ZADA^E f;gj 2 C1 Rn WYPUKLY I MNOVESTWO X REGULQRNO W L@BOJ TO^ KE TO x TO^KA OPTIMUMA W \TOJ ZADA^E TOGDA I TOLXKO TOGDA KOGDA W NEJ WYPOLNENY USLOWIQ OPTIMALXNOSTI DLQ dOKAZATELXSTWO. nEOBHODIMOSTX SLEDUET IZ PREDYDU]IH TEO REM POKAVEM DOSTATO^NOSTX dLQ DANNOGO W TO^KE x WYPOLNENO USLOWIE \KSTREMALXNOSTI x DLQ FUNKCII L ; s U^ETOM NEOTRICA TELXNOSTI \TA FUNKCIQ WYPUKLA PO x ZNA^IT x QWLQETSQ TO^KOJ EE MINIMUMA SM UTWERVDENIE x oTS@DA I IZ USLOWIQ DOPOLNQ@ ]EJ NEVESTKOSTI POLU^IM ^TO f x f x h; g x i L x ; : L x; f x h;g x i f x 8x 2 X IBO gj x DLQ x UDOWLE TWORQ@]IH OGRANI^ENIQM ^TO I TREBUETSQ W OPREDELENII aNALOGI^NYE TEOREMAM UTWERVDENIQ SPRAWEDLIWY I DLQ SLU ^AQ KOGDA X ZADAETSQ OGRANI^ENIQMI RAWENSTWAMI I DLQ SME[AN NYH SISTEM OGRANI^ENIJ RAWENSTW I NERAWENSTW gj x ; gi x tOLXKO NA SOOTWETSTWU@]IE OGRANI^ENIQM RAWENSTWAM MNOVITELI lAGRANVA i NE NADO NAKLADYWATX USLOWIQ NEOTRICATELXNOSTI A NA USLOWIE DOPOLNQ@]EJ NEVESTKOSTI \TI OGRANI^ENIQ NE WLIQ@T W SLU^AE OGRANI^ENIJ RAWENSTW WOOB]E OPUSKAEM I PRIHODIM K KLASSI^ESKOMU PRAWILU MNOVITELEJ lAGRANVA 2. tEPERX WSPOMNIM ^TO POLU^ENNYE USLOWIQ QWLQ@TSQ ZNA^IMY MI LI[X W PREDPOLOVENII REGULQRNOSTI OGRANI^ENIJ DLQ KOTOROGO OPREDELENIE NE DAET KONSTRUKTIWNOGO SPOSOBA PROWERKI w DANNOM .
,
.
2
-
(1),(3)
0,
:
,
) = 0
(
(6).
(1),(3)
-
,
(
(
),
).
(1),(3)
)
(
-
|
,
0.
-
,
.
(
).
,
(
.
2
,
(
) =
(
)+
(
8).
(
)
(
-
,
-
) =
(
)
)+
(
(
(
)
)
=
0
(
)
,
),
-
(2).
2{4
-
,
-
,
:
(
-
)
0
(
) = 0.
-
,
(
-
(6)
).
,
-
,
6
.
49
PUNKTE BUDUT RASSMOTRENY NEKOTORYE DOSTATO^NYE USLOWIQ REGULQR NOSTI OGRANI^ENIJ NERAWENSTW DLQ GLADKIH ZADA^ kROME G x OPREDELENNOGO W P 1 WWEDEM TAKVE MNOVESTWO
-
(3)
(
),
.
.
,
(
)
G0 x : fy 2 Rnj hrgj x ;yi < 8j 2 J x g; (
) =
0
(
)
OTLI^A@]EESQ ZAMENOJ NESTROGOGO NERAWENSTWA STROGIM nO \TO MNO VESTWO UVE WKL@^AETSQ W KONTINGENTNYJ KONUS uTWERVDENIE 5. w PREDPOLOVENII DIFFERENCIRUEMOSTI PO aDAMARU ILI NEPRERYWNOJ DIFFERENCIRUEMOSTI FUNKCIJ gj ZA DA@]IH OGRANI^ENIQ G0 x K X;x 8x 2 X dOKAZATELXSTWO OT PROTIWNOGO pUSTX SU]ESTWUET NAPRAWLE NIE y 2 G0 x NE WHODQ]EE W K X;x T E DLQ L@BOJ POSLEDOWATELX NOSTI FIGURIRU@]EJ W OPREDELENII NAJDETSQ PODPOSLEDOWATELX NOSTX t ;yt ! ;y x t yt 62 X SLEDOWATELXNO 8t 9 INDEKS j TAKOJ ^TO gj x t yt > wOZMOVNYH INDEKSOW KONE^NOE ^ISLO A RAZLI^NYH t BESKONE^NO MNOGO ZNA^IT NAJDETSQ OGRANI^ENIE PUSTX i E KOTOROE NARU[AETSQ BESKONE^NOE ^ISLO RAZ rASSMOTRIM SOOTWET STWU@]U@ PODPOSLEDOWATELXNOSTX ftk g gi x tk ytk > I USTREM LQQ k ! 1 POLU^IM ^TO gi x nO IZ USLOWIQ x 2 X SPRAWEDLIWO OBRATNOE NERAWENSTWO OTKUDA SLEDUET RAWENSTWO T E i 2 J : x oD NAKO DLQ \TOGO i PO OPREDELENI@ BUDEM IMETX hrgi x ;yi .
-
.
(
)
(3),
(
)
(
(
),
(
(
)
,
-
.
).
),
,
-
. .
-
5,
(
)
(+0
(
+
):
)
+
-
,
,
0.
,
|
,
,
,
,
- ,
.
:
,
,
(
)
(
-
+
)
0
,
-
0.
,
,
. .
4
(
(
)
).
-
=
gi x y0 gi x g i x t k y t k gi x : k!1 t k ( ;y !(+0;y ) pRI[LI K PROTIWORE^I@ S y 2 G0 x :
=
(
lim
+
)
(
)
0)
=
(
lim
(
+
)
(
)
0
).
oTS@DA POLU^AEM SLEDU@]EE USLOWIE REGULQRNOSTI
:
G x G0 x : (
) =
(
)
(7)
zDESX I DALEE ^ERTA NAD MNOVESTWOM OBOZNA^AET EGO ZAMYKANIE uTWERVDENIE 6. w SDELANNYH PREDPOLOVENIQH USLOWIE OBES PE^IWAET REGULQRNOSTX X W TO^KE x dLQ DOKAZATELXSTWA DOSTATO^NO ZAMETITX ^TO MNOVESTWO K X;x QWLQETSQ ZAMKNUTYM A WKL@^ENIE G0 x K X;x PRI WODIT K G0 x K X;x POSLE WZQTIQ OPERACII ZAMYKANIQ .
(7)
-
)
-
.
,
(
)
,
(
)
(
(
)
)
(
.
50
uTWERVDENIE 7. dOSTATO^NYM DLQ QWLQETSQ G0 x 6 ;: DLQ ALGEBRAI^ESKOJ SUMMY G I G0 SLE dOKAZATELXSTWO . iZ 0 0 DUET G G G T E G G0 G0 A G0 DAET G G0 G i IZ LINEJNOSTI OPERATORA ZAMYKANIQ I ZAMKNUTOSTI G POLU^AEM dLQ WYPUKLYH X WYPOLNENIE I SLEDOWATELXNO REGULQRNOSTX W L@BOJ TO^KE OGRANI^ENIJ GARANTIRUETSQ USLOWIEM sL\JTERA 9x0 2 X gi x0 < 8i 2 M lINEJNYE OGRANI^ENIQ WSEGDA REGULQRNY MNOVESTWO G SOWPADAET S KONTINGENTNYM KONUSOM HOTQ (7)
(
) =
(8)
(8)
:
+
,
. .
-
+
0
,
+
.
(7).
(8)
(
)
(
:
,
,
(3)
(
)
0
).
(
),
USLOWIE sL\JTERA ILI DLQ NIH MOVET NE WYPOLNQTXSQ dRUGIE TIPY USLOWIJ REGULQRNOSTI A TAKVE USLOWIQ REGULQR NOSTI DLQ SME[ANNYH SISTEM OGRANI^ENIJ RAWENSTW I NERAWENSTW SM W w ^ASTNOSTI KLASSI^ESKIM USLOWIEM REGULQRNOSTI DLQ OGRANI^ENIJ RAWENSTW QWLQETSQ LINEJNAQ NEZAWISIMOSTX GRADIENTOW OGRANI^ENIJ W \KSTREMALXNOJ TO^KE (8)
.
,
.
[4{6].
-
,
-
.
upravnenie 8. pOLU^ITX TEOREMU DWOJSTWENNOSTI lp KAK SLEDSTWIE TEOREMY kUNA-tAKKERA DLQ SLU^AQ OZlp (
).
uSLOWIQ OPTIMALXNOSTI SLUVAT OSNOWNYM INSTRUMENTOM TEORE TI^ESKOGO ISSLEDOWANIQ ZADA^ USLOWNOJ OPTIMIZACII ~TOBY ^ISLEN NO PRIBLIVENNO NAJTI USLOWNYJ \KSTREMUM S IH POMO]X@ PRIME NQ@T METODY BEZUSLOWNOJ OPTIMIZACII DLQ POISKA SEDLOWOJ TO^KI FUNKCII lAGRANVA ILI KOMBINIRU@T [TRAFNU@ FUNKCI@ S FUNK CIEJ lAGRANVA DLQ POLU^ENIQ TO^NOGO GLADKOGO [TRAFA k SOVA LENI@ WSE \TI METODY OSTANAWLIWA@TSQ W PERWOM POPAW[EMSQ LO KALXNOM \KSTREMUME gLOBALXNYJ OPTIMUM MOVNO ISKATX PEREBI RAQ LOKALXNYE OPTIMUMY NO DLQ ZADA^ NEODNOMERNOJ MINIMIZACII NE PONQTNO KAK NAHODITX WSE LOKALXNYE OPTIMUMY nEKOTORYE IZ SU]ESTWU@]IH PODHODOW K RE[ENI@ ZADA^ GLOBALXNOJ OPTIMIZACII PRIWODQTSQ W SLEDU@]EM PARAGRAFE -
.
(
-
)
,
-
-
.
-
,
-
.
,
,
,
.
.
51
-
4.
sposoby re{eniq perebornyh zada~
lITERATURA: pAPADIMITRIU h., sTAJGLIC k. kOMBINATORNAQ OPTIMIZACIQ. m.: mIR, 1985. 6. mINU m. mATEMATI^ESKOE PROGRAMMIROWANIE. m.: nAUKA, 1990. 2.
x10. gLOBALXNAQ OPTIMIZACIQ. mETOD WETWEJ I GRANIC
sLU^AJNYJ I POSLEDOWATELXNYJ PEREBOR. mETOD WETWEJ I GRANIC W GLOBALXNOJ OPTIMIZACII. oPISANIE I STRATEGII METODA. 1. kAK UVE OTME^ALOSX RANEE, ZADA^I GLOBALXNOJ OPTIMIZACII (T.E. W NEWYPUKLOM SLU^AE ZADA^I OPTIMIZACII WOOB]E) QWLQ@TSQ PEREBORNYMI. pEREBORNYE ALGORITMY NE \FFEKTIWNY (W RAS^ETE NA HUD[U@ ZADA^U), PO\TOMU USPEH W RE[ENII KAVDOJ KONKRETNOJ ZADA^I SU]ESTWENNYM OBRAZOM ZAWISIT OT SPOSOBA ORGANIZACII PEREBORA. eSLI MY GOTOWY OSTAWITX WOZMOVNOSTX ILI NEWOZMOVNOSTX RE[ENIQ NA[EJ ZADA^I NA WOL@ SLU^AQ, TO ESTESTWENNO ISPOLXZOWATX SLU^AJNYJ PEREBOR. |TOT SPOSOB PEREBORA OBY^NO QWLQETSQ SAMYM PROSTYM I, KAK PRAWILO, \KONOMIT PAMQTX. dLQ ZADA^I POISKA GLOBALXNOGO MINIMUMA EMU SOOTWETSTWUET SLEDU@]IJ METOD mONTE-kARLO. pUSTX RE[AETSQ ZADA^A (1) IZ x8, GDE (DLQ UPRO]ENIQ IZLOVENIQ) MNOVESTWO OGRANI^ENIJ X | EDINI^NYJ n-MERNYJ KUB. wYBIRAEM W SOOTWETSTWII S RAWNOMERNYM RASPREDELENIEM NA X SLU^AJNYE TO^KI xt, W KOTORYH WY^ISLQEM ZNA^ENIE CELEWOJ FUNKCII, ZAPOMINAEM TEKU]EE NAIMENX[EE ZNA^ENIE | REKORD | I REALIZU@]U@ EGO TO^KU. tOGDA 8" > 0 WEROQTNOSTX P(j min f (xt ) f j > ") ! 0 PRI t ! 1: t sHODIMOSTX TAKOGO METODA BUDET DOWOLXNO MEDLENNOJ. pRI \TOM NE IZWESTNO, NA KAKOM RASSTOQNII OT TO^KI MINIMUMA NAHODITSQ POLU^ENNAQ REALIZACIQ. sUZIM KLASS RASSMATRIWAEMYH ZADA^ (1), PREDPOLOVIW WDOBAWOK K PREDYDU]EMU, ^TO FUNKCIQ CELI LIP[ICEWA NA X S KONSTANTOJ L: f 2Lip(X;L), T.E. jf (x) f (x0)j Lkx x0k 8x;x0 2 X . i NE RASS^ITYWAQ NAJTI TO^NOE RE[ENIE, ZADADIMSQ PODHODQ]IM " > 0 S 52
CELX@ POISKA " PRIBLIVENNOGO RE[ENIQ x" f x" f x " nA BLIZOSTX x" I x NIKAKIH USLOWIJ NE NAKLADYWAETSQ tEPERX MY MOVEM PRIMENQTX METODY DETERMINIROWANNOGO PERE BORA pASSIWNYJ NE ISPOLXZU@]IJ PRI WYBORE O^EREDNOJ TO^KI INFORMACI@ POLU^ENNU@ DLQ PREDYDU]IH SPOSOB POISKA PRIWO X NA PODKUBY X j TAK ^TOBY DIT K POLNOMU PEREBORU RAZOBXEM : j j 0 0 8x;x 2 X kx x k "=L W KAVDOM X BEREM PROIZWOLXNU@ TO^KU xj I POLAGAEM : -
:
(
)
(
)+
. (
.)
-
.
(
,
)
-
:
,
:
=
,
f x" (
j
) = min
f xj : (
)
o^EWIDNO x" I ESTX ISKOMOE " PRIBLIVENNOE RE[ENIE dEJSTWI TELXNO 8j; 8x 2 X j f x" f xj f x " PO USLOWI@ lIP[ICA I W ^ASTNOSTI DLQ x x IMEEM f x" f x " SOOTWET STWIEpS OPREDELENIEM oDNAKO STORONA KAVDOGO j GO PODKUBA RAWNA "= L n A WSEGO PODKUBOW I SLEDOWATELXNO WY^ISLENIJ ZNA^ENIJ CE LEWOJ FUNKCII BUDET Lpn=" n W L@BOM SLU^AE ^TO NE MYSLIMO DAVE DLQ DESQTKA PEREMENNYH pO\TOMU RAZRABATYWA@TSQ METODY POSLE DOWATELXNOGO PEREBORA POZWOLQ@]IE U^ITYWATX UVE WY^ISLENNYE ZNA^ENIQ I ADAPTIROWATXSQ K NEHUD[EMU SLU^A@ pREDPOLOVIM ^TO UVE WY^ISLENY ZNA^ENIQ FUNKCII W TO^KAH j 1 I REKORDNYM OKAZALOSX ZNA^ENIE f xr R tOGDA ESLI x1;:::;x j f xr < f xr TO OBNOWLQEM REKORD r j; R f xj A ESLI f xj > f x :TO MOVNO NE WY^ISLQTX ZNA^ENIJ FUNKCII NA MNOVESTWE Tj R fx 2 X kx xj k jf xj R =Lg TAKj KAK \TOjNE DASTr NOWO GO REKORDA IBO 8x 2 Tr f x f x Lkx x k f x f x T E f x f xr R I ZNA^IT SREDI NIH NET GLOBALXNO OPTIMALXNOGO RE[ENIQ oBNOWLENIE REKORDA W PRINCIPE POZWOLQET OTBROSITX ANALOGI^NYE MNOVESTWA Ti R DLQ i ;:::;j eSTESTWENNO W Ti ; Tj MOGUT POPASTX I TO^KI xk S UVE WY^ISLEN NYM ZNA^ENIEM f xk KOTORYE TAKIM OBRAZOM WY^ISLQLISX ZRQ pO \TOMU HOTELOSX BY TAK ORGANIZOWATX PEREBOR ^TOBY PO WOZMOVNOSTI UMENX[ITX ^ISLO PODOBNYH ZRQ[NYH WY^ISLENIJ k SOVALENI@ OPTIMALXNOJ STRATEGII ORGANIZACII PEREBORA DLQ MNOGOMERNYH ZA DA^ NET iSPOLXZOWANIE SLU^AJNYH TO^EK xi PRIWODIT K PROBLEME HRANENIQ I OBNOWLENIQ SLOVNOGO MNOVESTWA [Ti R ZAWEDOMO NE OPTI MALXNYH TO^EK mETOD POSLOJNOGO PEREBORA DAET WOZMOVNOSTX SOKRA ]ENIQ LI[X PO ODNOJ PEREMENNOJ dLQ ZADA^ BOLX[OJ RAZMERNOSTI ,
-
,
(
,
,
)
(
)
(
=
(
-
|
-
,
)
(
) +
.)
(
. (
) +
-
),
,
(
,
-
)
,
.
-
,
.
,
(
(
)
(
),
(
(
),
:=
) =
:
(
(
(
)
(
(
) =
,
(
)
)
)
(
:=
) =
(
.
,
),
(
,
-
)
(
,
)
(
),
. .
-
).
\
(
)
)
= 1
"
1.
,
-
(
) (
).
-
,
\
"
.
,
-
.
(
.
)
-
-
.
53
PREDLAGAETSQ RAZLI^NYMI AWTORAMI SLEDU@]IJ METOD PEREBORA PO SHEME WETWEJ I GRANIC 2. mETOD WETWEJ I GRANIC (mwg) DLQ GLOBALXNOJ MINIMIZACII pUSTX x1 CENTR KUBA X wY^ISLQEM f x1 I PRISWAIWAEM \TO ZNA ^ENIE REKORDU R f x1 rAZBIWAEM KUB NA n ODINAKOWYH POD KUBOW X 1i SO STORONOJ I WY^ISLQEM ZNA^ENIQ CELEWOJ FUNKCII W IH CENTRAH f x1i ; i ;:::;1i n OBNOWLQQ PO HODU WY^ISLENIJ ZNA^ENIE REKORDA R i f x pROWERQEM WYPOLNENIE USLOWIQ X 1i T1i R DLQ i ;:::; n I OTBRASYWAEMnSOOTWETSTWU@]IE POD KUBY kAVDYJ IZ OSTAW[IHSQ RAZBIWAEM NA ODINAKOWYH PODKUBOW [AGE U NAS X 2ij SO STORONOJ I POSTUPAEM KAK PREVDE nA L@BOM FORMIRUETSQ MNOVESTWO K KUBIKOW SO STORONAMI l ; l CELOE pRAWILO WYBORA O^EREDNOGO KUBIKA DLQ RAZBIENIQ NAZYWAETSQ PRAWIWARIANTY PRIWODQTSQ NIVE kUBIKI SO LOM WETWLENIQ WOZMOVNYE STORONOJ NE BOLX[E "= Lpn ISKL@^A@TSQ IZ MNOVESTWA K DRO BLENIE KUBIKA ZAKAN^IWAETSQ tAKVE ISKL@^A@TSQ KUBIKI POPAW[IE W MNOVESTWO Tk R S INDEKSOM k NOMEROM KUBIKA DLQ TEKU]EGO ZNA^ENIQ REKORDA PRAWILO OTSE^ENIQ WETWEJ rEKORD OBNOWLQ ETSQ PRI POLU^ENII MENX[EGO ZNA^ENIQ CELEWOJ FUNKCII PRAWILO POLU^ENIQ GRANIC, T.E. OCENOK zNA^ENIQ CELEWOJ FUNKCII WY^I SLQ@TSQ W CENTRE KAVDOGO NOWOGO PODKUBIKA WKL@^AEMOGO W K POSLE RAZBIENIQ WYBRANNOGO DLQ \TOGO KUBIKA aLGORITM OSTANAWLIWAETSQ KOGDA K PUSTO uKAZANNAQ TERMINOLOGIQ I NAZWANIE METODA OPREDELQ@TSQ TEM ^TO WIZUALXNO DANNAQ SHEMA PEREBORA PREDSTAWLQETSQ W WIDE GRAFA DEREWA KORNEWAQ WER[INA KOTOROGO SOOTWETSTWUET KUBU X WER[I NY PERWOGO QRUSA PODKUBAM X 1i WER[INY WTOROGO QRUSA KUBI KAM X 2ij PODSOEDINENNYM K SWOIM POROVDA@]IM WER[INAM X 1i GO QRUSA I T D eSLI KUBIK ISKL@^AETSQ IZ K EGO WER[INA ZAKRYWAETSQ IZ NEE NE BUDUT IDTI WETWI NA SLEDU@]IJ QRUS eSLI KUBIK E]E NE WKL@^EN W K EGO WER[INA E]E NE RASKRYTA pORQDOK ZAKRYTIQ WER[INY OPREDELQETSQ PRAWILOM OTSE^ENIQ SWOIM DLQ KAVDOJ MAS SOWOJ ZADA^I SM TAKVE W x PORQDOK RASKRYTIQ PRAWILOM WE TWLENIQ SWOIM DLQ KAVDOJ INDIWIDUALXNOJ ZADA^I rAZLI^A@T DWA WIDA PRAWIL WETWLENIQ PO TIPU POSTROENIQ DEREWA RE[ENIJ WYBORA WER[IN DLQ RASKRYTIQ W [IRINU KOGDA SNA^ALA RASKRYWA@TSQ (
)
.
.
|
.
:=
(
(
)
-
).
2
-
1/2
:
(
)
= 1
:= min
(
)
= 1
2 ,
(
).
2
-
.
2
1/4
,
.
\
"
2
2,
|
.
(
)
|
.
(
.
-
,
) (
|
)
, |
.
-
(
).
-
,
.
,
.
,
-
,
,
|
,
-
|
,
,
-
1-
. .
,
|
.
,
.
(
|
.
-
11),
|
(
-
).
(
): \
",
54
WSE WER[INY ODNOGO QRUSA DO PEREHODA K SLEDU@]EMU I W GLUBINU WSQKIJ RAZ RASKRYWAETSQ LI[X ODNA OBY^NO S LU^[IM ZNA^ENIEM REKORDA WER[INA NA QRUSE DO KONCA WETWI nA PRAKTIKE REALIZU@T NEKOTORU@ SMESX NAPRIMER PERWOE PRAWILO POKA HWATAET MA[INNOJ PAMQTI W K NE SLI[KOM MNOGO \LEMENTOW ZATEM PEREKL@^AEMSQ NA WTOROE pREDPO^TITELXNOSTX TOJ ILI INOJ STRATEGII WETWLENIQ OCE NIWAETSQ KAVDYM WY^ISLITELEM PO SWOEMU ISHODQ IZ GLAWNOJ ZADA^I METODA WETWEJ I GRANIC BYSTREE POLU^ITX LU^[IJ REKORD ^TOBY OTSE^X BOLX[E WETWEJ w RASSMATRIWAEMOJ ZADA^E ESTX HORO[IJ SPOSOB ULU^[ENIQ RE KORDA LOKALXNAQ OPTIMIZACIQ SM W x eE IMEET SMYSL PROWO DITX IZ TEKU]EJ TO^KI W KOTOROJ PROIZO[LO OBNOWLENIE REKORDA NAPRIMER DELAQ NESKOLXKO [AGOW GRADIENTNOGO METODA pRI \TOM RASPOLOVENIE KUBIKOW MENQTX NE NADO PROSTO UWELI^IWAETSQ [ANS SOKRA]ENIQ PEREBORA OTBRASYWANIQ BOLX[IH KUBIKOW oTMETIM ^TO W HUD[EM SLU^AE f const [Ti ; NE UDAET SQ OTBROSITX NI ODNOJ TO^KI x I PRIHODIM K POLNOMU PEREBORU T E UKAZANNAQ W P \KSPONENCIALXNAQ OCENKA TO^NA NA KLASSE WSEH LIP[ICEWYH FUNKCIJ ,
|
\
"
(
)
.
,
,
,
(
),
.
-
-
,
|
,
.
-
|
(
.
8).
-
,
,
,
.
,
(
,
=
).
(
=
) |
|
. .
;
.1
.
x11. cELO^ISLENNOE LINEJNOE PROGRAMMIROWANIE (clp)
oTLI^IE ZADA^ clp I lp: SU]ESTWENNAQ NELINEJNOSTX OGRANI^ENIJ TIPA CELO^ISLENNOSTI. nE\FFEKTIWNOSTX OKRUGLENIQ RE[ENIQ lp DO BLIVAJ[EGO CELOGO. sLU^AJ WPOLNE UNIMODULQRNOJ MATRICY OGRANI^ENIJ. mwg W clp. mwg DLQ BULEWA LINEJNOGO PROGRAMMIROWANIQ (blp). 1. pO-WIDIMOMU, NAIBOLEE WAVNYM KLASSOM ZADA^ GLOBALXNOJ OPTIMIZACII QWLQ@TSQ ZADA^I clp. |TI ZADA^I FORMULIRU@TSQ KAK ZADA^I lp S DOPOLNITELXNYM OGRANI^ENIEM CELO^ISLENNOSTI PEREMENNYH. pOSLEDNEE OGRANI^ENIE, KAKIMI BY SPOSOBAMI OT NEGO NI IZBAWLQTXSQ, \PORTIT" SWOJSTWO WYPUKLOSTI (I POLINOMIALXNOSTI) ZADA^I lp. nAPRIMER, WYRAZIW USLOWIE CELO^ISLENNOSTI W FORME OGRANI^ENIJ NERAWENSTW, RASSMOTRENNOJ W DOKAZATELXSTWE UTWERVDENIQ 1 x8, I SNQW IH METODOM [TRAFOW, PRIDEM K ZADA^E GLOBALXNOJ OPTIMIZACII, IME@]EJ NE MENX[E LOKALXNYH \KSTREMUMOW, ^EM WARIANTOW DLQ CELO^ISLENNYH PEREMENNYH W ISHODNOJ clp. pO\TOMU 55
NA PRAKTIKE UDAETSQ RE[ATX ZADA^I clp TOLXKO NEBOLX[OJ RAZMER NOSTI ILI S OGRANI^ENIQMI CELO^ISLENNOSTI NE NA WSE A LI[X NA NESKOLXKO PEREMENNYH sU]ESTWUET ^ASTNYJ KLASS ZADA^ clp W KOTORYH OGRANI^ENIE CELO^ISLENNOSTI OKAZYWAETSQ NESU]ESTWENNYM oPREDELENIE 1. mATRICA NAZYWAETSQ WPOLNE UNIMODULQRNOJ ESLI OPREDELITELX L@BOJ EE NEWYROVDENNOJ KWADRATNOJ PODMATRICY RAWEN PO MODUL@ uTWERVDENIE 1. eSLI MATRICA OGRANI^ENIJ RAZRE[IMOJ ZADA ^I lp S CELYMI KO\FFICIENTAMI WPOLNE UNIMODULQRNA TO U NEE SU]ESTWUET CELO^ISLENNOE RE[ENIE dOKAZATELXSTWO O^EWIDNO IZ PRINCIPA GRANI^NYH RE[ENIJ x I PRAWILA kRAMERA SM DOKAZATELXSTWO TEOREMY x uTWERVDENIE 2. mATRICA A WPOLNE UNIMODULQRNA TOGDA I TOLX KO TOGDA KOGDA DLQ L@BOGO CELO^ISLENNOGO WEKTORA b WSE WER[INY MNOGOGRANNIKA Ax b; x QWLQ@TSQ CELO^ISLENNYMI dOKAZATELXSTWO W ODNU STORONU ANALOGI^NO PREDYDU]EMU W DRUGU@ STORONU SM SSYLKU W S tAKIM OBRAZOM WPOLNE UNIMODULQRNYMI MATRICAMI OGRANI^E NIJ W PRINCIPE OGRANI^IWAETSQ KLASS ZADA^ clp \KWIWALENTNYH lp I SLEDOWATELXNO DOPUSKA@]IH \FFEKTIWNOE RE[ENIE oTMETIM ^TO UKAZANNYJ KLASS HOTQ I ^REZWY^AJNO UZOK S FORMALXNOJ TO^KI ZRENIQ \LEMENTAMI MATRICY A MOGUT BYTX TOLXKO I PRI^EM PO BOLX[EJ ^ASTI SOOTWETSTWUET DOSTATO^NO [IROKOMU KLASSU PRAKTI^ESKIH ZADA^ OPTIMIZACII NA GRAFAH I SETQH ODNO I DWUH PRODUKTOWYE SETI DWUDOLXNYE GRAFY I T P pRIWEDEM BEZ DOKAZATELXSTWA E]E ODNO POLEZNOE UTWERVDENIE PO ZWOLQ@]EE W NEKOTORYH SLU^AQH POLU^ATX PRIBLIVENNOE RE[ENIE clp PUTEM RE[ENIQ lp uTWERVDENIE 3. eSLI WSE \LEMENTY SIMPLEKS TABLICY aij ; bi; cj NATURALXNYE ^ISLA TO DLQ L@BOGO RE[ENIQ x0 ZADA^I lp -
,
.
,
.
,
1.
-
,
.
( 5)
(
.
1
5).
-
,
0
.
,
.
[2,
. 333].
,
-
,
,
,
.
,
,
(
0, 1
-1,
0),
(
,
-
-
. .).
,
-
.
-
,
hc;xi
Axb; x0 max
WEKTOR bx0 c SOSTAWLENNYJ IZ KOMPONENT bx0j c BUDET DOPUSTIMYM W DANNOJ ZADA^E pRI \TOM DLQ RE[ENIQ x SOOTWETSTWU@]EJ ZADA^I ,
,
.
56
clp
Axmax b; x2Zn+ hc;xi
O^EWIDNA OCENKA jhc; bx0 ci hc;x ij hc; i uSLOWIE POLOVITELXNOSTI ISHODNYH DANNYH WYPOLNQETSQ DLQ NE KOTORYH \KONOMI^ESKIH ZADA^ tAKOJ VE REZULXTAT MOVNO POLU^ITX DLQ RQDA MNOGOPRODUKTOWYH POTOKOWYH ZADA^ NA SETQH I DRUGIH LI NEJNYH ZADA^ MAKSIMIZACII S POLOVITELXNYM c W KOTORYH DOPUSTI MOE MNOVESTWO WMESTE S L@BOJ TO^KOJ x SODERVIT I WSE x0 S KOMPO NENTAMI x0j 2 ;xj oDNAKO POISK x PO bx0 c MOVET POTREBOWATX PEREBORA n WARIANTOW OKRUGLENIQ KOMPONENT x0 k SOVALENI@ W OB]EM SLU^AE I PEREBORA WSEH WOZMOVNYH WARI ANTOW OKRUGLENIQ KOMPONENT RE[ENIQ NEPRERYWNOJ ZADA^I lp OKA ZYWAETSQ NEDOSTATO^NO DLQ POLU^ENIQ RE[ENIQ clp NAPRIMER PRI n ESLI DLQ POLOVITELXNOGO c RASSMOTRETX SISTEMU OGRANI^ENIJ x1 x2 ; x1 x2 tAKIM OBRAZOM POISK RE[ENIQ clp MOVET POTREBOWATX O^ENX BOLX[OGO PEREBORA CELO^ISLENNYH TO^EK I WOZNIKAET TA VE ^TO I W x ZADA^A ORGANIZACII PEREBORA S CELX@ POPYTATXSQ EGO SOKRATITX W SLU^AE NE SAMOJ PLOHOJ ZADA^I oDNIM IZ DOSTATO^NO UPOTREBITELXNYH METODOW PEREBORA ZDESX QWLQ ETSQ METOD WETWEJ I GRANIC KOTORYJ DLQ clp BUDET RASSMOTREN W P dRUGIE METODY SM W 2. mETOD WETWEJ I GRANIC DLQ clp rASSMATRIWAETSQ ZADA^A 1 .
-
.
-
,
-
-
[0
].
2
.
,
-
-
(
,
= 2,
9
+ 10
0
8
+ 10
,
1).
,
,
10,
.
-
,
.2.
.
[2,6].
.
n : Azbhc;z i; z2Zmax
(1)
RE[ENIEM KOTOROJ QWLQETSQ CELO^ISLENNYJ WEKTOR z w KORNEWOJ WER[INE METODA WMESTO ZADA^I RE[AETSQ OZlp .
(1)
n : Axbhc;xi; x2Rmax
(2)
RE[ENIEM KOTOROJ QWLQETSQ WEKTOR x0 eSLI x0 OKAZALSQ CELO^ISLEN NYM TO z x0 RE[ENIE ZADA^I ZAKON^ENO iNA^E 9x0j 62 Z I OSU]ESTWLQEM WETWLENIE PO j J KOMPONENTE SLEDU@]IM OBRAZOM iZ WER[INY WYHODQT DWE WETWI I NA NOWOM QRUSE K OGRANI^ENIQM OZlp RE[AEMOJ W POROVDA@]EJ WER[INE DOBAWLQETSQ OGRANI^ENIE .
,
:=
|
-
(1)
.
-
.
,
,
,
57
xj bx0j c DLQ J WETWI ILI xj dx0j e DLQ J WETWI zNA^ENIE 1-
2-
.
MAKSIMUMA W ISHODNOJ ZADA^E clp O^EWIDNO RAWNO MAKSIMALX NOMU IZ ZNA^ENIJ PODZADA^ clp NA KAVDOJ WETWI nO KAK I RANEE WMESTO PODZADA^I clp RASSMATRIWAETSQ PODZADA^A BEZ OGRANI^ENIQ CELO^ISLENNOSTI tAKAQ OZlp I RE[AETSQ W O^EREDNOJ POROVDENNOJ WER[INE W SLU^AE EE RASKRYTIQ OBOZNA^IM RE[ENIE ^EREZ xk eSLI xk CELO^ISLENNOE TO WER[INA ZAKRYWAETSQ A ZNA^ENIE hc;xk i FUNKCII CELI SRAWNIWAETSQ S REKORDOM DLQ EGO OBNOWLENIQ ILI PO PERWOMU RAZU PRISWAIWAETSQ REKORDU I TO^KA xk DOPU STIMAQ TO^KA W ZADA^E ZAPOMINAETSQ pOSLE POLU^ENIQ REKORDA MOVET BYTX ZAKRYTA L@BAQ RASKRYTAQ WER[INA DLQ KOTOROJ OPTI MALXNOE ZNA^ENIE CELEWOJ FUNKCII OKAVETSQ MENX[E REKORDA dEJ STWITELXNO POSKOLXKU MAKSIMUM PO BOLX[EMU MNOVESTWU NE MENX[E MAKSIMUMA PO MENX[EMU TO ZNA^ENIE OZlp DAET OCENKU SWERHU GRANICU ZNA^ENIQ SOOTWETSTWU@]EJ CELO^ISLENNOJ PODZADA^I I KOGDA WERHNQQ OCENKA NE PREWY[AET REKORDA BESSMYSLENNO PYTATXSQ UWE LI^ITX REKORD NA DANNOJ WETWI dRUGIM SLU^AEM ZAKRYTIQ WER[INY OTSE^ENIQ WETWI QWLQETSQ NERAZRE[IMOSTX POSTAWLENNOJ OZlp I SLEDOWATELXNO TOJ VE PODZA DA^I clp eSLI xk NECELO^ISLENNOE TO 9xki 62 Z I OSU]ESTWLQEM WE TWLENIE PO i J KOMPONENTE OPISANNYM WY[E SPOSOBOM pROCEDURA ZAKAN^IWAETSQ POSLE ZAKRYTIQ WSEH WER[IN TOGDA ZNA^ENIE RAW NO TEKU]EMU REKORDU LIBO REKORD OSTALSQ NEOPREDELENNYM I ZADA^A NE IMEET RE[ENIQ wYBOR STRATEGII WETWLENIQ W clp IGRAET NE MENX[U@ ROLX ^EM W GLOBALXNOJ OPTIMIZACII oTSUTSTWIE REKORDA PRIWODIT K LI[ NEMU PEREBORU NO PROCEDURA WETWLENIQ W GLUBINU MOVET WMESTO REKORDA DATX NESOWMESTNU@ SISTEMU OGRANI^ENIJ kROME TOGO DLQ NESKOLXKIH NECELYH KOMPONENT xk NE PONQTNO PO KAKOJ IZ NIH LU^ [E OSU]ESTWLQTX WETWLENIE PO NOWOJ KOTORAQ NE RASSMATRIWALASX NA PREDYDU]IH QRUSAH ILI SNA^ALA PEREBRATX WSE DOPUSTIMYE CE LYE ZNA^ENIQ ODNOJ IZ KOMPONENT PO ANALOGII S blp SM NIVE pOSLEDNQQ STRATEGIQ IMEET SMYSL PRI NALI^II DWUSTORONNIH OGRA NI^ENIJ NA PEREMENNYE 3. mETOD WETWEJ I GRANIC DLQ blp ~ASTNYM SLU^AEM ZADA^I (1),
,
-
.
,
,
.
,
|
.
,
,
,
,
,
(1) |
|
-
.
,
-
.
-
,
,
(
)
,
,
-
.
(
)
,
,
-
.
|
,
,
-
-
.
,
(1)
-
,
(1)
.
,
.
-
,
\
"
.
,
,
:
-
,
,
-
(
|
.
).
-
.
.
58
(1)
clp QWLQETSQ ZADA^A blp
n : Azbhc;z i; z2Bmax
(3)
RE[ENIE KOTOROJ WEKTOR z0 IZ BULEWA KUBA iZ REZULXTATOW x UTWERVDENIQ WYTEKAET NP TRUDNOSTX blp I SLEDOWATELXNO PRAWOMERNOSTX ISPOLXZOWANIQ PEREBORNYH SHEM DLQ RE[ENIQ w x BUDET POKAZANA SHEMA DINAMI^ESKOGO PRO GRAMMIROWANIQ DLQ blp S NEOTRICATELXNYMI KO\FFICIENTAMI A DLQ PROIZWOLXNYH ZADA^ PRIMENIMA SHEMA PREDYDU]EGO PUNKTA KOTORAQ NESKOLXKO UPRO]AETSQ ZA S^ET DOPOLNITELXNOGO OGRANI^E NIQ zi PREWRA]A@]EGO clp W blp a IMENNO POSLE ZAMENY Zn NA Bn PRI WETWLENII W NOWYE PODZADA^I DOBAWLQETSQ WMESTO OGRANI^ENIJ NERAWENSTW USLOWIE RAWENSTWA DLQ ODNOJ WE TWI ILI DLQ DRUGOJ TOJ PEREMENNOJ PO KOTOROJ OSU]ESTWLQETSQ WETWLENIE tAKIM OBRAZOM UKAZANNAQ PEREMENNAQ STANOWITSQ BULEWOJ WO WSEH NIVNIH QRUSAH T E PO NEJ NE PRIDETSQ WNOWX PROWODITX WE TWLENIE A ZNA^IT NA n M QRUSE RE[ENIE BUDET ZAKON^ENO ~ISLO RASKRYWAEMYH WER[IN ILI RE[ENIJ PODZADA^ lp PRI \TOM NE PRE WYSIT n+1 ^TO KONE^NO TOVE NEMALO NO ZAMETNO MENX[E ^EM DLQ clp SRAWNIMO SO SLU^AEM PREDUSMOTRENNYM UTWERVDENIEM |
.
2 (
,
8)
-
,
(3).
12
-
,
(3)
,
-
0
1,
.
,
,
0 (
)
1 (
)
-
,
.
,
,
,
. .
-
-
(3)
(
2
,
,
.
)
,
(
,
-
,
,
3).
x12. mETOD DINAMI^ESKOGO PROGRAMMIROWANIQ (dp)
tEORETI^ESKIE OSNOWY dp. oB]AQ SHEMA METODA. mETOD dp DLQ blp S NEOTRICATELXNYMI KO\FFICIENTAMI. sWQZX S mwg. 1. e]E ODNOJ TRADICIONNO ISPOLXZUEMOJ SHEMOJ PEREBORA QWLQETSQ METOD DINAMI^ESKOGO PROGRAMMIROWANIQ (dp). oDIN PRIMER ALGORITMA dp PRIWODILSQ W x4, GDE \TOD METOD POZWOLIL POSTROITX PSEWDOPOLINOMIALXNYJ ALGORITM RE[ENIQ ZADA^I O R@KZAKE. wOOB]E GOWORQ, PODOBNYE ALGORITMY I NADE@TSQ POLU^ITX PUTEM PRIMENENIQ SHEMY dp. oDNAKO dp MOVNO ISPOLXZOWATX NE DLQ PROIZWOLXNYH OPTIMIZACIONNYH ZADA^. kLASS PODHODQ]IH ZADA^ OPI[EM DALEE. oPREDELENIE 2. fUNKCIQ f NAZYWAETSQ RAZDELQEMOJ NA f1 I f2, ESLI ONA PREDSTAWIMA W WIDE
f x;y (
) =
f1 x;f2 y : (
59
( ))
(4)
oPREDELENIE 3. fUNKCIQ f NAZYWAETSQ RAZLOVIMOJ NA f1 I f2 ESLI ONA RAZDELQEMA NA f1 f2 I FUNKCIQ f1 MONOTONNO NE UBYWAET PO POSLEDNEMU ARGUMENTU tEOREMA 1 (OPTIMALXNOSTI DLQ RAZLOVIMYH FUNKCIJ)
,
,
.
.
x f1 (x; min y f2 (y)); x;y) f (x;y) = min
min
(
I TO^NO TAK VE DLQ
max.
dOKAZATELXSTWO PROWEDEM DLQ SLU^AQ MINIMUMA
.
rAWENSTWO BUDET WYTEKATX IZ PARY PROTIWOPOLOVNYH NERAWENSTW pO OPREDELENI@ MINIMUMA x;y f1 x;f2 y f1 x0 ;f2 y0 8x0 ;y0
(
.)
min
(
( ))
(
(
))
0 0 I; SLEDOWATELXNO; DLQ y0 y f2 y ; x x f1 x;f2 y ; ^TO DOKAZYWAET NERAWENSTWO aNALOGI^NO W SILU NEUBYWANIQ f1 PO POSLEDNEMU ARGUMENTU f1 x0 ; y f2 y f1 x0 ;f2 y0 8x0 ;y0 : 0 0 pOLOVIM y0 y f1 x ;f2 y ; x x f y f1 x;f2 y g: := arg min
\
,
:= arg min
( )
:= arg min
".
(
(
(
(
))
,
min
( ))
( ))
(
(
:= arg min min
))
(
( ))
pOSKOLXKU POWTORNYJ RAWEN DWOJNOMU W PRAWOJ ^ASTI POLU^ILI x;y f x;y ^EM DOKAZALI I NERAWENSTWO dLQ ZADA^I USLOWNOJ OPTIMIZACII TEOREMA OPTIMALXNOSTI DLQ RAZLOVIMYH FUNKCIJ PEREPISYWAETSQ SLEDU@]IM OBRAZOM min
min
(
,
),
\
".
:
(
min f (x;y ) = f (x; min f (y)); 6 ; 1 y2Y (x) 2 x;y x: Ymin )2
(x)=
(5)
GDE Y x fyj x;y 2 g uKAZANNAQ TEOREMA ISPOLXZUETSQ DLQ PONIVENIQ RAZMERNOSTI OPTIMIZACIONNYH ZADA^ I W METODE dp dLQ NA^ALA RASSMOTRIM ZADA^U OPTIMIZACII ZAPISANNU@ W WIDE (
) =
(
)
.
.
,
f g(x;y)2ET Rm f x;y ; x 2 X Rn; y 2 Y x Rk: =
min
(
)
(
)
(6)
zDESX ET NAZYWAETSQ MNOVESTWOM TERMINALXNYH SOSTOQNIJ SISTEMY PO ASSOCIACII S DINAMI^ESKIMI SISTEMAMI UPRAWLENIQ DLQ OPTIMI ZACII KOTORYH BYLO IZOBRETENO dp nAPRIMER DLQ g g1 ;:::;gm ,
.
60
,
= (
-
),
ESLI OGRANI^ENIQ ZADA^I ZADANY W FORME gi x;y ET Rm pUSTX f RAZLOVIMA A g RAZDELQEMA (
=
.
)
(4),
0
:
8i ;m = 1
TO
,
h2 y;h1 x ; h1 Rn ! Rm; h2 Rk+m ! Rm; TOGDA WWEDEM 8x;y E h1 x ; E 0 h2 y;E I WY^ISLQEM g KAK g x;y E 00 fUNKCII h1; h2 NAZYWA@TSQ FUNKCIQMI PEREHODA WEK TORY E; E SOSTOQNIQMI SISTEMY mNOVESTWO WSEH WOZMOVNYH SOSTOQNIJ SISTEMY OBOZNA^AETSQ E I FORMALXNO ZADAETSQ TAK E h 1 X : f h1 x j x 2 X g 8E 2 h1 X fh2 y;E jy 2 Y X g E g x;y (
) =
(
(
))
=
(
) =
:
(
:
)
=
(
)
.
,
|
-
.
:
1)
2)
(
) = (
(
)
)
(
,
)
(
)
MNOVESTWO W KA^ESTWE ARGUMENTA OZNA^AET OB_EDINENIE PO WSEM AR GUMENTAM IZ \TOGO MNOVESTWA rASSMOTRIM DLQ SEMEJSTWO ZADA^ POISKA (
-
).
(6)
F2 E (
) =
f2(y); y: h2 min (y;E )2ET
KOTORYE NUVNO RE[ATX 8E 2 E pO TEOREME OPTIMALXNOSTI .
f x2X f1 x;F2 h1 x : = min
(
(
(
)))
w REZULXTATE ZADA^A SWELASX K POSLEDOWATELXNOSTI jEj OPTI MIZACIONNYH ZADA^ MENX[EJ RAZMERNOSTI w METODE dp DANNAQ PROCEDURA PRIMENQETSQ REKURSIWNO K ZADA^E (6)
+ 1
-
.
F g(x ;:::;xn)2ET Rm f x1;:::;xn =
1
min
(
)
(7)
DLQ SWEDENIQ K SEMEJSTWU ODNOMERNYH ZADA^ SLEDU@]IM OBRAZOM pUSTX f POSLEDOWATELXNO RAZLOVIMA T E ,
f x1;:::;xn f x2;:::;xn :::::::::::::::::: fn 1 xn 1;xn (
)=
^( 2
^
)=
(
)=
.
. .
f1 x1;f2 x2;:::;xn ; f2 x2;f3 x3;:::;xn ; ::::::::::::::::::::: fn 1 xn 1;fn xn ; (
^(
))
(
^(
))
(
(
))
I WSE fi MONOTONNO NE UBYWA@T PO MU ARGUMENTU pUSTX g POSLEDOWA TELXNO RAZDELQEMA T E 9E Rm ; 9 FUNKCII PEREHODA h1 ;h2 ;:::;hn 2-
,
. .
61
.
:
8x 2 X Xi g x hn xn;En 1 En 1 hn 1 xn 1;En 2 ;::: E2 h2 x2;E1 E1 h1 x1 I Ei 2 E 8i ;n oBOZNA^IM 8i ;n ; 8E 2 E ^EREZ hi xi;xi+1 ;:::;xn;E 0 =
=
(
(
) =
),
=
(
(
),
=
)
= 2
(
= 1
)
,
1.
^ (
1
FUNKCI@ OPREDELQEMU@ REKURRENTNO RAWENSTWAMI Ei :
)
hi xi;E Ei0+1 hi+1 xi+1;Ei0 ; :::;En0 hn xn;En0 1 hi xi;xi+1;:::;xn;E zAMETIM ^TO W SLU^AE E Ei 1 hi xi ;xi+1 ;:::;xn ;Ei 1 g x I Ej0 Ej 8j i w SDELANNYH OBOZNA^ENIQH SPRAWEDLIWO WOZWRATNOE ,
:
=
(
)
=
,
=
=
(
),
)= ^ (
(
:
=
^ (
).
)=
(
)
.
SOOTNO[ENIE DLQ OGRANI^ENIJ
hi xi;xi+1;:::;xn;E hi+1 xi+1;:::;xn;hi xi;E : ^ (
)= ^
(
(
))
(8)
tOGDA PO OPREDELENI@
F x2X : h^ (x ;:::;x ;h (x ))2E f1 x1;f2 x2;:::;xn ; n T =
min
2
^(
(
2
1
I PO TEOREME OPTIMALXNOSTI
))
1
F x 2X f1 x1;F2 h1 x1 ; GDE 8E1 2 E F2 E1 : f2 x2;:::;xn ^ (x ;:::;x ;h (x ))2E (x ;:::;x ): h =
(
min
1
) =
(
min
n
2
2
n
2
(
)))
1
1
^(
(8))
=
min
x ;:::;xn ): h^ 3 (x3 ;:::;xn ;h2 (x2 ;E1 ))2ET
( 2
=
min
2
2
(
(
(5)
(
^(
(
=
= (
) =
^(
min
)) =
1 IMEEM )),
+
Fi E : h^ (x ;x ;:::;x ;E)2E fi xi;xi+1;:::;xn 8i;E i i i n T (
)=
)))
I T D POLAGAQ MINIMUM PO PUSTOMU MNOVESTWU RAWNYM . .,
(9)
T
f2 x2;f3 x3;:::;xn x 2X f2 x2 ;F3 h2 x2 ;E1 POSLEDNEE RAWENSTWO SLEDUET IZ S x x2 ; y x3 ;:::;xn IZ
(
(
(
1
,
)
(10)
+1
|
SEMEJSTWO ZADA^ W KOTOROE POGRUZILI ,
\
" (7),
fi(xi;Fi+1(hi(xi;Ei 1))) 8Ei 1 2 E xmin i 2Xi | WOZWRATNOE (FUNKCIONALXNOE) URAWNENIE dp 8i = 2;n 1, F i Ei (
1) =
Fn E (
) =
fn(xn): xn 2Xn : hmin n (xn ;E )2ET 62
(11)
(12)
aLGORITM dp: 8E 2 E WY^ISLQEM Fn(E) IZ (12), POSLEDOWATELXNO DLQ i = n 1;:::; 2 OPREDELQEM Fi (E ) IZ (11),(10), ZATEM F IZ (9). ~ISLO [AGOW ALGORITMA (RE[ENIJ ZADA^ ODNOMERNOJ MINIMIZACII) BUDET PORQDKA njEj. tAKIM OBRAZOM METOD dp IMEET SMYSL PRIMENQTX DLQ ZADA^ S NE O^ENX BOLX[IM ^ISLOM SOSTOQNIJ (jEj MALO). 2. pRIMERAMI RAZLOVIMYH FUNKCIJ MOGUT SLUVITX min, max, SUMMA, PROIZWEDENIE (S NEOTRICATELXNYMI KO\FFICIENTAMI) I T.P. iSHODNO METOD dp ISPOLXZOWALSQ DLQ OPTIMIZACII DINAMI^ESKIH SISTEM, ^TO NA[LO OTRAVENIE W PRIMENQEMOJ TERMINOLOGII. tAK, E SOOTWETSTWUET FIZI^ESKOMU PROSTRANSTWU SOSTOQNIJ (WOZMOVNYH KOORDINAT TRAEKTORII DWIVENIQ), xi | UPRAWLENI@ W MOMENT WREMENI ti, WOZDEJSTWIE UPRAWLENIQ NA TRAEKTORI@ OPREDELQETSQ FUNKCIEJ PEREHODA W SLEDU@]EE SOSTOQNIE, NA KONE^NOE SOSTOQNIE NALOVENY OGRANI^ENIQ PRINADLEVNOSTI K ET , NA^ALXNOE SOSTOQNIE FIKSIROWANO; fi (xi ;E ) | STOIMOSTX UPRAWLENIQ SISTEMOJ, NAHODQ]EJSQ W SOSTOQNII E , f | STOIMOSTX WSEJ TRAEKTORII E1 ;:::;En 1 . sOOTNO[ENIE (11) OZNA^AET MINIMIZACI@ STOIMOSTI \HWOSTA" TRAEKTORII W KAVDYJ MOMENT WREMENI, ^TO SOGLASUETSQ S PRINCIPOM OPTIMALXNOSTI, SFORMULIROWANNYM r. b\LLMANOM: OPTIMALXNAQ POLITIKA UPRAWLENIQ TAKOWA, ^TO DLQ L@BOGO NA^ALXNOGO SOSTOQNIQ I L@BYH RE[ENIJ (PO WYBORU UPRAWLENIQ), PRINQTYH NA NA^ALXNYH [AGAH, OSTAW[IESQ RE[ENIQ OBRAZU@T OPTIMALXNU@ POLITIKU, NA^INA@]U@SQ S SOSTOQNIQ, WOZNIK[EGO W REZULXTATE \TIH RE[ENIJ. (oTMETIM, ^TO W SLU^AE STROGOJ MONOTONNOSTI f TAKIM OBRAZOM MOVNO POLU^ITX L@BOE RE[ENIE, W SLU^AE NESTROGOJ MONOTONNOSTI | HOTQ BY ODNO). pROILL@STRIRUEM PRIMENENIE METODA dp NA PRIMERE RE[ENIQ ZADA^ blp S NEOTRICATELXNYMI KO\FFICIENTAMI (\LEMENTAMI SIMPLEKS-TABLICY). iTAK, WERNEMSQ K ZADA^E (3)
F z2Bn: Azbhc;zi W PREDPOLOVENII aij ; bi ; cj 2 Z+ oBOZNA^IM ^EREZ aj j J STOLBEC =
max
.
63
-
MATRICY A rASSMOTRIM SEMEJSTWO ZADA^ POISKA .
n X Fk E : z: zj 2f0;1g 8j=k;:::;n cj zj j=k (
) =
max
n X
aj zj b E; j=k GDE E 2 E =: fE 2 Zm+ j Ei bi 8i = 1;mg; k = 1;n. o^EWIDNO F ,
Fk E (
=
F1
wOZWRATNOE URAWNENIE W DANNOM SLU^AE
(0).
:
fFk+1 E ; ck Fk+1 E ak g; cn; E b an; Fn E
) = max
(
)
+
(
+ )
INA^E nAHODIM 8E 2 E Fn E I SOOTWETSTWU@]IE xn E ZATEM DLQ k n ;:::; OPREDELQEM Fk E I REALIZU@]IE IH xk E IZ WOZWRATNOGO URAWNENIQ WY^ISLQEM F1 ; x1 I DALEE x2 E 1 ;:::;xn E n 1 W ZAWISIMOSTI OT TOGO KAKIE SOSTOQNIQ E 1 ;:::;E n 1 BYLI W KONE^NOM S^ETE ISPOLXZOWANY PRI WY^ISLENII F1 ESLI POSMOTRETX PO WSEM [AGAM ALGORITMA ~ISLO [AGOW PREDLOVENNOGO ALGORITMA RAWNO n I NA n M [AGE RASSMATRIWAETSQ f b1 NA ::: bm ; n 1g nSOSTOQNIJ n M MINIMUM IZ LEWOJ ^ASTI RAWNOJ jEj I 2 I T P tAK ^TO PRI BOLX[IH b METOD dp RE[AET PRIMERNO STOLXKO VE ZADA^ SKOLXKO mwg W HUD[EM SLU^AE ODNAKO RE[AEMYE ZADA^I ZDESX PRO ]E PROWERKA OGRANI^ENIJ WMESTO lp pOD^ERKNEM ^TO PROCEDU RA dp NE DAET SPOSOBOW SOKRA]ENIQ PEREBORA TOGDA KAK UDA^NYJ WYBOR STRATEGII WETWLENIQ W mwg NAPRIMER NA OSNOWE IME@]EJ SQ U WY^ISLITELQ DOPOLNITELXNOJ INFORMACII ILI \WRISTI^ESKIH SOOBRAVENIJ POZWOLQET HOTQ I NE GARANTIROWANNO RE[ATX ZADA ^I BOLX[EJ RAZMERNOSTI oTMETIM TAKVE OTSUTSTWIE OGRANI^ENIQ NEOTRICATELXNOSTI KO\FFICIENTOW DLQ RABOTY mwg w PRINCIPE WOZMOVNO KOMBINIROWANIE OBEIH SHEM SM (
(
1
2
) =
0
.
)
(
(
,
)
),
(
(0)
(0)
(
=
)
)
(
)
,
(0),
.
-
min (
(
1)-
+ 1)
(
|
+ 1)
2
(
,
)
2
. .
,
,
-
(
).
,
-
,
(
)
,
(
-
)
-
.
.
(
64
. [6]).
,
sODERVANIE wwedenie w teori` slovnosti
x pONQTIE O SLOVNOSTI RE[ENIQ ZADA^ x POLNYE UNIWERSALXNYE ZADA^I x kLASSY SLOVNOSTI sILXNAQ POLNOTA I PSEWDOPOLINOMIALXNOSTX x pRIBLIVENNOE RE[ENIE ZADA^ KOMBINATORNOJ
1.
1.
2. NP3.
(
3
)
.
10
NP-
15
4.
OPTIMIZACII osnowy linejnogo programmirowaniq x pONQTIE O SLOVNOSTI ZADA^I LINEJNOGO PROGRAMMIROWANIQ lp x mETOD \LLIPSOIDOW x tEORIQ DWOJSTWENNOSTI lp iDEQ METODA kARMARKARA |lementy matemati~eskogo programmirowaniq x oBZOR IDEJ MATEMATI^ESKOGO PROGRAMMIROWANIQ mp x dWOJSTWENNOSTX W mp sposoby re{eniq perebornyh zada~ x gLOBALXNAQ OPTIMIZACIQ mETOD WETWEJ I GRANIC mwg x cELO^ISLENNOE LINEJNOE PROGRAMMIROWANIE clp x mETOD DINAMI^ESKOGO PROGRAMMIROWANIQ dp
21
2.
5.
(
)
6. 7.
.
24 29 33
3.
8.
(
)
9.
38 45
4.
10.
.
(
)
11.
(
12.
(
65
)
)
51 54 58
