Зведення матричної гри з нульовою сумою до задач лінійного програмування

 

 

Матрицю гри великих розмірів графічно зобразити неможливо. Тому таку гру часто зводять до задачі лінійного програмування. Нехай маємо таку матрицю:

 

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

Цілком зрозуміло, що

.

Тоді знайдемо мішану стратегію , яка забезпечує виграш не менше величини :

у разі відповіді стратегією виграш сторони

у разі відповіді стратегією виграш сторони А

,

де ціна гри також невідома.

Введемо змінні

.

Тоді має місце

(*)

та

.

Оскільки (максимізація виграшу), то

.

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

Якщо розглядається друга сторона гри В, то треба знайти значення ймовірностей та використання стратегій та . У цьому разі математична модель задачі сторони В є двоїстою задачею до математичної моделі сторони А. Така пара симетрична, тому двоїста задача матиме таку математичну модель:

Зрозуміло, що для сторони А, а для сторони В.

У загальному вигляді математичні моделі двоїстої пари задач лінійного програмування гри з матрицею записуються так:

пряма задача двоїста задача

При цьому

Приклад. Нехай задано таку матрицю:

	0,2	1,0
	0,5	0,25

 

Треба знайти ймовірність використання стратегій та і величину ціни гри .

Зведемо задачу до математичної моделі задачі лінійного програмування.

Згідно із заданою матрицею

 

.

 

Модель лінійної задачі

Наведемо розв’язування задачі різними методами.

1. Графічний метод ЗЛП.

х ₂ Область довільних розв’язків задачі

зображено на рис. 5.9.

Точка А – це точка мінімуму. Тому

A розв’язуємо систему рівнянь

х ₁

Рис.5.9.

Розв’язок: та .

Тоді

2. Симплексний метод.

Перетворюємо задану модель до стандартного вигляду:

Складаємо три симплекс-таблиці:

М

М

М

1/5

1/2

-1

М

1/4

-1

-М

-М

М

М

4/5

9/20

-1

1/5

М

1/4

-1

-М

 

 

М		4/5			-20/9	4/9
М		5/9			5/9	-10/9
			- 5/9	-2/3

 

Відповідь:

3. Графічний метод ігрової задачі. Розв’язування показано на рис. 5.10.

 

Згідно з графіком знаходимо

, , ,

В ₁

А ₁ А ₂

 

Рис.5.10

Висновки

 

 

1. Теорія ігор є математичною теорією конфліктних ситуацій одного з напрямків прикладної математики.

2. Методи розв’язування достатньо розроблені тільки для скінчених ігрових задач.

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

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

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

 

 

Контрольні запитання

 

1. Що таке стратегія?

2. У чому різниця між чистою та мішаною стратегіями?

3. Що таке активна стратегія?

4. Суть принципу мінімаксу.

5. Які засоби використовуються для спрощення ігор?

6. Чи можливі одночасно кілька сідлових точок?

7. Геометрична інтерпретація невигідної стратегії.

8. Чи може бути альтернативний оптимум в ігрових задачах?

9. Як показати ігрову задачу двоїстої пари задач лінійного програ-мування?

 

⇐ Предыдущая1234567

Поделиться:

Читайте также:

E) тело, размерами которого можно пренебречь в условиях данной задачи
I Приклади розв’язання задач
I ЭТАП. Постановка задачи
I. ОСНОВНІ ЗАДАЧІ І НАПРЯМКИ САМОСТІЙНОЇ НДР СТУДЕНТІВ
I. Цели и задачи учебной дисциплины
I. Цель задачи дисциплины «История государства и права зарубежных стран»
II Анализ задачного материала
II Раздаточный материал из сборника задач по технологии горячей и холодной прокатки стали и сплавов. Протасов А.А. Изд-во «Металлургия» М.1972, 320 с.
II. Задачи работы с классом
II. Типовые задачи.

Воспользуйтесь поиском по сайту: