13.4 2Хn матрицалық ойындардың геометриялық шешімі

ойыншының – 2 таза стратегиясы, ойыншының – таза стратегиясы бар ойынды қарастырайық.

.

стратегиясының тиімділік көрсеткіші мына формуламен есептеледі:

.

Егер болса, онда болғандықтан . Сонда, мына формуламен өрнектеледі:

. (10.27)

Сонымен, ықтималдығы болатын сызықтық , функцияның төменгі орайжанауышын береді, олардың әрқайсысының графигі осы сызықтық функцияның бұрыштық коэффициентінің оң, теріс немесе нөлге тең болуына тәуелді өспелі (оң көлбеу), кемімелі (теріс көлбеу) немесе горизонталь кесінді болады.

, (10.28)

теңдігін қанағаттандыратын стратегиясы тиімді (матрицалық ойындардың фон Нейманның негізгі теоремасы бойынша) болып табылады, яғни төменгі орайжанауыштың максимал (ең жоғарғы) нүктесінің абсциссасы ойыншы өзінің таза стратегиясын ықтималдықпен, стратегиясын ықтималдықпен болатындай кездейсоқ таңдайтын тиімді стратегиясын анықтайды, мұндағы – ойыншының барлық аралас (олардың ішінде таза стратегия да бар) стратегиялар жиыны.

Матрицалық ойындардың негізгі фон Нейман теоремасы бойынша ойынның құны

, (10.29)

яғни ойынның құны төменгі орайжанауыштың максимал нүктесінің ординатасына тең.

Сонымен, ойыншының тиімді стратегиясы мен ойын құнын табудың геометриялық (графикалық) алгоритмін жазайық.

Алгоритм « »

1. горизонталь кесіндісін қарастырамыз.

2.  кесінділерінің ұштары арқылы сол жақ және оң жақ екі перпендикуляр жүргіземіз.

3. 0 нүктесінен кесіндісімен қиылысқандағы вертикаль сандық осьтің бойында жататын сол жақ перпендикулярдың бойынан матрицасының бірінші жолының барлық элементтерін белгілейміз.

4. 1 нүктесінен кесіндісімен қиылысқандағы (вертикаль сандық осьтегі сияқты) жүргізілген оң жақ перпендикулярдың бойынан матрицасының екінші жолының барлық элементтерін белгілейміз.

Ескерту. Сол жақ және оң жақ перпендикулярлардағы масштаб бірдей болу керек, бірақ горизонталь кесіндінің масштабымен бірдей болу міндетті емес.

5. матрицасының -ші, бағанында орналасқан және элементтерін бейнелейтін нүктелердің әрбір жұбын кесіндісімен қосамыз.

Осылайша, сызықтық функцияның графигін беретін

, , (10.30)

кесінділер тұрғызылады.

6. Егер , барлық кесінділер кемімелі емес (теріс емес көлбеуі бар) болса, онда стратегиясы стратегиясын доминациялайды.

Егер , барлық кесінділер өспелі (оң көлбеуі бар) болса, онда стратегиясы стратегиясын қатаң доминациялайды.

7. Егер , барлық кесінділер өспелі емес (оң емес емес көлбеуі бар) болса, онда стратегиясы стратегиясын доминациялайды.

Егер , барлық кесінділер кемімелі (теріс көлбеуі бар) болса, онда стратегиясы стратегиясын қатаң доминациялайды.

8. Егер кесіндісі , , кесіндісінен төмен емес орналасса, онда стратегиясы стратегиясын доминациялайды.

Егер кесіндісі , , кесіндісінен жоғары орналасса, онда стратегиясы стратегиясын қатаң доминациялайды.

9. Дербес жағдайда кесінді болуы мүмкін, жалпы жағдайда жоғары дөңес қисықты беретін (10.30) кесінділер үйірінің (10.27) төменгі орайжанауышын табамыз.

10. Төменгі орайжанауыштың максимал (ең жоғарғы) нүктесін (немесе нүктелерін) табамыз.

11. Осы нүктенің абсциссасы ((10.28) теңдікті қанағаттандыратын) ойыншының тиімді аралас стратегиясындағы таза стратегиясын таңдау ықтималдығы болып табылады.

12. Төменгі орайжанауыштың ең жоғарғы нүктесінің ординатасы ойынның құнын береді ((10.29) қараңыз).

