Îïèñàíèå ìåòîäîâ, àëãîðèòìîâ è ýêñïåðèìåíòîâ

2.1. Ìîäåëè

 êà÷åñòâå ìàòåìàòè÷åñêèõ ìîäåëåé ðàññìîòðåíû ñëåäóþùèå ïîñòàíîâêè çàäà÷ íàèëó÷øåãî âûáîðà:

Ì_I: Ñëó÷àé, êîãäà ÷èñëî çàêàç÷èêîâ N –

ñëó-÷àéíî èëè èçâåñòíî çàðàíåå, ðàñïðåäåëåíèå öåí íåèçâåñòíî, à â êà÷åñòâå êðèòåðèÿ ïðåäëàãàåòñÿ ìàêñèìèçèðîâàòü âåðîÿòíîñòü âûáîðà îäíîãî (äâóõ) ëó÷øèõ çàêàç÷èêîâ.

Âîçìîæíûì ñ÷èòàåòñÿ ðåøåíèå, êîãäà áàííåðû èëè ñëîâà íå áóäóò ïðîäàíû íèêîìó.

Ì_II: Ìîäåëü, â êîòîðîé èçâåñòíî ÷èñëî

çàêàç-÷èêîâ è ðàñïðåäåëåíèå öåí, à â êà÷åñòâå êðèòåðèÿ îïòèìàëüíîñòè ïðåäëàãàåòñÿ ìàêñèìèçèðîâàòü âåðî-ÿòíîñòü âûáîðà îäíîãî (äâóõ) ëó÷øèõ çàêàç÷èêîâ.

Ì_III: Ñëó÷àé, ïðè êîòîðîì íóëåâîå ðåøåíèå èñêëþ÷àåòñÿ, òî åñòü ñëîâà áóäóò ïðîäàíû îäíîìó (äâóì) ïîñëåäíèì çàêàç÷èêàì, åñëè âûáîð ïî îï-òèìàëüíîé ñòðàòåãèè íå äàë ðåçóëüòàòà. Ðàññìàòðè-âàåòñÿ ñëåäóþùàÿ ìîäåëü.

 êà÷åñòâå êðèòåðèÿ ïðèíèìàåòñÿ ìàêñèìèçàöèÿ ïðåäëàãàåìûõ çàêàç÷èêàìè öåí (ñóììû öåí). Âîçìîæ-íû äâà âàðèàíòà: 1) äëÿ èçâåñòíîãî ðàñïðåäåëåíèÿ öåí è 2) äëÿ íåèçâåñòíîãî ðàñïðåäåëåíèÿ öåí (ñëó÷àé àäàïòèâíûõ ìîäåëåé, ñóùåñòâåííî îòëè÷àþùèõñÿ îò ïðåäûäóùèõ âàðèàíòîâ).

Ì_IV: Òåîðåòèêî-èãðîâàÿ ïîñòàíîâêà çàäà÷è ñ äâóìÿ êîíêóðèðóþùèìè ïîèñêîâûìè ñèñòåìàìè (äàëåå – èãðîêàìè): ìîäåëü ñ äîìèíèðóþùèì èã-ðîêîì – çàêàç÷èêè îáðàùàþòñÿ ê îäíîé ïîèñêî-âîé ñèñòåìå, è ëèøü ïîëó÷èâ îòêàç, îáðàùàþòñÿ êî âòîðîé.

2.2. Ìîäåëü I: N – ïîñòîÿííàÿ âåëè÷èíà, íåò èíôîðìàöèè î öåíàõ

 äàííîé ìîäåëè ïðåäïîëàãàåòñÿ, ÷òî ÷èñëî

çàêàç-÷èêîâ N ÿâëÿåòñÿ ïîñòîÿííîé âåëè÷èíîé, è îòñóò-ñòâóåò èíôîðìàöèÿ î ðàñïðåäåëåíèè ïðåäëàãàåìûõ öåí. Ïîèñêîâàÿ ñèñòåìà ñòðåìèòñÿ ìàêñèìèçèðî-âàòü âåðîÿòíîñòü âûáîðà ëó÷øåãî çàêàç÷èêà (äâóõ ëó÷øèõ çàêàç÷èêîâ).

1) Âûáîð îäíîãî íàèëó÷øåãî çàêàç÷èêà

Äàííàÿ çàäà÷à â ëèòåðàòóðå èçâåñòíà êàê êëàñ-ñè÷åñêàÿ çàäà÷à íàèëó÷øåãî âûáîðà [1]. Äëÿ ïðî-äàâöà çàêàç÷èêè óïîðÿäî÷åíû ïî ðàíãó (àáñîëþò-íûé ðàíã). Ðàíã 1 èìååò íàèëó÷øèé çàêàç÷èê, ðàíã N – íàèõóäøèé. Çàêàç÷èêè ïîñòóïàþò ïîñ-ëåäîâàòåëüíî â ñëó÷àéíîì ïîðÿäêå, ïðè ýòîì ïðî-äàâåö íàáëþäàåò ðàíã i-òîãî çàêàç÷èêà îòíîñè-òåëüíî âñåõ ïðåäûäóùèõ (îòíîñèòåëüíûé ðàíã).

Àáñîëþòíûå ðàíãè çàêàç÷èêîâ íåèçâåñòíû ïîèñ-êîâîé ñèñòåìå.

Ââåäåì ñëåäóþùèå îáîçíà÷åíèÿ: a_i – àáñîëþò-íûé ðàíã i-ãî çàêàç÷èêà, y_i – îòíîñèòåëüíûé ðàíã i-ãî çàêàç÷èêà. Âåðîÿòíîñòü òîãî, ÷òî i-îå ïðåäëî-æåíèå áóäåò àáñîëþòíî ëó÷øèì ïðè óñëîâèè, ÷òî îíî ëó÷øå âñåõ ïðåäûäóùèõ ðàâíà

N y i

a

P (

_i

= 1 /

_i

= 1 ) =

Îïòèìàëüíàÿ ñòðàòåãèÿ τ^* ñëåäóþùàÿ

} 1 :

min{

^*

*

= m ≥ k y

m

=

τ

^,

ãäå m = k^*, …, N.

Âåðîÿòíîñòü óäà÷íîãî âûáîðà ïî ïðîèçâîëüíîé ñòðàòåãèè âû÷èñëÿåòñÿ ïî ôîðìóëå (1).

∑

₌ ⁻₋

= ^N

k

s N s

P k

) 1 (

1 (1)

Äëÿ äîñòàòî÷íî áîëüøèõ N, ïîëàãàÿ

N k

N→∞

= lim α

ïîëó÷àåì íàèáîëüøóþ âåðîÿòíîñòü P = e^–1 = 0.368 ïðè α = e^–1 = 0.368.

Òàê êàê ÷èñëî çàêàç÷èêîâ ó êîìïàíèè ßíäåêñ äîñòàòî÷íî âåëèêî, òî, ïðèìåíÿÿ ïîëó÷åííûå ðå-çóëüòàòû, ìîæíî ñôîðìóëèðîâàòü îïòèìàëüíóþ ñòðàòåãèþ ïîèñêîâîé ñèñòåìû:

1) ïåðâûå [0,368•N] ïðåäëîæåíèé çàêàç÷èêîâ íåîáõîäèìî ïðîïóñòèòü, ïðè ýòîì îïðåäåëÿÿ

çíà-÷åíèå Ê íàèâûñøåé öåíû èç âñåõ ïðåäëîæåííûõ;

2) âûáîð çàêàç÷èêà:

– íà÷èíàÿ ñ íîìåðà [0,368•N] + 1 ïðèíèìàåòñÿ

ïðåäëîæåíèå çàêàç÷èêà ñ ïîðÿäêîâûì íîìåðîì m, êîòîðûé ïðåäëàãàåò öåíó M áîëüøå K.

Ñëåäóÿ ýòîé ñòðàòåãèè, ìîæíî ñ ìàêñèìàëüíîé âåðîÿòíîñòüþ âûáðàòü «íàèëó÷øåãî» çàêàç÷èêà.

