Решение задачи графическим методом

Симплекс-методом можно найти решение матричной игры произвольной размерности. Графическим же способом найти решение можно лишь для игры размерности 2 х n.

В ответе мы должны получить смешанные стратегии – два вектора PA = (p1, p2) и QB = (q1, q2, …, qn). Причем, p2 = 1 – p1.

В этом случае выигрыш игрока А, соответствующий j-той чистой стратегии игрока В, будет вычисляться по формуле:

aj* = a1j p1 + a2j p2 = a1j p1 + a2j (1 – p1) = (a1j – a2j) p1 + a2j

Нахождение наименьшего гарантированного выигрыша для игрока А подразумевает минимизацию данного выражения.

По условию наша игра имеет размерность 2 х n. То есть j = . В итоге будем иметь n аналогичных выражений, которые надо минимизировать. После этого согласно принципу максимина из найденных минимумов нужно выбрать наибольший:

a =

Решим графическим способом предыдущий числовой пример.

В данном случае будем иметь четыре уравнения, соответствующие четырем возможным чистым стратегиям игрока В:a1* = р1 + 3

a2* = –4р1 + 7

a3* = 7р1 + 1

a4* = –р1 + 3

Чтобы определить наилучший результат из наихудших, построим нижнюю огибающую четырех заданных прямых (на рисунке выделена жирной линией). Эта огибающая представляет минимальный гарантированный выигрыш игрока А, независимо от того, что делает игрок В. Точка максимума нижней огибающей – это и есть решение задачи по принципу максимина. Координатами этой точки будут р1 – одна из вероятностей смешанной стратегии игрока А и a – выигрыш игрока А.

# Заметим, что содержательной является только часть графика, заключенная в интервале 0 ≤ р1 ≤ 1 . Все линии и точки, лежащие за пределами этого интервала не принимаются во внимание. #

"На глаз" координаты точки максимума нижней огибающей видны плохо. Точка максимума нижней огибающей – это точка пересечения прямой 3 и прямой 4. Найдем её точные координаты, решив систему соответствующих уравнений:

Þ Þ Þ

Далее находим p2: p2 = 1 – p1 = 1 – =

Итак, для игрока А все ясно:

смешанная стратегия игрока А: Р = ,

выигрыш игрока А:a = .

Аналогичные рассуждения нужно повторить и для игрока В.

Точка максимума нижней огибающей – это точка пересечения прямой 3 и прямой 4. Значит оптимальная смешанная стратегия игрока В определяется двумя стратегиями В3 и В4 соответственно.

Проигрыш игрока В, соответствующий i-той чистой стратегии игрока A, будет вычисляться по формуле:

вi* = ai3 q3 + ai4 q4 = ai3 q3 + ai4 (1 – q3) = (ai3 – ai4) q3 + ai4

В данном случае будем иметь два уравнения, соответствующие двум возможным чистым стратегиям игрока А:

в1* = 6q3 + 2

в2* = –2q3 + 3

Решив систему этих двух уравнений, найдем q3 – одну из вероятностей смешанной стратегии игрока В и в – выигрыш игрока В:

Þ Þ Þ

Далее находим q4: q4 = 1 – q3 = 1 – =

Все выяснили также и для игрока В:

смешанная стратегия игрока В: Q =

проигрыш игрока В:в =

Выигрыш игрока А и проигрыш игрока В совпадают – это и будет ценой игры.

Ответ: смешанная стратегия для первого игрока Р = ,

смешанная стратегия для второго игрока Q = ,

цена игры n = .

Видим, что ответы в случае решения задачи симплекс-методом и в случае решения этой же задачи графическим методом совпали.

Мораль вышесказанного такова, что если имеем задачу размерности 2 х n и под рукой нет компьютера, то точное решение можно получить с помощью графического метода.

Если имеем задачу размерности m х 2 , то делаем то же самое, поменяв игроков местами и транспонировав платежную матрицу. #

Если же под рукой есть компьютер, то такие задачи удобнее решать симплекс-методом средствами MS Excel. Если же поставленная задача любой большей размерности, то решить ее можно только симплекс-методом либо вручную, либо опять таки средствами MS Excel.