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

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

Страница 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 © 2020 - All Rights Reserved - www.bravoschool.ru