Ðàññìîòðèì ýòî íà ïðèìåðå.  òàáëèöå 1 ïðåä-ñòàâëåíû äàííûå, ïðåäîñòàâëåííûå êîìïàíèåé ßí-äåêñ. Ïóñòü èìååòñÿ 10 çàêàç÷èêîâ, êîòîðûå ïðåä-ëàãàþò öåíû â ñîîòâåòñòâèè ñ òàáë. 1.

Òàáëèöà 1 Çíà÷åíèÿ ïðåäëàãàåìûõ öåí äëÿ N = 10

k 1 2 3 4 5

Öåíà 74,68 152,17 10,23 14,85 0,06

k 6 7 8 9 10

Öåíà 2,37 25,36 220,52 168,04 27,53

Ñëåäóÿ îïòèìàëüíîé ñòðàòåãèè, ïðîäàâåö ïðî-ïóñêàåò ïåðâûå òðè ïðåäëîæåíèÿ, è îñòàíàâëèâà-åòñÿ íà ïðåäëîæåíèè ïîä íîìåðîì 8.  ðåçóëüòàòå îí ïîëó÷àåò ïðåäëîæåíèå çàêàç÷èêà 220.52.

1) Âûáîð äâóõ ëó÷øèõ çàêàç÷èêîâ

Ïðè òåõ æå óñëîâèÿõ íåîáõîäèìî âûáðàòü äâóõ ëó÷øèõ ïî êà÷åñòâó çàêàç÷èêîâ.

 çàäà÷å íàèëó÷øåãî âûáîðà íåîáõîäèìî íàéòè îïòèìàëüíóþ ñòðàòåãèþ τ^* = (τ₁,τ₂), 1 ≤ τ₁< τ₂≤ N, äëÿ êîòîðîé

)).

1 a , 2 a ( ) 2 a , 1 a ((

P sup

)) 1 a , 2 a ( ) 2 a , 1 a ((

P

2 1 2

2 1 1,

* 2

* 1

* 2

* 1

=

=

∪

=

=

=

=

=

=

∪

=

=

τ τ τ

τ τ τ

τ τ τ

τ

 ýòîì ñëó÷àå îïòèìàëüíàÿ ñòðàòåãèÿ ñëåäóþùàÿ

} :

ìíîæåñòâå{ íà

}}

1 , : min{

}, 1 : min{min{

} 1 : min{

* 1

* * 2

* * 1

m

y l n m n y

m n

y k m

m n

m

=

=

≥

>

=

>

=

=

≥

=

τ ω τ

τ

Âåðîÿòíîñòü óäà÷íîãî âûáîðà ïî ïðîèçâîëüíîé ñòðàòåãèè (s, t) âû÷èñëÿåòñÿ ïî ôîðìóëå (2).

∑∑

∑ ∑

∑

−

= =

−

= =+

−

=

−

−

−

− + −

−

− + −

− +

−

−

− −

−

−

−

= −

1 l

k s

N

l t 1

N

k s

N

1 s t

2 l

k s

) 2 t )(

1 s (

1 )

1 N ( N

) 2 l )(

1 k ( 2 2 t

1 )

1 N ( N

) 1 k ( 2

) 1 N ( N

) 1 k l )(

1 k ( 1 s

1 ) 1 N ( N

) 2 l )(

1 k P (

(2)

Äëÿ äîñòàòî÷íî áîëüøèõ N, ïîëàãàÿ, êàê è ðàíüøå

N k

N→∞

= lim

α ,

N l

N→∞

=lim

β ïîëó÷àåì íàèáîëüøóþ âåðîÿòíîñòü P ≈ 0,025 ïðè α ≈ 0,229, β ≈ 0,607.

Ñòðàòåãèÿ ïðîäàâöà âûãëÿäèò ñëåäóþùèì îá-ðàçîì:

1) ïåðâûå [0,229•N] ïðåäëîæåíèé çàêàç÷èêîâ íåîáõîäèìî ïðîïóñòèòü, ïðè ýòîì îïðåäåëÿÿ

çíà-÷åíèå K íàèâûñøåé öåíû èç âñåõ ïðåäëîæåí-íûõ;2) âûáîð çàêàç÷èêà ïåðâîãî áàííåðà:

– íà÷èíàÿ ñ íîìåðà [0,229•N] + 1 ïðèíèìàåòñÿ ïðåäëîæåíèå çàêàç÷èêà ñ ïîðÿäêîâûì íîìåðîì m, êîòîðûé ïðåäëàãàåò öåíó M áîëüøå K;

3) âûáîð çàêàç÷èêà âòîðîãî áàííåðà:

– äî íîìåðà [0,607•N] + 1 ïðèíèìàåòñÿ ïðåäëî-æåíèå çàêàç÷èêà ñ ïîðÿäêîâûì íîìåðîì n, êîòî-ðûé ïðåäëàãàåò öåíó Ò âûøå M,

– åñëè òàêîãî çàêàç÷èêà íå îêàçûâàåòñÿ, òî,

íà-÷èíàÿ ñ íîìåðà [0,607•N] + 1 ïðèíèìàåòñÿ

çàêàç-÷èê, ïðåäëîæèâøèé öåíó, êîòîðàÿ íèæå òîëüêî öåíû M.Äàííàÿ çàäà÷à áûëà ðåøåíà Íèêîëàåâûì â ðà-áîòå [4].

Ðàññìîòðèì ïðèìåð, äàííûé â òàáë. 1. Ïåðâûõ äâóõ çàêàç÷èêîâ ïðîäàâåö ïðîïóñêàåò. Ñâîé ïåðâûé âûáîð îí äåëàåò íà 8-ì øàãå, âòîðîé – íà 9-ì.  ðå-çóëüòàòå îí ïîëó÷àåò äâóõ çàêàç÷èêîâ, ïðåäëàãàþ-ùèõ öåíû 220.52 è 168.04.

2.3. Ìîäåëü I: N – ñëó÷àéíàÿ âåëè÷èíà

Ïðåäûäóùóþ ìîäåëü ìîæíî ðàñøèðèòü, ïîëàãàÿ, ÷òî

÷èñëî çàêàç÷èêîâ N ÿâëÿåòñÿ ñëó÷àéíîé âåëè÷èíîé (òàê êàê â äåéñòâèòåëüíîñòè êîëè÷åñòâî çàêàç÷èêîâ íåèçâåñòíî).

 äàííîé ìîäåëè ïðåäïîëàãàåòñÿ, ÷òî åñëè îï-òèìàëüíàÿ ñòðàòåãèÿ íå äàëà ðåçóëüòàòîâ, òî íå áóäåò âûáðàí íè îäèí çàêàç÷èê.

1) Âûáîð îäíîãî íàèëó÷øåãî çàêàç÷èêà

Ïóñòü ÷èñëî çàêàç÷èêîâ N ÿâëÿåòñÿ äèñêðåò-íîé ñëó÷àéäèñêðåò-íîé âåëè÷èäèñêðåò-íîé, ðàñïðåäåëåíäèñêðåò-íîé ðàâíî-ìåðíî îò 1 äî M. Îáîçíà÷èì âåðîÿòíîñòü óäà÷íî-ãî âûáîðà ïî ôîðìóëå (1) ïðè ïîñòîÿííîì N

∑

₌ ⁻₋

= ^N

k

s N(s 1)

1 ) k

