Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Визначення оптимального рішення у матричній грі

Теорія ігор

У теорії ігор досліджуються в умовах невизначеності рішення, що приймаються декількома супротивниками, кожний з яких прагне оптимізувати свої рішення за рахунок інших. До типових прикладів подібних ситуацій можна віднести рекламування конкуруючих товарів та тактичне планування дій протидіючих армій.

Супротивників у теорії ігор звичайно називають гравцями. Кожний гравець має деяку множину можливих дій. Результати гри залежать від дій кожного гравця. Ігри з двома гравцями, у яких виграш одного гравця дорівнює програшу іншого, називають іграми двох осіб з нульовою сумою. У такій грі достатньо задати результати (наприклад, у вигляді виграшів) для одного гравця. Для цього застосовують матрицю А = || aij || i,j =1 m,n, рядки якої відповідають діям одного гравця, а стовпці – діям іншого. Значення елементу aij дорівнює виграшу (програшу) одного гравця при виборі ним i-ї дії і виборі другим гравцем j-ї. Задача полягає у визначенні найкращої у певному розумінні дії кожого гравця.

Оскільки вихідні дані задаються за допомогою матриці подану задачу ще називають матричною грою.

У поданій задачі розглядається граничний випадок повної відсутності інформації у одного гравця про дії іншого. Враховуючи, що гравці знаходяться у стані конфлікту, доцільним вважають застосування найбільш обережного критерію, тобто критерію мінімакса-максиміна. При цьому дії одного гравця для іншого відіграють роль станів абстрактної системи, про яку шла мова при розгляданні загальної задачі прийняття рішення в умовах невизначеності.

Згідно з критерієм мінімакса-максиміна для кожного гравця обирається дія, яка дає найкращий результат у найгіршому випадку. Кажуть, що оптимальне рішення отримано, якщо жодному з гравців невигідно змінювати варіант дії. Якщо існує така ситуація, то гра називається стабільною, а при обраних вказаним чином діях вважають, що гра знаходиться у стані рівноваги.

Надалі будемо вважати, що рядки матриці А відповідають діям гравця 1 і містять виграши цього гравця. Стовпчики матриці А відповідають діям гравця 2. Тоді застосування максимінного критерія для гравця 1 призводить до вибору рядка, мінімальний елемент у якому має найбільше значення. Для гравця 2 застосування мінімаксного критерія призводить до вибору стовпчика, максимальний елемент у якому має найменше значення. Нехай, для гравця 1 обрано рядок r, а для гравця 2 - стовпчик s. Якщо елемент ars є мінімальним у рядку r і разом з тим максимальним у стовпчику s, то кажуть, що гра має сідлову точку. Наявність сідлової точки є характерною властивістю стабільної гри.

У загальному випадку поведінка гравця являє собою застосування кожної дії з деякою ймовірністю при умові, що у кожному випадку якась дія обов’язково застосовується. Таким чином, якщо за умовою задачі для гравця визначені m можливих дій, то поведінка гравця визначається сукупністю чисел x1, x2, …, xm таких, що xi = 1 та xi ³ 0, i = 1, m. Така поведінка гравця називається стратегією. Вибір однієї дії, коли деяке xi = 1, а усі інші дорівнюють нулю, називається чистою стратегією. У випадку, коли принаймні дві дії обираються з ненульовою ймовірністю, поведінка гравця називається змішаною стратегією. Спочатку обмежемося розгляданням чистих стратегій і розв’яжемо приклад матричної гри, для якої вихідні дані наведені у табл.17.1.

Таблиця 17.1
Стратегії гравця 2 Мінімуми у рядках  
Стратегії гравця 1            
           
           
    -4     -4
Максимуми у стовпцях          
                 

Гравець 1, обираючи другу стратегію (дію), максимізує свій мінімальний виграш при будь-якій стратегії другого гравця: max{2, 5, -4} = 5. Обрана гравцем 1 стратегія називається максимінною, а відповідне значення виграшу – максимінним (нижнім) значенням гри.

Гравець 2, обираючи третю стратегію мінімізує свій максимальний програш: min{8, 5, 9, 18} = 5. Ця стратегія називається мінімаксною, а відповідне значення програша гравця B – мінімаксним (верхнім) значенням гри.

З означення прямує, що мінімаксне значення завжди не менше максимінного. Дійсно, нехай ars - мінімаксне значення і atu - максимінне. Тоді маємо ars ³ ats ³ atu. У випадку, коли має місце рівність (як у розглянутому прикладі), відповідні чисті стратегії називаються оптимальними, а про гру кажуть, що вона має сідлову точку. Оптимальність вказаних стратегій означає, що жодному гравцю невигідно змінювати стратегію, оскільки зміна стратегії кожним гравцем при незмінній стратегії супротивника не призводить до покращення результату.

<== предыдущая лекция | следующая лекция ==>
Для розглянутого вище прикладу матриця жалю приймає вигляд | Математического описания алгоритма работы информационной системы
Поделиться с друзьями:


Дата добавления: 2014-01-13; Просмотров: 440; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.012 сек.