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

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

Рассмотрим стратегии игроков, основанные на вероятностном выборе ходов. Такие стратегии называются смешанными. Пусть я строка выбирается первым игроком с вероятностью = 1,2,...,m), a j-й столбец выбирается вторым игроком с вероятностью (j = l,2,...,n). Так как одна из строк и один из столбцов будут обязательно выбраны (каждый игрок обязан сделать ход), то

Цена игры V определяется как математическое ожидание величины а, т. е.

V=

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

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

Математическую модель можно упростить, разделив все (+1) ограничений на цену игры>0, систему ограничений можно записать так:

Пусть . Так как →max, то . Получим задачу линейного программирования вида

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

Задача второго игрока является двойственной по отношению к задаче первого игрока и имеет вид.

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

где

Можно найти решение одного из игроков, а затем по теоремам двойственности – решение другого.

Пример 2.Решить игру,заданную матрицей

.

Решение Находим нижнюю и верхнюю цену игры.

= max(l;3) = 3;

Так как они не равны, то применяем смешанные стратегии. Находим сначала оптимальную стратегию второго игрока, т.е. находим наибольшее значение функции и соответствующие значения неотрицательных переменных , если выполняются неравенства:

Для решения этой задачи используем симплексный метод, проводя вычисления в таблицах.

		Таблица 1				Таблица 2
						1/9	1/9	1/9
						51/9	-3/9	6/9
	-1	-1				-8/9	1/9	1/9

Таблица 3

	1/51	6/51	5/51
	9/51	-3/51	6/51
	8/51	3/51	11/51

Таким образом, имеем: = 6/51, t₂ = 5/51, = 6/51 • 51/11 = 6/11, у₂ = 5/51 • 51/11 = 5/11. Итак, второй игрок должен выбирать первый столбец с вероятность 6/11, а второй 5/11.Используем соответствие t₃u 4, то из таблицы 3 имеем: u= 3/51, u₂ = 8/51. Следовательно, x= 3/51 • 51/11 = 3/11, х₂ = 8/51 • 51/11 = 8/11. . Итак, первый игрок должен выбирать первую строку с вероятность 3/11, а вторую 8/11 .