N (

Q _.

Òîãäà âåðîÿòíîñòü óäà÷íîãî âûáîðà îäíîãî çà-êàç÷èêà, åñëè N ÿâëÿåòñÿ ñëó÷àéíîé âåëè÷èíîé, âû÷èñëÿåòñÿ ïî ôîðìóëå

) i ( Q ) i N ( P P

M

1

∑

i₌ ⁼

= _.

Òàê êàê ïðè ðàâíîìåðíîì ðàñïðåäåëåíèè

M ) 1 i N (

P = = _{, òî} Q(i) M

P 1

M

1

∑

i₌

= _.

 òàáë. 2 äàíû çíà÷åíèÿ îïòèìàëüíîãî k äëÿ ðàç-ëè÷íîãî ÷èñëà çàêàç÷èêîâ M (äàííûå ïðåäîñòàâëå-íû êîìïàíèåé ßíäåêñ çà 2006–2007 ãîä). Òàê êàê ñî-ãëàñíî ýòèì äàííûì M äîñòàòî÷íî âåëèêî, òî âåðî-ÿòíîñòü óäà÷íîãî âûáîðà áóäåò ïðèìåðíî ðàâíà 0,2707.

Òàáëèöà 2 Çíà÷åíèÿ îïòèìàëüíîãî k

äëÿ ðàçëè÷íûõ çíà÷åíèé M

M k^* M k^*

13277 1798

13700 1855

13958 1890

14014 1898

14561 1972

15636 2117

16942 2294

18022 2440

18211 2466

17986 2435

19278 2610

20731 2807

21709 2939

Ïëîòíîñòü ðàñïðåäåëåíèÿ öåí N = 114 (λλλλλ= 0.008)

0 0,001 0,002 0,003 0,004 0,005 0,006 0,007 0,008 0,009 0,01

0 250 500 750 1000 1250

1500 1750 200 0

2250

Òàêèì îáðàçîì, îïòèìàëüíàÿ ñòðàòåãèÿ ïîèñêî-âîé ñèñòåìû ñîñòîèò â ñëåäóþùåì: íåîáõîäèìî ïðî-ïóñòèòü k çàêàç÷èêîâ, ïðè ýòîì, çàïîìèíàÿ íàèâûñ-øóþ èç ïðåäëîæåííûõ öåí, à çàòåì âûáðàòü òîãî çàêàç÷èêà, êîòîðûé ïðåäëîæèò öåíó, ïðåâûøàþùóþ âñå ïðåäûäóùèå ïðåäëîæåíèÿ.

Èç äàííûõ, ïðåäîñòàâëåííûõ êîìïàíèåé ßíäåêñ, âèäíî, ÷òî ÷èñëî çàêàç÷èêîâ êîëåáëåòñÿ îò 10000 äî 30000. Òî åñòü ðàñïðåäåëåíèå ÷èñëà çàêàç÷èêîâ ìîæ-íî ïðåäïîëîæèòü ðàâìîæ-íîìåðíûì îò 10000 äî 30000.

Òîãäà îïòèìàëüíîå k áóäåò ðàâíî 6372, à âåðîÿò-íîñòü óñïåõà óâåëè÷èâàåòñÿ äî 0,35.

1) Âûáîð äâóõ ëó÷øèõ çàêàç÷èêîâ

Êàê è ðàíåå ïóñòü ÷èñëî çàêàç÷èêîâ N ðàñïðå-äåëåíî ðàâíîìåðíî îò 1 äî Ì. Îáîçíà÷èì âåðîÿò-íîñòü óäà÷íîãî âûáîðà ïðè ïîñòîÿííîì N èç ôîð-ìóëû (2)

t . s

1 N

N l k t

N N

k

1 N N

1 k l k 1 s

1 N

N l N k

S

1 l

k s

N

l t 1

N

k s

N

1 s t

2 l

k s

∑∑

∑ ∑

∑

−

= =

−

= =+

−

=

−

−

−

− + −

−

− + −

−

−

−

− −

−

−

−

= −

2) 1)(

( 1)

( 2) 1)(

2(

2 1 1)

( 1) 2(

) (

) 1)(

( 1)

( 2) 1)(

) ( (

Òîãäà âåðîÿòíîñòü óñïåõà âû÷èñëÿåòñÿ ïî ôîð-ìóëåP P(N i)S(i)

M

1

∑

i₌ ⁼

= èëè, ó÷èòûâàÿ, ÷òî

i M N

P 1

)

( = = _, 1 ()

i M S P

M

1

∑

i₌

= . Åñëè æå N

ðàñïðå-äåëåíî îò M₁ äî M₂, òî 1 () i M S

P M

2

1 M

M 1 i

2 ₋

∑

₌

= .

Íàïðèìåð, åñëè N ðàñïðåäåëåíî ðàâíîìåðíî îò 100 äî 300, òî âåðîÿòíîñòü íàèëó÷øåãî âûáîðà ðàâíà 0.239 ïðè îïòèìàëüíûõ k^*= 40 è λ^*= 79.

2.4. Ìîäåëü II: N – ïîñòîÿííàÿ âåëè÷èíà, ðàñïðåäåëåíèå öåí èçâåñòíî

 äàííîé ìîäåëè ïðè âûáîðå çàêàç÷èêîâ ó÷èòû-âàåòñÿ èíôîðìàöèÿ î ïðåäëàãàåìûõ èìè öåíàõ (èçâåñòíà ôóíêöèÿ ðàñïðåäåëåíèÿ öåí). Ýòî òàê íàçûâàåìûé ñëó÷àé ñ ïîëíîé èíôîðìàöèåé.

1) Ôóíêöèÿ ðàñïðåäåëåíèÿ öåí

Äëÿ òîãî ÷òîáû ñìîäåëèðîâàòü çàäà÷è, ñâÿçàí-íûå ñ ðàñïðåäåëåíèåì ïðåäëàãàåìûõ öåí, íåîáõî-äèìî íàéòè ñàìè ôóíêöèè ðàñïðåäåëåíèÿ öåí èëè ïëîòíîñòè ðàñïðåäåëåíèÿ, òàê êàê èññëåäóåìûå íàìè âåëè÷èíû ÿâëÿþòñÿ íåïðåðûâíûìè.

Äëÿ íàõîæäåíèÿ ôóíêöèè ðàñïðåäåëåíèÿ âîñ-ïîëüçóåìñÿ ìåòîäàìè ìàòåìàòè÷åñêîé ñòàòèñòèêè.

Íà îñíîâå ïðåäîñòàâëåííîé êîìïàíèåé ßíäåêñ èíôîðìàöèè î öåíàõ çàêàç÷èêîâ êîíòåêñòíîé ðåê-ëàìû, ñäåëàëàñü âûáîðêà èç 114 çíà÷åíèé öåí.

ßñíî, ÷òî äëÿ ðàçëè÷íûõ îáëàñòåé ðåêëàìû ðàñ-ïðåäåëåíèÿ öåí áóäóò ðàçíûìè. Äëÿ ìîäåëèðîâà-íèÿ áûëè âûäåëåíû ÷åòûðå ÿðêî âûðàæåííûå îá-ëàñòè: îòäûõ, ñòðîèòåëüñòâî, ïðîèçâîäñòâî è ïî-ñòàâêè, ðåêëàìà (òàáë. 3).

Ìåòîäîì íàèìåíüøèõ êâàäðàòîâ áûëè íàéäåíû ôóíêöèè ðàñïðåäåëåíèÿ öåí è èõ ïàðàìåòðû.

Òàáëèöà 3 Ôóíêöèè ðàñïðåäåëåíèÿ öåí

Îáëàñòü Êîëè÷åñòâî Ôóíêöèÿ ðàñïðåäåëåíèÿ, çàêàç÷èêîâ N F(x)=1−e^−λx

ïàðàìåòð λλλλλ

îòäûõ 14 λ= 0 ,0 1

ñòðîèòåëüñòâî 10 λ= 0 ,0 2

ïðîèçâîäñòâî

è ïîñòàâêè 32 λ= 0 ,0 0 6

ðåêëàìà 58 λ= 0 ,0 1

âñå 114 λ= 0 ,0 0 8

Íà äèàãðàììå ïðèâåäåí ïðèìåð ïëîòíîñòè ðàñ-ïðåäåëåíèÿ îáùåãî êîëè÷åñòâà öåí N = 114 (λ= 0.008). Ó÷èòûâàÿ ïîëó÷åííóþ èíôîðìàöèþ î ðàñ-ïðåäåëåíèè öåí, íàéäåì ðåøåíèå â äàííîé ìîäåëè.

2) Âûáîð îäíîãî íàèëó÷øåãî çàêàç÷èêà

