Вариант 15. Решить матричные игры со следующими матрицами потерь первого игрока

  • ID: 23110 
  • 11 страниц

Фрагмент работы:

Вариант 15. Решить матричные игры со следующими матрицами потерь п…

1 - 3 Решить матричные игры со следующими матрицами потерь первого игрока:

Решение:

1)...

Определим верхнюю и нижнюю цену игры:

?1 ?2 ?3...

?1 -6 0 -2 0

?2 0 -1 1 1

-6 -1 -2

0

-1

Т.к...., то игра не имеет седловой точки и неразрешима в чистых стратегиях.

Найдем решение игры графическим методом. Т.к. две стратегии имеет первый игрок, то решаем задачу первого игрока. Сначала составляем линейные функции, которые выражают ожидаемые выигрыши первого игрока, соответствующие чистым стратегиям второго игрока

Строим эти прямые на графике на отрезке 0..1 и находим верхнюю огибающую этих прямых.

Как видно из рисунка, решением является точка пересечения функций f2 и f3. Найдем координаты точки пересечения.

==>..., ==>...

Таким образом, оптимальная стратегия первого игрока будет....

Цена игры

Найдем оптимальную стратегию второго игрока. Т.к...., то y1=0 и стратегия второго игрока принимает вид y = (0, y2, 1-y2). Тогда

==>...

Таким образом, оптимальная стратегия второго игрока будет y = (0; 0,75; 0,25).

2)...

Определим верхнюю и нижнюю цену игры:

?1 ?2 ?3 ?4...

?1 7 -8 2 -6 7

?2 8 0 2 9 9

?3 0 -9 -3 -9 0

?4 -3 -3 -3 0 0

-3 -9 -3 -9

0

-3

Т.к...., то игра не имеет седловой точки и неразрешима в чистых стратегиях.

Упростим игру. Стратегия ?3 доминирует стратегии ?1 и ?2, поэтому их можно исключить.

Получим игру:....

Далее. Стратегия ?1 доминирует стратегии ?2 и ?3, поэтому их можно исключить. Получим игру 2х2:...

Найдем решение этой игры. Обозначим через d=a11+a22-a12-a21

=...

Учитывая отброшенные стратегии, получим следующее решение:

3)...

Определим верхнюю и нижнюю цену игры:

?1 ?2 ?3 ?4...

?1 7 8 9 6 9

?2 8 9 7 6 9

?3 9 7 8 6 9

?4 5 5 5 7 7

5 5 5 6

7

6

Т.к...., то игра не имеет седловой точки и неразрешима в чистых стратегиях.

Эта игра упрощению не подлежит, т.к. ни одна из стратегий не доминирует над другой как у первого, так и у второго игрока.

Составим системы уравнений для прямой и двойственной задач линейного программирования для нахождения решения этой игры:

прямая задача:

двойственная задача:

Найдем решение этих задач двойственным симплекс-методом:

v1 v2 v3 v4

x1 x2 x3 x4...

u1 y1 7 8 9 5 1

u2 y2 8 9 7 5 1

u3 y3 9 7 8 5 1

u4 y4 6 6 6 7 1

-1 -1 -1 -1 0

Разрешающий столбец любой, т.к. в последней строке симплекс-таблицы находятся одинаковые числа. Пусть это будет первый столбец. Минимальное симплексное отношение равно:..., ==> разрешающая строка третья, а разрешающий элемент равен 9. Переходим к следующей симплекс-таблице:

u3 v2 v3 v4

y3 x2 x3 x4...

u1 y1 - 7/9 2 5/9 2 7/9 1 1/9 2/9

u2 y2 - 8/9 2 7/9 - 1/9 5/9 1/9

v1 x1 1/9 7/9 8/9 5/9 1/9

u4 y4 - 2/3 1 1/3 2/3 3 2/3 1/3

1/9 - 2/9 - 1/9 - 4/9 1/9

Разрешающий столбец четвертый, разрешающая строка также четвертая, а разрешающий элемент равен 11/3. Переходим к следующей симплекс-таблице:

u3 v2 v3 u4

y3 x2 x3 y4...

u1 y1 - 19/33 2 5/33 2 19/33 - 10/33 4/33

u2 y2 - 26/33 2 19/33 - 7/33 - 5/33 2/33

v1 x1 7/33 19/33 26/33 - 5/33 2/33

v4 x4 - 2/11 4/11 2/11 3/11 1/11

1/33 - 2/33 - 1/33 4/33 5/33

Разрешающий столбец второй, разрешающая строка также вторая, а разрешающий элемент равен 85/33. Переходим к следующей симплекс-таблице:

u3 u2 v3 u4

y3 y2 x3 y4...

u1 y1 7/85 - 71/85 2 64/85 - 3/17 6/85

v2 x2 - 26/85 33/85 - 7/85 - 1/17 2/85

v1 x1 33/85 - 19/85 71/85 - 2/17 4/85

v4 x4 - 6/85 - 12/85 18/85 5/17 7/85

1/85 2/85 - 3/85 2/17 13/85