13. Төменгі орайжанауыштың перпендикулярларда жатқан екі шетінің жоғарғысы ойынның таза стратегиялардағы төменгі құнын береді.

14.  , кесінділерінің шеттерінің жоғарғыларының төменгісі ойынның таза стратегиялардағы жоғарғы құнын береді.

15. Өзі орналасқан перпендикулярда төменгі нүкте болып табылатын және кесіндінің жоғарғы шеті болып табылатын матрицасының элементі ойынның ер нүктесі болып табылады.

Бұл жағдайда нөмірі ер нүктенің екінші индексімен беттесетін ойыншының таза стратегиясы тиімді болып табылады.

10.8-суретте , – кесінділерінен төменгі орайжанауышты анықтауға қатысты үшеуі көрсетілген; – осы орайжанауыштың максимал нүктесі; – нүктесінің абсциссасы; демек, – ойыншының тиімді аралас стратегиясы; ойын құны нүктесінің ординатасына тең; таза стратегиялардағы ойынның төменгі құны: ; таза стратегиялардағы ойынның жоғарғы құны: ; суреттен көрініп отырғандай .

0 1

10.8-сурет

Теорема 10.12. Егер , кесінділерінің төменгі орайжанауышының ойыншының , таза стратегияларымен жасақталатын максимал нүктесі арқылы қандай да бір мен , , кесінділері өтсе, онда нүктесінің абсциссасы

(10.31)

және демек,

, (10.32)

ал ойынның құны

. (10.33)

(10.31), (10.32) және (10.33) формулаларда және болған кезде сәйкес (10.24) қатынасының екінші формуласын, (10.24) қатынасының бірінші формуласын және (10.25) қатынасын аламыз.

Біз төменгі орайжанауыштың максимал нүктесі арқылы бірден артық кесінді өтетінін қарастырдық (10.8-сурет). Практикада нүктесі арқылы бір ғана кесінді өтетін жағдай да кездеседі. 10.9, 10.10, 10.11 және 10.12-суреттерде төменгі орайжанауыштың максимал нүктесі арқылы жалғыз ғана кесіндісі өтеді. Егер кесіндісі кесіндісіне параллель болса, онда максимал нүктелері қандай да бір аралықты толықтырады. 10.9-суретте төменгі орайжанауыштың максимал нүктесі кесіндісінің бөлігін, атап айтқанда, аралығын, 10.10-суретте кесіндісін толығымен толықтырады. Сондықтан, 10.9-суретте ойыншының тиімді стратегиялар жиыны

мұндағы және төменгі орайжанауыштың сәйкес және шеттік максимал нүктелерінің абсциссалары. Бұл жиыны кесіндісімен өрнектеледі.

0 1	0 1
10.9-сурет	10.10-сурет

10.10-суретте ойыншының тиімді стратегиялар жиыны оның барлық стратегиялар жиынымен беттеседі:

және кесіндісімен өрнектеледі; дербес жағдайда, оның және таза стратегиялары да тиімді болып табылады.

10.11-суретте кесіндісі кесіндісіне параллель емес және оң көлбеу болғандықтан, жалғыз максимал нүкте оң жақ перпендикулярда жатады. Сондықтан, ойыншының таза стратегиясы жалғыз тиімді стратегия болып табылады.

0 1	0 1
10.11-сурет	10.12-сурет

Егер кесіндісінің теріс көлбеуі бар болса, онда жалғыз максимал нүктесі сол жақ перпендикулярда жатады және таза стратегиясы ойыншының жалғыз тиімді стратегиясы болып табылады. 10.9-суретте ойыншының тиімді стратегиялар жиынын бейнелейтін кесіндісі кесіндісінің ішінде жатқандықтан ер нүкте жоқ. Осы себеппен барлық тиімді стратегиялар аралас стратегиялар болып табылады. Ойынның құны таза стратегиядағы ойынның жоғарғы құнымен беттеседі.

10.10 және 10.11-суреттерде элементі, 10.12-суретте элементі ер нүкте болып табылады.

Теорема 10.13. , кесінділерінің төменгі орайжанауышының ойыншының , таза стратегияларымен жасақталатын максимал нүктесі арқылы қандай да бір мен , , кесінділері өтсін.

ойыншының аралас стратегиясы тиімді болу үшін мен кесінділерінің көлбеулері әр түрлі болу керек, мұндағы

, (10.34)

, (10.35)

, . (10.36)