Ïóñòü íåîáõîäèìî âûáðàòü íàèëó÷øåãî çàêàç÷è-êà, åñëè èçâåñòíî ðàñïðåäåëåíèå ïðåäëàãàåìûõ öåí.

 äàííîé ìîäåëè âûáîð îñóùåñòâëÿåòñÿ íà îñíîâå îäíîïîðîãîâîé ñòðàòåãèè. Òî åñòü ïåðåä ïîñòóïëå-íèåì ïåðâîãî ïðåäëîæåíèÿ óêàçûâàåòñÿ çíà÷åíèå ïîðîãà a. Ïðåäëîæåíèå çàêàç÷èêà ïðèíèìàåòñÿ, òîëü-êî åñëè îíî ïðåâûøàåò çíà÷åíèå a è îòâåðãàåòñÿ

èíà-÷å. Ñëåäîâàòåëüíî, â îòëè÷èå îò ïðåäûäóùèõ ðàñ-ñìîòðåííûõ çàäà÷, âûáîð ìîæåò áûòü ñäåëàí óæå íà ïåðâîì øàãå.

Ó÷èòûâàÿ ðàñïðåäåëåíèå öåí, âåðîÿòíîñòü óäà÷-íîãî âûáîðà ìîæåò áûòü âû÷èñëåíà ñëåäóþùèì îáðàçîì.

⎟⎟⎠⎞

⎜⎜⎝⎛

+

−

− − +

− −

= ^{− −+}

−

=

∑

^{(1 e}− ⁾ _N ¹_{i 1} ⁽¹_N^e _i⁾₁ ¹

P

i x N 1

N i

1 i

a λⁱ

λ (3)

 òàáë. 4 äàíû ÷èñëåííûå ðåçóëüòàòû äëÿ ðàçëè÷-íûõ N è λ.

Ñðàâíèì çíà÷åíèÿ âåðîÿòíîñòåé óñïåøíîãî âûáîðà äëÿ ñëó÷àÿ áåç èíôîðìàöèè (Ìîäåëü I) è ñëó÷àÿ ñ ïîëíîé èíôîðìàöèåé (Ìîäåëü II). Èç ïîëó÷åííûõ çíà÷åíèé âèäíî, ÷òî îáëàäàíèå èí-ôîðìàöèåé î ðàñïðåäåëåíèè öåí ñóùåñòâåííî ïî-âûøàåò øàíñû íà óñïåõ.

Ðàññìîòðèì ïðèìåð äëÿ N = 32 è λ= 0 ,0 0 6.

 òàáë. 5 äàíû öåíû, ïðåäëîæåííûå çàêàç÷èêàìè â îáëàñòè ïðîèçâîäñòâà è ïîñòàâîê.

Òàáëèöà 4 Çíà÷åíèå âåðîÿòíîñòåé óäà÷íîãî âûáîðà äëÿ ðàçëè÷íûõ N è λλλλλ

Êîëè÷åñòâî Ôóíêöèÿ ðàñïðåäåëåíèÿ, Çíà÷åíèå ïîðîãà a Âåðîÿòíîñòü óñïåõà çàêàç÷èêîâ N F(x)= 1–e^–λx,ïàðàìåòð λ

14 λ= 0.01 224.527 0.533766

10 λ= 0.02 95.7238 0.54068

32 λ= 0.006 510.701 0.524385

58 λ= 0.01 365.628 0.521205

114 λ= 0.008 541.306 0.519304

Òàáëèöà 6 Çíà÷åíèå âåðîÿòíîñòåé óäà÷íîãî âûáîðà äëÿ ðàçëè÷íûõ N è λλλλλ

Êîëè÷åñòâî Ôóíêöèÿ ðàñïðåäåëåíèÿ, Çíà÷åíèå ïîðîãà a Âåðîÿòíîñòü óñïåõà çàêàç÷èêîâ N F(x)= 1–e^–λx,ïàðàìåòð λ

14 λ= 0.01 177.961 0.386136

10 λ= 0.02 72.3362 0.398144

32 λ= 0.006 433.608 0.37082

58 λ= 0.01 319.483 0.365858

114 λ= 0.008 483.711 0.362944

Çíà÷åíèå îïòèìàëüíîãî ïîðîãà, âû÷èñëåííîå ïî ôîðìóëå (3), a= 510.701. Ïî îïòèìàëüíîé ñòðàòåãèè ïåðâûå 8 çàêàç÷èêîâ ïðîäàâåö ïðîïóñêàåò, òàê êàê ïðåäëîæåííûå èìè öåíû íå ïðåâûøàþò a. Ñâîé âû-áîð ïðîäàâåö äîëæåí ñäåëàòü íà 9-ì øàãå.  ðåçóëü-òàòå, îí ïðèíèìàåò ïðåäëîæåíèå çàêàç÷èêà ñ öåíîé ðàâíîé 2358.03.

3) Âûáîð äâóõ ëó÷øèõ çàêàç÷èêîâ

Ïóñòü òðåáóåòñÿ âûáðàòü äâóõ ëó÷øèõ çàêàç÷è-êîâ, åñëè èçâåñòíî ðàñïðåäåëåíèå ïðåäëàãàåìûõ öåí.

 äàííîé ìîäåëè òàêæå íåîáõîäèìî íàéòè ïîðîã à äëÿ ïðèíÿòèÿ íàèëó÷øåãî çàêàç÷èêà. Òîãäà âåðî-ÿòíîñòü óäà÷íîãî âûáîðà âû÷èñëÿåòñÿ ïî ôîðìóëå (4)

(4)

⎟⎟⎠⎞ + + − +

−

− −

⎜⎜⎝⎛

+

− − +

−

− −

−

=

+

−

−

=

+

−

− −

∑

−

1 i N

1 1