Разрешающий столбец третий, разрешающая строка первая, а разрешающий элемент равен 234/84. Переходим к следующей симплекс-таблице:

u3 u2 u1 u4

y3 y2 y1 y4...

v3 x3 7/234 - 71/234 85/234 - 5/78 1/39

v2 x2 - 71/234 85/234 7/234 - 5/78 1/39

v1 x1 85/234 7/234 - 71/234 - 5/78 1/39

v4 x4 - 1/13 - 1/13 - 1/13 4/13 1/13

1/78 1/78 1/78 3/26 2/13

Находим решение игры:..., ==>...

4 Формализовать и решить матричную игру. Ответ записать словами (в терминах условия):

Бомбить аэродром отправляются 7 самолетов, 1 из них - бомбардировщик. Противник может выстрелить по одному самолету. При выстреле по самолету он поражает летящий первым с вероятностью 0,6, любой другой - с вероятностью 0,4. Аэродром разбомблен, если бомбардировщик уцелел.

Решение:

Данную задачу можно рассматривать как игру, в которой у 1 игрока (аэродром) есть 7 стратегий:

I: ?i={выстрелить по i-му самолету}...

У второго игрока (самолеты) есть также 7 стратегий:

II: ?j={бомбардировщик находится на j-м месте}...

Определим потери 1 игрока в каждом случае. Будем считать, что если аэродром разбомблен, то потери 1 игрока равны 1, в противном случае -1. Очевидно, что если нет выстрела по бомбардировщику, то аэродром однозначно разбомблен, поэтому aij=1.... При i=j=1 получаем следующие потери I игрока: 0,6?(-1)+0,4?1=-0,2, а в остальных случаях 0,4?(-1)+0,6?1=0,2. Получим следующую матрицу потерь первого игрока.

I II ?1 ?2 ?3 ?4 ?5 ?6 ?7

?1 -0,2 1 1 1 1 1 1

?2 1 0,2 1 1 1 1 1

?3 1 1 0,2 1 1 1 1

?4 1 1 1 0,2 1 1 1

?5 1 1 1 1 0,2 1 1

?6 1 1 1 1 1 0,2 1

?7 1 1 1 1 1 1 0,2

Для нахождения решения игры определим, имеет ли матрица потерь седловую точку:

I II ?1 ?2 ?3 ?4 ?5 ?6 ?7...

?1 -0,2 1 1 1 1 1 1 1

?2 1 0,2 1 1 1 1 1 1

?3 1 1 0,2 1 1 1 1 1

?4 1 1 1 0,2 1 1 1 1

?5 1 1 1 1 0,2 1 1 1

?6 1 1 1 1 1 0,2 1 1

?7 1 1 1 1 1 1 0,2 1

-0,2 0,2 0,2 0,2 0,2 0,2 0,2

=1

=0,2

Т.к...., то игра не имеет седловой точки и неразрешима в чистых стратегиях.

Для нахождения решения составляем системы уравнений для прямой и двойственной задачи и находим их решение.

прямая задача:

двойственная задача:

Найдем решение этих задач двойственным симплекс-методом:

x1 x2 x3 x4 x5 x6 x7...

y1 -0,2 1 1 1 1 1 1 1

y2 1 0,2 1 1 1 1 1 1

y3 1 1 0,2 1 1 1 1 1

y4 1 1 1 0,2 1 1 1 1

y5 1 1 1 1 0,2 1 1 1

y6 1 1 1 1 1 0,2 1 1

y7 1 1 1 1 1 1 0,2 1

-1 -1 -1 -1 -1 -1 -1 0

Разрешающий столбец 1, разрешающая строка 2

y2 x2 x3 x4 x5 x6 x7...

y1 0,2 1,04 1,2 1,2 1,2 1,2 1,2 1,2

x1 1 0,2 1 1 1 1 1 1

y3 -1 0,8 -0,8 0 0 0 0 0

y4 -1 0,8 0 -0,8 0 0 0 0

y5 -1 0,8 0 0 -0,8 0 0 0

y6 -1 0,8 0 0 0 -0,8 0 0

y7 -1 0,8 0 0 0 0 -0,8 0

1 -0,8 0 0 0 0 0 1

Разрешающий столбец 2, разрешающая строка 3

y2 y3 x3 x4 x5 x6 x7...

y1 1,5 -1,3 2,24 1,2 1,2 1,2 1,2 1,2

x1 1,25 -0,25 1,2 1 1 1 1 1

x2 -1,25 1,25 -1 0 0 0 0 0

y4 0 -1 0,8 -0,8 0 0 0 0

y5 0 -1 0,8 0 -0,8 0 0 0

y6 0 -1 0,8 0 0 -0,8 0 0

y7 0 -1 0,8 0 0 0 -0,8 0

0 1 -0,8 0 0 0 0 1

Разрешающий столбец 3, разрешающая строка 4

y2 y3 y4 x4 x5 x6 x7...

y1 1,5 1,5 -2,8 3,44 1,2 1,2 1,2 1,2

x1 1,25 1,25 -1,5 2,2 1 1 1 1

