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

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

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

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

Теоретические основы процесса воспитания
Понятие «воспитание» тесно связано с понятиями «образование» и «обучение». В современной педагогической науке нет определенности в отношении приоритета понятий «воспитание» и «образование». Воспитание ведет свой изначальный смысл от старославянского слова «питати» — кормить и, следовательно, означа ...

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

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

Главное меню

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