және болған кезде (10.34) формула (10.26) қатынасының бірінші формуласына, ал (10.35) формула (10.26) қатынасының екінші формуласына айналады.

Егер кесіндісі горизонталь болса, онда ойыншының стратегиясы тиімді.

және кесінділерінің бұрыштық коэффициенттері

_{, .}

және кесінділерінің көлбеулері бірдей болғандықтан олар не екеуі де оң, не екеуі де теріс, не екеуі де нөлге тең болады. Осы кездегі барлық мүмкін болатын жағдай 10.1-кестеде келтірілген.

10.1-кесте

№			-
1	>0	>0	<0	>0	<0
2	>0	>0	<0	<0	>1
3	>0	>0	<0	=0	=-∞
4	<0	<0	>0	<0	<0
5	<0	<0	>0	>0	>1
6	<0	<0	>0	=0	=+∞
7	=0	=0	=0	=0	=0/0

10.1-кестеде келтірілген 1-7 жағдайлардың геометриялық инерпретациясы 10.13-10.19 суреттерде бейнеленген.

0 1	0 1	0 1
10.13-сурет	10.14-сурет	10.15-сурет

0 1	0 1	0 1
10.16-сурет	10.17-сурет	10.18-сурет

0 1

10.19-сурет

10.1-кестенің соңғы бағаны ( )

формуласының көмегімен толтырылады, және кестеден көріп отырғанымыздай ықтималдық бола алмайды.

және кесінділерінің көлбеулері әр түрлі жағдайды қарастырайық. Бұл кездегі барлық мүмкін болатын жағдайдың саны 6-ға тең (10.2-кестеде келтірілген).

10.2-кесте

№			-
1	>0	>0	>0	>0	>0
2	>0	=0	=0	= >0	=0
3	<0	>0	<0	<0	>0
4	<0	=0	=0	= <0	=0
5	=0	>0	<0	=- <0	=1
6	=0	<0	>0	=- >0	=1

(10.15), (10.16), (10.17) формулаларының көмегімен , кесіндісінің төменгі орайжанауышының максимал нүктесі арқылы көлбеуі әр түрлі болатын олардың (кесіндінің) тек қана екеуі өтетін жағдайдағы ойыншының тиімді стратегиясын табуға болады.

Максимал нүктесі арқылы бірдей көлбеуі бар екі кесінді өтетін барлық мүмкін болатын жағдай 10.1-кестеде келтірілген және 10.13-10.19 суреттерде геометриялық бейнеленген. 10.1-кестедегі 1, 2, 3 жағдайларда және оларға сәйкес 10.13, 10.14, 10.15-суреттерде элементтері ер нүктелері болып табылады; ал, 10.1-кестедегі 4, 5, 6 жағдайларда және оларға сәйкес 10.16, 10.17, 10.18-суреттерде элементтері ер нүктелері болып табылады және 10.1-кестедегі 7-жағдайда, 10.19-суретте элементтері ер нүктелері болып табылады. Сондықтан, 10.1-кестедегі барлық жағдайда (1-7) және стратегиялары тиімді болып табылады.

Енді , кесінділерінің төменгі орайжанауышының максимал нүктесі арқылы олардың біреуі өтетін жағдайды қарастырайық. Егер осы кесіндінің көлбеуі нөлден өзге болса (егер ол горизонталь болмаса), онда нүктесі кесіндісіне перпендикулярлардың біреуінде жатады. 10.20-суретте кесіндісінің оң көлбеуі бар және нүктесі оң жақ перпендикулярда жатыр. Бұл жағдайда элементі ер нүкте болып табылады. 10.21-суретте кесіндісінің көлбеуі теріс; нүктесі сол жақ перпендикулярда жатыр; элементі ер нүкте. 10.22-суретте кесіндісінің әрбір нүктесі максимал және элементтері ер нүкте болып табылады.

Сондықтан, 10.20, 10.21, 10.22-суреттерде бейнеленген барлық үш жағдайда да стратегиясы тиімді болып табылады.

0 1	0 1	0 1
10.20-сурет	10.21-сурет	10.22-сурет

Салдар 10.1 (10.13-теоремадан алынады). Егер 10.13-теореманың шартындағы кесіндісі горизонталь болмаса, яғни нөлдік емес көлбеуі бар болса, онда ойыншының таза стратегиясы белсенді болып табылады.

