<< . .

. 17
( : 19)



. . >>

¦— = ’U 6min " ï®òå°è ®ò åã® ó·à±òèÿ â À‘ â ò®·í®±òè °àâí» ò®© ꮬïåí±àöèèD
6
ê®ò®°óþ öåíò°ó ï°èø«®±ü á» â»ï«à·èâàòü å¬ó íå âê«þ·àÿ â ±®±òàâ À‘F …±«è á»
U min D ò® öåíò° ừ á» á姰৫è·åí ¬å¦¤ó âê«þ·åíèå¬ è íå âê«þ·åíèå¬ â ±®±òàâ
À‘ ïÿò®ã® ÀÝ è ò®·í® íå âê«þ·è« á» øå±ò®© ÀÝF
Ï°å¤ï®«®¦è¬ òåïå°üD ·ò® 4ï«àòà §à ó·à±òèå â À‘4 {U imax } ï®íè§è«à±ü è ±òà«à
°àâíà íó«þD à âå«è·èí» {U imin } ±òà«è °àâí» ò°å¬ å¤èíèöଠ" ±¬F òàá«èöó TF


’àá«èöà 6. ’àá«èöà ê ï°è¬å°ó 11.

Ïà°à¬åò° \ i I P Q R S T
IP IH V T R P
ri
H HHHH H
U imax
Q QQQQ Q
U imin
T SRQP I
¦— i



’®ã¤à ¦i ({1}) = ’9D ¦i ({1}∪{2}) = ’1D ¦i ({1}∪{2}∪{3}) = 6D ¦i ({1}∪{2}∪{3}∪
{4}) = 12D ¦i ({1}∪{2}∪{3}∪{4}∪{5}) = 17D ¦i ({1}∪{2}∪{3}∪{4}∪{5}∪{6}) = 21F
’åïå°ü öåíò°ó â»ã®¤í® âê«þ·àòü â ±®±òàâ À‘ â±å øå±òü ÀÝF•
‚ °à±±¬®ò°åíí®© â»øå ¬®¤å«è ó·èò»âà«à±ü íå®áµ®¤è¬®±òü ®áå±ïå·åíèÿ ó·à±òE
íèêଠÀ‘ è ÀÝD íå âµ®¤ÿùè¬ â åå ±®±òàâD íåê®ò®°®ã® ãà°àíòè°®âàíí®ã® ó°®âíÿ
ﮫå§í®±òèF Îïèøå¬ ¬®¤å«èD â ê®ò®°»µ ÀÝ ãà°àíòè°óåò±ÿ íó«å⮩ ó°®âåíü ﮫå§E
í®±òè @êàê è â ¬®¤å«ÿµD ®ïè±àíí»µ â ïå°â»µ ¤åâÿòè ·à±òÿµ íà±ò®ÿùå© °àá®ò»AD í®
¤®µ®¤ öåíò°à ®ò ï°èâ«å·åíèÿ ¤®ï®«íèòå«üí»µ ÀÝ óá»âàåò @è«è °à±òåò ¬å¤«åííååD
ò® å±òü ï°å¤å«üí»© ï°®¤óêò ò°ó¤à óá»âàåò " ±¬F â»øåA ± °®±ò®¬ ·è±«à ÀÝD ó¦å
â®øå¤øèµ â ±®±òàâ À‘F Á®«åå ê®íê°åòí®D áó¤å¬ ±·èòàòüD ·ò® â nEý«å¬åíòí®© À‘
@n = |I|A ôóíêöèÿ ¤®µ®¤à öåíò°à è¬ååò âè¤

@IHTA H(yI ) = g(n) yi ,
i∈I

ã¤å g(n) " óá»âàþùàÿ ôóíêöèÿ ·è±«à ÀÝ â À‘F

