Вариант 7

Вариант 7

ЗАДАЧА 3.A. Провести анализ и составить платежные матрицы следующих игр:

Вариант 8.

В игре двух игроков А и В участвуют восемь карт: четыре «туза» и четыре «шестерки». Игроки берут по две карты и выкладывают их на стол. Игрок, выложивший большую карту, выигрывает 1 рубль, другой игрок, соответственно, этот рубль проигрывает. Если игроки выкладывают одинаковые карты, то никто из игроков не выигрывает

Решение

Игра состоит из двух случайных ходов (раздача карт) и двух личных ходов — выкладывание карт на стол. У игрока А возможны следующие случайные ходы: А1 — игрок А берет 2 тузов; А2 — игрок А берет туза и «шестерку»; А3 — игрок А берет две «шестерки». Аналогично у игрока В: В1 — игрок В берет 2 тузов; В2 — игрок В берет туза и «шестерку»; В3 — игрок В берет две «шестерки».

Возможны следующие ситуации:

А1-В1. Оба игрока берут по два туза, «выигрыши» игроков равны 0;

А1-В2. Игрок А взял два туза, игрок В — туз + «шестерку». Выигрыш игрока А равен 1;

А1-В3. Игрок А взял два туза, игрок В — две «шестерки». Выигрыш игрока А равен 2;

А2-В1. Игрок А взял туз + «шестерку», игрок В — два туза. Выигрыш игрока А равен -1;

А2-В2. Оба игрока взяли туза + «шестерку», выигрыши игроков равны 0;

А2-В3. Игрок А взял туза + «шестерку», игрок В — две «шестерки». Выигрыш игрока А равен 1;

А3-В1. Игрок А взял две «шестерки», игрок В — двух тузов, выигрыш игрока А равен -2;

А3-В2. Игрок А взял две «шестерки», игрок В — туза + «шестерку», выигрыш игрока А равен -1;

А3-В3. Оба игрока взяли по две «шестерки», выигрыши игроков равны 0.

Игра представляет собой игру 3?3 с матрицей, приведенной в таблице:

Таблица

B

A B1

(Т+Т) B2

(Т+6) B3

(6+6)

A1 (Т+Т) 0 1 2

А2 (Т+6) -1 0 1

A3 (6+6) -2 -1 0

ЗАДАЧА 3.С. Решение конечной матричной игры в смешанных стратегиях графоаналитическим методом;

Вариант 8.

Имеется игра с матрицей

В1 В2

А1

1 0

А2 3 1

А3

-2 3

А4

0 -4

А5 5 -3

А6

0,5 2

Решение:

Убеждаемся, прежде всего, в том, что в игровой матрице нет седловых точек. Для этого вычислим нижнюю и верхнюю цены игры

? = max min ? ij = max (0; 1; -2; -4; -3; 0,5) = 1,

i j i

? = min max ? ij = min (5; 3) = 3

j i j

и приходим к выводу, что ? ? ?. Следовательно, игра не имеет седловой точки и решение следует искать в области смешанных стратегий.

Строим графики функций выигрышей. Так как данная игра размера 6 х 2, строим графики функции выигрышей 2-го игрока в зависимости от вероятностей применения им своих чистых стратегий при различных стратегиях 1-го игрока (рис. 4с.3). Как видно из рисунка, стратегии А1 и А4 заведомо невыгодные.

Выделим жирной линией верхнюю границу выигрышей — ломаную — MLNP — максимальные проигрыши игрока В. Находим точку N, в которой эти максимальные проигрыши достигают наименьшего значения.

В точке N пересекаются линии стратегий А2, А3 и А6, которые являются активными стратегиями игрока А. Из этих стратегий сторона А может выбрать любые две с противоположным наклоном, например, А2, А3 или А2, А6 (выбор А3, А6 исключен, так как они имеет одинаковые наклоны, что приведет к решению игры в чистых стратегиях).

