Эксперт по сдаче вступительных испытаний в ВУЗах
ПРАКТИЧЕСКАЯ РАБОТА № 5.
РЕШЕНИЕ ЗАДАЧ ТЕОРИИ ИГР СВЕДЕНИЕМ К ДВОЙСТВЕННОЙ ЗАДАЧЕ ЛП.
Игру двух лиц с нулевой суммой в смешанных стратегиях можно представить парой двойственных задач линейного программирования и решить, например, симплекс-методом.
Предположим игра, задана платежной матрицей
Вычмслим
α = max (min ai j ) нижнею цену игры и
β = min (max ai j) верхнею цену игры. Проверим на наличие седловой точки,
α= 1,
β= 2 → игра без седловой точки.
Пусть
(р1, р2) – смешанная стратегия игрока
А,
(q1, q2, q3) – смешанная стратегия игрока
В. Напомним, что
р1 + р2 = 1, и q1 + q2 + q3 =1.
Воспользуемся теоремой Неймана утверждающей, что:
Существует такое число
v (цена игры), что если игрок
А придерживается оптимальной смешанной стратегии, то математическое ожидание его выигрыша (т.е. средний гарантированный выигрыш) будет не меньше
v. Аналогичное утверждение относительно игрока
В: математическое ожидание его проигрыша будет не больше
v.
Для игрока А:
3р1 + р2 ≥ v
3р2 ≥ v (5.1)
р1 + 2р2 ≥ v
F = v → max
Преобразуем ограничения, разделив все члены неравенств на v (обозначим
y1 = р1/v, y2 = р2/v, заметим, что
v = 1/(y1 + y2)).
Итак, задача принимает вид:
3y1 + y2 ≥ 1
3y2 ≥ 1 (5.2)
y1 + 2y2 ≥ 1
G = y1 + y2 → min
Для игрока B:
3q1 + q3 ≤ v
q1 + 3q2 +2q3 ≤ v (5.3)
F = v → min
Преобразуем ограничения, разделив все члены неравенств на v (обозначим
х1 = q1/v, х2 = q2/v, x3= q3/v, заметим, что
v= 1/(x1 + x2+x3)).
Итак, задача принимает вид:
3x1 + x3 ≤ 1
x1 + 3x2 +2x3 ≤ 1 (5.4)
F = x1+x2+x3 → max
Таким образом получена
пара двойственных задач (5.2) и (5.4)
. Напомним, что, решив одну из них, например, симплекс-методом, мы автоматически найдем решение другой. Для решения задачи может быть использована стандартная процедура поиск решения в среде Microsoft Excel. Формат представления данных и результатов решения приведены в прил. 2.
Решить игру, заданную платежной матрицей, используя сведение к двойственным задачам линейного программирования:
Расчеты выполняются в среде EXCEL
Ссылка на первоисточник:
http://www.msgi.info