‚ ﮤ®áí»µ ±«ó·àÿµ, íàâå°í®å, öå«å±®®á°à§í® ï°èíÿòü ãèï®òå§ó á«à㮦å«àòå«üí®ã® ®òí®øåíèÿ
7
öåíò°à ê ÀÝ  âê«þ·åíèå ÀÝ â ±®±òàâ À‘ (ò°ó¤®ó±ò°®©±òâ®), ¤à¦å ï°è ®áå±ïå·åíèè å¬ó íó«åâ®ã®
ó°®âíÿ ﮫå§í®±òè, ÿâ«ÿåò±ÿ âà¦í»¬ ¬®òèâè°óþùè¬ ôàêò®°®¬.
IPP
’®ã¤àD â °à¬êൠï°å¤ï®«®¦åíè© ÀFI è ÀFPD ®·åâè¤í®D ±óùå±òâóåò ®ïòè¬à«üí»©
°à§¬å° n— À‘D ê®ò®°»© ¬®¦åò á»òü ®ï°å¤å«åí ¬åò®¤à¬èD ®ïè±»âà嬻¬è íè¦åF
‘®¤å°¦àòå«üí®D íà«è·èå â â»°à¦åíèè @IHTA óá»âàþùå© ï® n ôóíêöèè ¬®¦åò
®áúÿ±íÿòü±ÿ íå®áµ®¤è¬®±òüþ ±®§¤àíèÿ í®â»µ °àá®·èµ ¬å±òD °®±ò®¬ ï®±ò®ÿíí»µ
觤尦åê è òF¤F
Ïó±òü ÀÝ ®¤í®°®¤í»F Çàïèøå¬ öå«åâóþ ôóíêöèþ öåíò°à â âè¤åX

¦(y, n) = ng(n)y ’ nc(y).

‚»·è±«è¬ ®ïòè¬à«üí®å ¤«ÿ öåíò°à °åà«è§óå¬®å ¤å©±òâèå ÀÝX y — = ξ(g(n))D
ã¤å ξ(·) = c ’1 (·) " ôóíêöèÿD ®á°àòíàÿ ï°®è§â®¤í®© ôóíêöèè §àò°àòF Ï®¤±òàâ«ÿÿ
â â»°à¦åíèå ¤«ÿ ¦(y, n) §íà·åíèå y = y— = ξ(g(n))D ﮫó·è¬X


@IHUA ¦(n) = ng(n)ξ(g(n)) ’ nc(ξ(g(n))).

