Решение игры в смешанных стратегиях 2 (стр. 2 из 5)

рис 1.

Через точки

проводятся оси I-I, II-II и III-III, перпендикулярные к плоскости

. На оси I-I откладываются выигрыши при стратегии на осях II-II и III-III — выигрыши при стратегиях . Каждая стратегия противника

изобразится плоскостью, отсекающей на осях I-I, II-II и III-III, отрезки, равные выигрышам

при соответствующих стратегия

и стратегия

. Построив, таким образом, все стратегии противника, мы получим семейство плоскостей над треугольником (рис2) .

рис 2

Для этого семейства также можно построить нижнюю границу выигрыша, как мы это делали в случае,

и найти на этой границе точку N с максимальной высотой нал плоскостью . Эта высота и будет ценой игры .

Частоты

стратегий в оптимальной стратегии будут определяться координатами (x, у) точки N, а именно:

Однако такое геометрическое построение даже для случая

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

Все эти методы по существу сводятся к решению задачи путем последовательных проб, но упорядочение последовательности проб позволяет построить алгоритм, приводящий к решению наиболее экономичным способом.

Здесь мы вкратце остановимся на одном расчетном методе решения игр

— на так называемом методе «линейного программирования».

Для этого дадим сначала общую постановку задачи о нахождении решения игры

. Пусть дана игра с т стратегиями игрока А иnстратегиями игрока В и задана платежная матрица

Требуется найти решение игры, т. е. две оптимальные смешанные стратегии игроков А и В

где

(некоторые из чисел и могут быть равными нулю).

Наша оптимальная стратегия S*_Aдолжна обеспечивать нам выигрыш, не меньший

, при любом поведении противника, и выигрыш, равный , при его оптимальном поведении (стратегия S*_B).Аналогично стратегия S*_Bдолжна обеспечивать противнику проигрыш, не больший , при любом нашем поведении и равный при нашем оптимальном поведении (стратегия S*_A).

Величина цены игры

в данном случае нам неизвестна; будем считать, что она равна некоторому положительному числу. Полагая так, мы не нарушаем общности рассуждений; для того чтобы было > 0, очевидно, достаточно, чтобы все элементы матрицы были неотрицательными. Этого всегда можно добиться, прибавляя к элементам достаточно большую положительную величину L;при этом цена игры увеличится на L, а решение не изменится.

Пусть мы выбрали свою оптимальную стратегию S*_A. Тогда наш средний выигрыш при стратегии

противника будет равен:

Наша оптимальная стратегия S*_Aобладает тем свойством, что при любом поведении противника обеспечивает выигрыш не меньший, чем

; следовательно, любое из чисел не может быть меньше . Получаем ряд условий:

(1)

Разделим неравенства (1) на положительную величину

и обозначим :

Тогда условие (1) запишется виде

(2)

где

— неотрицательные числа. Так как величины удовлетворяют условию

(3)

Мы хотим сделать свой гарантированный выигрыш максимально возможным; очевидно, при этом правая часть равенства (3) принимает минимальное значение.

Таким образом, задача нахождения решения игры сводится к следующей математической задаче: определить неотрицательные величины

, удовлетворяющиеусловиям (2), так, чтобы их сумма

была минимальной.

Обычно при решении задач, связанных с нахождением экстремальных значений (максимумов и минимумов), функцию дифференцируют и приравнивают производные нулю. Но такой прием в данном случае бесполезен, так как функция Ф, которую нужно обратить в минимум, линейна, и ее производные по всем аргументам равны единице, т. е. нигде не обращаются в нуль. Следовательно, максимум функции достигается где-то на границе области изменения аргументов, которая определяется требованием неотрицательности аргументов и условиями (2). Прием нахождения экстремальных значений при помощи дифференцирования непригоден и в тех случаях, когда для решения игры определяется максимум нижней (или минимум верхней) границы выигрыша, как мы. например, делали при решении игр

.Действительно, нижняя граница составлена из участков прямых линий, и максимум достигается не в точке, где производная равна нулю (такой точки вообще нет), а на границе интервала или в точке пересечения прямолинейных участков.

Для решения подобных задач, довольно часто встречающихся на практике, в математике разработан специальный аппарат линейного программирования.

Задача линейного программирования ставится следующим образом.

Дана система линейных уравнений:

(4)

Требуется найти неотрицательные значения величин

удовлетворяющие условиям (4) и вместе с тем обращающие в минимум заданную однородную линейную функцию величин (линейную форму):