Шешуші нҥктесі жоқ ойындарды шешу

Жалпы шешуші нүктесі бар ойындар аз кездеседі. Көп ойындардың шешуі нүктесі болмайды. Полковник Блоттоның ойыны да осы ойындарға жатады. Толық информациялы ойындардың әруақытта шешуші нүктесі болатындығы дәлелденген.

Егер ойынның шешуші нүктесі болмаса, онда A ойыншы өзінің максимин

стратегисын қолданып отырып ⁿ¹ ден кем ұтпайды, ал B ойыншысы ^{n 2} ден артық ұтылмайды. Мұндай ойындардың кезкелген партиясында таза стратегияны

қолданып ойыншылардың ұтысын (ⁿ¹ ) арттыру немесе ұтылысын (^{n 2} ) кеміту мүмкіндік бермейді. Ал ол мүмкін болуы үшін таза стратегияны жиілігін өзгертіп, кездейсоқ ауыстырып бірнеше рет қайталау керек. Мұндай стратегиялар аралас деп аталады. Олардың элементтері таза стратегиялар.

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

ықтималдықтары ^pi және ^{q j} бар стратегиялары белсенді деп аталады.

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

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

Реті ( ^{m ´ n} ) болатын шешуші нүктесі жоқ төлем матрицасы берілсін. Ойында сызықтық программалау есептеріне келтіру үшін, артық стратегияларынан құтылып, оңайлату керек. 7.3 кестесіндегі ойыннның оңайлату процесін қарастырайық.

Кесте

Бірінші A ойыншының стратегиясын қарайық. Матрицаны талдау ^A1 стратегиясы ^A3 стратегиясын қайталағаны көрініп тұр. Сондықтан біреуін ^A3 ( ^A1 ) шығарып тастауға болады. ^A1 жолындағы барлық ұтыс ^A2 жолындағылардан тең немесе

үлкен, сондықтан ^A1 қарағанда ^A2 стратегиясы пайдасыз. Оны алып тастауға болады. Қысқартулардан кейінгі ойын түрі 7.4 кестеде көрсетілген.

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

Ойынды сызықтық программалау есебіне келтіруді сипаттайық. Төлем

матрицасының барлық ^aij элементтері оң болсын. Ол үшін матрицаның барлық мүшесіне үлкен оң M санын қосу керек. Одан ойынның бағасы (ⁿ ) M -ге артады, ал

әрбір ойыншы үшін мүмкін болатын максималды орташа ұтысты (минималды

орташа ұтылыс) табу керек. Бірінші ^{S A*} табайық. A ойыншысы B ойыншысының стратегиясы қандай болған күнде де өзінің оптиальды стратегиясын қолдана отырып ⁿ кем ұтыс алмайды. Яғни, оны былай аламыз:

Теңсіздіктің екі жағын ⁿ оң санына бөлеміз:

Төмендегідей белгілеулер енгіземіз:

сызықтық функциясын минимумға айналдыратын, ^{x1 , x2 ,} оң мәндерін табу керек, яғни:

(7.3) сызықтық программалау есебіне жатады. ^{x1 , x2 , ..., xm}

^{..., x}n _{айнымалыларының}

мәндерін анықтаған соң

^p1 ^{, p}2 ^{, ..., p}m _, n _{табамыз, яғни} B ойыншысының оптималды

^{S A*} оптималды стратегиясын табамыз.

стратегиясы осыған ұқсас табылады. Тек қана B өз

ұтылысын (ⁿ ) минималдауы қажет, яғни ⁿ шамасы максималды, ал шектеулер « £ » түріне енуі керек.

B ойыншысы үшін сызықтық программалау есебі мынадай түрде болады:

Z = y₁+ y₂+...+ y_n ®max

(7.3) және (7.4) қосалқы жұп есепті көрсетеді.

Қосалқы есептің негізгі теоремасы бойынша ^{min f = max Z} . Яғни, бағасы тең, олай болса шешуші нүктесі бар.

38. Таза және аралас стратегия және ершік нүктені анықтау

Ойын теориясының негізін салушы американ математигі Дж Фон Нейман 1928 ж. ойын теориясының негізгі теоремасы – мини-макс теоремасын дәлелдеп берді.Ойын теориясы 1944 ж. Дж Фон Нейман және тО.Моргенштерннің “Ойын теориясы және экономикалық тәртіп’ атты кітабы жарыққа шыққан соң жылдам дами бастады.Ойын теориясының дамуына электронды есептегіш машиналарының жетілдірілуі де үлкен әсерін тигізді.

Практикалық есептерде белгісіз шарттар арқылы шешім қабылдау керек. Ондай шарттарды «ситуация» деп атаймыз. Ондай ситуациялар келесі ойындарда болуы мүмкін: шахмат, шашка, домино және т.б., ал экономикада ол банк пен клиент, сатушы мен сатып алушы және т.с.с. Әрбір ойында ережелер беріледі. Егер ойынға қатысушылар екеу болса, онда ойын «жұп» деп аталады. Егер көп болса, «көптік» ойын деп аталады. Есептерде ойын төлем матрицасы арқылы беріледі. Әрбір матрицаның бағасы болады: - төменгі баға, - жоғарғы баға.

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

Анықтама 2. ойынның жоғарғы бағасы немесе минимакс, ал оған сәйкес ойыншы стратегиясы (баған) – минимаксті деп аталады.

Анықтама 3. Егер болса, онда ойынның таза бағасы деп аталады. Егер таза бағасы табыса, онда есеп «таза стратегия» арқылы есептеледі деп саналады.

Мысалы:

Ойынның бағасын анықтау керек. Төлем матрицасы берілген.

	В1	В2	В3
А1	0,5	0,6	0,8	0,5
А2	0,9	0,7	0,8	0,7
А3	0,7	0,6	0,6	0,6
	0,9	0,7	0,8