Теорія Ігор
Теорія Прийняття рішень
© ЄА.
Лавров, 2014-2019/14
Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Основи Теорії Ігор
Содержание
- 1. Основи Теорії Ігор
- 2. Основи Теорії Ігор Теорія Прийняття рішень © ЄА. Лавров, 2014-2019/30
- 3. Слайд 3
- 4. Лекція 7. Основні поняття Теорії ІГОРЗміст лекції:1.
- 5. Теоретико-системные основы математического моделирования (с) Н.М. Светлов,
- 6. Теорія ігор .Проблема Прийняття рішень в умовах
- 7. Теорія ігор .Проблема Прийняття рішень в умовах
- 8. Теорія ігор .Проблема Прийняття рішень в умовах
- 9. Теоретико-системные основы математического моделирования (с) Н.М. Светлов,
- 10. 2. Оптимальне рішення гри двох
- 11. 2. Оптимальне рішення гри двох
- 12. 2. Оптимальне рішення гри двох
- 13. 2. Оптимальне рішення гри двох осіб з
- 14. 2. Оптимальне рішення гри двох осіб з
- 15. 2. Оптимальне рішення гри двох осіб з
- 16. 2. Оптимальне рішення гри двох осіб з
- 17. 2. Оптимальне рішення гри двох осіб з
- 18. 2. Оптимальне рішення гри двох осіб з
- 19. 2. Приклад2. Максиміна і мінімаксна
- 20. 2. Приклад2. Постійна спокуса кожного гравця
- 21. 2. Оптимальне рішення гри двох
- 22. 2. Оптимальне рішення гри двох
- 23. 2. Оптимальне рішення гри двох
- 24. 2. Оптимальне рішення гри двох
- 25. 2. Оптимальне рішення гри двох
- 26. Слайд 26
- 27. 3Рішення матричних ігор у змішаних стратегіях
- 28. 3Рішення матричних ігор у змішаних
- 29. Теоретико-системные основы математического моделирования (с) Н.М. Светлов,
- 30. 3Рішення матричних ігор у змішаних
- 31. 3Рішення матричних ігор у змішаних
- 32. 3Рішення матричних ігор у змішаних
- 33. 3Рішення матричних ігор у змішаних
- 34. 4. Рішення матричних ігор методами лінійного програмування Теорія Прийняття рішень © ЄА. Лавров, 2014-2019/100
- 35. 4. Рішення матричних ігор методами
- 36. 4. Рішення матричних ігор методами
- 37. Довідка
- 38. 4. Рішення матричних ігор методами
- 39. 4. Рішення матричних ігор методами
- 40. 4. Рішення матричних ігор методами
- 41. 4. Рішення матричних ігор методами
- 42. 4. Рішення матричних ігор методами
- 43. 4. Рішення матричних ігор методами
- 44. 5. Приклад рішення матричної гри методами лінійного програмування Теорія Прийняття рішень © ЄА. Лавров, 2014-2019/100
- 45. 5. Приклад рішення матричної гри методами лінійного
- 46. 5. Приклад рішення матричної гри методами лінійного
- 47. 5. Приклад рішення матричної гри методами лінійного
- 48. Теоретико-системные основы математического моделирования (с) Н.М. Светлов, 2006/20
- 49. Теоретико-системные основы математического моделирования (с) Н.М. Светлов, 2006/20
- 50. Скачать презентанцию
Основи Теорії Ігор Теорія Прийняття рішень © ЄА. Лавров, 2014-2019/30
Слайды и текст этой презентации
Слайд 4Лекція 7. Основні поняття Теорії ІГОР
Зміст лекції:
1. Теорія ігор .Проблема
Прийняття рішень в умовах конфлікту
2.Оптимальне рішення гри двох осіб з
нульовою сумою.3.Рішення матричних ігор у змішаних стратегіях
4. Рішення матричних ігор методами лінійного програмування
5. Приклад рішення матричної гри методами лінійного програмування
Теорія Прийняття рішень
© ЄА. Лавров, 2014-2019
/100
Слайд 5Теоретико-системные основы математического моделирования
(с) Н.М. Светлов, 2006
/20
1.Теорія ігор .Проблема
Прийняття рішень в умовах конфлікту
Слайд 6Теорія ігор .Проблема Прийняття рішень в умовах конфлікту
В теорії ігор
розглядаються ситуації, пов'язані з прийняттям рішень, в яких :
два розумних
противника мають конфліктуючі цілі.
типові приклади
рекламування конкуруючих товарів
планування військових стратегій протиборчих армій.
Відмінність від попередніх ситуацій
Раніше природа не виступала в ролі противника (недоброзичливця)
яким відповідають платежі,
які залежать від випадкових станів
природи.
Теорія Прийняття рішень
© ЄА. Лавров, 2014-2019
/14
Слайд 7Теорія ігор .Проблема Прийняття рішень в умовах конфлікту
В ігровому конфлікті
беруть участь два противника, іменовані гравцями,
кожен з яких має
деяку множину (кінцеву або нескінчену) можливих виборів, які називаються стратегіями. З кожною парою стратегій пов'язаний платіж, який один з гравців виплачує іншому.
Такі ігри відомі як ігри двох осіб з нульовою сумою, (виграш одного гравця дорівнює програшу іншого).
У такій грі достатньо задати
результати у вигляді платежів
для одного з гравців.
Теорія Прийняття рішень
© ЄА. Лавров, 2014-2019
/14
Слайд 8Теорія ігор .Проблема Прийняття рішень в умовах конфлікту
При позначенні гравців
через А і В з числом стратегій
n і m
відповідно гру зазвичай представляють у вигляді матриці платежів гравцеві А:Таке представлення матричної гри означає, що
якщо гравець А використовує стратегію i,
а гравець В - стратегію j,
то платіж гравцеві А становить аij і, отже,
гравцеві В - (-аij ).
Теорія Прийняття рішень
© ЄА. Лавров, 2014-2019
/14
Слайд 9Теоретико-системные основы математического моделирования
(с) Н.М. Светлов, 2006
/20
2.Оптимальне рішення гри
двох осіб з нульовою сумою.
Слайд 10
2. Оптимальне рішення гри двох осіб з нульовою сумою
Оскільки гри
беруть свій початок в конфлікті інтересів, оптимальним рішенням гри є
одна або декілька таких стратегій для кожного з гравців,
при цьому будь-яке відхилення від даних стратегій не покращує плату того чи іншого гравця.
Ці рішення можуть бути у вигляді
єдиної чистої стратегії
або декількох стратегій, які є змішаними ( відповідно з заданими вірогідностями).
Розглянуті нижче приклади демонструють перераховані ситуації.
Теорія Прийняття рішень
© ЄА. Лавров, 2014-2019
/14
Слайд 11
2. Оптимальне рішення гри двох осіб з нульовою сумою
Приклад 1
. Дві компанії А і В продають два види ліків
проти грипу.Компанія А рекламує продукцію
на радіо (А1),
телебаченні (А2)
і в газетах (А3).
Компанія В, на додаток до використання радіо (B1), телебачення (B2) і газет (B3), розсилає також поштою брошури (B4).
Теорія Прийняття рішень
© ЄА. Лавров, 2014-2019
/14
Слайд 12
2. Оптимальне рішення гри двох осіб з нульовою сумою
Приклад 1
продовження. Залежно від уміння й інтенсивності проведення рекламної кампанії, кожна
з компаній може залучити на свою сторону частину клієнтів конкуруючої компанії.Наведена матриця характеризує відсоток клієнтів, залучених або втрачених компанією A.
Теорія Прийняття рішень
© ЄА. Лавров, 2014-2019
/14
Слайд 132. Оптимальне рішення гри двох осіб з нульовою сумою. Приклад
1. продовження
Аналіз стратегій комп. А.
Рішення гри засноване на забезпеченні
найкращого результату з найгірших для кожного гравця. Якщо компанія A вибирає стратегію A1, то, незалежно від того, що вживає компанія В, найгіршим результатом є втрата компанією А 3% ринку на користь компанії В. Це визначається мінімумом елементів першого рядка матриці платежів.
Аналогічно при виборі стратегії A2 найгіршим результатом для компанії А є збільшення ринку на 5% за рахунок компанії В. Нарешті, найгіршим результатом при виборі стратегії A3 є втрата компанією А 9% ринку на користь компанії В. Ці результати містяться в стовпці "Мінімуми рядків"
Теорія Прийняття рішень
© ЄА. Лавров, 2014-2019
/14
Слайд 142. Оптимальне рішення гри двох осіб з нульовою сумою. Приклад1.продовження
Аналіз стратегій комп. B.
Так як елементи матриці є платежами компанії
А, критерій найкращого результату з найгірших для компанії В відповідає вибору мінімаксного значення.
В результаті приходимо до висновку, що вибором компанії В є стратегія B2.
Теорія Прийняття рішень
© ЄА. Лавров, 2014-2019
/14
Слайд 152. Оптимальне рішення гри двох осіб з нульовою сумою. Приклад1.
продовження
Оптимальним рішенням у грі є вибір стратегій A2 і
B2, тобто обом компаніям слід проводити рекламу на телебаченні.
При цьому виграш буде на користь компанії А,
так як її ринок збільшиться на 5%.
У цьому випадку говорять, що
ціна гри дорівнює 5% і що
компанії А і В використовують стратегії, відповідні седловій точці.
Теорія Прийняття рішень
© ЄА. Лавров, 2014-2019
/14
Слайд 162. Оптимальне рішення гри двох осіб з нульовою сумою. Приклад
1. продовження
Рішення, що відповідає сідловой точці, гарантує, що жодної
компанії немає сенсу намагатися вибрати іншу стратегію. Дійсно, якщо компанія В переходить до іншої стратегії (B1, B3 або B4), то компанія А може зберегти свій вибір стратегії A2, що призведе до більшої втрати ринку компанією B (6 або 8%).
З тих же причин компанії А немає резону використовувати іншу стратегію, бо якщо вона застосує, наприклад, стратегію A3, то компанія В може використовувати свою стратегію B3 і збільшити свій ринок на 9%
.Аналогічні висновки мають місце, якщо компанія А буде використовувати стратегію A1.
Теорія Прйняття рішень
© ЄА. Лавров, 2014-2019
/14
Слайд 172. Оптимальне рішення гри двох осіб з нульовою сумою. Приклад1.
продовження
Оптимальне рішення гри, що відповідає сідловой точці,
не обов'язково
має характеризуватися чистими стратегіями. Замість цього оптимальне рішення може вимагати змішування випадковим чином двох або більше стратегій
( як це зроблено в наступному прикладі)
Теорія Прйняття рішень
© ЄА. Лавров, 2014-2019
/14
Слайд 182. Оптимальне рішення гри двох осіб з нульовою сумою. Приклад2.
Два гравці A і В грають у гру на
підкидання монети. Гравці одночасно і незалежно один від одного вибирають герб (Г) або решку (Р).
Якщо результати двох підкидань монети збігаються (тобто ГГ або РР), то гравець А отримує один долар від гравця В .
Інакше гравець А платить один долар гравцеві В.
Матриця платежів гравцеві А показує величини мінімальних елементів рядків і максимальних елементів стовпців, відповідних стратегій обох гравців.
Теорія Прйняття рішень
© ЄА. Лавров, 2014-2019
/14
Слайд 192. Приклад2.
Максиміна і мінімаксна величини (ціни) для
цієї гри
дорівнюють-1 дол. і 1 дол. відповідно.
Так як ці величини не рівні між собою,
гра не має рішення в чистих стратегіях.
Зокрема, якщо гравець А використовує стратегію AГ, гравець В вибере стратегію BР, щоб отримати від гравця А один долар. Якщо це станеться, гравець А може перейти до стратегії AР, щоб змінити результат гри і отримати один долар від гравця В.
Теорія Прйняття рішень
© ЄА. Лавров, 2014-2019
/14
Слайд 202. Приклад2.
Постійна спокуса кожного гравця перейти до іншої
стратегії вказує на те, що рішення у вигляді чистої стратегії
неприйнятне.Замість цього обидва гравці повинні використовувати належну випадкову комбінацію своїх стратегій.
У розглянутому прикладі оптимальне значення ціни гри знаходиться десь між максімінною і мінімаксною цінами для цієї гри:
Максиміна(нижня)ціна≤ ціна гри ≤ мінімаксна (верхня) ціна.
В даному випадку ціна гри (в доларах) повинна лежати в інтервалі
[-1,1] .
Теорія Прйняття рішень
© ЄА. Лавров, 2014-2019
/14
Слайд 21
2. Оптимальне рішення гри двох осіб з нульовою сумою
Приклад 3
. Знайдіть рішення, яке визначається сідловою точкою
відповідні чисті стратегії та
ціну гри для гри (платежі задані для гравця А)Теорія Прийняття рішень
© ЄА. Лавров, 2014-2019
/14
Слайд 22
2. Оптимальне рішення гри двох осіб з нульовою сумою
Приклад 3
. Знайдіть рішення, яке визначається сідловою точкою
відповідні чисті стратегії та
ціну гри для гри (платежі задані для гравця А)Рішення
Ціна гри = 4.
Теорія Прийняття рішень
© ЄА. Лавров, 2014-2019
/14
Слайд 23
2. Оптимальне рішення гри двох осіб з нульовою сумою
Приклад 3
. Знайдіть рішення, яке визначається сідловою точкою
відповідні чисті стратегії та
ціну гри для гри (платежі задані для гравця А)Теорія Прийняття рішень
© ЄА. Лавров, 2014-2019
/14
Слайд 24
2. Оптимальне рішення гри двох осіб з нульовою сумою
Приклад 4
. Вкажіть область, якій належить ціна гри припускаючи, що платежі
задані для гравця А.Теорія Прийняття рішень
© ЄА. Лавров, 2014-2019
/14
Слайд 25
2. Оптимальне рішення гри двох осіб з нульовою сумою
Приклад 4
. Вкажіть область, якій належить ціна гри припускаючи, що платежі
задані для гравця А.Рішення
Позначимо через v ціну гри.
Тоді 2 < v < 4.
Теорія Прийняття рішень
© ЄА. Лавров, 2014-2019
/14
Слайд 26
3.Рішення матричних ігор у змішаних стратегіях
Теорія Прийняття рішень
©
ЄА. Лавров, 2014-2019
/14
Слайд 27
3Рішення матричних ігор у змішаних стратегіях
Може бути знайдено
графічно,
або
методами лінійного програмування.
Графічний метод можна застосовувати для вирішення ігор,
в яких хоч один гравець має дві чисті стратегії. Цікавий в тому плані, що графічно пояснює поняття сідлової точки.
Методами лінійного програмування може бути вирішена будь-яка гра двох осіб з нульовою сумою.
Теорія Прийняття рішень
© ЄА. Лавров, 2014-2019
/14
Слайд 28
3Рішення матричних ігор у змішаних стратегіях. Постановка задачі
Розглянемо гру 2
х n, в якій гравець А має дві стратегії.
Гра
передбачає, що гравець А змішує стратегії А1 и А2 з відповідними вірогідностями x1 та 1 - x1, 0 < x1 < 1.Гравець Б змішує стратегії B1, B2, ..., BN з вірогідностями y1, y2, ..., yn,
де yJ ≥ 0, j = 1, 2, ..., n, та y1 + y2 + ... + yn = 1.
У цьому випадку очікуваний виграш гравця А, що відповідає j-й чистій стратегії гравця Б, обчислюється в вигляді (a1j - a2j)x1 - a2j, j = 1, 2, ..., n.
Отже, гравець А шукає величину x1, яка максимізує мінімум очікуваних виграшів
Теорія Прийняття рішень
© ЄА. Лавров, 2014-2019
/14
Слайд 29Теоретико-системные основы математического моделирования
(с) Н.М. Светлов, 2006
/20
Рассмотрим следующую игру 2x4,
в которой платежи выплачиваются игроку A.
Игра не
имеет решения в чистых стратегиях, и, следовательно, стратегии должны быть смешанными. Ожидаемые выигрыши игрока А, соответствующие чистым стратегиям игрока В, приведены в следующей таблице
Слайд 30
3Рішення матричних ігор у змішаних стратегіях.
Графічний метод рішення. Приклад.
Рассмотрим следующую
игру 2x4, в которой платежи выплачиваются игроку A.
Игра
не имеет решения в чистых стратегиях, и, следовательно, стратегии должны быть смешанными. Ожидаемые выигрыши игрока А, соответствующие чистым стратегиям игрока В, приведены в следующей таблице/14
Слайд 31
3Рішення матричних ігор у змішаних стратегіях.
Графічний метод рішення. Приклад. Продовження
4 прямі лінії, відповідають чистим стратегіям гравця В.
Щоб визначити найкращий результат з найгірших, побудована нижня обвідна чотирьох прямих (зображена товстими сегментами), яка представляє мінімальний (найгірший) виграш для гравця А незалежно від того, що робить гравець В. Максимум нижньою обвідної відповідає Максиміну (в точці x1 = 0,5).
Ця точка визначається
перетином прямих 3 і 4.
/14
Оптимальним рішенням для гравця А є змішування стратегій A1 і A2 з імовірностями 0,5 і 0,5 відповідно.
Відповідна ціна гри v визначається підстановкою x1 = 0,5 в рівняння
прямої 3, або 4
Слайд 32
3Рішення матричних ігор у змішаних стратегіях.
Графічний метод рішення. Приклад. Продовження
Оптимальна
змішана стратегія гравця В визначається двома стратегіями, які формують нижню
огибаючу графіка.Це означає, що гравець В може змішувати стратегії B3 і B4, в цьому випадку y1 = y2 = 0 и y4 = 1- y3. Отже, очікувані платежі гравця В, що відповідають чистим стратегіям гравця А, мають вигляд
/14
Найкраще рішення з найгірших для гравця В являє собою точку мінімуму верхньої обвідної заданих двох прямих (побудувати самостійно). Ця процедура еквівалентна рішенням рівняння 4y3 - 1 = -4y3 + 6
Рішеня y3 = 7/8,
Ціна гри v = 4 х (7/8) - 1 =5/2
Слайд 33
3Рішення матричних ігор у змішаних стратегіях.
Графічний метод рішення. Приклад. Продовження
Результат
Рішення гри для гравця А -змішування стратегій A1 і
A2 з рівними ймовірностями 0,5 і 0,5, а для гравця В - змішування стратегій B3 і B4, з вірогідністю 7/8 і 1/8. (Насправді гра має альтернативне рішення для гравця В, так як Максиміна точка на рис. 1 визначається більш ніж двома прямими. Будь яка опукла лінійна комбінація цих альтернативних рішень також є рішенням задачі.)
/14
Для гри, в якій гравець А має m стратегій, а гравець В - тільки дві, рішення знаходиться аналогічно. Головна відмінність полягає в тому, що тут будуються графіки функцій, що представляють очікувані платежі другого гравця, відповідні чистим стратегіям гравця А.
В результаті ведеться пошук мінімаксної точки верхньої обвідної побудованих прямих.
Слайд 34
4. Рішення матричних ігор методами лінійного програмування
Теорія Прийняття рішень
©
ЄА. Лавров, 2014-2019
/100
Слайд 35
4. Рішення матричних ігор методами лінійного програмування
Теорія ігор знаходиться в
тісному зв'язку з лінійним програмуванням,
так як будь-яку кінцеву гру
двох осіб з нульовою сумою можна представити у вигляді задачі лінійного програмування і навпаки. /14
Дж. Данциг зазначає, що, коли
в 1947 році творець теорії ігор Дж. фон Нейман
вперше ознайомився з симплекс-методом, він відразу встановив цей взаємозв'язок і звернув особливу увагу на концепцію подвійності в лінійному програмуванні.
Слайд 36
4. Рішення матричних ігор методами лінійного програмування
Оптимальні значення ймовірностей
xi, i = 1, 2, ..., m,
гравця А можуть
бути визначені шляхом вирішеннямаксимінної задачі.
/14
Слайд 37Довідка Джон фон Нейман
.
англ. John von Neumann),
Нейман Янош Лайош (угор. Neumann János
Lajos), Йоганн фон Нойман (нім. Johann von Neumann) * 28 грудня 1903 — † 8 лютого 1957) — американський математик угорського походження, що зробив значний вклад у квантову фізику, функціональний аналіз, теорію множин, інформатику, економічні науки та в інші численні розділи знання. Він став засновником теорії ігор разом із Оскаром Морґенштерном у 1944 році.
Розробив архітектуру (так звану «архітектуру фон Неймана»), яка використовується в усіх сучасних комп'ютерах
/14
Слайд 38
4. Рішення матричних ігор методами лінійного програмування
Оптимальні значення ймовірностей
xi, i = 1, 2, ..., m,
гравця А можуть
бути визначені шляхом вирішеннямаксимінної задачі.
/14
Слайд 39
4. Рішення матричних ігор методами лінійного програмування
Щоб сформулювати цю
задачу у вигляді задачі лінійного програмування, припустимо
Звідси витікає , що
/14
Тоді
задача гравця м.б. сформульована як
Слайд 40
4. Рішення матричних ігор методами лінійного програмування
Щоб сформулювати цю
задачу у вигляді задачі лінійного програмування, припустимо
Звідси витікає , що
/14
Тоді
задача гравця м.б. сформульована як
Слайд 41
4. Рішення матричних ігор методами лінійного програмування
Щоб сформулювати цю
задачу у вигляді задачі лінійного програмування, припустимо
Звідси витікає , що
/14
Тоді
задача гравця м.б. сформульована як
Слайд 42
4. Рішення матричних ігор методами лінійного програмування
Відзначимо, що ціна
гри v може бути як позитивною, так і негативною.
Оптимальні стратегії
y1, y2, ...,yn гравця В визначаються шляхом рішення задачіВикористовуючи процедуру, аналогічну наведеній вище для гравця А, приходимо до висновку, що задача для гравця В зводиться до задачі
/14
Слайд 43
4. Рішення матричних ігор методами лінійного програмування
Дві отримані задачі
оптимізують одну і ту ж (не обмежену в знаці) змінну
v, яка є ціною гри.Причиною цього є те, що задача гравця В є двоїстою до задачі гравця А.
/14
Це означає, що оптимальне рішення однієї із задач автоматично визначає оптимальне рішення іншої
Слайд 44
5. Приклад рішення матричної гри методами лінійного програмування
Теорія Прийняття рішень
© ЄА. Лавров, 2014-2019
/100
Слайд 455. Приклад рішення матричної гри методами лінійного програмування
Задача
Значення ціни гри
v знаходиться між -2 та 2.
? Що необхідно знайти????
Теорія
Прийняття рішень © ЄА. Лавров, 2014-2019
/100
Слайд 465. Приклад рішення матричної гри методами лінійного програмування
Задача
Задача лінійного програмування
и для гравця А
Максимізувати z = v
v - 3x1
+ 2x2 + 5x3 ≤ 0,
v + x1 - 4x2 + 6x3 ≤ 0,
v + 3x1 + x2 - 2x3 ≤ 0,
x1 + x2 + x3 = 1,
x1, x2, x3 ≥ 0,
v не обмежена в знаці. Оптимальне рішення x1 = 0,39, x2 = 0,31, x3 = 0,29
v = -0,91.
Теорія Прийняття рішень
© ЄА. Лавров, 2014-2019
/100
Слайд 475. Приклад рішення матричної гри методами лінійного програмування
Задача
Задача лінійного програмування
и для гравця В
Мінімізувати z = v
v - 3y1 +
y2 + 3y3 ≥ 0,
v + 2y1 - 4y2 + y3 ≥ 0,
v + 5y1 + 6y2 - 2y3 ≥ 0,
y1 + y2 + y3 = 1,
y1, y2, y3 ≥ 0,
v не обмежена в знаці. Оптимальне рішення y1 = 0,32, y2 = 0,08, y3 = 0,60
v = -0,91.
Теорія Прийняття рішень
© ЄА. Лавров, 2014-2019
/100
