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

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

Страница 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 

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

Результаты работы по программе экологического образования и воспитания младших школьников
Формирующий эксперимент, проводимый по нашей программе во втором классе читинской средней школы № 47 показал, что дети стали больше интересоваться природой, у них расширились экологические знания. Учащиеся стали более эмоционально воспринимать природу и произведения искусства о природе. Так, наприм ...

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

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

Copyright © 2013-2021 - All Rights Reserved - www.getvos.site