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

 

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

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

 

 

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

V=

 

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

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

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

 

 

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

 

 

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

 

 

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

 

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

где

 

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

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

 

.

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

 

= max(l;3) = 3;

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

 

 

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

 

		Таблица 1					Таблица 2
	1	9	1			1/9	1/9	1/9
	6	3	1			51/9	-3/9	6/9
	-1	-1	0			-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,   = 51/11,y = 6/51 • 51/11 = 6/11, у₂ = 5/51 • 51/11 = 5/11. Итак, второй игрок должен выбирать первый столбец с вероятность 6/11, а второй 5/11.Используем соответствие t₃  u , t ₄  u , то из таблицы 3 имеем: u = 3/51, u₂ = 8/51. Следовательно, x = 3/51 • 51/11 = 3/11, х₂ = 8/51 • 51/11 = 8/11.. Итак, первый игрок должен выбирать первую строку с вероятность 3/11, а вторую 8/11.

 

Пример решения матричной игры средствами Excel

       Решим, используя надстройку «Поиск решения» Excel  игру, заданную матрицей

 

.

  Нижняя и верхняя цены игры:

 

= max(l;3) = 3;

не совпадают, поэтому применяем смешанные стратегии.

       Для нахождения оптимальной стратегии первого игрока решаем задачу линейного программирования: найти минимальное значение функции  при ограничениях

 

 

,

;

, .

 

        Здесь ,   где  вероятность выбора первой строки  вероятность выбора второй строки,  цена игры.

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

 

	A	B	C	D
1	u1	u2	L
2
3	1	1
4	1	6		1
5	9	3		1

 

Вводим зависимости для целевой функции и системы ограничений. Для этого в ячейку С2 вводим формулу =СУММПРОИЗВ(A2:B2;A3:B3). В ячейки С4 и С5 соответственно формулы: =СУММПРОИЗВ(A2:B2;A4:B4) и =СУММПРОИЗВ(A2:B2;A5:B5). В результате получаем таблицу.

	A	B	C	D
1	u1	u2	L
2			0
3	1	1
4	1	6	0	1
5	9	3	0	1

 

 

Запускаем команду «Поиск решения» и заполняем появившееся окно Поиск решения следующим образом. В поле «Оптимизировать целевую функцию» вводим ячейку С2. Выбираем оптимизации значения целевой ячейки «Минимум».

 В поле «Изменяя ячейки переменных» вводим изменяемые ячейки A2:B2. В поле «В соответствии с ограничениями» вводим заданные ограничения с помощью кнопки «Добавить». Ссылки на ячейку $C$4:$C$5 Ссылки на ограничения =$D$4:$D$5 между ними знак => затем кнопку «ОК».

Ставим флажок в поле «Сделать переменные без ограничений неотрицательными». Выбрать метод решения «Поиск решения линейных задач симплекс-методом». 

Нажатием кнопки «Найти решение» запускается процесс решения задачи. В итоге появляется диалоговое окно «Результаты поиска решения» и исходная таблица с заполненными ячейками для значений переменных и оптимальным значением целевой функции.

 

 

	A	B	C	D
1	u1	u2	L
2	0,058824	0,156863	0,215686
3	1	1
4	1	6	1	1
5	9	3	1	1

 

В диалоговом окне «Результаты поиска решения» сохраняем результат u1=0,058824, u2=0,156863, L=0,215686-равный минимальному значению целевой функции. Заметим, что нужное количество знаков после запятой можно ввести, выбрав команду Формат ячеек.

Так как  и , , то находим, что =4,63637, =0,272728 0,27, =0,727274 0,73 с такими вероятностями первый игрок должен выбирать первую и вторую строки.

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

 

Здесь ,   где  вероятность выбора первогостолбца  вероятность выбора второго столбца,  цена игры.

Решение этой задачи с использованием надстройки «Поиск решения» Excel  дано в таблице

 

	A	B	C	D
1	t1	t2	L
2	0,117647	0,098039	0,215686
3	1	1
4	1	9	1	1
5	6	3	1	1

Так как  и , , то находим, что =4,63637, =0,545455 0,55, =0,454546 0,45 с такими вероятностями второй игрок должен выбирать первый столбец и второй.