§3. Теорема существования решений в смешанных стратегиях

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

Пусть для игры Г с – матрицей цена положительна. Это условие не ограничивает общность рассуждений, т.к. прибавлением ко всем элементам матрицы , положительного числа можно сформировать новую матрицу , все элементы которой

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

Согласно теореме 2.3 оптимальная смешанная стратегия второго игрока и цена должны удовлетворять условиям

, (3.1)

, (3.2)

. (3.3)

Так как , то после деления соотношений (3.1) – (3.3) на знаки неравенств в них не изменятся, а обозначив

, (3.4)

получим систему

, (3.5)

, (3.6)

. (3.7)

Поскольку цена игры это выигрыш первого игрока, то второй игрок заинтересован в минимизации . Конечно, он этого реально сделать не может, т.к. цена определяется заданием матрицы выигрышей и равна значению функции в ее седловой точке. Но возникает подозрение, не следует ли для нахождения оптимальной стратегии второго игрока решить задачу минимизации неизвестной при ограничениях (3.5) и (3.7), т.е. задачу линейного программирования

, (3.8)

, (3.9)

, (3.10)

затем найти из равенства (3.6) и по формулам (3.4)?

Аналогично рассуждая за первого игрока, используем теорему 2.1, согласно которой оптимальная стратегия первого игрока и цена должны удовлетворять условиям

,

,

.

А после деления этих соотношений на , введения обозначения

(3.11)

желание первого игрока максимизировать приведет к задаче линейного программирования

(3.12)

, (3.13)

, (3.14)

которая является двойственной для задачи (3.8) – (3.10). Будут ли , найденные по формулам (3.11) координатами оптимальной стратегии?

Исследуем итоги проведенного анализа и высказанных предположений.

Теорема 3.1 (существования решения игр). Любая матричная игра имеет решение в смешанных стратегиях.

Доказательство. Пусть Г – игра, определена матрицей , все элементы которой положительны. Как уже отмечалось в начале настоящего параграфа, это предположение не ограничивает общности рассуждений. Построим пару двойственных задач (3.8) – (3.10) и (3.12) – ( 3.14). В силу (3.10) переменные ограничены снизу, а в силу (3.9) и условия для всех , все переменные ограничены сверху. Таким образом, множество допустимых решений в задаче (3.8) – (3.10) является ограниченным. Поскольку во всех ограничениях этой задачи присутствует знак равенства, то оно и замкнуто. Значит, непрерывная функция достигает на множестве допустимых решений своего максимума. Следовательно, задача (3.8) – (3.10) имеет решение, но тогда по основной

теореме двойственности и двойственная ей задача (3.12) – (3.14) имеет решение.

Пусть – решения задач (3.8) – (3.10) и (3.12) – (3.14), соответственно. По лемме двойственности значения линейных форм двойственных задач для оптимальных планов совпадают, т.е.

. (3.15)

Из (3.13) следует, что . Обозначим

.

Отсюда число положительно, для всех и , . Таким образом, векторы являются смешанными стратегиями. Убедимся, наконец, что эти стратегии являются оптимальными, а число – ценой игры.

Так как вектор удовлетворяет ограничениям задачи (3.8) – (3.10), а – ограничениям задачи , то, подставляя их в неравенства (3.9), (3.13), получим

; .

Отсюда для числа и смешанных стратегий выполняются неравенства

.

Тогда в силу следствия теоремы 2.1 число – цена игры а – оптимальные смешанные стратегии. Теорема доказана.

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

1. Для решения игры, заданной матрицей размерности и имеющей положительную цену, выписывается пара двойственных задач (3.8) – (3.10) и (3.12) – (3.14) .

2. Отыскиваются решения задач (3.8) – (3.10) и (3.12) – (3.14). Пусть – решения задач (3.8) – (3.10) и (3.12) – (3.14), соответственно, и – минимальное значение линейной формы (3.8). Вычисляется цена игры.

3. Вычисляются координаты оптимальных стратегий по формулам . Решение окончено.

Оказывается, что для нахождения оптимальных стратегий не обязательно решать обе задачи, поставленные в первом пункте сформулированного принципа. Покажем, что достаточно решить симплексным методом наиболее простую из них – задачу (3.8) – (3.10), а решение задачи (3.12) – (3.14) можно найти в строке оценок заключительной симплексной таблицы. После обоснования этого утверждения будет сформулирован реализуемый алгоритм.