Выберем стратегии А2 и А3. Тогда для игры 2 х 2 (стратегии А2,А3 и В1, В2) составим систему уравнений согласно теореме об активных стратегиях.

а) для стороны А: 3?p2 — 2?p3 = ?;

p2 + 3?p3 = ?;

p2 + p3 = 1.

Из (3) p2 = 1 — p3

из (1) 3? (1 — p3) — 2?p3 = ? ? 3 — 5?p3 = ?

из (2) 1 — p3 + 3?p3 = ? ? 1 + 2?p3 = ?

далее 3 — 5?p3 = 1 + 2?p3 ? 7?p3 = 2;

Отсюда p3 = 2/ 7; p2 = 5/ 7; ? = 11/ 7.

б) для стороны В: 3?q1 + q2 = 11/ 7;

-2?q1 + 3?q2 = 11/ 7.

Из (1) q2 = 11/ 7 — 3?q1

из (2) -2?q1 + 3? (11/ 7 — 3?q1) = 11/ 7

-2?q1 — 9?q1 = 11/ 7 — 33/ 7

11?q1 = -22/ 7

Отсюда q1 = 2/ 7; q2 = 5/ 7;

Таким образом, оптимальными стратегиями сторон являются:

Sa* = (0; 5/ 7; 2/ 7; 0; 0; 0)

Sb* = (2/ 7; 5/ 7) при значении выигрыша ? = 11/ 7.

Теперь выберем стратегии А2 и А6. Решив соответствующие системы

уравнений, получим p2 = 3/ 7; p6 = 4/ 7; ? = 11/ 7

q1 = 2/ 7; q2 = 5/ 7.

Sa* = (0; 3/ 7; 0; 0; 0; 4/ 7)

Sb* = (2/ 7; 5/ 7)

при том же значении выигрыша ? = 11/ 7.

ЗАДАЧА 3.В. Решение конечной игры в чистых стратегиях методом минимакса с помощью седловой точки

Для игр с приведенными платежными матрицами определить:

— нижнюю и верхнюю цены игры;

— минимаксные стратегии;

— оптимальные решения игры в чистых стратегиях с помощью седловой точки.

Вариант 8. 2 5 3 3

6 8 5 7

3 5 4 4

2 3 4 4

Запишем матрицу игры в виде таблицы:

В1 В2 В3 B4 ?i Проанализируем ситуацию.

Какую бы стратегию не выбрал игрок А, его противник В выберет такую стратегию, чтобы минимизировать свой проигрыш. Так как W2 = -W1, то игрок В, тем самым, старается минимизировать выигрыш игрока А, т.е. чтобы выигрыш игрока А был равен

A1 2 5 3 3 2

A2 6 8 5 7 5

A3 3 5 4 4 3

A4 2 3 4 4 2

?j 6 8 5 5 ?=5

?=5

Определим ?i для каждой стратегии игрока А.

В ответ игрок А выберет свою стратегию таким образом, чтобы в этой cитуации максимизировать свой минимальный выигрыш, т.е.

a23 = 5.

? = 5 есть нижняя цена игры, она достигается при стратегии А2, которая является максиминной стратегией игрока А.

С другой стороны, какую бы стратегию не выбрал игрок В, игрок А выберет свою такую стратегию, чтобы максимизировать свой выигрыш и, тем самым максимизировать проигрыш игрока В, т.е. .

Определим для каждой стратегии игрока В.

В ответ игрок В выберет свою стратегию таким образом, чтобы в этой ситуации минимизировать свой проигрыш, т.е.

a23 = 5.

? = 5 есть верхняя цена игры, она достигается при стратегии В3, которая является минимаксной стратегией игрока В.

В данной игре ?=?= a23 = 5, т.е. игра имеет седловую точку, в которой оба игрока получают свои гарантированные выигрыши, равные цене игры

V = ?= ? = 5.

Стратегии А2 и В3 являются оптимальными стратегиями.

ЗАДАЧА 3.D. Приведение конечной матричной игры к задачам линейного программирования;

Для игры, заданной платежной матрицей (таблицей) :

