Основи Теорії Ігор - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Основи Теорії Ігор. Доклад-сообщение содержит 49 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Розділ 5

Слайд 2

Описание слайда:

Основи Теорії Ігор

Слайд 3

Описание слайда:

Теорія Ігор

Слайд 4

Описание слайда:

Лекція 7. Основні поняття Теорії ІГОР Зміст лекції: 1. Теорія ігор .Проблема Прийняття рішень в умовах конфлікту 2.Оптимальне рішення гри двох осіб з нульовою сумою. 3.Рішення матричних ігор у змішаних стратегіях 4. Рішення матричних ігор методами лінійного програмування 5. Приклад рішення матричної гри методами лінійного програмування

Слайд 5

Описание слайда:

Слайд 6

Описание слайда:

Теорія ігор .Проблема Прийняття рішень в умовах конфлікту В теорії ігор розглядаються ситуації, пов'язані з прийняттям рішень, в яких : два розумних противника мають конфліктуючі цілі. типові приклади рекламування конкуруючих товарів планування військових стратегій протиборчих армій. Відмінність від попередніх ситуацій Раніше природа не виступала в ролі противника (недоброзичливця) яким відповідають платежі, які залежать від випадкових станів природи.

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

Теорія ігор .Проблема Прийняття рішень в умовах конфлікту При позначенні гравців через А і В з числом стратегій n і m відповідно гру зазвичай представляють у вигляді матриці платежів гравцеві А: Таке представлення матричної гри означає, що якщо гравець А використовує стратегію i, а гравець В - стратегію j, то платіж гравцеві А становить аij і, отже, гравцеві В - (-аij ).

Слайд 9

Описание слайда:

Слайд 10

Описание слайда:

2. Оптимальне рішення гри двох осіб з нульовою сумою Оскільки гри беруть свій початок в конфлікті інтересів, оптимальним рішенням гри є одна або декілька таких стратегій для кожного з гравців, при цьому будь-яке відхилення від даних стратегій не покращує плату того чи іншого гравця. Ці рішення можуть бути у вигляді єдиної чистої стратегії або декількох стратегій, які є змішаними ( відповідно з заданими вірогідностями). Розглянуті нижче приклади демонструють перераховані ситуації.

Слайд 11

Описание слайда:

2. Оптимальне рішення гри двох осіб з нульовою сумою Приклад 1 . Дві компанії А і В продають два види ліків проти грипу. Компанія А рекламує продукцію на радіо (А1), телебаченні (А2) і в газетах (А3). Компанія В, на додаток до використання радіо (B1), телебачення (B2) і газет (B3), розсилає також поштою брошури (B4).

Слайд 12

Описание слайда:

2. Оптимальне рішення гри двох осіб з нульовою сумою Приклад 1 продовження. Залежно від уміння й інтенсивності проведення рекламної кампанії, кожна з компаній може залучити на свою сторону частину клієнтів конкуруючої компанії. Наведена матриця характеризує відсоток клієнтів, залучених або втрачених компанією A.

Слайд 13

Описание слайда:

2. Оптимальне рішення гри двох осіб з нульовою сумою. Приклад 1. продовження Аналіз стратегій комп. А. Рішення гри засноване на забезпеченні найкращого результату з найгірших для кожного гравця. Якщо компанія A вибирає стратегію A1, то, незалежно від того, що вживає компанія В, найгіршим результатом є втрата компанією А 3% ринку на користь компанії В. Це визначається мінімумом елементів першого рядка матриці платежів. Аналогічно при виборі стратегії A2 найгіршим результатом для компанії А є збільшення ринку на 5% за рахунок компанії В. Нарешті, найгіршим результатом при виборі стратегії A3 є втрата компанією А 9% ринку на користь компанії В. Ці результати містяться в стовпці "Мінімуми рядків"

Слайд 14

Описание слайда:

2. Оптимальне рішення гри двох осіб з нульовою сумою. Приклад1.продовження Аналіз стратегій комп. B. Так як елементи матриці є платежами компанії А, критерій найкращого результату з найгірших для компанії В відповідає вибору мінімаксного значення. В результаті приходимо до висновку, що вибором компанії В є стратегія B2.

Слайд 15

Описание слайда:

2. Оптимальне рішення гри двох осіб з нульовою сумою. Приклад1. продовження Оптимальним рішенням у грі є вибір стратегій A2 і B2, тобто обом компаніям слід проводити рекламу на телебаченні. При цьому виграш буде на користь компанії А, так як її ринок збільшиться на 5%. У цьому випадку говорять, що ціна гри дорівнює 5% і що компанії А і В використовують стратегії, відповідні седловій точці.

