Лекції - Теорія систем і системний аналіз

Тема 1.Лекція 1_Вводная.doc (1 стор.)
Тема 2.Лекція 2_Основние понятія.doc (1 стор.)
Тема 3_Реалізація СА, показателі.doc (1 стор.)
Тема 4_Вибор.doc (1 стор.)
Тема 5.Лекція 5_ЛП.doc (1 стор.)
Тема 5.Лекція 6_НП.doc (1 стор.)
Тема 6_Лекція 7_ Багатокритеріальні задачі.doc (1 стор.)
Тема 7_Лекція 8_Вибор в умовах ріска.doc (1 стор.)
Тема 8-9_Лекція 10_Ігра з природою, СА істочніков.doc (1 стор.)
Тема 8_Лекція 9_Теорія ігр.doc (1 стор.)
Оригінал


ТЕМА 8. Теорії матричних ігор

Лекція 9


1. Постановка задачі вибору в умовах невизначеності

2.Основні визначення і теореми теорії ігор

3.Прімери вирішення завдань при парній грі з нульовою сумою.


1. Постановка задачі вибору в умовах невизначеності


Раніше ми познайомилися з завданнями вибору рішення, коли кожній альтернативі (варіанту вибору) відповідав певний результат. Це був, таким чином, вибір в умовах визначеності.

У реальних задачах часто доводиться мати справу з ситуацією, коли альтернатива неоднозначно визначає наслідки зробленого вибору. Іншими словами, є набір можливих результатів y Y, з яких один виявиться поєднаним з обраної альтернативою, але з якою саме - в момент вибору невідомо, але стане ясно тільки тоді, коли вибір вже зроблено, і нічого змінити не можна. Хоча з різною альтернативою x  X пов'язане одне і те ж безліч исходов Y, для різних альтернатив різні результати мають неоднакове значення.


1.1 Завдання невизначеності за допомогою матриці


У разі дискретного набору альтернатив і результатів описану вище стіуацію можна представити у вигляді матриці


X, Y

y 1

y 2

y 3

y j

...

y m

x 1

a 11

a 12

a 13

a 1i

...

a 1m

x 2

a 21

a 22

a 23

a 2i

...

a 2m

x i

a i1

a i2

a i3

a ii

...

a im

...

...

...

...

...

...

...

x n

a n1

a n2

a n3

a ni

...

a nm


Вектор y = (y 1, .... y m) - це всі можливі наслідки. Числа a ii виражають оцінку ситуації, коли зроблений вибір альтернативи х i й реалізувався результат y i. У різних випадках числа a ii можуть мати різний сенс ("виграш", "втрати", "платіж").

Можливі два варіанти:

  1. всі рядки a i = (a i 1,.... a im) (тобто ми бачимо, це теж вектор) однакові і проблеми вибору між альтернативами немає;

  2. рядки різні, отже, виникає проблемв вибору альтернативи.


У разі безперервних множин X та Y ситуація описується аналогічно з допомогою поставлених на цих множинах функціях a (x, y), x X, y Y.

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


2.Основні визначення й теореми теорії ігор


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

Початком теорії ігор як послідовної математичної теорії поведінки можна вважати вихід у світ 50 років тому монографії Дж. фон Неймана і О. Моргенштерна. Французький математик Е. Мулен так характеризує значення теорії ігор для соціально-економічних наук: «На нашу думку, теорія ігор являє собою набір інструментів для побудови моделей в економічних і політичних теоріях. Єдиним, але цілком достатнім виправданням існування теорії ігор служить її зростаюче застосування в цих дисциплінах. Вона є воістину невичерпним джерелом гнучких концепцій, кожна з яких проливає світло на певні сторони соціальних взаємин. ».

Спочатку введемо кілька фундаментальних поняття теорії ігор, після цього дамо визначення цьому розділу прикладної математики.

Конфлікт - це протиріччя, викликане протилежними інтересами сторін.

Конфліктна ситуація - ситуація в якій беруть участь сторони інтереси яких повністю або частково протилежні.

Гра - це дійсний або формальний конфлікт, в якому є принаймні два учасники, кожен з яких прагне до досягнення власних цілей

Правилами гри називають допустимі дії кожного з гравців, спрямовані на досягнення певної мети.

Платежем називається кількісна оцінка результатів гри.

Парна гра - гра в якій беруть участь тільки дві сторони (два гравці).

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

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

Оптимальна стратегія - це така стратегія гравця, яка при багаторазовому повторенні гри забезпечує йому максимально можливий середній виграш або мінімально можливий середній програш.

Нехай ми маємо парну гру з нульовою сумою, один гравець може вибрати при даному ході i-ю стратегію з m своїх можливих (i = 1 .. m), а другий, не знаючи вибору першого j-ю стратегію з n своїх можливих стратегій ( j = 1 .. n). У результаті перший гравець виграє величину , А другий програє цю величину. З цих величин складемо матрицю A.