i N

) e 1 (

2 i N

1 2

i N

) e 1 ) ( e 1 )(

1 i ( 2

1 i N a N

2 i

2 i N a 2 i a

λ

λ λ

∑ ∑ ∫

∫

∫

∫

∫

∑ ∑ ∫ ∫ ∫ ∫

−

= =+

∞ − − − −

−

−

+

∞

−

−

= =+

∞

+

−

−

−

=

=

=

1 N

1 i

N

1 i

k a

i x k N x x 2 k a

x

0 N x

0 1 k x

k a

0 1 k 1 N

1 i

N

1 i

k a

a

0 1 i i a

0 1 i a

0 1

dx e ) e 1 ( e ) e 1 ( 2

) x ( dF ...

) x ( dF ) x ( dF ) x ( dF ...

) x ( dF ) x ( dF ) x ( dF ...

) x ( dF 2

P

i i i

i i

i

λ λ λ

λ λ

 òàáë. 6 äàíû ÷èñëåííûå ðåçóëüòàòû äëÿ ðàç-ëè÷íûõ N è λ.

Ðàññìîòðèì âèä îïòèìàëüíîé ñòðàòåãèè äëÿ ñè-òóàöèè, îïèñàííîé â òàáë. 5. Îïòèìàëüíàÿ ñòðàòå-ãèÿ âûãëÿäèò ñëåäóþùèì îáðàçîì: Íà êàæäîì øàãå óñòàíàâëèâàåòñÿ ïîðîã äëÿ ïðèíÿòèÿ ïðåòåíäåíòîâ a= 433.608. Ïî îïòèìàëüíîé ñòðàòåãèè ïåðâûå 8 çàêàç÷èêîâ ïðîäàâåö ïðîïóñêàåò, òàê êàê ïðåäëî-æåííûå èìè öåíû ìåíüøå ÷åì a. Âûáîð ïåðâîãî çàêàç÷èêà ïðîäàâåö äîëæåí ñäåëàòü íà 9-ì øàãå, à âòîðîãî – íà 21-ì.  ðåçóëüòàòå îí ïðèíèìàåò ïðåä-ëîæåíèÿ äâóõ çàêàç÷èêîâ ñ öåíàìè 2358.03 è 1239.75.

2.5. Ìîäåëü II: êðèòåðèé îïòèìàëüíîñòè – ìàêñèìèçàöèÿ îæèäàåìîé öåíû (ñóììû öåí)

Êðèòåðèé îïòèìàëüíîñòè – ìàêñèìèçàöèÿ âå-ðîÿòíîñòè âûáîðà íàèëó÷øåãî çàêàç÷èêà, íå âñå-ãäà ìîæåò ïðèâåñòè ê ïîëó÷åíèþ íàèáîëüøåé öåíû.

Íàïðèìåð, åñëè íàèëó÷øèå çàêàç÷èêè îêàçàëèñü â ñàìîì íà÷àëå, òî ïî îïèñàííîé âûøå îïòèìàëüíîé ñòðàòåãèè ïðîäàâåö èõ íå ïðèìåò, è â ðåçóëüòàòå ìî-æåò ïîëó÷èòü 0.  ðåàëüíûõ ñèòóàöèÿõ ïðîäàâöó íå îáÿçàòåëüíî âûáèðàòü ñàìîãî ëó÷øåãî, îí ëèøü çà-èíòåðåñîâàí â óâåëè÷åíèè îæèäàåìîé ïðåäëàãàåìîé Òàáëèöà 5 Öåíû çàêàç÷èêîâ â îáëàñòè ïðîèçâîäñòâà è ïîñòàâîê N = 32, λλλλλ= 0,006

1 2 3 4 5 6 7 8 9

258.57 68.49 20.99 450 48.04 194.8 257.02 211.25 2358.03

10 11 12 13 14 15 16 17 18

Öåíû, â ó.å. 51.08 338.44 33 29.54 14.64 211.33 28.55 336.38 163.11

19 20 21 22 23 24 25 26 27

371.55 115.97 1239.75 222.03 146.41 115.97 28.63 72.6 44.5

28 29 30 31 32

35.53 311.13 18.2 22.94 41.19

öåíû. Èñïîëüçîâàíèå ïîèñêîâîé ñèñòåìîé òàêîãî êðèòåðèÿ îïòèìàëüíîñòè óìåíüøàåò âåðîÿòíîñòü âûáîðà íàèáîëüøåãî ïðåäëîæåíèÿ äëÿ êàæäîé îò-äåëüíîé ðåêëàìíîé êàìïàíèè, íî óâåëè÷èâàåò ñðåä-íåå ïîëó÷àåìîå çíà÷åíèå ïðè ïðîâåäåíèè áîëüøî-ãî ÷èñëà ðåêëàìíûõ êàìïàíèé.

Ðàññìîòðèì ìîäåëü, â êîòîðîé:

– ïîñëåäíèå çàêàç÷èêè ïðèíèìàþòñÿ;

– ïðîäàâåö ñòðåìèòñÿ ìàêñèìèçèðîâàòü ìàòåìà-òè÷åñêîå îæèäàíèå öåí (ñóììû öåí);

– ðàñïðåäåëåíèå öåí èçâåñòíî.

1) Âûáîð îäíîãî çàêàç÷èêà

Ðåøåíèå äàííîé çàäà÷è íàõîäèòñÿ ìåòîäàìè äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ. Îáîçíà÷èì u_i– âûèãðûø ïðîäàâöà íà øàãå i. Íà ïîñëåäíåì øàãå ïðîäàâåö ïðèíèìàåò ïîñëåäíåãî çàêàç÷èêà, è åãî âûèãðûø â ýòîì ñëó÷àå ðàâåí λ

) 1 x ( dF x u

0

N =

∫

^∞ = ^Íà

øàãå N-1 âûèãðûø ðàâåí

) x ( dF x ) x ( dF u u

N N

u u

0 N 1

N^{− =}

∫

⁺

∫

^∞

Íà øàãå i-1 âûèãðûø âû÷èñëÿåòñÿ ïî ðåêóð-ðåíòíîé ôîðìóëå

dx e x dx e u u

i i

u x x

u

0 i 1

i^{− =}

∫

^{λ −λ +}

∫

^{∞ λ −λ}

Ïîäñ÷èòàåì âûèãðûøè èãðîêà äëÿ äàííûõ, ïðåäîñòàâëåííûõ ïîèñêîâîé ñèñòåìîé ßíäåêñ.

 òàáë. 7 äàíû îïòèìàëüíûå ïîðîãè äëÿ ïðèíÿòèÿ ïðåäëîæåíèÿ çàêàç÷èêà ïðè N = 32 è λ= 0,006. Èñ-ïîëüçóÿ óêàçàííûå âûøå ôîðìóëû, ïîëó÷àåì ñëåäó-þùóþ îïòèìàëüíóþ ñòðàòåãèþ äëÿ ïðîäàâöà (ïðè-ìåíèòåëüíî ê äàííûì, ïðåäñòàâëåííûì â òàáë. 5):

ïðîäàâåö äîëæåí îñòàíîâèòüñÿ íà 9-ì øàãå.  ýòîì ñëó÷àå îí ïðèíèìàåò ïðåäëîæåíèå çàêàç÷èêà, ïðåä-ëîæèâøåãî öåíó 2358.03.

2) Âûáîð äâóõ çàêàç÷èêîâ

 äàííîé ìîäåëè ïðîäàâöó òðåáóåòñÿ âûáðàòü äâóõ çàêàç÷èêîâ. Ïðè ýòîì îí ñòðåìèòñÿ ìàêñè-ìèçèðîâàòü ìàòåìàòè÷åñêîå îæèäàíèå ñóììû ïðåä-ëàãàåìûõ öåí. Îïðåäåëèì ñëåäóþùèå ïîñëåäîâà-òåëüíîñòè, íà îñíîâå êîòîðûõ ñòðîÿòñÿ çíà÷åíèÿ âûèãðûøåé.

N m 1 k }, V E

; X X max{

V

1 N k 1 }, V E

; V E max{

V

1 m , k m , k m k m

, k

1 k k 1 k , k k k

≤

≤ + +

=

−

≤

≤

=

+ + +

0 u

; 0 u

1 N , k

1 N

=

=

+ +

Îáîçíà÷èì u_k – âûèãðûø èãðîêà íà øàãå k, åñëè îí âûáèðàåò ïåðâîãî çàêàç÷èêà, u_k,m – âûèãðûø èã-ðîêà íà øàãå m, åñëè îí âûáèðàåò âòîðîãî çàêàç÷è-êà ïðè óñëîâèè, ÷òî ïåðâîãî îí óæå âûáðàë íà øàãåk.

N m k u

; X max E u

N k u

; u X max E u

1 m , k m m

, k

1 k 1 k , k k k

≤

≤ +

=

−

≤

≤ +

=

+ + +

1 }), {

(

1 }),1

{ (

Âû÷èñëèì çíà÷åíèÿ âûèãðûøåé

) ( )

(

}) {

(

}) {

(

x dF x ) x ( dF u u u

u u

; X max E u

u

; u X max E u

1 k , k 1 k 1

k , k 1 k

u u u

u

0

1 k , k 1 k 1

k , k

1 k , k 1 k k 1

k , k

1 k 1 k , k k k

∫

∫

₋^∞

−

+ + +

+ + +

+ +

+ + +

+

+

− +

=

− +

=

+

=

) ( )

(

})