а) убедиться в отсутствии решения в чистых стратегиях;

б) обосновать необходимость решения игры путем приведения ее к задаче ЛП;

в) сформулировать для игроков соответствующие задачи линейного программирования (составить целевые функции, системы ограничительных условий), провести анализ полученных задач ЛП на двойственность.

Вариант 8. 4 3 4 2

А = 3 4 6 5

2 5 1 3

5 3 6 11

Решение:

Сначала проверим наличие седловой точки в данной игре:

? = ?ij = max (2; 3; 1; 3) = 3

? = ?ij = min (5; 5; 6; 11) = 4.

Видим, что ???, то есть, игра не имеет седловой точки, следовательно ее решение ищем в области смешанных стратегий. Так как игра имеет размерность 4х4, для ее решения применим симплексный метод. С этой целью сведем игру к задаче линейного программирования.

Для определения оптимальной стратегии игрока А согласно теореме об активных стратегиях составим следующую систему уравнений:

4•р1 + 3•р2 + 2•р3 + 5•р4 ? ? — при В1;

3•р1 + 4•р2 + 5•р3 + 3•р4 ? ? — при В2

4•р1 + 6•р2 + р3 + 6•р4 ? ? — при В3;

2•р1 + 5•р2 + 3•р3 + 11•р4 ? ? — при В4;

р1 + р2 + р3 + р4 = 1, — как сумма вероятностей

рi ? 0, i = 1, 4 достоверных событий.

Разделив обе части неравенств и уравнения на ? ? 0 и обозначив Gi = pi/ ?, получим 4•G1 + 3•G2 + 2•G3 + 5•G4 ? 1;

3•G1 + 4•G2 + 5•G3 + 3•G4 ? 1;

4•G1 + 6•G2 + G3 + 6•G4 ? 1; (1.1)

2•G1 + 5•G2 + 3•G3 + 11•G4? 1;

G1 + G2 + G3 + G4 = 1/ ?.

Решение игры для игрока А должно максимизировать значение ?, значит, функция Ф = 1/? = G1 + G2 + G3 + G4 должна принимать минимальное значение. То есть, имеем задачу линейного программирования :

найти значения переменных Gi ? 0, i = 1, 4, обеспечивающие минимум линейной функции Ф = G1 + G2 + G3 + G4 при ограничениях (1.1) и условии неотрицательности переменных Gi

Для определения оптимальной стратегии игрока В составим систему

уравнений: 4•q1 + 3•q2 + 4•q3 + 2•q4 ? ? — при А1;

3•q1 + 4•q2 + 6•q3 + 5•q4 ? ? — при А2;

2•q1 + 5•q2 + q3 + 3•q4 ? ? — при А3;

5•q1 + 3•q2 + 6•q3 +11•q4 ? ? — при А4;

q1 + q2 + q3 + q4= 1; qj ? 0, ( j = 1, 4 )

Разделив обе части уравнений на ? > 0 и обозначив Uj = qj/ ?, получим 4•U1 + 3•U2 + 4•U3 + 2•U4 ? 1,

3•U1 + 4•U2 + 6•U3 + 5•U4 ? 1, (1.2)

2•U1 + 5•U2 + U3 + 3•U4 ? 1,

5•U1 + 3•U2 + 6•U3 + 11•U4 ? 1,

U1 + U2 + U3 + U4 = 1/ ?.

Так как решение игры для игрока В должно минимизировать ?, следовательно максимизировать 1/ ?, получим задачу линейного программирования:

найти значения переменных Uj ? 0, j = 1, 4, обеспечивающие максимум линейной функции F = 1/ ? = U1 + U2 + U3 + U4 при ограничениях (1.2) и условии неотрицательности переменных Gi

Данная задача является двойственной к задаче определения оптимальной стратегии игрока А. Введя дополнительные неотрицательные переменные z1, z2, z3, z4 приведем ее к каноническому виду, затем решим полученную задачу линейного программирования с помощью симплексного метода.