Математика \ Математика

Транспортная задача. Матричные игры: Методические указания к практическим занятиям, страница 17

В некоторых случаях можно уменьшить размеры матрицы исследуемой игры за счет исключения заведомо невыгодных чистых стратегий. Говорят, что (чистая) стратегия игрока доминируется стратегией и пишут если все элементы ой строки матрицы игры не больше соответствующих элементов ой строки, Стратегия игрока доминируется стратегией (обозначение: ), если все элементы ого столбца не меньше соответствующих элементов ого столбца,

По определению, замена чистой стратегии на не уменьшает выигрыш игрока , а замена на не увеличивает проигрыш игрока при любых ответах противника, если или соответственно. Используя это свойство, можно показать, что при исследовании игры, в которой есть доминируемые стратегии, надо просто «сократить» платёжную матрицу, вычеркнув из неё строки и столбцы, соответствующие доминируемым стратегиям. Цена исходной игры равна цене игры с сокращенной матрицей; в решении исходной игры вероятности доминируемых стратегий равны нулю, а все остальные совпадают с соответствующими вероятностями «сокращенной» игры.

Пример 11. Найти решение и цену игры с матрицей из примера 8. Описать оптимальное поведение фирм и в рассматриваемой конфликтной ситуации.

Решение:Игра не имеет решения в чистых стратегиях, т.к. (см. пример 8). По матрице находим и , т.е.

и доминируемые стратегии (в данном случае это следует также из и Вычеркнув из 4-ю строку и 1-ый столбец, получим матрицу, в которой можно вычеркнуть столбец, соответствующий ( в «сокращенной» игре ),

На рис.12 представлена геометрическая интерпретация игры с матрицей

4 4

3 C 3

2 2

1/2 1

Рис.12

Здесь

Верхняя огибающая прямых

состоит из двух звеньев, соответствующих и

По рис. 12 находим (сравните с примером 10) сначала

из уравнений а затем из уравнений ( и угловые коэффициенты прямых и пересекающихся в точке С). Все остальные вероятности и в решении равны нулю. Таким образом, в игре с матрицей

т.е. в примере 8 при фирма должна с вероятностями

начинать продажу с 1-го или 3-го дня сезона, а фирма с вероятностями со 2-го или 3-го дня сезона.

Приведение матричной игры к задаче ЛП. Покажем сначала, как сводится к задаче ЛП игра, в которой все элементы платёжной матрицы положительны. Рассмотрим задачу ЛП

(36)

(37)

и двойственную к ней задачу [2, cтр. 3]

(38)

(39)

Обе задачи имеют допустимые планы: ограничениям (37) удовлетворяют планы вида при достаточно малых а ограничениям (39) – планы вида при достаточно больших По первой теореме двойственности [2, стр.4] обе задачи разрешимы, т.е. имеют оптимальные планы и соответственно, причём экстремальные значения и целевых функций совпадают,