; { (

x dF x x dF u

u X max E u

1 m , k 1

m , k

u u

0 1 m , k

1 m , k m m

, k

∫

∫

^{+ ∞}

+

+ +

+

=

=

Äëÿ ïðèìåðà èç òàáë. 5 ïîëó÷èì, ÷òî îæèäàå-ìûå âûèãðûøè uk,mðàâíû âûèãðûøàì, ïîëó÷åí-íûì äëÿ ñëó÷àÿ, êîãäà âûáèðàåòñÿ îäèí çàêàç÷èê.

Ïîðîãè äëÿ ïðèíÿòèÿ ïåðâîãî çàêàç÷èêà äàíû â òàáë. 8.

Ðàññìîòðèì âèä îïòèìàëüíîé ñòðàòåãèè äëÿ N = 32 è λ= 0,006 (íà îñíîâå äàííûõ, ïðåäñòàâ-ëåííûõ â òàáë. 5). Íà êàæäîì øàãå óñòàíàâëèâà-þòñÿ ïîðîãè äëÿ ïðèíÿòèÿ ïðåòåíäåíòà. Ïî îïòè-ìàëüíîé ñòðàòåãèè ïåðâûì ïðèíèìàåòñÿ äåâÿòûé çàêàç÷èê, òàê êàê åãî öåíà 2358.03 áîëüøå îæèäàå-ìîãî âûèãðûøà íà äåñÿòîì øàãå (542.445), âòîðûì ïðèíèìàåòñÿ äåâÿòíàäöàòûé çàêàç÷èê, òàê êàê åãî öåíà âûøå îæèäàåìîãî âûèãðûøà íà ñëåäóþùåì øàãå (342.692).  ðåçóëüòàòå, ïðîäàâåö ïîëó÷àåò â ñóììå 2729.58.

Íåòðóäíî çàìåòèòü, ÷òî äëÿ ïðèâåäåííîãî ïðè-ìåðà îïòèìàëüíàÿ ñòðàòåãèÿ äàåò õîðîøèé, íî íå ñàìûé ëó÷øèé âîçìîæíûé ðåçóëüòàò.

2.6. Ìîäåëü III: Àäàïòèâíûå ìîäåëè äëÿ íåèçâåñòíîãî ðàñïðåäåëåíèÿ öåí Ðàññìîòðèì ìîäåëü, â êîòîðîé:

– ïîñëåäíèå çàêàç÷èêè ïðèíèìàþòñÿ;

– ïðîäàâåö ñòðåìèòñÿ ìàêñèìèçèðîâàòü ìàòåìà-òè÷åñêîå îæèäàíèå öåí (ñóììû öåí);

– âèä ðàñïðåäåëåíèÿ ïðåäëàãàåìûõ çàêàç÷èêàìè 0

V 0 V

1 N , k

1 N

=

=

+ +

k

k EV

u =

Òàáëèöà 7 Çíà÷åíèÿ âûèãðûøåé äëÿ N = 32 è λλλλλ= 0,006

k 1 2 3 4 5 6 7 8 9 10

592.863 587.968 582.922 577.717 572.341 566.783 561.029 555.066 548.877 542.445

11 12 13 14 15 16 17 18 19 20

535.749 528.767 521.472 513.835 505.822 497.393 488.503 479.096 469.109 458.462

u_k 21 22 23 24 25 26 27 28 29 30

447.062 434.791 421.501 407.004 391.05 373.304 353.294 330.327 303.321 270.421

31 32

227.98 166.667

öåí èçâåñòåí, íàïðèìåð, ýòî ýêñïîíåíöèàëüíîå ðàñ-ïðåäåëåíèå, íî ïàðàìåòð ýòîãî ðàñïðåäåëåíèÿ λ íå-èçâåñòåí.

Ïðåäëàãàåòñÿ àäàïòèâíàÿ ìîäåëü íàèëó÷øåãî âûáîðà, â êîòîðîé íà êàæäîì øàãå ïðîäàâåö íà îñ-íîâå ïîëó÷åííûõ ðàíåå ïðåäëîæåíèé îöåíèâàåò ïàðàìåòð ðàñïðåäåëåíèÿ öåí è, ó÷èòûâàÿ ñäåëàí-íóþ îöåíêó, ðåøàåò çàäà÷ó íàèëó÷øåãî âûáîðà.

Çàêîí ðàñïðåäåëåíèÿ èìååò âèä F(x) = 1–e^–λx, x ≥ 0.  äàííîé ïîñòàíîâêå ïàðàìåòð ë íåèçâåñòåí.

Îí îöåíèâàåòñÿ â ïðîöåññå íàáëþäåíèÿ. Òàê êàê ìàòåìàòè÷åñêîå îæèäàíèå òàêîãî ðàñïðåäåëåíèÿ ðàâ-íî 1/λ, òî â êà÷åñòâå îöåíêè ë èñïîëüçóåòñÿ ñòàòè-ñòèêà, ðàâíàÿ âåëè÷èíå, îáðàòíîé âûáîðî÷íîìó ñðåäíåìó, ò. å.

1

1

1 ⁻

= ⎟⎟⎠⎞

⎜⎜⎝⎛

=

=

∑

_jⁱ₁ ^j

i

i x

i

λ a .

Áóäåì ïðåäïîëàãàòü, ÷òî íà i-òîì øàãå èñïîëü-çóåòñÿ íåêîòîðàÿ îöåíêà λ_i ïàðàìåòðà λ. Çàòåì ñ÷è-òàåòñÿ, ÷òî ïîñëåäóþùèå íàáëþäåíèÿ ðàñïðåäåëå-íû ïî çàêîíó ñ ïîëó÷åíðàñïðåäåëå-íûì ïàðàìåòðîì. Ïî ìåðå ïîñòóïëåíèÿ èíôîðìàöèè îöåíêà óòî÷íÿåòñÿ.

Ïîñëå ïîëó÷åíèÿ î÷åðåäíîãî íàáëþäåíèÿ x_{i + 1} âûáîðî÷íàÿ ñðåäíÿÿ ïåðåñ÷èòûâàåòñÿ ïî ôîðìó-ëåa_i+₁=a_i+(x_i+₁−a_i)/(i+1)_.

Îáîçíà÷èì f_λ(x)– ïëîòíîñòü ýêñïîíåíöèàëüíîãî ðàñïðåäåëåíèÿ F_λ(x) ñ íåèçâåñòíûì ïàðàìåòðîì λ.

f_λ(x)=λe^-λx, x ≥ 0.

Îáîçíà÷èì ÷åðåç v(x, a, i), i = 1, …, N, ôóíêöèþ ìàêñèìàëüíîãî îæèäàåìîãî âûèãðûøà íà i-ì øàãå, êîãäà òåêóùàÿ îöåíêà ñðåäíåãî ðàâíà à. Òîãäà v óäîâ-ëåòâîðÿåò óðàâíåíèþ îïòèìàëüíîñòè

⎭⎬

⎫

⎩⎨

⎧ + −

=

−

∫

^∞

0

a /

1 t dt

f i a ,

a a t , x ( v , x max i

, a , x

v( 1) ) ( ) _.

 ñëó÷àå, åñëè äî ïîñëåäíåãî øàãà íå áûëî ñäåëà-íî âûáîðà, ïðîäàâåö âûíóæäåí îñòàñäåëà-íîâèòüñÿ íà ïîñ-ëåäíåì ïðåäëîæåíèè, ñëåäîâàòåëüíî, v(x, a, N)= x.

Íåòðóäíî äîêàçàòü, ÷òî ôóíêöèÿ v(x, a, i) èìååò âèä

v ⁽ x , a , i − ¹⁾ = max { x , a α

_i

} , i = 2 ,..., N − ¹

ãäå ïîñëåäîâàòåëüíîñòü α₁ óäîâëåòâîðÿåò ðåêóð-ðåíòíûì ôîðìóëàì

1

1

N₋

=

α

,...,α_i−₁=1+α_i(1−e^−β−βe^−β/i)−(1−e^−β−βe^−β)_, è ãäå, â ñâîþ î÷åðåäü,β =(i−1)α_i/(i−α_i).

Òåïåðü àäàïòèâíàÿ ñõåìà âûáîðà âûãëÿäèò ñëåäó-þùèì îáðàçîì.  íà÷àëå äëÿ çàäàííîãî îáúåìà

âû-áîðêè N âû÷èñëÿåòñÿ ïîñëåäîâàòåëüíîñòü α₁, i = N

–1, …, 2. Äàëåå íåîáõîäèìî ñëåäèòü çà ïîñòóïàþ-ùèìè ïðåäëîæåíèÿìè x_i, i= 1, 2, …. Ïî äàííûì íàáëþäåíèÿì ïåðåñ÷èòûâàåì òåêóùåå âûáîðî÷íîå ñðåäíåå a₁= x₁, ⁼

∑

₌ⁱ

1 j

j

i x

i

a 1 , i ≥ 2.

Íàêîíåö, ïðàâèëî îïòèìàëüíîãî âûáîðà âûãëÿ-äèò òàê. Êàê òîëüêî ïîñòóïèâøåå ïðåäëîæåíèå x_i áîëüøå èëè ðàâíîaαi, ïðîäàâåö âûáèðàåò ýòî íàáëþ-äåíèå.

Ïðîäåìîíñòðèðóåì ýòî íà ïðèìåðå, ðàññìîòðåí-íîì âûøå, ñ öåíàìè â îáëàñòè ïðîèçâîäñòâà è ïîñòàâîê.  ýòîì ïðèìåðå N= 32. Âíà÷àëå âû÷èñëÿåì ïîñëåäîâàòåëüíîñòü α_i, i= 2, …, N– 1. Ïîñëåäîâàòåëü-íî íàõîäèì α_N–1 = 1 è äàëåå äëÿ i = N– 2, …, 2

1.356; 1.598; 1.782; 1.932; 2.057; 2.165;

2.258; 2.342; 2. 416; 2. 482; 2.543; 2.598;

2.648; 2.693; 2.734; 2.772; 2.806; 2.837;

2.864; 2.889; 2.909; 2.927; 2.941; 2.952;

2.959; 2.963; 2.964; 2.965; 2.965.

Òåïåðü íàáëþäàåì çà ïðåäëîæåíèÿìè è ñðàâ-íèâàåì èõ ñ âåëè÷èíàìèaαi. Íà ïåðâîì øàãå èìååì a₁= x₁= 258.57. Íà âòîðîì øàãå îöåíêà a₂= 163.530 è, çíà÷èò, a₂α₂= 484.966. Ïîñêîëüêó ïîñòóïèâøåå ïðåäëîæåíèå x₂= 68.49 ìåíüøå ýòîãî ïîðîãà, îòâåð-ãàåì ïðåäëîæåíèå. Íà òðåòüåì øàãå îöåíêà ñðåäíå-ãî a₃= 116.017, è, çíà÷èò, ïîðîã ðàâåí a₃α₃= 343.989.

Ïîñòóïèâøåå íàáëþäåíèå x₃= 20.99 îïÿòü ìåíüøå ïîðîãà, åãî òàêæå îòâåðãàåì. Â òàáë. 9 äàíû ïîðîãè äëÿ äàííîãî ïðèìåðà.

Òàáëèöà 9 Çíà÷åíèÿ ïîðîãîâ äëÿ N = 32

Øàã à_i aiαi

1 258.57 766.660

2 163.530484.866

3 116.017 343.989

4 199.521 591.355

5 169.205 501.393

6 173.491 513.332

7 185.426 547.347

8 188.644 554.855

9 429.738 1257.700

Òàáëèöà 8 Çíà÷åíèÿ ïîðîãîâ äëÿ N = 32 è λλλλλ= 0,006

k 1 2 3 4 5 6 7 8 9 10

472.395 467.347 462.138 456.758 451.196 445.437 439.469 433.274 426.836 420.132

11 12 13 14 15 16 17 18 19 20

413.141 405.837 398.189 390.163 381.719 372.811 363.383 353.369 342.692 331.252

21 22 23 24 25 26 27 28 29 30

318.932 305.579 290.997 274.929 257.021 236.771 213.422 185.748 151.49 105.353

31 32

0

1 k ,

uk

u_k+₁− ₊

Ïîñëåäîâàòåëüíî âû÷èñëÿÿ ïîðîãè ÷åðåç ïîñòó-ïèâøèå íàáëþäåíèÿ íà øàãàõ i= 4, 5, …, 8, ïðåäëî-æåíèÿ ïîñëåäîâàòåëüíî îòâåðãàþòñÿ, íî íà 9-ì øàãå ïîñòóïèâøåå ïðåäëîæåíèå x₉= 2358.03 çíà÷èòåëü-íî ïðåâûøàåò ïîðîã 1257.700, ïîýòîìó ýòî ïðåäëî-æåíèå âûáèðàåòñÿ.

2.7. Ìîäåëü IV: Òåîðåòèêî-èãðîâàÿ ïîñòàíîâêà çàäà÷è ñ äâóìÿ êîíêóðèðóþùèìè ïîèñêîâûìè ñèñòåìàìè

Îñîáûé èíòåðåñ ïðåäñòàâëÿþò òåîðåòèêî-èãðîâûå ïîñòàíîâêè çàäà÷è íàèëó÷øåãî âûáîðà. Òàêèå ìî-äåëè ïîçâîëÿþò èññëåäîâàòü âçàèìíîå âëèÿíèå äâóõ êîíêóðèðóþùèõ ïîèñêîâûõ ñèñòåì íà îïòèìàëüíûå ñòðàòåãèè ïîâåäåíèÿ äðóã äðóãà ïðè ïîèñêå íàèëó÷-øåãî çàêàç÷èêà ðåêëàìíûõ êîìïàíèé.

 ïðåäñòàâëåííîé ðàáîòå èññëåäóåòñÿ ìîäåëü, â êîòîðîé îäíà èç ïîèñêîâûõ ñèñòåì ÿâëÿåòñÿ çíà÷è-òåëüíî áîëåå ïðèâëåêàçíà÷è-òåëüíîé (äîìèíèðóåò), íåæå-ëè âòîðàÿ. Ýòî îçíà÷àåò, ÷òî êàæäûé ïîòåíöèàëü-íûé çàêàç÷èê ðåêëàìíîé êàìïàíèè îáðàùàåòñÿ ñî ñâîèì ïðåäëîæåíèåì â ïåðâóþ ïîèñêîâóþ ñèñòåìó è ëèøü â ñëó÷àå îòêàçà, îáðàùàåòñÿ êî âòîðîé ïî-èñêîâîé ñèñòåìå. Òàêàÿ ñèòóàöèÿ äàåò ëó÷øèå øàí-ñû íà ïîëó÷åíèå âûèãðûøà äëÿ äîìèíèðóþùåãî èãðîêà.

Ðàññìîòðèì èãðó äâóõ ïðîäàâöîâ. Äâà ïðîäàâöà (I è II èãðîêè) õîòÿò âûáðàòü ïî äâà çàêàç÷èêà. Çà-êàç÷èêè ïîñòóïàþò ïîñëåäîâàòåëüíî è ïðåäëàãàþò öåíû, èìåþùèå ôóíêöèþ ðàñïðåäåëåíèÿ F(x). Èã-ðîêè ñòðåìÿòñÿ ìàêñèìèçèðîâàòü ñóììó ïðåäëàãàå-ìûõ çàêàç÷èêàìè öåí.

Ðàññìîòðèì ñëó÷àé, êîãäà èìååòñÿ äîìèíèðóþ-ùèé èãðîê (I èãðîê), ò. å. ïðè âñòðå÷å ñ î÷åðåäíûì çàêàç÷èêîì, çàêàç÷èê ðåøàåò ðàçìåñòèòü ñâîþ ðåê-ëàìó ó I èãðîêà, è ëèøü ïîëó÷èâ îòêàç, óõîäèò êî II èãðîêó.

Îáîçíà÷èìuk¹,m_,u_k²_,m âûèãðûøè èãðîêîâ: åñëè îñòàëñÿ òîëüêî îäèí èãðîê (äðóãîé èãðîê óæå âûá-ðàë îáîèõ çàêàç÷èêîâ) è äâà èãðîêà ñîîòâåòñòâåí-íî, ïðè ýòîì èãðîê óæå âûáðàë îäíîãî çàêàç÷èêà íà øàãå k (1 ≤ k ≤ N – 1, 2 ≤ m ≤ N) • u_k¹,uk² _–

âûèãðûøè èãðîêîâ äëÿ âûáîðà ïåðâîãî çàêàç÷èêà, åñëè îñòàëñÿ îäèí èãðîê èëè äâà èãðîêà ñîîòâåò-ñòâåííî.

Äëÿ ïåðâîãî èãðîêà îïòèìàëüíî âåñòè ñåáÿ òàê (â ñèëó åãî äîìèíèðóåìîñòè), åñëè áû îí îäèí âû-áèðàë çàêàç÷èêîâ. Åãî âûèãðûøè ðàâíû u¹k,m è u¹k

ñîîòâåòñòâåííî. Äëÿ âòîðîãî èãðîêà, åñëè ïåðâûé èãðîê óæå âûáðàë çàêàç÷èêà, âûèãðûøè òàêæå ðàâ-íû u¹k,m è u¹k ñîîòâåòñòâåííî.

Âû÷èñëèì uk²,m è uk². Ïðè ýòîì âûèãðûø âòîðî-ãî èãðîêà áóäóò çàâèñåòü îò òîâòîðî-ãî, âûáðàë ëè ïåðâûé èãðîê ïåðâîãî çàêàç÷èêà èëè íåò. Îáîçíà÷èì âûèã-ðûøè âòîðîãî èãðîêà, åñëè ïåðâûé èãðîê âûáðàë çàêàç÷èêà íà øàãå p êàê u²_{k, m+1}(IB), u²_{k, m+1}(IH), u²_k(IB), u²_k(IH).

Ó÷èòûâàÿ u²_{k, k+ 1} ≤ u¹_{k, k+ 1} ≤ u²_{k+ 1} ≤u¹_{k+ 1} ïîëó÷àåì çíà÷åíèÿ îæèäàåìûõ âûèãðûøåé

) x ( dF u

) x ( dF x ) x ( dF ) ( u

}) u );

