Лекция 6. Решение матричных игр с помощью линейного программирования

План.

6.1. Связь матричных игр и линейного программирования.

6.2. Алгоритм решения матричных игр с помощью линейного программирования.

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

Теория игр находится в тесной связи с линейным программированием, так как каждая конечная игра двух лиц с нулевой суммой может быть представлена как задача линейного программирования. Г Данциг указывает, что создатель теории игр Дж. Фон Нейман, который первым ввел симплекс-метод в линейное программирование (1947 г.), установил это соотношение и в дальнейшем обосновал и развил концепцию двойственности в линейном программировании.

Допустим, дана игра двух лиц, заданная платежной матрицей Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru . Тогда оптимальная смешанная стратегия первого игрока определяется условиями

Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru , Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru . (6.1)

Эта задача может быть сформулирована в виде задачи линейного программирования. Пусть

Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru .

Тогда может быть составлена математическая модель задачи для первого игрока. Исходя из чистых стратегий второго игрока целевая функция игры:

Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru (6.2)

при ограничениях

Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru

Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru

Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru .

Для второго игрока задача записывается в виде

Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru , Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru .

Промежуточное соотношение:

Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru .

Тогда задача примет вид

Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru (6.3)

при ограничениях

Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru

Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru

Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru .

Задача для второго игрока (6.3) является двойственной к задаче для первого игрока (6.2). Задача для второго игрока может быть решена, например, стандартным симплекс-методом, а для первого игрока – двойственным симплекс-методом. Выбор метода определяется тем, какая из задач имеет меньше ограничений, что в свою очередь зависит от числа чистых стратегий каждого из игроков.

Математическую модель задачи (6.2) можно упростить, разделив все (n + 1) ограничения на v. Это возможно при v ¹ 0. При v = 0 рекомендуется прибавить любое положительное число ко всем элементам платежной матрицы, что гарантирует положительность значения модифицированной игры. Действительное значение игры получается вычитанием из модифицированного значения этого положительного числа. Если v < 0, то надо сменить знаки неравенств.

Полагая v > 0, систему ограничений можно записать:

Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru

Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru .

Полагая Xi = xi / v и если v ® max, то 1/v ® min, получим задачу линейного программирования вида

Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru

при ограничениях

Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru

Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru .

Аналогично, исходя из чистых стратегий первого игрока или по правилам составления двойственных задач, принимая математическую модель первого игрока как исходную, математическая модель второго игрока записывается в виде

Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru

при ограничениях

Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru

Лекция 6. Решение матричных игр с помощью линейного программирования - student2.ru ,

где S(Y)max = L(X)min = 1/v, Yj = yj/n.

Наши рекомендации