A


Платіжна матриця - так назвемо матрицю A або ще по іншому матрицею гри.

Кінцевою грою розмірності (m  n) називається гра певна матрицею А має m рядків і n стовпців.


Максимін або нижньої ціною гри назавем число ,

а відповідна йому стратегія (рядок) Максимін.

Мінімакс або верхньої ціною гри назавем число

,

а відповідна йому стратегія (стовпець) мінімаксного.

Теорема 1.1. Нижня ціна гри завжди не перевершує верхню ціну гри.

Грою з сідловою точкою називається гра для якої .

Ціною гри називається величина , Якщо .

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

Можлива гра і з декількома сідловими точками. Тоді гра має кілька оптимальних рішень, але з однаковою ціною гри.

Найчастіше зустрічаються матричні ігри без сідлової точки, коли    і тоді для знаходження її рішення використовуються змішані стратегії.

Змішаною стратегією гравця називається вектор, кожна з компонент якого показує відносну частоту використання гравцем відповідної чистої стратегії.

Теорема 1.2. Основна теорема теорії матричних ігор. Всяка матрична гра з нульовою сумою має рішення в змішаних стратегіях.

Теорема 1.3. Якщо один з гравців застосовує оптимальну змішану стратегію, то його виграш дорівнює ціні гри  в не залежності від того, з якими частотами буде застосовувати другий гравець свої стратегії (в тому числі і чисті стратегії).


2. Приклади розв'язання задач при парній грі з нульовою сумою


Завдання 1.1.

Знайти рішення гри, заданої матрицею А


А = .

Рішення. Перш за все перевіримо наявність сідлової точки в даній матриці.

Для цього знайдемо нижню і верхню ціну гри.

Мінімальні елементи по рядках дорівнюють (2 і 3) тоді нижня ціна гри  = max (2, 3) = 3. Максимальні елементи по стовпцях дорівнюють (3 і 6) тоді верхня ціна гри  = min (3, 6) = 3. Звідси видно, що  =  = 3 і ми маємо сідлову точку . = 3, тобто завдання має рішення в чистих стратегіях.

Оптимальні чисті стратегії для першого і другого гравців дорівнюють відповідно U * = (0; 1), Z * = (1; 0), а ціна гри  = 3.


Завдання 1.2.

Знайти рішення гри, заданої матрицею А


А = .


Рішення. Перш за все перевіримо наявність сідлової точки в даній матриці.

Для цього знайдемо нижню і верхню ціну гри.

Мінімальні елементи по рядках дорівнюють (2 і 3) тоді нижня ціна гри  = max (2, 3) = 3. Максимальні елементи по стовпцях рівні (4 і 6) тоді верхня ціна гри  = min (4, 6) = 4. Звідси видно, що    і ми маємо гру, яка має рішення в змішаних стратегіях, а ціна гри     .

Припустимо, що для першого гравця змішана стратегія задається вектором U = (u 1; u 2). Перший гравець, якщо дотримується своєї оптимальної стратегії, незалежно від стратегії другого гравця отримує ціну гри , тобто


4u 1 * + 3u 2 * =  (1)

2u 1 * + 6u 2 * = .


Крім цього відносні частоти пов'язані умовою:


u 1 * + u 2 * = 1.


Вирішуємо отриману систему трьох лінійних рівнянь з трьома невідомими. Отримаємо оптимальну стратегію першого гравця і ціну гри:


U * = (u 1 *; u 2 *) = (3/5, 2/5),  = 18/5.


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


4z 1 * + 2z 2 * =  = 18/5 (2)

3z 1 * + 6z 2 * =  = 18/5.


Вирішуємо отриману систему двох лінійних рівнянь з двома невідомими. Отримаємо оптимальну стратегію другого гравця:


Z * = (z 1 *; z 2 *) = (4/5; 1/5).


Розглянемо геометричну інтерпретацію цього завдання в змішаних стратегіях. Для цього в площині введемо систему координат і на горизонтальній осі Ou відкладемо ймовірність застосування першим гравцем його двох стратегій, сума цих ймовірностей дорівнює 1, тому весь графік розташується на відрізку одиничної довжини. У точках 0 стратегія (1; 0), а в 1 стратегія (0; 1).



Малюнок 1.

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

Анологічно можна побудувати графік для знаходження оптимальної стратегії другого гравця.

Ми розглянули тільки найпростіший варіант парної матричної гри з нульовою сумою, але вона досить наочно показує, що іноді можна кількісно оцінити і вибрати оптимальний варіант поведінки в конфліктній ситуації.
Навчальний матеріал
© uadoc.zavantag.com
При копіюванні вкажіть посилання.
звернутися до адміністрації