( u

; X (max{

E ) ( u

1 m , 1p

1 m , 1p

1 m , 2k 1

m , 2k

u 1 m , k 1

u

u )

( u

0 1 m , 2k

1 m , 1k 1

m , 2k m 2

m , k

∫

∫

∫

∞ + +

+ +

+

+

+ +

+

+ +

=

=

=

B) (I B

I

B I

B I B

I

) x ( dF ) ( u

) x ( dF x ) x ( dF ) ( u

)}) ( u );

( u

; X (max{

E ) ( u

1 1 m , 1 m 1m

1 1 m , 1 m 1m

1 m , 2k 1

m , 2k

u u

1 m , 2k

u u

u )

( u

0 1 m , k 2

1 m , 2k 1

m , 2k m 2

m , k

∫

∫

∫

∞

− +

− +

+ +

+ +

+ +

+ +

+

+ +

=

=

=

B I H I

B I H

I H

I

H) (I H

I

Âûèãðûøè âòîðîãî èãðîêà ïðè âûáîðå ïåðâîãî çàêàç÷èêà âû÷èñëÿþòñÿ ñëåäóþùèì îáðàçîì

) x ( dF )]

( u u [ ) x ( dF x

) x ( dF )]

( u ) ( u [ )

( u

}) u );

( u );

