НОВОСТИ    БИБЛИОТЕКА    ЭНЦИКЛОПЕДИЯ    БИОГРАФИИ    КАРТА САЙТА    ССЫЛКИ    О ПРОЕКТЕ  

предыдущая главасодержаниеследующая глава

7.7. Матричные игры и линейное программирование

Рассмотрим антагонистическую игру с матрицей выигрыша A = (aij) размерности m×n:


Пусть вектор вероятностей x = (x1, x2, ..., xm) (где xi ≥ 0 при всех i = 1, ..., m, и ) есть некоторая оптимальная стратегия первого игрока. Тогда, применяя против нее любую свою стратегию, второй игрок не сможет помешать первому выиграть v или даже больше, чем v, где v - цена игры (вспомним теорему о минимаксе!), пока нам неизвестная. Таким- образом, можно записать неравенства


Кроме того, можно учесть условие нормировки вектора х:

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


Теперь введем новые переменные


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


при ограничениях

a11ξ1 + a21ξ2 + a31ξ3 + ... + am1ξm≥1,
a12ξ1 + a22ξ2 + a32ξ3 + ... + am2ξm≥1,
.......................
a1nξ1 + a2nξ2 + a3nξ3 + ... + amnξm≥1,
ξi≥0 (i = 1, ..., m).

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

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

Теперь - хоккей!

предыдущая главасодержаниеследующая глава











© MATHEMLIB.RU, 2001-2021
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'Математическая библиотека'
Рейтинг@Mail.ru