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

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

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

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

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

Этапы формирования культуры поведения в дошкольном возрасте
Формирование культуры поведения в дошкольном возрасте проходит поэтапно. На каждом из этих этапов дети согласно возрастным психологическим особенностям усваивают культуру деятельности, культуру общения, культурно-гигиенические навыки и привычки. Т. А. Куликова выделяет следующие этапы воспитания ку ...

Развитие и уточнение пространственно-временных представлений
Последовательность во времени звуков и слогов, составляющих слово, а также временная последовательность слов, составляющих фразу, в письме находит отражение в соответствующей пространственной последовательности букв, слогов, слов, располагающихся на строках тетради при записи. Упражнения в определе ...

Главное меню

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