Находим решение игры в смешанных стратегиях.
Математические модели пары двойственных задач линейного программирования можно записать так:
найти минимум функции 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/