Платёжная матрица имеет вид:
Решение:
Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.
| Игроки | B1 | B2 | B3 | B4 | a = min(Ai) |
| A1 | 3 | -1 | 5 | 3 | -1 |
| A2 | 1 | 2 | 0 | 4 | 0 |
| A3 | 2 | -1 | 3 | 2 | -1 |
| A4 | -3 | 0 | -2 | 5 | -3 |
| b = max(Bi) | 3 | 2 | 5 | 5 |
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 0, которая указывает на максимальную чистую стратегию A2.
Верхняя цена игры b = min(bj) = 2.
Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 0 ≤ y
Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.
Стратегия A1 доминирует над стратегией A3 (все элементы строки 1 больше или равны значениям 3-ой строки), следовательно исключаем 3-ую строку матрицы. Вероятность p3 = 0.
| 3 | -1 | 5 | 3 |
| 1 | 2 | 0 | 4 |
| -3 | 0 | -2 | 5 |
С позиции проигрышей игрока В стратегия B1 доминирует над стратегией B4 (все элементы столбца 1 меньше элементов столбца 4), следовательно исключаем 4-й столбец матрицы. Вероятность q4 = 0.
| 3 | -1 | 5 |
| 1 | 2 | 0 |
| -3 | 0 | -2 |
Стратегия A2 доминирует над стратегией A3 (все элементы строки 2 больше или равны значениям 3-ой строки), следовательно исключаем 3-ую строку матрицы. Вероятность p3 = 0.
| 3 | -1 | 5 |
| 1 | 2 | 0 |
Мы свели игру 4 x 4 к игре 2 x 3.
Так как игроки выбирают свои чистые стратегии случайным образом, то выигрыш игрока I будет случайной величиной. В этом случае игрок I должен выбрать свои смешанные стратегии так, чтобы получить максимальный средний выигрыш.
Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.
В матрице присутствуют отрицательные элементы. Для упрощения расчетов добавим к элементам матрицы (1). (по теореме фон Неймана).
| 4 | 0 | 6 |
| 2 | 3 | 1 |
Находим решение игры в смешанных стратегиях.
Математические модели пары двойственных задач линейного программирования можно записать так:
найти минимум функции F(x) при ограничениях:
4x1+2x2 ≥ 1
3x2 ≥ 1
6x1+x2 ≥ 1
F(x) = x1+x2 → min
найти максимум функции Ф(y) при ограничениях:
4y1+6y3 ≤ 1
2y1+3y2+y3 ≤ 1
Ф(y) = y1+y2+y3 → max
Определим максимальное значение целевой функции F(X) = x1 + x2 + x3 при следующих условиях-ограничений.
4x1 + 6x3≤1
2x1 + 3x2 + x3≤1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
4x1 + 0x2 + 6x3 + 1x4 + 0x5 = 1
2x1 + 3x2 + 1x3 + 0x4 + 1x5 = 1
| Базис | B | x1 | x2 | x3 | x4 | x5 | min |
| x4 | 1 | 4 | 0 | 6 | 1 | 0 | 1/6 |
| x5 | 1 | 2 | 3 | 1 | 0 | 1 | 1 |
| F(X1) | 0 | -1 | -1 | -1 | 0 | 0 | 0 |
| Базис | B | x1 | x2 | x3 | x4 | x5 | |
| x3 | 1/6 | 2/3 | 0 | 1 | 1/6 | 0 | |
| x5 | 5/6 | 4/3 | 3 | 0 | -1/6 | 1 | |
| F(X1) | 1/6 | -1/3 | -1 | 0 | 1/6 | 0 | |
| Базис | B | x1 | x2 | x3 | x4 | x5 | min |
| x3 | 1/6 | 2/3 | 0 | 1 | 1/6 | 0 | — |
| x5 | 5/6 | 11/3 | 3 | 0 | -1/6 | 1 | 5/18 |
| F(X2) | 1/6 | -1/3 | -1 | 0 | 1/6 | 0 | 0 |
| Базис | B | x1 | x2 | x3 | x4 | x5 | |
| x3 | 1/6 | 2/3 | 0 | 1 | 1/6 | 0 | |
| x2 | 5/18 | 4/9 | 1 | 0 | -1/18 | 1/3 | |
| F(X2) | 4/9 | 1/9 | 0 | 0 | 1/9 | 1/3 |
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Оптимальный план можно записать так:
x3 = 1/6
x2 = 5/18
F(X) = 1•1/6 + 1•5/18 = 4/9
Цена игры будет равна g = 1/F(x)
вероятности применения стратегий игроков: qi = g*yi; pi = g*xi.
В нашем случае
Цена игры: g = 1/4/9 = 9/4
p1 = 9/4 • 1/9 = ¼
p2 = 9/4 • 1/3 = ¾
Оптимальная смешанная стратегия игрока I:
P = (1/4; 3/4)
q1 = 9/4 • 0 = 0
q2 = 9/4 • 5/18 = 5/8
q3 = 9/4 • 1/6 = 3/8
Оптимальная смешанная стратегия игрока II:
Q = (0; 5/8; 3/8)
Поскольку ранее к элементам матрицы было прибавлено число 1, то вычтем это число из цены игры. 9/4 — 1 = 5/4
Цена игры: v=5/4/