Решить игру симплекс-методом 1 Проверяем имеет ли платежная матрица седловую точку

Решить игру симплекс-методом.

1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.
Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.
Находим гарантированный выигрыш, определяемый нижней ценой игры
a = max(ai) = 4, которая указывает на максимальную чистую стратегию A3.
Верхняя цена игры b = min(bj) = 4.
Седловая точка (3, 3) указывает решение на пару альтернатив (A3,B3). Цена игры равна 4.
2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы.
Иногда на основании простого рассмотрения матрицы игры можно сказать, что некоторые чистые стратегии могут войти в оптимальную смешанную стратегию лишь с нулевой вероятностью.
Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если aij ≥ akj для всех j Э N и хотя бы для одного j aij > akj. В этом случае говорят также, что i-я стратегия (или строка) – доминирующая, k-я – доминируемая.
Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M aij ≤ ail и хотя бы для одного i aij < ail. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю – доминируемой.
Стратегия A2 доминирует над стратегией A4 (все элементы строки 2 больше или равны значениям 4-ой строки), следовательно исключаем 4-ую строку матрицы. Вероятность p4 = 0.
В платежной матрице отсутствуют доминирующие столбцы.
Мы свели игру 4 x 4 к игре 3 x 4.
3. Находим решение игры в смешанных стратегиях.
Математические модели пары двойственных задач линейного программирования можно записать так:
найти минимум функции F(x) при ограничениях:
x1+3×2+5×3 ≥ 1
2×1+8×2+4×3 ≥ 1
3×1+2×2+4×3 ≥ 1
x2+6×3 ≥ 1
F(x) = x1+x2+x3 → min
найти максимум функции Ф(y) при ограничениях:
y1+2y2+3y3 ≤ 1
3y1+8y2+2y3+y4 ≤ 1
5y1+4y2+4y3+6y4 ≤ 1
Ф(y) = y1+y2+y3+y4 → max
Решаем эти системы симплексным методом.
Решение симплекс-методом доступно в расширенном режиме.
Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков:
pi = g*xi; qi = g*yi.
Цена игры: g = 1 : 1/4 = 4
p1 = 4 • 0 = 0
p2 = 4 • 0 = 0
p3 = 4 • 1/4 = 1
Оптимальная смешанная стратегия игрока I:
P = (0; 0; 1)
q1 = 4 • 0 = 0
q2 = 4 • 1/12 = 1/3
q3 = 4 • 1/6 = 2/3
q4 = 4 • 0 = 0
Оптимальная смешанная стратегия игрока II:
Q = (0; 1/3; 2/3; 0)
Цена игры: v=4
4. Проверим правильность решения игры с помощью критерия оптимальности стратегии.
∑aijqj ≤ v
∑aijpi ≥ v
M(P1;Q) = (1•0) + (2•1/3) + (3•2/3) + (0•0) = 2.67 ≤ v
M(P2;Q) = (3•0) + (8•1/3) + (2•2/3) + (1•0) = 4 = v
M(P3;Q) = (5•0) + (4•1/3) + (4•2/3) + (6•0) = 4 = v
M(P;Q1) = (1•0) + (3•0) + (5•1) = 5 ≥ v
M(P;Q2) = (2•0) + (8•0) + (4•1) = 4 = v
M(P;Q3) = (3•0) + (2•0) + (4•1) = 4 = v
M(P;Q4) = (0•0) + (1•0) + (6•1) = 6 ≥ v
Все неравенства выполняются как равенства или строгие неравенства, следовательно, решение игры найдено верно.
Поскольку из исходной матрицы были удалены строки, то найденные векторы вероятности можно записать в виде:
P(0,0,1,0)
Q(0,1/3,2/3,0)