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), впевнюємось, що вони є взаємно-двоїстими. При розв’язуванні конкретних задач слід вибрати ту, розв’язок якої більш простіший, а розв’язок іншої знайти за теоремою двоїстості.

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

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

Попит Прод.
	3	6	8	3
	9	4	2	2
	7	5	4	4
	9	6	8

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

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

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

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

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

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

.

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

Б			1	1	1	0	0	0
	0	1	3		8	1	0	0
	0	1	9	4	2	0	1	0
	0	1	7	5	4	0	0	1
		0	-1	-1	-1	0	0	0

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

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

Б			1	1	1	0	0	0
	1			1			0	0
	0		7	0			1	0
	0			0			0	1
				0			0	0

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

Б			1	1	1	0	0	0
	1		0	1			0
	0		0	0			1
	1		1	0			0
			0	0			0

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

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

	0	0				0

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

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

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

.

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

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

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

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

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

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