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

Лемма. Если увеличить все элементы платежной матрицы на одно и тоже число, то цена игры увеличится на то же число, а решение задачи (выбор стратегий) не изменится.

Из этого следует, что всегда можно, увеличив элементы матрицы на какое-либо число, добиться, чтобы цена игры стала положительной v>0. Поэтому далее будем считать, что v>0.

При использовании оптимальной смешанной стратегии игроком А его выигрыш будет не меньше цены игры v, в том числе при условии, что противник выберет чистую стратегию В_к . Получаем систему неравенств:

Введем обозначения (i = 1,..., n). Так как вероятности неотрицательны и v>0, то и . Перепишем систему неравенств с новыми переменными

(*)

Учитывая, что , сумма новых переменных ,

Цена игры для первого игрока должна быть как можно больше , поэтому величина должна быть как можно меньше.

Итак, мы имеем задачу линейного программирования (ЗЛП): надо найти неотрицательные значения переменных , которые удовлетворяют системе неравенств (*) и обращают целевую функцию Z в минимум.

Аналогично, с точки зрения игрока В: его проигрыши при использовании им оптимальной смешанной стратегии S_B( ) не могут превышать цену игры, в том числе, если А применяет одну из чистых стратегий А_i. Обозначив (k = 1,…,m) и целевую функцию , получим двойственную ЗЛП.

, где , , , определяется как решения двойственных задач линейного программирования:

Пример. Рассмотрим платежную матрицу без седловой точки, полученную в предыдущем примере . Найти решение задачи в области смешанных стратегий. ► Пусть сторона А использует первую стратегию с вероятностью p₁, вторую стратегию с вероятностью p₂. Обозначив , , получим систему ограничений:

Целевая функция

Эту задачу линейного программирования можно решить геометрически (рис.6), построив область допустимых решений (ОДР) и семейство уровней целевой функции. Оптимальное решение находится в точке пересечения ограничивающих ОДР прямых, координаты этой точки являются решением системы двух уравнений:

Из оптимального решения ЗЛП найдем:

.

Оптимальная смешанная стратегия первого игрока состоит в том, чтобы применять первую чистую стратегию с частотой и вторую чистую стратегию с частотой , чередуя их случайным образом (например, вынимая наугад шарик из урны, где лежат два черных и один белый шарики: попался белый шар – используй первую стратегию, черный – вторую). Тогда его средний выигрыш составит , но он может быть и больше, если второй игрок ведет себя неразумно. Мы видим, что цена игры находится между нижней и верхней ценой игры, т.е. между числами 3 и 5.

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

Игры с природой.

Задачапринятия решения в условиях неопределенности называется «игрой с природой». Под «природой» будем понимать совокупность неопределенных факторов, влияющих на эффективность принимаемых решений. Неопределенность в принятии решения возникает в тех случаях, когда отсутствует достаточно полная информация о состоянии объекта управления и о состоянии внешней среды. Природа выступает в качестве внешней среды. Предполагается, что множество состояний природы известно. Лицо, принимающее решение (ЛПР), является первым игроком А, который в процессе игры выбирает одну из m возможных строк платежной матрицы (они же стратегии) A_1, А₂,…, A_m. Второй игрок П – природа, основной особенностью которой является её незаинтересованность в выигрыше. Этот противник пассивен и не противодействует достижению намеченной цели, меняя свои состояния стихийно. Пусть стратегии природы П_{1, …,} П_n – это её состояния. Выигрыши игрока А при каждой паре стратегий А_i и П_j известны и заданы платежной матрицей (a_ij). Задача заключается в определении такой стратегии, применение которой обеспечило бы наибольший выигрыш игроку А. Для оценки эффективности стратегии используется критерий – числовая функция - вычисляемый по элементам платежной матрицы.

К наиболее часто используемым подходам для обоснования выбора решения ЛПР (методам выбора оптимальной стратегии) в условиях неопределенности можно отнести:

Название критерия	Критерий выбора оптимальной стратегии
Критерий Вальда (пессимиста)
Критерий оптимиста
Критерий Гурвица	где a - показатель пессимизма
Критерий Сэвиджа (минимальных сожалений)	- матрица рисков (минимальных сожалений)
Критерий Лапласа

Анализ матрицы выигрышей игры с природой начинается с выявления и отбрасывания дублирующих и доминируемых стратегий ЛПР – игрока А. Но! Ни одну из стратегий природы отбросить нельзя, так как каждое из состояний природы может наступить случайным образом, независимо от действий игрока А.

Критерий Вальда (пессимиста, или гарантированного результата) считает наилучшей стратегией максиминную стратегию, т.е. ту, которая гарантирует в наихудших условиях максимальный выигрыш.

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

Критерий Гурвица помогает найти компромиссное решение между крайне пессимистичной оценкой по критерию Вальда (α=1) и крайне оптимистичной оценкой при α=0, используя промежуточное значение показателя пессимизма-оптимизма, которое характеризует степень активного «противодействия» природы с точки зрения ЛПР. Коэффициент выбирается на основании опыта, здравого смысла и т.д.

Принцип Лапласаприменяется, когда ни одно состояние природы нельзя предпочесть другому, поэтому субъективно они оцениваются как равновероятные.

Пример. Руководство торговой фирмы разработало 4 плана продажи товаров A_1, А₂, A_3, А₄. В зависимости от конъюнктуры рынка П_1, П₂, П₃, П₄ рассчитаны значения прибыли (в млн.руб.) для каждой стратегии, представленные в виде матрицы выигрышей:

	П1	П2	П3	П4
A1
А2
A3
А4

Определить оптимальный план продажи товаров.

► Проанализировав платежную матрицу, убеждаемся, что дублирующих и доминирующих стратегий у игрока А нет.

Найдем минимальный элемент в каждой строке и впишем его в дополнительный столбец – наихудший результат применения данной стратегии. Максимальный элемент этого столбца 9. Следовательно, оптимальной стратегией по критерию Вальда является А₃, которая гарантирует прибыль не менее 9 млн.руб.

В следующий столбец впишем максимальный элемент матрицы выигрышей по каждой строке. Оптимист выбрал бы план продажи А₂, дающий наибольшую прибыль 13 при состоянии рынка П₂. Но кто даст гарантию, что именно это состояние рынка наступит? Поэтому воспользуемся критерием Гурвица с показателем пессимизма α=0.4. Посчитаем линейную комбинацию минимальной и максимальной величины прибыли по каждой строке и внесем её в последний столбец. Наибольшее значение критерия Гурвица G_i достигается в строке А₂, значит, по критерию Гурвица следует выбрать план продажи А₂.

	П1	П2	П3	П4	aij	aij	Gi=0.4 aij + 0.6 aij
A1							G1=0.4*8+0.6*11=9.8
А2						13	G2=0.4*7+0.6*13=10.6
A3					9		G3=0.4*9+0.6*11=10.2
А4							G1=0.4*8+0.6*12=10.4
aij

Если мы вычислим средний выигрыш по каждой строке, то по критерию Лапласа оптимальной будет стратегия А₃.

Построим матрицу рисков. Для этого найдем максимальный элемент в каждом столбце состояния природы. Затем вычислим разность между ним и каждым элементом матрицы в этом столбце и занесем найденное значение r_ij в новую таблицу (матрицу рисков):

	П1	П2	П3	П4	rij
A1
А2
A3					3
А4

Согласно критерию Сэвиджа, рекомендуется выбрать ту стратегию, при которой в наихудших условиях величина риска (упущенная прибыль) принимает наименьшее значение. В каждой строке матрицы риска ищем наибольший элемент, заносим его в дополнительный столбец, сравниваем элементы этого столбца. Итак, минимальны будут сожаления при выборе плана продаж А₃. Окончательный выбор между вторым и третьим планами продаж должно сделать руководство торговой фирмы (ЛПР), а критерии помогли оценить принимаемое решение с разных позиций, дабы избежать грубых ошибок. ◄