( u X (max{

E ) ( u

1 k , 1p 1

k , 1p

1 k , 2k 1 2k

1 k , 2k 1 2k

u

1 k , k 2 1 k 1 u

) ( u ) ( u

) ( u ) ( u

0

1 k , 2k 1

2k 1

k , 2k

1 k 1 1

k 2 1

k , k 2 k 2

k

∫

∫

∫

∞

+ +

−

−

+ +

+

+ +

+

+ +

+ +

+ +

− +

+

+

− +

=

= +

=

B I

B I B

I B

I

B I B

I B

I

B I B I

B I B I

) x ( dF )]

( u ) ( u [ ) x ( dF x

) x ( dF )]

( u ) ( u [ )

( u

)}) ( u );

( u );

( u X (max{

E ) ( u

1 1 k , 1 k 1k 1

1 k , 1 k k 1

1 k , 2k 1 2k

1 k , 2k 1 2k

u u

1 k , k 2 1

k 2 u

u

) ( u ) ( u

) ( u ) ( u

0

1 k , k 2 1

k 2 1

k , k 2

1 k 2 1 k 2 1 k , k 2 k 2

k

∫

∫

∫

∞

−

+ +

−

−

−

+ +

+

+ +

+

+ + + +

+ +

+ +

− +

+

+

− +

=

= +

=

H I B

I

H I H

I H

I

H I H I H I H

I

H I H I

H I H I

Ðàññìîòðèì ðåøåíèå çàäà÷è äëÿ êîíêðåòíîãî ïðèìåðà (ñì. òàáë. 5), ó÷èòûâàÿ äàííûå ïî ïðåäëî-æåííûì öåíàì.

Îïòèìàëüíûå ñòðàòåãèè ïðîäàâöîâ âûãëÿäÿò ñëåäóþùèì îáðàçîì:

I ïðîäàâåö, ó÷èòûâàÿ ñâîå äîìèíèðóþùåå ïî-ëîæåíèå, äåéñòâóåò òàê, êàê áóäòî îí îäèí ïðè-ñóòñòâóåò íà ðûíêå. Ïîýòîìó åãî âûèãðûøè ñî-âïàäàþò ñî ñëó÷àåì, ðàññìîòðåííûì â íåèãðîâîé ìîäåëè.

II-ìó ïðîäàâöó íåîáõîäèìî îïòèìàëüíî äåé-ñòâîâàòü ñëåäóþùèì îáðàçîì.

Íà êàæäîì øàãå óñòàíàâëèâàþòñÿ ïîðîãè äëÿ ïðèíÿòèÿ ïðåòåíäåíòà. Ïî îïòèìàëüíîé ñòðàòåãèè ïåðâûì ïðèíèìàåòñÿ ÷åòâåðòûé çàêàç÷èê, òàê êàê åãî öåíà 450 áîëüøå îæèäàåìîãî âûèãðûøà íà ïÿ-òîì øàãå (341.109), âòîðûì ïðèíèìàåòñÿ äåâÿòíàä-öàòûé çàêàç÷èê, òàê êàê åãî öåíà 371.55 âûøå îæè-äàåìîãî âûèãðûøà (342.692).  ðåçóëüòàòå îí

ïîëó-÷àåò â ñóììå 821.55.

Ðåçóëüòàòû èññëåäîâàíèé ïîêàçûâàþò, ÷òî âòî-ðîé ïðîäàâåö â ñèëó åãî âòîðè÷íîãî ïîëîæåíèÿ ïî-ëó÷àåò âîçìîæíîñòü ïðèíèìàòü çàêàç÷èêîâ ñ íå

ñà-Òàáëèöà 10 Çíà÷åíèÿ ïîðîãîâ äëÿ N= 32 è λλλλλ= 0.006

k

1 k , k

1 1 k 1

u u

− +

+ 1

1 k ,

uq ₊

H) (I

H) (I

2 1 k , k

1 2k

u u

+ +

− (IH)

1 k , 2p

u +

Â) (I

1 k , 2p

u +

1 472.395 356.768

2 467.347 351.713

3 462.138 346.497

4 456.758 341.109

5 451.196 383.552

6 445.437 377.789

7 439.469 371.815

8 433.274 365.615

9 426.836 359.169

10535.749 420.132

11 528.767 413.141

12 521.472 405.837

13 513.835 398.189

14 505.822 390.163

15 497.393 381.719

16 488.503 372.811

17 479.096 363.383

18 469.109 353.369

19 458.462 342.692

20447.062

21 434.791

ドキュメント内 untitled (ページ 127-134)