Лекция: Решение игры для игрока B

Перейдем к матрице с неотрицательными элементами так же как и при решении для участника А. Через обозначим проигрыш игрока при фиксированной стратегии игрока :

.

Для вероятностей выполняется условие: .

Введем обозначение. Задача минимизации эквивалентна поиску.Произведем замену переменных:

.

Получаем задачу линейного программирования:

при ограничениях: (при ).

Решив задачу линейного программирования, получим и значение целевой функции ( ). Цена игры –, а искомые вероятности – .

Алгоритм решения игры n xm для участника В

1. Переходим к положительным элементам платежной матрицы:

.

2. Решаем задачу линейного программирования:

3. Интерпретируем результаты:

.

4. Корректируем :

.

Вернемся к теореме о минимаксе (см. п. 2.3).

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

для – из условия ,

для – из условия ,

– цена игры.

Доказательство.

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

;

и существует решение для участника В ,определяемоеиз условия:

.

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