Слайд 16

Описание слайда:

2. Оптимальне рішення гри двох осіб з нульовою сумою. Приклад 1. продовження Рішення, що відповідає сідловой точці, гарантує, що жодної компанії немає сенсу намагатися вибрати іншу стратегію. Дійсно, якщо компанія В переходить до іншої стратегії (B1, B3 або B4), то компанія А може зберегти свій вибір стратегії A2, що призведе до більшої втрати ринку компанією B (6 або 8%). З тих же причин компанії А немає резону використовувати іншу стратегію, бо якщо вона застосує, наприклад, стратегію A3, то компанія В може використовувати свою стратегію B3 і збільшити свій ринок на 9% .Аналогічні висновки мають місце, якщо компанія А буде використовувати стратегію A1.

Слайд 17

Описание слайда:

2. Оптимальне рішення гри двох осіб з нульовою сумою. Приклад1. продовження Оптимальне рішення гри, що відповідає сідловой точці, не обов'язково має характеризуватися чистими стратегіями. Замість цього оптимальне рішення може вимагати змішування випадковим чином двох або більше стратегій ( як це зроблено в наступному прикладі)

Слайд 18

Описание слайда:

2. Оптимальне рішення гри двох осіб з нульовою сумою. Приклад2. Два гравці A і В грають у гру на підкидання монети. Гравці одночасно і незалежно один від одного вибирають герб (Г) або решку (Р). Якщо результати двох підкидань монети збігаються (тобто ГГ або РР), то гравець А отримує один долар від гравця В . Інакше гравець А платить один долар гравцеві В. Матриця платежів гравцеві А показує величини мінімальних елементів рядків і максимальних елементів стовпців, відповідних стратегій обох гравців.

Слайд 19

Описание слайда:

2. Приклад2. Максиміна і мінімаксна величини (ціни) для цієї гри дорівнюють -1 дол. і 1 дол. відповідно. Так як ці величини не рівні між собою, гра не має рішення в чистих стратегіях. Зокрема, якщо гравець А використовує стратегію AГ, гравець В вибере стратегію BР, щоб отримати від гравця А один долар. Якщо це станеться, гравець А може перейти до стратегії AР, щоб змінити результат гри і отримати один долар від гравця В.

Слайд 20

Описание слайда:

2. Приклад2. Постійна спокуса кожного гравця перейти до іншої стратегії вказує на те, що рішення у вигляді чистої стратегії неприйнятне. Замість цього обидва гравці повинні використовувати належну випадкову комбінацію своїх стратегій. У розглянутому прикладі оптимальне значення ціни гри знаходиться десь між максімінною і мінімаксною цінами для цієї гри: Максиміна(нижня)ціна≤ ціна гри ≤ мінімаксна (верхня) ціна. В даному випадку ціна гри (в доларах) повинна лежати в інтервалі [-1,1] .

Слайд 21

Описание слайда:

2. Оптимальне рішення гри двох осіб з нульовою сумою Приклад 3 . Знайдіть рішення, яке визначається сідловою точкою відповідні чисті стратегії та ціну гри для гри (платежі задані для гравця А)

Слайд 22

Описание слайда:

Слайд 23

Описание слайда:

Слайд 24

Описание слайда:

2. Оптимальне рішення гри двох осіб з нульовою сумою Приклад 4 . Вкажіть область, якій належить ціна гри припускаючи, що платежі задані для гравця А.

Слайд 25

Описание слайда:

2. Оптимальне рішення гри двох осіб з нульовою сумою Приклад 4 . Вкажіть область, якій належить ціна гри припускаючи, що платежі задані для гравця А. Рішення Позначимо через v ціну гри. Тоді 2 < v < 4.

Слайд 26

Описание слайда:

3.Рішення матричних ігор у змішаних стратегіях

Слайд 27

Описание слайда:

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

Слайд 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, яка максимізує мінімум очікуваних виграшів

Слайд 29

Описание слайда:

Слайд 30

Описание слайда:

3Рішення матричних ігор у змішаних стратегіях. Графічний метод рішення. Приклад. Рассмотрим следующую игру 2x4, в которой платежи выплачиваются игроку A. Игра не имеет решения в чистых стратегиях, и, следовательно, стратегии должны быть смешанными. Ожидаемые выигрыши игрока А, соответствующие чистым стратегиям игрока В, приведены в следующей таблице

Слайд 31

Описание слайда:

3Рішення матричних ігор у змішаних стратегіях. Графічний метод рішення. Приклад. Продовження 4 прямі лінії, відповідають чистим стратегіям гравця В. Щоб визначити найкращий результат з найгірших, побудована нижня обвідна чотирьох прямих (зображена товстими сегментами), яка представляє мінімальний (найгірший) виграш для гравця А незалежно від того, що робить гравець В. Максимум нижньою обвідної відповідає Максиміну (в точці x1 = 0,5). Ця точка визначається перетином прямих 3 і 4.

Слайд 32

Описание слайда:

3Рішення матричних ігор у змішаних стратегіях. Графічний метод рішення. Приклад. Продовження Оптимальна змішана стратегія гравця В визначається двома стратегіями, які формують нижню огибаючу графіка. Це означає, що гравець В може змішувати стратегії B3 і B4, в цьому випадку y1 = y2 = 0 и y4 = 1- y3. Отже, очікувані платежі гравця В, що відповідають чистим стратегіям гравця А, мають вигляд

Слайд 33

Описание слайда:

3Рішення матричних ігор у змішаних стратегіях. Графічний метод рішення. Приклад. Продовження Результат Рішення гри для гравця А -змішування стратегій A1 і A2 з рівними ймовірностями 0,5 і 0,5, а для гравця В - змішування стратегій B3 і B4, з вірогідністю 7/8 і 1/8. (Насправді гра має альтернативне рішення для гравця В, так як Максиміна точка на рис. 1 визначається більш ніж двома прямими. Будь яка опукла лінійна комбінація цих альтернативних рішень також є рішенням задачі.)

Слайд 34

Описание слайда:

4. Рішення матричних ігор методами лінійного програмування

Слайд 35

Описание слайда:

4. Рішення матричних ігор методами лінійного програмування Теорія ігор знаходиться в тісному зв'язку з лінійним програмуванням, так як будь-яку кінцеву гру двох осіб з нульовою сумою можна представити у вигляді задачі лінійного програмування і навпаки.

Слайд 36

Описание слайда:

4. Рішення матричних ігор методами лінійного програмування Оптимальні значення ймовірностей xi, i = 1, 2, ..., m, гравця А можуть бути визначені шляхом вирішення максимінної задачі.

Слайд 37

Описание слайда:

Довідка Джон фон Нейман . англ. John von Neumann), Нейман Янош Лайош (угор. Neumann János Lajos), Йоганн фон Нойман (нім. Johann von Neumann) * 28 грудня 1903 — † 8 лютого 1957) — американський математик угорського походження, що зробив значний вклад у квантову фізику, функціональний аналіз, теорію множин, інформатику, економічні науки та в інші численні розділи знання. Він став засновником теорії ігор разом із Оскаром Морґенштерном у 1944 році. Розробив архітектуру (так звану «архітектуру фон Неймана»), яка використовується в усіх сучасних комп'ютерах

Слайд 38

Описание слайда:

Слайд 39

Описание слайда:

4. Рішення матричних ігор методами лінійного програмування Щоб сформулювати цю задачу у вигляді задачі лінійного програмування, припустимо Звідси витікає , що

Слайд 40

Описание слайда:

Слайд 41

Описание слайда:

Слайд 42

Описание слайда:

4. Рішення матричних ігор методами лінійного програмування Відзначимо, що ціна гри v може бути як позитивною, так і негативною. Оптимальні стратегії y1, y2, ...,yn гравця В визначаються шляхом рішення задачі Використовуючи процедуру, аналогічну наведеній вище для гравця А, приходимо до висновку, що задача для гравця В зводиться до задачі

Слайд 43

Описание слайда:

4. Рішення матричних ігор методами лінійного програмування Дві отримані задачі оптимізують одну і ту ж (не обмежену в знаці) змінну v, яка є ціною гри. Причиною цього є те, що задача гравця В є двоїстою до задачі гравця А.

Слайд 44

Описание слайда:

5. Приклад рішення матричної гри методами лінійного програмування

Слайд 45

Описание слайда:

5. Приклад рішення матричної гри методами лінійного програмування Задача Значення ціни гри v знаходиться між -2 та 2. ? Що необхідно знайти????

Слайд 46

Описание слайда:

5. Приклад рішення матричної гри методами лінійного програмування Задача Задача лінійного програмування и для гравця А Максимізувати 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.

Слайд 47

Описание слайда:

5. Приклад рішення матричної гри методами лінійного програмування Задача Задача лінійного програмування и для гравця В Мінімізувати 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.