Осылайша, егер кесіндісі горизонталь болмаса, онда ойыншының таза стратегиясы белсенді болып табылады.

Сонымен, егер мен кесінділерінің біреуі де горизонталь болмаса, онда мен стратегиялары белсенді болып табылады.

Салдар 10.2 (10.13-теоремадан алынады). Егер 10.13-теореманың шартындағы кесіндісі горизонталь болса, онда ойыншының стратегиясы тиімді.

Егер кесіндісі горизонталь болса, онда ойыншының стратегиясы тиімді.

(10.34), (10.35), (10.36) формулаларының көмегімен , кесіндісінің төменгі орайжанауышының максимал нүктесі арқылы әр түрлі көлбеудегі олардың екеуі өтетін жағдайдағы ойыншының тиімді стратегиясын табуға болады.

Енді , кесінділерінің төменгі орайжанауышының максимал нүктесі арқылы олардың біреуі өтетін жағдайды қарастырайық. Егер осы кесіндінің көлбеуі нөлден өзге болса (егер ол горизонталь болмаса), онда нүктесі кесіндісіне перпендикулярлардың біреуінде жатады. 10.20-суретте кесіндісінің оң көлбеуі бар және нүктесі оң жақ перпендикулярда жатыр. Бұл жағдайда элементі ер нүкте болып табылады. 10.21-суретте кесіндісінің көлбеуі теріс; нүктесі сол жақ перпендикулярда жатыр; элементі ер нүкте. 10.22-суретте кесіндісінің әрбір нүктесі максимал және элементтері ер нүкте болып табылады

Сондықтан, 10.20, 10.21, 10.22-суреттерде бейнеленген барлық үш жағдайда да стратегиясы тиімді болып табылады.

Осы тақырыптағы ойынына жүргізілген талдаудан және ойыншыларының әрқайсысының екіден артық емес таза стратегиясы бар тиімді стратегиясының болатыны алынды.

10.14-мысал.

_{ұтыс матрицасымен берілген ойынның шешімін табу керек.}

Шығарылуы. _; ; _; .

9

8

7

6

5

4

3

2

1

0 1

Ойынның ер нүктесі жоқ. Сондықтан ойынның тиімді шешімін аралас стратегиялар облысынан іздейміз. Жазықтықта екінші ойыншының стратегияларына сәйкес кесінділерді тұрғызамыз.

А алгоритмін пайдаланып, есепті талдайық.

кесіндісі кесіндісінен (өспелі, оң көлбеуі бар) жоғары жатқандықтан стратегиясы стратегиясын қатаң доминациялайды.

кесіндісі кесіндісінен (кемімелі, теріс көлбеуі бар) жоғары жатқандықтан стратегиясы стратегиясын қатаң доминациялайды. Яғни екінші ойыншыға және стратегияларын ұстаған қолайлы емес, сондықтан оларды қолдану ықтималдығы нөлге тең: , .

Доминациялау принципін пайдалана отырып берілген ұтыс матрицасын редуциялау нәтижесінде ұтыс матрицасын аламыз:

Алынған ойынды өзімізге белгілі тәсілдердің біреуімен шешіп мына шешімді аламыз:

; ; ; . .

Жауабы. Ойыншылардың тиімді аралас стратегиялары:

; . Ойынның құны: .

10.15-мысал.

_{ұтыс матрицасымен берілген ойынның шешімін табу керек.}

_{Шығарылуы. А алгоритмі бойынша берілген ойынның геометриялық бейнесін тұрғызамыз.}

Кесінділердің төменгі орайжанауышы қалыңдатылып боялған. Оның максимал нүктесі – . нүктесінің абсциссасын табу үшін қиылысуында осы нүкте жатқан екі түзуді жүйе ретінде шешеміз.

₀

Немесе (10.31) формулада және мәндерінде

.

_{мәнін аламыз. Осыдан}

.

(10.33) формула бойынша ойынның құны

.

Төменгі орайжанауыштың перпендикулярлардағы екі төменгі мәндердің ( және ) жоғарғысы , сондықтан таза стратегиялардағы ойынның төменгі құны .

Жоғарғы ұштардың ( , , , ) арасындағы ең төменгі нүкте . Сондықтан таза стратегиялардағы ойынның жоғарғы құны .

Сонымен, . Ойында ер нүкте жоқ.

Жауабы. , .

14-лекция. Жаппай қызмет көрсету жүйелері