x2 -1,25 0 1,25 -1 0 0 0 0

x3 0 -1,25 1,25 -1 0 0 0 0

y5 0 0 -1 0,8 -0,8 0 0 0

y6 0 0 -1 0,8 0 -0,8 0 0

y7 0 0 -1 0,8 0 0 -0,8 0

0 0 1 -0,8 0 0 0 1

Разрешающий столбец 4, разрешающая строка 5

y2 y3 y4 y5 x5 x6 x7...

y1 1,5 1,5 1,5 -4,3 4,64 1,2 1,2 1,2

x1 1,25 1,25 1,25 -2,75 3,2 1 1 1

x2 -1,25 0 0 1,25 -1 0 0 0

x3 0 -1,25 0 1,25 -1 0 0 0

x4 0 0 -1,25 1,25 -1 0 0 0

y6 0 0 0 -1 0,8 -0,8 0 0

y7 0 0 0 -1 0,8 0 -0,8 0

0 0 0 1 -0,8 0 0 1

Разрешающий столбец 5, разрешающая строка 6

y2 y3 y4 y5 y6 x6 x7...

y1 1,5 1,5 1,5 1,5 -5,8 5,84 1,2 1,2

x1 1,25 1,25 1,25 1,25 -4 4,2 1 1

x2 -1,25 0 0 0 1,25 -1 0 0

x3 0 -1,25 0 0 1,25 -1 0 0

x4 0 0 -1,25 0 1,25 -1 0 0

x5 0 0 0 -1,25 1,25 -1 0 0

y7 0 0 0 0 -1 0,8 -0,8 0

0 0 0 0 1 -0,8 0 1

Разрешающий столбец 6, разрешающая строка 7

y2 y3 y4 y5 y6 y7 x7...

y1 1,5 1,5 1,5 1,5 1,5 -7,3 7,04 1,2

x1 1,25 1,25 1,25 1,25 1,25 -5,25 5,2 1

x2 -1,25 0 0 0 0 1,25 -1 0

x3 0 -1,25 0 0 0 1,25 -1 0

x4 0 0 -1,25 0 0 1,25 -1 0

x5 0 0 0 -1,25 0 1,25 -1 0

x6 0 0 0 0 -1,25 1,25 -1 0

0 0 0 0 0 1 -0,8 1

Разрешающий столбец 7, разрешающая строка 1

y2 y3 y4 y5 y6 y7 y1...

x7 75/352 75/352 75/352 75/352 75/352 -1 13/352 25/176 15/88

x1 25/176 25/176 25/176 25/176 25/176 25/176 - 65/88 5/44

x2 -1 13/352 75/352 75/352 75/352 75/352 75/352 25/176 15/88

x3 75/352 -1 13/352 75/352 75/352 75/352 75/352 25/176 15/88

x4 75/352 75/352 -1 13/352 75/352 75/352 75/352 25/176 15/88

x5 75/352 75/352 75/352 -1 13/352 75/352 75/352 25/176 15/88

x6 75/352 75/352 75/352 75/352 -1 13/352 75/352 25/176 15/88

15/88 15/88 15/88 15/88 15/88 15/88 5/44 1 3/22

Находим решение игры:..., ==>...

Таким образом, с вероятностью 0,1 следует производить выстрел по первому самолету и с вероятностью 0,15 по любому другому. В этом случае из 25 выстрелов аэродром не будет уничтожен в среднем 3 раза.

5 - 6 Найти байесовскую стратегию первого игрока в играх с матрицами задач 1 - 2 в предположении, что второй игрок выбирает каждую последующую стратегию с вероятностью вдвое большей, чем предыдущую.

Решение:

5) Пусть вероятность выбора вторым игроком первой стратегии равна q1, тогда вероятность выбора второй и третьей стратегий соответственно будут равны 2q1 и 4q1, а их сумма будет равна 7q1, ==>.... Рассчитаем средние потери для каждой стратегии первого игрока:

=...

=...

-2, поэтому по байесовскому подходу оптимальная стратегия первого игрока будет стратегия ?1.

6) Пусть вероятность выбора вторым игроком первой стратегии равна q1, тогда вероятность выбора второй, третьей и четвертой стратегий соответственно будут равны 2q1, 4q1 и 8q1, а их сумма будет равна 15q1, ==>.... Рассчитаем средние потери для каждой стратегии первого игрока:

=...

=...

=...

=...

-..., поэтому по байесовскому подходу оптимальная стратегия первого игрока будет стратегия ?3.

7 - 8 Найти минимаксную и байесовскую (с равными вероятностями применения стратегий вторым игроком) стратегии в статистической игре с матрицами:

Решение:

7) Найдем чистые стратегии первого игрока в статистической игре. Всего таких стратегий будет 22=4:............

Отобразим на плоскости точки...:

Определим минимаксную стратегию:

8) Определим байесовскую стратегию при равных вероятностях применения стратегий вторым игроком. Для этого рассчитаем средние потери для каждой стратегии первого игрока:

=...

=...

=...

=...

Выбираем среди них минимальные. Минимальные средние потери соответствуют стратегии S4.