Решение игры в чистых стратегиях. Построение платежных матриц. Понятие и поиск седловой точки. Определение гарантированного и вероятностного выигрыша. Применение метода Гаусса при решении системы неравенств. Минимизация математического ожидания игрока.
Аннотация к работе
Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии). Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии). Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.
План
Оптимальный план можно записать так: x2 = 1/9 x3 = 1/18 x1 = 1/6
F(X) = 1•1/9 1•1/18 1•1/6 = 1/3
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис. Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных.
Тогда Y = C*A-1 =
Оптимальный план двойственной задачи равен: y1 = 1/6 y2 = 1/9 y3 = 1/18
Z(Y) = 1*1/6 1*1/9 1*1/18 = 1/3
Критерий оптимальности полученного решения. Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно.
Цена игры будет равна g = 1/F(x), а вероятности применения стратегий игроков: qi = g*yi; pi = g*xi.
Оптимальная смешанная стратегия игрока II: Q = (1/2; 1/3; 1/6)
Поскольку ранее к элементам матрицы было прибавлено число (3), то вычтем это число из цены игры.
3 - 3 = 0
Цена игры: v=0
4. Проверим правильность решения игры с помощью критерия оптимальности стратегии.
?aijqj ? v
?aijpi ? v
M(P1;Q) = (0•1/2) (1•1/3) (-2•1/6) = 0 = v
M(P2;Q) = (-1•1/2) (0•1/3) (3•1/6) = -0 = v
M(P3;Q) = (2•1/2) (-3•1/3) (0•1/6) = 0 = v
M(P;Q1) = (0•1/2) (-1•1/3) (2•1/6) = -0 = v
M(P;Q2) = (1•1/2) (0•1/3) (-3•1/6) = 0 = v
M(P;Q3) = (-2•1/2) (3•1/3) (0•1/6) = -0 = v
Все неравенства выполняются как равенства или строгие неравенства, следовательно, решение игры найдено верно.
Задание 6
Условие: Решить игру с природой, заданную платежной матрицей u по критерию Гурвица, ?=0,3;
u по критерию Лапласа;
u по критерию Сэвиджа;
u по критерию Вальда
Критерий Лапласа. Если вероятности состояний природы правдоподобны, для их оценки используют принцип недостаточного основания Лапласа, согласно которого все состояния природы полагаются равновероятными, т.е.: q1 = q2 = ... = qn = 1/n. qi = 1/4
Ai П1 П2 П3 П4 ?(aij)
A1 1.5 1.25 0.25 -0.75 2.25
A2 1 -0.5 2.5 0.25 3.25
A3 -0.75 2.25 -0.5 1.75 2.75
A4 0.25 1.5 0.5 2.5 4.75 pj 0.25 0.25 0.25 0.25
Выбираем из (2.25; 3.25; 2.75; 4.75) максимальный элемент max=4.75
Вывод: выбираем стратегию N=4.
Критерий Вальда. По критерию Вальда за оптимальную принимается чистая стратегия, которая в наихудших условиях гарантирует максимальный выигрыш, т.е. a = max(min aij)
Критерий Вальда ориентирует статистику на самые неблагоприятные состояния природы, т.е. этот критерий выражает пессимистическую оценку ситуации.
Ai П1 П2 П3 П4 min(aij)
A1 6 5 1 -3 -3
A2 4 -2 10 1 -2
A3 -3 9 -2 7 -3
A4 1 6 2 10 1
Выбираем из (-3; -2; -3; 1) максимальный элемент max=1
Вывод: выбираем стратегию N=4.
Критерий Севиджа. Критерий минимального риска Севиджа рекомендует выбирать в качестве оптимальной стратегии ту, при которой величина максимального риска минимизируется в наихудших условиях, т.е. обеспечивается: a = min(max rij)
Критерий Сэвиджа ориентирует статистику на самые неблагоприятные состояния природы, т.е. этот критерий выражает пессимистическую оценку ситуации.
Находим матрицу рисков.
Риск - мера несоответствия между разными возможными результатами принятия определенных стратегий.
Максимальный выигрыш в j-м столбце bj = max(aij) характеризует благоприятность состояния природы.
Выбираем из (13; 11; 12; 8) минимальный элемент min=8
Вывод: выбираем стратегию N=4.
Критерий Гурвица. Критерий Гурвица является критерием пессимизма - оптимизма.
За оптимальную принимается та стратегия, для которой выполняется соотношение: max(si) где si = y min(aij) (1-y)max(aij)
При y = 1 получим критерий Вальде, при y = 0 получим - оптимистический критерий (максимакс).
Критерий Гурвица учитывает возможность как наихудшего, так и наилучшего для человека поведения природы. Как выбирается y? Чем хуже последствия ошибочных решений, тем больше желание застраховаться от ошибок, тем y ближе к 1.