‚»·è±«è¬ ï°®è§â®¤íóþ â»°à¦åíèÿ @IHUAX
d¦(n) dg(n)
@IHVA ’ c(ξ(g(n)).
= ξ(g(n)) g(n) + n
dn dn
…±«è ÀÝ è¬åþò ôóíêöèè §àò°àò òèïà Ê®ááàE„óã«à±àD ò® å±òü c(y) = ± y ± r1’± D
1

ò® ï°è°àâíèâàÿ @IHVA íó«þ è ï°®âå°ÿÿ §íàê âò®°®© ï°®è§â®¤í®©D ﮫó·àå¬D ·ò®
¬àê±è¬è§è°óþùàÿ öå«åâóþ ôóíêöèþ öåíò°à §àâè±è¬®±òü g — (n) ¤®«¦íà ó¤®â«åE
òâ®°ÿòü ±«å¤óþùå¬ó ¤èôôå°åíöèà«üí®¬ó ó°àâíåíèþX
±’1 dg(n)
@IHWA g 1/(±’1) (n) g(n) + n = 0.
± dn
Ðåøåíèå ó°àâíåíèÿ @IHWA ï°è 󱫮âèè g(1) = 1 å±òü

@IIHA g — (n) = n(1’±)/± .

’å®°å¬à 2. …±«è ÀÝ è¬åþò ôóíêöèè §àò°àò òèïà Ê®ááàE„óã«à±àD ò® ï°è
ôóíêöèÿµ g(n)D â±þ¤ó óá»âàþùèµ á»±ò°åå ôóíêöèè g — (n)D ®ï°å¤å«ÿ嬮© @IIHAD
®ïòè¬à«üí»¬ ÿâ«ÿåò±ÿ ¬èíè¬à«üí»© ±®±òàâ À‘ @n— = 1AD ï°è g(n)D â±þ¤ó óá»âàE
þùèµ ¬å¤«åííåå g — (n)D ®ïòè¬à«üí»¬ ÿâ«ÿåò±ÿ ¬àê±è¬à«üí»© ±®±òàâ À‘ @n— = N AD
â ®±òà«üí»µ ±«ó·àÿµ ¬®¦åò ±óùå±òâ®âàòü ï°®¬å¦óò®·í»© ®ïòè¬à«üí»© °à§¬å°
À‘F
Ï°è¬å° 12. Ïó±òü ôóíêöèè §àò°àò ®¤í®°®¤í»µ ÀÝ è¬åþò âè¤X ci (yi ) = yi2 /2rD
ò®ã¤à ÀÝ è¬åþò ôóíêöèè §àò°àò òèïà Ê®ááàE„óã«à±à ± ± = 2F ’®ã¤à ¦(y, n) =
g(n)ny ’ ny 2 /2rF ‚»·è±«ÿÿ ï°è ôèê±è°®âàíí®¬ n ¬àê±è¬ó¬ ¦(y, n) ï® yD ﮫóE
·è¬X ¦— (n) = max{g(n)ny ’ ny 2 /2r} = ng 2 (n)r/2F ‚»·è±«ÿÿ ¬àê±è¬ó¬ ¦— (n) ï®
y∈A
nD ﮫó·àå¬ ¤èôôå°åíöèà«üí®å ó°àâíåíèå ¤«ÿ ôóíêöèè g(n) : g(n) + 2n dg(n) = 0F
dn
Ëåãê® âè¤åòüD ·ò® ®ïòè¬à«üíàÿ §àâè±è¬®±òü ¤®µ®¤à öåíò°à ®ò 4¬à±øòàá®â ï°®è§E
⮤±òâà4 ﮫó·àåò±ÿ ï°è g(n) ≈ 1/n1/2 F …±«è ôóíêöèÿ g(n) â±þ¤ó óá»âàåò ¬å¤«åíE
íååD ·å¬ 1/n1/2 D ò® ®ïòè¬à«üí»¬ ÿâ«ÿåò±ÿ ¬àê±è¬à«üí»© ±®±òàâ À‘D 屫è â±þ¤ó
óá»âàåò á»±ò°ååD ·å¬ 1/n1/2 D ò® ®ïòè¬à«üí»¬ ÿâ«ÿåò±ÿ ¬èíè¬à«üí»© ±®±òàâ À‘D
à â ®±òà«üí»µ ±«ó·àÿµ ¬®¦åò ±óùå±òâ®âàòü ï°®¬å¦óò®·í»© ®ïòè¬à«üí»© °à§¬å°
À‘F
IPQ
Ï®¤±òàâ«ÿÿ â â»°à¦åíèå ¤«ÿ ¦— (n) ê®íê°åòíóþ §àâè±è¬®±òü g(n) = ±/nD ï®E
«ó·àå¬D ·ò® ¬àê±è¬ó¬ öå«å⮩ ôóíêöèè öåíò°à ¤®±òèãàåò±ÿ ï°è n = n— = 1F
…±«è g(n) = 1/n1/4 D ò® n— = N D 屫è g(n) = e’γn D ò® n— = 1/2γD 屫è g(n) = 1+γn2
1


D ò® n— = 3γ è òF¤F•
1

Ðà±±¬®ò°è¬ òåïå°ü §à¤à·ó ô®°¬è°®âàíèÿ ±®±òàâà À‘ â ±«ó·àåD ê®ã¤à öåíò° è±E
ﮫü§óåò óíèôèöè°®âàííóþ ﰮﮰöè®íà«üíóþ ±è±òå¬ó ±òè¬ó«è°®âàíèÿ ±® ±òàâE
ꮩ ®ï«àò» » < 1F8 ’®ã¤à â °à¬êൠï°å¤ï®«®¦åíè© ÀFI è ÀFP ¤å©±òâèÿD â»áè°à嬻å
ÀÝD å±òü yi = ξi (»)D ã¤å ξi (·) = ci’1 (·)D i ∈ IF


–å«åâàÿ ôóíêöèÿ öåíò°àD ï°å¤±òàâ«ÿþùàÿ ±®á®© °à§í®±òü ¬å¦¤ó «èíå©í»¬
¤®µ®¤®¬ @±¬F ï°å¤ï®«®¦åíèå ÀFIFA è §àò°àòà¬è íà ±òè¬ó«è°®âàíèåD è¬ååò ï°è ýò®¬
âè¤X
@IIIA ¦(yI ) = (1 ’ ») ξi (»).
i∈I

Ëåãê® âè¤åòüD ·ò® â °à¬êൠï°å¤ï®«®¦åíèÿ ÀFPD ξi (·) " íåï°å°»âí»å ⮧°àE
±òàþùèå â®ãíóò»å ôóíêöèèD ï®ýò®¬ó @IIIA òàê¦å ÿâ«ÿåò±ÿ â®ãíóò®© ôóíêöå©F
‘«å¤®âàòå«üí®D ¤«ÿ êত®ã® ôèê±è°®âàíí®ã® ±®±òàâà À‘ I ∈ „µ ±óùå±òâóåò å¤èíE
±òâåííàÿ ®ïòè¬à«üíàÿ ± ò®·êè §°åíèÿ öåíò°à ±òàâêà ®ï«àò» »— (I)F „°óãè¬è ±«®E
âà¬èD ®ïòè¬à«üí®© áó¤åò ±«å¤óþùàÿ ±ò°àòåãèÿ öåíò°à " «èá® âê«þ·àòü â ±®±òàâ
À‘ â±å ÀÝD «èá® íèê®ã®F
„«ÿ ò®ã®D ·ò®á» ó©òè ®ò ﮫó·åíí®ã® ò°èâèà«üí®ã® °åøåíèÿD ï°å¤ï®«®¦è¬D
·ò® ó êত®ã® ÀÝ ±óùå±òâóåò ±â®© °å§å°âí»© ó°®âåíü §à°àá®òí®© ï«àò» U i @®òE
¬åòè¬D ·ò® °å·ü è¤åò ® °å§å°âí®© §à°àá®òí®© ï«àòåD à íå ±®®òâåò±òâóþùå© å©
°å§å°âí®© ﮫå§í®±òèAD ò® å±òü ÀÝ ±®ã«àøàåò±ÿ ó·à±òâ®âàòü â À‘D ò®«üê® å±«è
å㮠⮧íàã°à¦¤åíèå ï°åâ»øàåò °å§å°âíóþ ﮫå§í®±òüF ’àêè¬ ®á°à§®¬D 󱫮âèå
ó·à±òèÿ iEã® ÀÝ è¬ååò âè¤X
@IIPA »ξi (») ≥ U i , i ∈ N.
Îᮧíà·è¬ »i " °åøåíèå ó°àâíåíèÿ »ξi (») = U i D i ∈ N D ®òí®±èòå«üí® »D è
óï®°ÿ¤®·è¬ ÀÝ â ï®°ÿ¤êå ⮧°à±òàíèÿ »i F Çíà·åíèå öå«å⮩ ôóíêöèè öåíò°à ï°è
âê«þ·åíèè â À‘ ïå°â»µ k ÀÝ °àâí®X
k
@IIQA ¦(k) = (1 ’ »k ) ξi (»k ), k = 1, N .
i=1

Ðåøåíèå §à¤à·è ±èíòå§à ®ïòè¬à«üí®ã® ±®±òàâà À‘ è¬ååò âè¤X I — = {1, 2, ..., k — }D
ã¤å
@IIRA k — = argmax ¦(k).
k=1,N

Ï°è¬å° 13. Ïó±òü ôóíêöèè §àò°àò ÀÝ è¬åþò âè¤X ci (yi ) = yi2 /2ri D ò®ã¤à
ξi (») = »ri D ¦(yI ) = (1 ’ »)» ri F Ìèíè¬à«üí»å ±òàâêè ®ï«àò»D §à ê®ò®°»å ±®E
i∈I

®òâåò±òâóþùèå ÀÝ ±®ã«à±ÿò±ÿ ó·à±òâ®âàòü â À‘D °àâí» »i = F …±«è è¬ååò±ÿ
Ui
2ri

’àê êàê ôóíêöèÿ ¤®µ®¤à öåíò°à ï°ÿ¬® ﰮﮰöè®íà«üíà ¤å©±òâèÿ¬ ÀÝ, ò® è±ï®«ü§®âàíèå ±òàâ®ê
8
®ï«àò», ᮫üøèµ å¤èíèö», ï°èâå¤åò ê ®ò°èöàòå«üí»¬ §íà·åíèÿ¬ öå«å⮩ ôóíêöèè öåíò°à è åå óá»âà-
íèþ ï® «þỬ ¤®ïó±ò謻¬ ¤å©±òâèÿ¬ ÀÝ.
IPR
â±åã® ïÿòü ÀÝ " ï°åòåí¤åíò®â íà ó·à±òèå â À‘ " ± ïà°à¬åò°à¬èD ï°èâå¤åíí»¬è
â òàá«èöå UD ò® k — = 4D ò® å±òü ®ïòè¬à«üí»¬ ÿâ«ÿåò±ÿ ±®±òàâ À‘D âê«þ·àþùè©
ïå°â»å @â óï®°ÿ¤®·åíèè »i A ·åò»°å ÀÝF•

’àá«èöà 7. ’àá«èöà ê ï°è¬å°ó 13.

Ïà°à¬åò° \ i I P Q R S
I I I I I
ri
HFT HFU HFUS HFV HFW
Ui
HFUU HFVR HFVU HFVW HFWS
»i
HFIURT HFPUQQ HFQRVI HFQUUU HFPRQR
¦(i)

Ï°®âå¤åíí»© àíà«è§ °å§ó«üòàò®â °åøåíèÿ §à¤à· ô®°¬è°®âàíèÿ ±®±òàâà ¬í®E
ã®ý«å¬åíòí»µ À‘ ± ±åïà°àáå«üí»¬è §àò°àòà¬è ÀÝ ï®§â®«ÿåò ±¤å«àòü â»â®¤D ·ò®
â ýò®¬ ê«à±±å ¬®¤å«å© ó¤àåò±ÿ íà ®±í®âàíèè è¬åþù婱ÿ èíô®°¬àöèè óï®°ÿ¤®·èòü
ÀÝD è °åøàòü §à¤à·ó ®ï°å¤å«åíèÿ ®ïòè¬à«üí®© ꮬáèíàöèè ÀÝ íà ¬í®¦å±òâå N
ꮬáèíàöè©D à íå íà ¬í®¦å±òâå â±åµ ⮧¬®¦í»µ 2N ꮬáèíàöè©F
Îòêà¦å¬±ÿ ®ò ï°å¤ï®«®¦åíèÿ ® ±åïà°àáå«üí®±òè §àò°àòD ®±òàâèâ â ±è«å ï°å¤E
ﮫ®¦åíèÿ ÀFI è ÀFPF Çà¤à·à ±èíòå§à ®ïòè¬à«üí®ã® ±®±òàâà À‘ ï°è¬åò âè¤X
@IISA I — = argmax ¦(I),
I∈„µ
ã¤å
@IITA (yi ’ ci (yI ))
¦(I) = max
yI ∈AI
i∈I

ï°è 󱫮âèèD ·ò® ¦(I — ) ≥ 09F
Êàê í室í®ê°àòí® ®ò¬å·à«®±ü â»øåD ï°è °åøåíèè §à¤à·è @IISA ⮧íèêàþò ¤âå
®±í®âí»å ï°®á«å¬»X â»±®êàÿ ⻷豫èòå«üíàÿ ±«®¦í®±òü @᮫üø®å ·è±«® ±®±òàâ®â
À‘D ¤«ÿ ê®ò®°»µ íå®áµ®¤è¬® ⻷豫ÿòü ¬àê±è¬à«üí»å ýôôåêòèâí®±òè óï°àâ«åE
íèÿ è ±°àâíèâàòü èµ ¬å¦¤ó ±®á®©A è íå®áµ®¤è¬®±òü ê®í±ò°óêòèâí®ã® ®ï°å¤å«åíèÿ
§àò°àò ÀÝ â §àâè±è¬®±òè ®ò ±®±òàâà À‘ è ¤å©±òâè© â±åµ ÀÝD âµ®¤ÿùèµ â ýò®ò
±®±òàâ @íàﮬíè¬D ·ò® ±®®òâåò±òâóþùàÿ §àâè±è¬®±òü ¤«ÿ ôóíêöèè ¤®µ®¤à öåíò°à
â⮤èò±ÿ â ï°å¤ï®«®¦åíèè ÀFIFAF
Ðà±±¬®ò°è¬ ±«å¤óþùè© ï°è¬å°D è««þ±ò°è°óþùè© ±ïåöèôèêó ±ô®°¬ó«è°®E
âàíí®© §à¤à·è @±¬F òàê¦å ï°è¬å°»D ï°èâå¤åíí»å â»øåAF
Ï°è¬å° 14. Ïó±òü ÀÝ ®¤í®°®¤í» è è¬åþò ôóíêöèè §àò°àò @|±| ¤ 1/nA

yi + ± yj
j∈I\i
@IIUA , i ∈ N.
ci (yI ) =
2r
…±«è öåíò° ¤®«¦åí ãà°àíòè°®âàòü êত®¬ó ÀÝ ó°®âåíü ﮫå§í®±òè U D ò® ®ïòèE
¬à«üí®© ÿâ«ÿåò±ÿ êâà§èꮬïåí±àò®°íàÿ ±è±òå¬à ±òè¬ó«è°®âàíèÿD ï°è è±ï®«ü§®E
âàíèè ê®ò®°®© §íà·åíèå öå«å⮩ ôóíêöèè öåíò°à °àâí®X
@IIVA yi ’ ci (yI ) ’ nU ,
¦(yI ) = g(n)
i∈I i∈I

„àíí®å ®ã°àíè·åíèå ¬®¦åò íå °à±±¬àò°èâàòü±ÿ, å±«è ¦(…) = 0.
9

IPS
ã¤å g(n) " ¬í®¦èòå«üD ®òâå·àþùè© §à óá»âàíèå ¤®µ®¤à öåíò°à ± °®±ò®¬ ·è±«à
ÀÝD âê«þ·åíí»µ â ±®±òàâ À‘F Îï°å¤å«è¬ ¤å©±òâèÿ ÀÝD íàè᮫åå â»ã®¤í»å ¤«ÿ
rng(n)
öåíò°àX y — = (1+±(n’1))2 F ’®ã¤à §àâè±è¬®±òü öå«å⮩ ôóíêöèè öåíò°à ®ò ·è±«à n
ÀÝD âµ®¤ÿùèµ â À‘D è¬ååò âè¤X
n2 g 2 (n)r
@IIWA ’ nU .
¦(n) =
2(1 + ±(n ’ 1))2
Îá±ó¤è¬ °®«ü ïà°à¬åò°à ±D âµ®¤ÿùåã® â ôóíêöèþ §àò°àò ÀÝ è ®òâå·àþùåã®
§à â«èÿíèå ¤å©±òâè© ¤°óãèµ ÀÝ íà §àò°àò» ¤àíí®ã® ÀÝF
‚®Eïå°â»µD ï°è ± ≥ 0 §àò°àò» êত®ã® ÀÝ â®§°à±òàþò ± °®±ò®¬ ¤å©±òâè©
¤°óãèµ ÀÝD à ï°è ± ¤ 0 " óá»âàþòF ‘®¤å°¦àòå«üí® ýò®ò ôàêò ¬®¦åò èíòå°E
ï°åòè°®âàòü±ÿ ±«å¤óþùè¬ ®á°à§®¬X â ïå°â®¬ ±«ó·àå ÀÝ 4¬åøàþò4 ¤°óã ¤°óãó
@íàï°è¬å°D ï°è ®ã°àíè·åíí»µ òåµí®«®ãèå© â®§¬®¦í®±òÿµ ï°®è§â®¤±òâàAD à â® âò®E
°®¬ " 4ﮬ®ãàþò4 @íàï°è¬å°D ﰮ豵®¤èò °à§¤å«åíèå ò°ó¤à è òF¤FAF ‚®Eâò®°»µD
ôóíêöèÿ @IIWA óá»âàåò ï® ïà°à¬åò°ó ±D ò® å±òü ± åã® °®±ò®¬ ï°è «þᮬ ôèêE
±è°®âàíí®¬ ±®±òàâå ¤®µ®¤ öåíò°à óá»âàåòF Áó¤å¬ ±·èòàòüD ·ò® ± < 0D ò®ã¤à ï°è
g(n) = n’1/2 ﮫó·àå¬D ·ò® ¦(n) = 2(1+±(n’1))2 ’ nU F Ï°å¤ï®«àãàÿ ±óùå±òâ®âàíèå
r

íåíó«åâ®ã® âíóò°åííåã® °åøåíèÿD ﮫó·è¬D ·ò® ®ïòè¬à«üí»© °à§¬å° À‘ °àâåíX
1/3
F
n— = 1 ’ ± ’ ± ±r
1 1
U
‘ ó¬åíüøåíèå¬ §íà·åíèÿ ïà°à¬åò°à10 ± °à±òåò ®ïòè¬à«üí»© °à§¬å° À‘D ±
óâå«è·åíèå¬ ãà°àíòè°®âàíí®ã® ó°®âíÿ ﮫå§í®±òè U ®í óá»âàåòF•
‚ ᮫åå ®áùå¬ ±«ó·àå ¬®¦í® °à±±¬®ò°åòü ¤âà òèïà â§à謮â«èÿíèÿ ÀÝX
E ± óâå«è·åíèå¬ ±®±òàâà À‘ §àò°àò» êত®ã® ÀÝ íå ⮧°à±òàþòX
∀i ∈ N, ∀I ∈ „µ, ∀j ∈ N \I, ∀y ∈ Ai ci (yI ) ≥ ci (yI∪{j} );
i∈N

E ± óâå«è·åíèå¬ ±®±òàâà À‘ §àò°àò» êত®ã® ÀÝ íå óá»âàþòX
∀i ∈ N, ∀I ∈ „µ, ∀j ∈ N \I, ∀y ∈ Ai ci (yI ) ¤ ci (yI∪{j} ).
i∈N

‘®¤å°¦àòå«üí»å èíòå°ï°åòàöèè ®á®èµ ±«ó·àåâ ®·åâè¤í»F




Îò¬åòè¬, ·ò® â °à±±¬àò°èâà嬮¬ ï°è¬å°å ï°è ± ®ïòè¬à«üí»© °à§¬å° À‘ íå ï°åâ»øàåò
10 >0
å¤èíèö».
IPT
Ï°è«®¦åíèå 5. Ïå°±®íèôèöè°®âàíí»å ±è±ò嬻
±òè¬ó«è°®âàíèÿ

Ðà±±¬®ò°è¬ §à¤à·ó ¬èíè¬è§àöèè §àò°àò ¤«ÿ °åà«è§àöèè íåê®ò®°®ã® ¤å©±òâèÿ
â àêòèâí»µ ±è±òå¬àµ À‘I è À‘S " ¬» ¬®¦å¬ íà§íà·àòü êত®¬ó è§ àêòèâí»µ
ý«å¬åíò®â ïå°±®íà«üíóþ ±è±òå¬ó ±òè¬ó«è°®âàíèÿ @±·èòàå¬D ·ò® òèï êত®ã® àêE
òèâí®ã® ý«å¬åíòà íଠò®·í® è§âå±òåí è ·ò® ï® ýò®¬ó òèïó ¬» ¬®¦å¬ ò®·í® â®±E
±òàí®âèòü åã® ôóíêöèþ §àò°àòAF
Ðà±±¬®ò°è¬ ¤è±ê°åòí»© ±«ó·à©D à è¬åíí®D ïó±òü â àêòèâí®© ±è±òå¬å è¬ååò±ÿ
n àêòèâí»µ ý«å¬åíò®âD ï°è·å¬ iE© àêòèâí»© ý«å¬åíò è¬ååò òèï ri ∈ „¦D {ri }n =
i=1
„¦ ‚ „¦F
’®ã¤à §à¤à·à ¬èíè¬è§àöèè ±ó¬¬à°í»µ §àò°àò íà ±òè¬ó«è°®âàíèå §àïè±»âàåòE
±ÿ ±«å¤óþùè¬ ®á°à§®¬X

n
@IPHA σi (f (ri )) ’ min
f (r),σi (x)∈M
i=1

ï°è â»ï®«íåíèè 󱫮âè©

@IPIA f (ri ) ∈ Argmax(σi (x) ’ c(ri , x));
x
n
@IPPA f (ri ) = x,
¯
i=1

ã¤å f (r) å±òü ôóíêöèÿ ¤å©±òâèÿ àêòèâí»µ ý«å¬åíò®âD à σi (x) " ôóíêöèÿ ±òè¬ó«èE
°®âàíèÿ iEã® àêòèâí®ã® ý«å¬åíòàF
‚ ‘47“ ï®êà§àí®D ·ò® ï°è ¤àíí®© ï®±òàí®âêå §à¤à·è ®ïòè¬à«üí»¬è ÿâ«ÿþò±ÿ
êâà§èꮬïåí±àò®°í»å ±è±ò嬻 ±òè¬ó«è°®âàíèÿD è â¬å±ò® ôóíêöè© ±òè¬ó«è°®âàE
íèÿ ¤®±òàò®·í® °à±±¬àò°èâàòü ci " ò®·å·í»å ±òè¬ó«è°®âàíèÿ àêòèâí»µ ý«å¬åíò®â
ï°è °åà«è§àöèè íå®áµ®¤è¬»µ ¤å©±òâè© xi D ï°è·å¬ ci = c(ri , xi )F ’®ã¤àD ﮱꮫüêó
σi (x) = ci I{x=xi } D ã¤å I{·} " ôóíêöèÿEèí¤èêàò®°D §à¤à·à ïå°åïè±»âàåò±ÿ â ±«å¤óþE
ùå¬ âè¤åX
n
c(ri , xi ) ’ min
{xi }
i=1
ï°è â»ï®«íåíèè 󱫮âèÿ
n
x i = x.
¯
i=1
Ðåøàÿ ¬èíè¬è§àöè®ííóþ §à¤à·ó ¬åò®¤®¬ ¬í®¦èòå«å© Ëàã°àí¦à
n n
c(ri , xi ) + » x ’ ’ min
L= xi
¯
{xi }
i=1 i=1
IPU
ﮫó·àå¬D ·ò®
cx (ri , xi ) = » ≥ 0, i = 1, n,
±«å¤®âàòå«üí® ¤®«¦í® â»ï®«íÿòü±ÿ
@IPQA cx (ri , xi ) = cx (rj , xj ), j, i = 1, n.
Ï°è¬å° 15. Ðà±±¬®ò°è¬ ±«ó·à© êâरàòè·í»µ §àò°àò àêòèâí»µ ý«å¬åíò®â
c(ri , x) = x2 /ri D è ïó±òü ¬í®¦å±ò⮠⮧¬®¦í»µ òèï®â å±òü „¦ = {ri }n D „¦ ‚ „¦F i=1
’®ã¤à
cx (ri , xi ) = cx (rj , xj ) ’ 2xi /ri = 2xj /rj ’ xi = xj ri /rj .
‘ó¬¬à°í®å ¤å©±òâèå
n n n
x= xi = x1 ri /r1 = x1 ri /r1 ;
¯
i=1 i=1 i=1

n
x1 = xr1 ri .
¯
i=1
‚ ±è«ó ýò®ã® ﮫó·àå¬D ·ò® ¤å©±òâèå iEã® ÀÝ
n
xi = xri rk .
¯
k=1

Ìèíè¬à«üí»å §àò°àò» íà °åà«è§àöèþ ¤å©±òâèÿ x °àâí»
¯
2
n
xri ri
¯
n n n
i=1
σi (xi ) = c(ri , xi ) =
ri
i=1 i=1 i=1
n
x2 x2
¯ ¯
ri = .•
= n
2
n
ri
i=1
ri
i=1
i=1

Ë嬬à 1. Ïó±òü x— (¯) " °åøåíèå §à¤à·è @IPHAE@IPPA ï°è §à¤àíí®¬ xF ’®ã¤à
ix ¯
n
σi (x— )
d i
i=1
= cx (rj , x— ), j = 1, n;
j

x
n
σi (x— )
2
d i
1
i=1
.
= n
d¯2
x 1
cxx (ri ,x— )
i
i=1

Çà¬åòè¬D ·ò® ï® Ë嬬å I è â ±è«ó 󱫮âè© íà ôóíêöèè §àò°àò â»ï®«íåí®
n
σi (x— )
2
d i
1
i=1
> 0,
= n
d¯2
x 1
cxx (ri ,x— )
i
i=1

ò® å±òü ôóíêöèÿ ±°å¤íèµ ¬èíè¬à«üí»µ §àò°àò íà °åà«è§àöèþ ¤å©±òâèÿ â»ïóê«àF
Ýò®D â ·à±òí®±òèD ã®â®°èò ® ò®¬D ·ò® öåíò°ó íåâ»ã®¤í® è±ï®«ü§®âàòü ±¬åøàíí»å
±ò°àòåãèèF
IPV
Ï°è¬å° 16. Ðà±±¬®ò°è¬ §àò°àò» âè¤à

<< . .

. 17
( : 19)



. . >>