Най-четените учебни материали
Най-новите учебни материали
SMS Login
За да използвате ПЪЛНОТО съдържание на сайта изпратете SMS с текст STG на номер 1092 (обща стойност 2.40лв.)| Теория на игрите |
 |
 |
 |
|
Теория на игрите В много задачи изследването на операции се налага де се решават задачи от изследване на операциите свързани с проблеми на взимане на решение в условия на неопределеност Неопределености могат да бъдат условия за изпълнение на операции,или съзнателни действия на противника от които зависи успеха на операцията. неопределеностите в една или друга степен могат да се отнасят към успеха на операцията. Този успех не винаги зависи от пълното изчерпване на един показател – ефективност на операцията. При решаването на различни практически задачи от изследване на операциите се налага де се анализират ситуации, в които имаме две или повече враждуващи страни, преселващи различни цели, от които зависи успеха на операцията. Такива операции ние ще наричаме конфликтни операции. От необходимостта да се анализират такива ситуации е разработен спирален математически апарат наречен теория на игрите. Всяка непосредствена ситуация от практиката е много сложна и анализирането и е от многото привлечени, несъществени фактори. За да се анализират такива модели е необходимо да се игнорират второстепенни фактори от които не зависи успеха на играта, и този модел ние ще наричаме игра. От реално ситуация на която ние изграждаме модел, използващ определени правила. При формализирането на тези правила са реализирани на различни игри като игра на шашки, шах, дама и др. Нека имаме игра от двама участника А и В с противоположни интереси. Под игра ще разбираме мероприятие или ред от действия или ходове от страна на А и В. За да анализираме играта е необходимо да формираме правила на играта т.е система от условия регламентиращи: 1 възможни варианти от действия на играта; 2 обем от информация за всяка страна от поведение на другия играч; 3 резултат (изход) от играта, който ще получим от определени действия на играчите. Игра с нулева сума се нарича ако единия играч печели толкова колкото губи другия т.е сумата от спечеленото от двете страни е равно на нула. В играта с нулева сума интересите на противниците са противоположни. ние ще разглеждаме само такива игри. Развитието на играта във времето ние ще представяме като последователност от действия или ходове. Ход в теория на игрите е да изберем едно от възможните правила за действия в играта и неговото реализиране. Ходовете биват лични или случайни. Лични ходове ще наричаме съзнателния избор на играча на един от възможните варианти от действия и неговото реализиране. Случайни ходове ще наричаме избор от вариант от възможните действия, реализиран по случаен принцип (хвърляне на монета, избор на карта и др). За всеки случаен ход правилата на играта определят вероятностно разпределение от възможните изходи. Стратегия на играта ще наричаме съвкупност от правила, определяща избора на вариант от действия при всеки личен ход на играча в зависимост от ситуацията. Една игра ще бъде наричана крайна, ако за всеки играч има само краен брой стратегии или безкрайно ако броят е безкраен. Оптималната стратегия на играча наричаме такава стратегия, която при многократно повторение на играта обезпечава на дадения играч максимална възможност за средно спечелване (или минимална възможност за средна загуба). При избора на тази стратегия основното предположение е, че противника също е разумен, като нас и ни пречи да постигнем нашите цели. Платежна матрица Нека разгледаме крайна игра, в която играча А (ние) има m стратегии, а В (противника) – n стратегии. Такава игра наричаме m x n. ще означим нашите стратегии с A1, А2, ..., Am , а стратегиите на противника с В1, В2, ..., Вn. Предполагаме, че всяка страна избира стратегия: ние избираме стратегия Ai, а противника Bj. Ако играта се състои само от лични ходове, то избора на стратегии Ai, Bj еднозначно определя изхода от играта – спечелване или загуба, което ние означаваме с aij. Ако играта съдържа освен лични ходове и случайни, то при избраната двойка стратегии Ai, Bj съдържа и случайни величини. В този случай естествена оценка на очаквания печеливш е математическото очакване. Ние ще го означаваме със същия знак като при игра само с лични ходове с aij. Да предположим, че са ни известни значенията на aij. Те могат да бъдат записани в таблица:
Тази таблица наричаме платежна матрица или просто матрица на играта.
Долна и горна цена на играта. Принцип на минимакса. Разглеждаме матрица mxn.
Поставяме задача: Поставяме задача: да се определи най-добрата от нашите стратегии А1, А2,....Аn. Анализираме всяка от тях като започваме с А1 до Аn. Избираме Ai и съответно си мислим, че противника е избрал стратегия Bj, с която шанса ни да спечелим е минимален. Намираме минималното число aij и в iтата - колоната го обозначаваме с i: (знакът означава минималното значение на дадения параметър при всички възможни стойности на j). Написваме минималната стойност на редовете от дясно като допълнителна колона:
Избираме стратегия Аi, ние предполагаме, че в резултат от разумните действия на противника ще спечелим само i. Естествено действайки най-внимателно т.е. избягвайки всякакъв риск, ние сме длъжни да изберем стратегия, която i, е максимално Като използваме предишната формула получаваме: Величината наричаме долна цена на играта или с други думи казано максиминимум спечелено или максиминимум. Стратегията на играча А, която съответства на се нарича максиминимална стратегия. Очевидно аналогични разсъждения могат да се направят и за противника. Той е заинтересован да промени нашия резултат т.е да загубим. Написваме максималното значение на aij по стълбове и намираме техният минимум. или Величината се нарича горна цена на играта или минимакса на спечеленото Стратегията съответстваща на се нарича минимаксимална стратегия. Игрите, при които = се наричат игри със седлова точка. В матрицата на такава игра този елемент е минимален в своя ред и максимален в своя стълб. Този елемент се нарича седлова точка. Общото значение на долната и горната граница на играта е = = се нарича чиста цена на играта. Стратегии, които имат случайно редуване на чисти стратегии, се наричат игри със смесени стратегии. Въвеждаме специални обозначение за смесени стратегии Нека имаме игра И, в която ние имаме стратегии A1, А2, ..., Am , а стратегиите на противника с В1, В2, ..., Вn. Ще означаваме нашата смесена стратегия с , в която нашите стратегии A1, А2, ..., Am приемат вероятностите , където . Аналогично обозначаваме и смесените стратегии на противника Където Решението на играта наричаме двойката оптимални стратегии в общия случай смесени стратегии, имащи следните свойства ако един от играчите използва своята оптимална стратегия, за другия не е изгодно да отстъпва от своята оптимална стратегия. Печелившото решение се нарича цена на играта и ще го обозначаваме с . Всяка крайна игра има поне едно възможно решение в областта на смесените стратегии. Всяка крайна игра има цена , която е между долната и горната цена на играта. . Действително е максималната цена, която ние можем да спечелим като използваме само чисти стратегии. Тъй като при смесените стратегии се съдържат и случайни стратегии, освен чисти, ние няма да използваме максимално своите възможности т.е. . Аналогичните разсъждения провеждаме и за противника т.е. . Предполагаме, че играта е mxn, тогава нейното решение е , Решение на играта mxn Трябва да намерим две оптимални смесени стратегии на играчите А и В: , , Където - вероятности за приемане на чисти стратегии, някои от тях съответстват на неактивни стратегии и могат да са равни на нула. Нашата оптимална стратегия ни осигурява печалба, при всякакво поведение на противника, не по малка от цената на играта , освен това всяко от числата аj не може да бъде по малко от . Разделяме неравенствата на положителната величина и въвеждаме означенията Тогава тези Където са неотрицателни числа и от въведените по –горе означения Променливите удовлетворяват условието
Ние желаем да гарантираме максимална печалба на печелившия играч. Очевидно е, че дясната част на горното равенство трябва да е минимално. Да се определят неотрицателните променливи удовлетворяващи условията дефинирани преди малко т.е. min
Е типична задача линейна оптимизационна задача. З да намерим оптималната стратегия на играча В решаваме обратната задача
Където са неотрицателни променливи и трябва да се максимизира линейната функция max
|