Ойын теориясының элементтері
Шешуші нүктесі жоқ ойындарды шешу
жүктеу/скачать 31,61 Kb.
|
Ерболат Нұрай-СӨЖ теория игр
| Шешуші нүктесі жоқ ойындарды шешу
Жалпы шешуші нүктесі бар ойындар аз кездеседі. Көп ойындардың шешуі нүктесі болмайды. Полковник Блоттоның ойыны да осы ойындарға жатады. Толық информациялы ойындардың әруақытта шешуші нүктесі болатындығы дәлелденген. Егер ойынның шешуші нүктесі болмаса, онда А ойыншы өзінің максимин стратегисын қолданып отырып V1-ден кем ұтпайды, ал В ойыншысы V2 –тық ұтылмайды. Мұндай ойындардың кезкелген партиясында таза стратегияны қолданып ойыншылардың ұтысын арттыру немесе ұтылысын кеміту мүмкіндік бермейді. Ал ол мүмкін болуы үшін таза стратегияны жиілігін өзгертіп, кездейсоқ ауыстырып бірнеше рет қайталау керек. Мұндай стратегиялар аралас деп аталады. Олардың элементтері таза стратегиялар. Біржүрісті ойынның бір партиясында ойыншы бір ғана таза стратегияны қолданады. А және В ойыншыларының аралас стратегиясын SA=(p1, p2…pi…pm) және SB=(q1, q2…qj…pn) деп белгілейік. Мұндағы pi А ойыншының таза стратегиясын қолдану ықтималдығы (жиілік), ал qj В ойыншының стратегиясын қолдану (жиілігі) ықтималдығы. А және В ойыншыларының аралас стратегияларының нөлден өзге Ықтималдықтары pi және qj бар стратегиялары белсенді деп аталады. Ойын теориясының негізгі теоремасы (минимакс туралы теорема). Кез-келген қосындысы нӛл болатын екі жақтың аяқталған ойынының кем дегенде бір шешімі болады, яғни жалпы жағдайда бағасы болатын аралас жұп оптималды стратегиясы болады. Шешуші нүктесі болмайтын ойындардың шешімі әртүрлі әдістермен алынады. Ондай ойындардың кейбірінің шешімі сызықтық программалау есептеріне келтіріледі.Реті (mxn) болатын шешуші нүктесі жоқ төлем матрицасы берілсін. Ойында сызықтық программалау есептеріне келтіру үшін, артық стратегияларынан құтылып, оңайлату керек. 1 кестесіндегі ойыннның оңайлату процесін қарастырайық. 1 кесте
Бірінші А ойыншысыың стратегиясын қарайық. Матрицаны талдау А1 стратегиясы А3 стратегиясын қайталағанын кқріп тұр. Сондықтан біреуін А3(А1) шығаруға болады. А1 жолындағы барлық ұтыс А2 жолындағылардан тең немесе үлкен, сондықтан А1 қарағанда А2 стратегиясы пайдасыз. Оны алып тастауға болады. Қысқартулардан кейінгі ойын түрі 2 кестеде көрсетілген. 2 кестесі бойынша В ойыншының стратегияларын таңдаймыз. Вj бағанасындағы ұтылыстар В4 үлкен, яғни ол B үшін тиімісіз. Сондықтан В3 алып тастап, 3 кестеде берілген ойынды аламыз. (4x4) тӛлем матрицасы қысқартулар көмегімен (2x3) ретті матрицаға айналады.
2 кесте 3 кесте
Ойынды сызықтық программалау есебіне келтіруді сипаттайық. Төлем матрицасының барлық aij элементтері оң болсын. Ол үшін матрицаның барлық мүшесіне үлкен оң M санын қосу керек. Одан ойынның бағасы V(M)-ге артады, ал есептің шешімі . Егер aij оң болса, онда ойынның бағасы V>0. Ойынның шешімін, яғни екі оптималды аралас стратегияны =(p1, p2…pi…pm) және =(q1, q2…qj…pn) әрбір ойыншы үшін мүмкін болатын максималды орташа ұтысты (минималды орташа ұтылыс) табу керек. Бірінші табайық. А ойыншысы В ойыншысының стратегиясы қандай болған күнде де ӛзінің оптиальды стратегиясын қолдана отырып V кем ұтыс алмайды. Яғни, оны былай аламыз: а11p1+a21p2+…am1pm ≥ V а12p1+a22p2+…am2pm ≥ V … … … … … … … а1np1+a2np2+…amnpm ≥ V Теңсіздіктің екі жағын V оң санына бөлеміз. а11 + a21 +…+ am1 ≥1 а12 + a22 +…+ am2 ≥1 … … … … … … … а1n + a2n +…+ amn ≥1 Төмендегідей белгілеулер енгіземіз: x1= , x2= ,…,xi= ,…,xm= Бұл жүйе мына түрге енеді: а11x1+a21x2+…am1xm ≥ 1 а12x1+a22x2+…am2xm ≥ 1 … … … … … … … а1nx1+a2nx2+…amnxm ≥ 1 xi ≥ 0 (i=1,m) xi (i=1,m) және p1+p2+…pm=1 болғандықтан айнымалылар x1, x2, … , xm мына шартты қанағаттандырады: x1+ x2+ … + xm = V шамасы А ойыншысының кепілді ұтысы, v шамасы максималды,ал минималды болуы керек.Сонымен, ойынның шешімі мынадай есепке келтірілді. Сызықтық шектеулер – теңсіздікті қанағаттандырып, осы айнымалылардың сызықтық функциясын минимумға айналдыратын, x1, x2, … , xm айнымалыларының оң мәндерін табу керек, яғни: F = x1+ x2+ … + xm → min мына түрге енеді: а11x1+a21x2+…am1xm ≥ 1 а12x1+a22x2+…am2xm ≥ 1 … … … … … … … а1nx1+a2nx2+…amnxm ≥ 1 xi ≥ 0 (i=1,m) Бұл жүйе сызықтық программалау есебіне жатады. x1, x2, … , xm мәндерін анықтаған соң p1, p2, … , pm, v табамыз. Яғни оптималды стратегиясын табамыз. В ойыншысының оптималды стратегиясы осыған ұқсас табылады. Тек қана В өз ұтылысын (v) минималдауы қажет, яғни шамасы максималды, ал шектеулер «≤» түріне енуі керек.В ойыншысы үшін сызықтық программалау есебі мынадай түрде болады: Z=y1+y2+…+yn → max а11y1+a21y2+…am1ym ≥ 1 а12y1+a22y2+…am2ym ≥ 1 … … … … … … … а1ny1+a2ny2+…amnym ≥ 1 yj ≥ 0 (j=1,m) Соңғы жүйе қосалқы жұп есепті көрсетеді. Қосалқы есептің негізгі теоремасы бойынша min F = max Z. Яғни, бағасы тең, олай болса шешуші нүктесі бар Аралас стратегиядағы ойын. Негізгі анықтамалар Модель өзімен қоса онда бар белгілерді жасайтын анықталған жүйені суреттейді. Математикалық программалау моделі көмегімен экономикалық процесстерді тексеру тапсырмаларды қарау. Ағымды мәліметтердің тапсырмаларымен және ағымды шешімдер арасындағы математикалық қатынастарды анықтайды. Жалпы жағдайда кіріске тәуелді шығатын мәліметтерді анықтайтын қатынастардың жиынтығын жүйенің немесе процесстің математикалық моделі деп атайды. Математикалық модельдердің тапсырмалары негізгі тапсырманың формальді құрамын көрсетеді. Негізгі тапсырмаларының құрамын бейнелейтін математикалық формулалар сызықты теңдеулер түріндегі процесстер тапсырмалардың формализациясы деп аталады. Математикалық программалу экстремальді тапсырмаларының теориялық негізін құрайды. Математикалық программаның құрылымдық бөлігі болып сызықтық, сызықтық емес және тапсырмаларды шешуде ең қолайлысы сызықтық программалау әдісі болып табылады. Олар экономикалық және өндірістік тапсырмаларда кең таралған. Программалық тапсырмаларды экономика – математикалық әдісі мен оптималды шешуде, оптималды критериясын таңдауға көңіл бөлу керек. Яғни экстремалды тапсырманы қажет ететін экономикалық көрсеткіш. Берілген тапсырманың негізімен оптималды критерияны таңдау қажет. Мысалға, экономикалық топтастырудың оптиамльды критериесін таңдауда бірден, халық шаруашылық экономикалық эффектифтілігін қарайтын процестердің бейнелейтін көрсеткішке бағдарлау керек. Сонымен қатар өзгерістерді көрсететін кезеңдерін және бұл эффективті деңгейін көрсететін кәсіпорын жұмыстарының көрсеткішін бағдарлау қажет. Жеңіл өндірістік кәсіпорын жұмыстарының жетекші көрсеткіштері болып жалпы рентабельдік, суммалық және жеке пайда капиталды шығындарды алатын мерзімі, фонды (отдача) қайтару өнімдерінің фондтық көлемі, өнімнің еңбек көлемі және т.б. экстималды экономикалық тапсырмалардыңоптимальды критериелерін шешу теңдеу түрінде алатын мақсаттық тәуелділіктерде көрсетіледі. Сондықтан оптимальды критериелердің теңдеулері мақсатталған функция деп аталады. Әрбір экономикалық экспериментальды тапсырмаға бір мақсатталған функция сәйкес келеді. Яғни сызықты программалау әдісі арқылы шешілетін әрбір осындай тапсырмаларда критери көрсеткіштерінің тек бір максимальды немесе минимальды мәндері бар екенін білдіреді. Әрине, әрбір экстримальды тапсыпманы әр түрлі оптимальды критериелерге қатысты шешуге болады. Өндірістік немесе экономикалық тапсырманың модельі кесіп орынның жұмыс істеу шарттарын көрсету керек. Сондықтан мұндай программаға мақсатталған функциядан басқа қосымша шарттар керек. Мысалы, теңсіздіктер және теңдеулерде көрсетілген. Бұл теңдеулер және теңсіздіктер шектеу жүйесін құрайды. Ал теңсіздіктер мен теңдеулердің өздері шектеулі деп аталады. Осылайша экстримальды тапсырмалар модельдерінің құрылуында шектеулердің біреуінде моделдің әрбір ауыспалы көлемі теріс мәнге ие бола алмайды. Ал теңдеулердің шектеулі жүйесіндегі әрбір бас бөлігі он мәнге немесе нолге тең болуы керек. Белгісіздерге қатысты шектеулі теңдеулерінің жүйесінің шешімі тапсырмаларының жіберілетін шешімін көрсетеді. Ал оның жіберілетін шешімдерінің бірі тапсырманың оптимальды шешімі болып табылады, оның математикалық моделі құралған және басқару параметрлері үшін байланыстар анықталған тапсырмаларды шешу үшін есептелінетін алгоритмді құруды базалайтын арнайы ережелер қолданылады. Алгоритм – қойылған тапсырмаларды шешу үшін қажет. жүктеу/скачать 31,61 Kb. Достарыңызбен бөлісу:
|