3. Ойындар теориясының есептерін сызықтық программалау есептеріне келтіру
Келесі матрицамен анықталатын,
ойының қарастырайық:
Нейманның екінші теоремасына сәйкес, бірінші ойыншының
тиімді стратегиясы және ойын бағасы v үшін келесі теңсіздік орындалады:
.
Айталық,
болсын деп жорамалдайық. Мұндай жағдайды, А матрицасының барлық
элементтеріне тұрақты бір С саның қосу арқылы алуға болады. Бұл тиімді
шешімге ешқандай әсерін тигізбейді, тек ғана ойынның бағасы С шамасына
артық болады.
Енді соңғы теңсіздіктің екі жағын v –ға бөлсек, онда
.
;
.
Жоғарыдағы еңгізілген белгілеуді пайдалансақ, онда
шарты келесі түрде болады:
Бірінші ойыншы максимальды ұтыс алғысы келетіндіктен, ол
шамасын минимдауға ұмтылуы керек. Осыны ескерсек, бірінші ойыншының тиімді
стратегиясын анықтау, келесі функцияның минимальды мәнің анықтауға келтіріледі:
келесі шарт жағдайында
;
.
Осыған ұқсас талқылаулар арқылы, екінші ойыншының тиімді стратегиясын анықтау келесі функцияның максимальды мәнің анықтауға келтіріледі:
келесі шарт жағдайында
.
Мұнда
,
ал
екінші ойыншының тиімді стратегиясы.
Сонымен, А матрицасы арқылы анықталатын ойынды шешу үшін келесі қос екі жақты есепті құрып, оның шешімін табу керек болады.
Тура есеп:
(3.6)
функцияның максимальды мәнің келесі шарт жағдайларында анықтау керек:
;
.
Екі жақты есеп:
(3.7)
функцияның максимальды мәнің келесі шарт жағдайларында анықтау керек:
;
.
Қос екі жақты есептің шешімдерін пайдаланып, ойынның тиімді стратегияларын және бағасын анықтайтын формуланы аламыз:
;
(3.8)
.
Сонымен, ойынның шешімін сызықтық программалау әдістері арқылы табу келесі қадамдардан тұрады:
1-қадам. Матрицалық ойынға эквивалентті (3.6) және (3.7) қос екі жақты сызықтық программалау есептерін құрамыз.
2-қадам. Қос екі жақты есептердің тиімді жоспарларын анықтаймыз.
3-қадам. Қос екі жақты есептің тиімді жоспарлары мен ойынның тиімді стратегиялары және бағасы араларындағы (3.8) қатынасты пайдаланып ойынның шешімін анықтаймыз.
Мысал 6. Келесі матрица арқылы берілген ойынның шешімін анықтайық:
Шешуі. Сызықтық программалау есебінің қос екі жақты есебін құрамыз: тура есеп:
функциясының максимумын келесі шарт жағдайларында анықтау керек:
Екі жақты есеп:
функциясының минимумын келесі шарт жағдайларында анықтау керек:
Тура және екі жақты есептің тиімді жоспарларын анықтаймыз (кесте 3.1).
Кесте 3.1
|
РБ |
СБ |
Р0 |
1 |
1 |
1 |
0 |
0 |
0 |
|
Р1 |
Р2 |
|
Р4 |
Р5 |
Р6 |
|||
|
Р4 |
0 |
1 |
1 |
2 |
0 |
1 |
0 |
0 |
|
Р5 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
|
Р6 |
0 |
1 |
2 |
1 |
0 |
0 |
0 |
1 |
|
D J |
0 |
—1 |
—1 |
—1 |
0 |
0 |
0 |
|
|
Р4 |
0 |
1 |
1 |
2 |
0 |
1 |
0 |
0 |
|
Р3 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
|
Р6 |
0 |
1 |
2 |
1 |
0 |
0 |
0 |
1 |
|
D j |
1 |
0 |
—1 |
0 |
0 |
1 |
0 |
|
|
Р2 |
1 |
1/2 |
1/2 |
1 |
0 |
1/2 |
0 |
0 |
|
Р3 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
|
Р6 |
0 |
1/2 |
3/2 |
0 |
0 |
-1/2 |
0 |
1 |
|
D j |
3/2 |
1/2 |
0 |
0 |
1/2 |
1 |
0 |
|
3.1-кестеден көрініп тұрғандай тура есептің тиімді жоспары X*=(0; 1/2; 1), ал екі жақты есептің тиімді жоспары У*=(1/2; 1; 0) болатының көру қиын емес. Онда ойынның бағасы
,
ал ойыншылардың тиімді стратегиялар U*=(l/3; 2/3;0); Z*=(0; 1/3;
2/3) түрінде болады.
Жауабы:
Жоғарыда, кез келген матрицалық ойын үшін симметриялық қос екі жақты есеп құруға болатының көру қиын емес. Керісінше тұжырым да дұрыс: кез келген симметриялық қос екі жақты есеп үшін матрицалық ойынды жазуға болады.
Айталық симметриялық қос екі жақты есеп берілсін:
Тура есеп Екі жақты есеп
Онда осы симметриялық қос екі жақты есепке келесі матрица арқылы анықталатын ойын сәйкес келеді:
мұндағы Т индексі транспонирлеу амалын білдіреді.
Ескерту 3.1. егер кез келген матрицалық ойынның тиміді стратегиялары бар болса да, кез келген сызықтық программалау есебінің шешімі бола бермейтінің ескертеміз.
Ойындар теориясы, адам өмірінің келеспеушілік немесе анықталмағандық жағдайларында шешім қабылдауға тура келетін кез келген қызмет салаларында кездесуі мүмкін.
