Теория игр находится в тесной связи с линейным программированием, так как каждая конечная игра двух лиц с нулевой суммой может быть представлена как задача линейного программирования и решена симплексным методом и, наоборот, каждая задача линейного программирования может быть представлена как конечная игра двух лиц с нулевой суммой. Рассмотрим игру двух лиц с нулевой суммой, заданную платежной матрицей
.
Если платежная матрица не имеет седловой точки, т.е. a <b и , то решение игры представлено в смешанных стратегиях
(x1, x2, ., xm) и
(y1, y2, ., yn). Применение первым игроком оптимальной стратегии
опт должно обеспечить ему при любых действиях второго игрока выигрыш не меньше цены игры.
,
.
Рассмотрим задачу отыскания оптимальной стратегии игрока А, для которой имеют место ограничения
Величина v неизвестна, однако можно считать, что цена игры v > 0. Последнее условие выполняется всегда, если все элементы платежной матрицы неотрицательны, а этого можно достигнуть, прибавив ко всем элементам матрицы некоторое положительное число.
Преобразуем систему ограничений, разделив все члены неравенств на v.
(1)
где
,
. (2)
По условию x1 + x2 + … +xm = 1.
Разделим обе части этого равенства на v.
.
Оптимальная стратегия (x1, x2, ., xm) игрока А должна максимизировать величину v, следовательно, функция
(3)
должна принимать минимальное значение.
Таким образом, получена задача линейного программирования: найти минимум целевой функции (3) при ограничениях (1), причем на переменные наложено условие неотрицательности (2). Решая ее, находим значения ,
и величину 1/v, затем отыскиваются значения xi = vti.
Аналогично для второго игрока оптимальная стратегия опт должна обеспечить при любых стратегиях первого игрока проигрыш, не превышающий цену игры.
,
.
Рассмотрим задачу отыскания оптимальной стратегии игрока B, для которой имеют место ограничения
Преобразуем систему ограничений, разделив все члены неравенств на v.
Похожие статьи:
Функции форм обучения
Обучающе-образовательная. Форма обучения конструируется и используется для того, чтобы создать наилучшие условия для передачи обучаемым знаний, умений и навыков, формирования их мировоззрения, развития дарований, практических способностей, активного участия в производстве и общественной жизни. Восп ...
Методика разработки программы развития ДОУ
Программа развития дошкольного учреждения должна отвечать следующим качествам: Актуальность — свойство программы быть ориентированной на решение наиболее важных проблем для будущей системы дошкольного воспитания конкретного детского сада. Прогностичность — свойство программы отражать в своих целях ...
Теоретические основы проблемы изучения словообразования
существительных в онтогенезе
Современные представления о речевой деятельности, во многом основанные на данных онтогенеза, позволили сформулировать некоторые базовые положения о языковой способности как о функционирующем механизме. Процесс формирования речевой деятельности в онтогенезе рассматривается как развитие связи, устана ...