Сведение матричной игры к задаче линейного программирования

Педагогика и воспитание » Теория игр » Сведение матричной игры к задаче линейного программирования

Страница 2

(4) где , . (5)

По условию y1 + y2 + … +yn = 1. Разделим обе части этого равенства на v.

.

Оптимальная стратегия (y1, y2, ., yn) игрока В должна минимизировать величину v, следовательно, функция

(6)

должна принимать максимальное значение.

Получена задача линейного программирования: найти максимум целевой функции (6) при ограничениях (4), причем на переменные наложено условие неотрицательности (5).

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

Пример. Найти решение игры, заданной матрицей

.

a = max (2, 3,1) = 3, b = min (4, 5, 6,5) = 4, a ¹ b, .

Игра не имеет седловой точки. Оптимальное решение следует искать в области смешанных стратегий.

Для определения оптимальной стратегии игрока А имеем следующую задачу линейного программирования:

,

*, .

Для нахождения оптимальной стратегии игрока В имеем следующую задачу линейного программирования:

,

, .

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

, , .

Учитывая соотношения между xi и ti, yj и sj, а также равенство

,

можно найти оптимальные стратегии игроков и цену игры:

* (1/2, 1/2, 0), (3/4, 0, 0, 1/4), v=7/2.

Страницы: 1 2 

Похожие статьи:

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

Контроль и оценка скоростных способностей у младших школьников
Л.П. Матвеев утверждает, что несмотря на то, что понятие «контроль» представляется вполне ясным (проверка, обследование, наблюдение, оценка и т.п.) в конкретном истолковании, в частности при характеристике контроля в процессе физического воспитания, это понятие трактуется далеко не однозначно. Долг ...

Возрастные особенности психического развития детей старшего дошкольного возраста
Старший дошкольный возраст (6 – 7 лет) характеризуется как период существенных изменений в организме ребенка и является определенным этапом созревания организма. В этот период идет интенсивное развитие и совершенствование опорно-двигательной и сердечно-сосудистой систем организма, развитие мелких м ...

Главное меню

Copyright © 2019 - All Rights Reserved - www.bravoschool.ru