• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Теорема. Кожна скінчена гра має принаймні один оптимальний розв’язок, можливо, серед мішаних стратегій.

Ця теорема має велике практичне значення – вона дає конкретні моделі знаходження оптимальних стратегій при відсутності сідлової точки.

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

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

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

Нехай гра задана платіжною матрицею .

Середній виграш гравця , якщо він використає оптимальну мішану стратегію , а гравець -- стратегію дорівнює ціні гри :

.

Такий же виграш і при застосуванні другим гравцем стратегії , тобто

.

Враховуючи, що , одержимо систему рівнянь для визначення оптимальної стратегії і ціни гри :

( 12.1 )

Розв’язуючи цю систему, одержимо оптимальну стратегію

і ціну гри

.

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

( 12.2 )

Тоді оптимальна стратегія визначається формулами

Приклад. Застосуємо одержані результати для знаходження оптимальних стратегій для гри «Пошук»:

Розв’язок. Гра «Пошук» задана платіжною матрицею без сідлової точки:

.

Шукаємо розв’язок в мішаних стратегіях. Для гравця середній виграш дорівнює ціні гри (при і ); для гравця середній програш дорівнює ціні гри (при і ). Системи рівнянь мають вигляд:

( 12.3 )

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

5. Зведення гри до двоїстої пари ЗЛП.

Гра може бути зведена до розв’язання задачі лінійного програмування.

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

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

Для оптимальної стратегії всі середні виграші не менші ціни гри , тому отримаємо систему нерівностей:

( 12.4 )

Кожну з нерівностей поділимо на і введемо нові змінні: , , . Тоді система ( 12.4 ) матиме вигляд

( 12.5 )

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

Визначити значення змінних так, щоб вони задовольняли лінійним обмеженням ( 12.5 ) і при цьому лінійна функція Z досягала свого мінімального значення

( 12.6 )

Це задача лінійного програмування.

Розв’язуючи задачу ( 12.5 ) – ( 12.6 ) одержимо оптимальний розв’язок і оптимальну стратегію .

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

( 12.7 )

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

Якщо позначити , то одержимо систему нерівностей:

( 12.8 )

Змінні задовольняють умові: .

Гра звелась до наступної задачі:

Визначити значення змінних , які задовольняють системі нерівностей ( 12.8 ) і максимізують лінійну функцію

( 12.9 )

Розв’язок задачі лінійного програмування (12.8)-(12.9) визначає оптимальну стратегію . При цьому ціна гри

. ( 12.10 )

Порівнюючи задачі (12.5) – (12.6) і (12.8) – (12.9), впевнюємось, що вони є взаємно-двоїстими. При розв’язуванні конкретних задач слід вибрати ту, розв’язок якої більш простіший, а розв’язок іншої знайти за теоремою двоїстості.

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

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

Попит Прод.

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

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

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

Задача 1	Задача 2

Розв’язуємо симплексним методом одну із задач, наприклад, задачу 2, оскільки для неї легко знайти початковий опорний план. Запишемо основну систему обмежень (ОСО) в канонічному вигляді:

I крок. Ортонормований базис складають вектори . Базисні змінні - ; вільні змінні - . Початковий опорний план має вигляд

.

Складемо першу симплексну таблицю і перевіримо умови оптимальності:

Б
		-1	-1	-1

План не є оптимальним, так як серед оцінок векторів є від’ємні. Перейдемо до нового опорного плану. Введемо до базису вектор на місце вектора .

Складемо другу симплексну таблицю:

Б

Опорний план не є оптимальним, так як оцінка вектора від’ємна. Вектор виведемо з базису, а на його місце введемо вектор . Складемо наступну симплексну таблицю:

Б

Всі оцінки невід’ємні, отже, план - оптимальний план, .

Встановимо відповідність між змінними взаємно-двоїстих задач і визначимо оптимальний розв’язок задачі 1 за допомогою теорем двоїстості та даних індексного рядка останньої симплексної таблиці:

Оптимальний розв’язок задачі 1: , причому . Із співвідношень (12.10) знаходимо ціну гри .

Зауважимо, що оптимальний розв’язок двоїстої задачі можна знайти за формулою: .

Оптимальну стратегію випуску продукції знайдемо, скориставшись співвідношенням , тобто

.

Отже підприємство повинно випустити 40% продукції і 60% продукції , а продукцію взагалі не випускати.

Оптимальна стратегія попиту визначається аналогічно: , тобто . Таким чином, оптимальний попит в 20% знаходиться в стані і 80% - в стані .

При розв’язуванні довільної скінченої гри розміром рекомендується притримуватись наступнох схеми:

1. Виключити з платіжної матриці завідомо невигідні стратегії в порівнянні з іншими стратегіями. Такими стратегіями для гравця (гравця ) є ті, яким відповідають рядки (стовпці) з елементами меншими (більшими) в порівнянні з елементами інших рядків (стовпців).

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

3. Якщо сідлова точка відсутня, то розв’язок слід шукати в мішаних стратегіях. Для гри розміру рекомендується симплексний метод, а для гри розміру - графо-аналітичний метод.

Переглядів: 1291