56. Свойства оптимальных стратегий.

Теорема Пусть Е-мат.ожидание выигрыша в прямоуг-ой игре с м-цей порядка mxn, имеющей цену V.Тогда , для того чтобы эл-т Х^ мн-ва S_m был оптимальной стратегией для Р₁ необх-мо и дост-но, чтобы для каждого эл-та Y мн-ва S_n имело место нер-во V  E(X^ ,Y).Анал-но, для того чтобы эл-т Y^ мн-ва S_nбыл оптимальной стратегией для Р₂ необх-мо и дост-но, чтобы для каждого эл-та X мн-ва S_m имело место нер-во E(X,Y^ )  V.

 Теорема Пусть Е-мат.ожидание выигрыша прямоуг-ой игры с м-цей порядка mxn, пусть V-действ-ое число, и пусть X^ и Y^ - соот-но эл-ты мн-в S_m и S_n. Тогда, для того чтобы V было ценой игры, а X^ и Y^ - оптимальными стратегиями соот-но для Р₁ и Р₂, необх-мо и дост-но, чтобы для 1  i  m и 1  j  n     E(i,Y^ ) V  E(X^ ,j).

 Теорема Пусть Е-мат.ожидание выигрыша прямоуг-ой игры с м-цей порядка mxn, цена кот-рой есть V. Тогда, для того чтобы эл-т X^ мн-ва S_m был оптимальной стратегией для Р₁ необх-мо и дост-но, чтобы для 1  j  n выполнялось V  E(X^ ,j). Анал-но, для того чтобы эл-т Y^ мн-ва S_n был оптимальной стратегией для Р₂ необх-мо и дост-но, чтобы для 1  i  m выполнялось E(i,Y^ )  V.

 Теорема Пусть Е-мат.ожидание выигрыша прямоуг-ой игры с м-цей порядка mxn, пусть X^Y^ - решение этой игры. Тогда max_{1  i  m} E(i,Y^ )=min_{1  j  n} E(X^ ,j).

 Теорема Пусть Е-мат.ожидание выигрыша для прямоуг-ой игры с м-цей порядка mxn, имеющей цену V, и пусть X^=x₁^...x_m^ и Y^=y₁^...y_n^ - оптимальные стратегии соот-но для Р₁ и Р₂. Тогда для любого i, при кот-ром E(i,Y^ ) < V, имеет место рав-во x_i^=0, а для любого j такого,что V < E(X^ ,j), имеет место рав-во y_j^=0.

 Теорема Пусть Е-мат.ожидание выигрыша прямоуг-ой игры с м-цей порядка mxn, и пусть Х^ и Y^ - соот-но эл-ты мн-в S_m и S_n.Тогда имеют место следующие эквивал-ные утверждения:

 1.X^ есть оптимальная стратегия для Р₁, а Y^ - для Р₂.

2.Если Х есть любой эл-т мн-ва S_m, а Y - любой эл-т мн-ва S_n, то E(X,Y^ )  E(X^ ,Y^ )  E(X^ ,Y).

3. Если i и j любые целые числа, такие, что 1  i  m и 1  j  n, то E(i,Y^ )  E(X^ ,Y^ )  E(X^ ,j).

56. Решение матричных игр методом линейного программирования.

Теория игр находится в тесной связи с линейным программированием, так как любую конечную игру двух лиц с нулевой суммой можно представить в виде задачи линейного программирования и наоборот. Дж. Данциг отмечает, что, когда в 1947 году создатель теории игр Дж. фон Нейман впервые ознакомился с симплекс-методом, он сразу установил эту взаимосвязь и обратил особое внимание на концепцию двойственности в линейном программировании. Этот шаг иллюстрирует решение матричных игр методами линейного программирования.

    Оптимальные значения вероятностей x_i, i = 1, 2, ..., m, игрока А могут быть определены путем решения следующей максиминной задачи.

    Чтобы сформулировать эту задачу в виде задачи линейного программирования, положим

    Отсюда вытекает, что

    Следовательно, задача игрока А может быть записана в виде

    Отметим последнее условие, что цена игры v может быть как положительной, так и отрицательной. Оптимальные стратегии y₁, y₂, ...,y_n игрока В определяются путем решения задачи

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

    Две полученные задачи оптимизируют одну и ту же (не ограниченную в знаке) переменную v, которая является ценой игры. Причиной этого служит то, что задача игрока В является двойственной к задаче игрока А. Это означает, что оптимальное решение одной из задач автоматически определяет оптимальное решение другой.