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

Построение задач линейного программирования базируется на следующих утверждениях:

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

2) Если второй применяет оптимальную стратегию, то выигрыш 1го будет не больше, чем цена игры при любых действиях 1го, в т.ч. при выборе 1м его чистой стратегии.

Рассмотрим преобразованную матрицу A’ = (a_ij’), где a_ij’ = a_ij + b

Описанные преобразования корректны, когда цена игры v> 0. Это обеспечивается гарантированно при положительных элементах матрицы А. Есть в А есть отриц, то в A’, в b также все элементы > 0. (wtf?)

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

Относительно 1го и 2го получены симметричные взаимно двойственные задачи линейного программирования.

1) число переменных одной совпадает с числом переменных другой

2) коэффициенты при переменных одной задачи совпадают с правыми ограничениями другой задачи.

3) матрица условий одной задачи есть транспонированная матрица другой

4) переменные обеих задач не отрицательны.

Из этих задач достаточно решить только одну. Решаются по этим теоремам:

Алгоритм решения матричных игр:

1. Находим alpha – нижнюю цену и beta- верхнюю цену игры. Проверяем наличие седловой точки. Если alpha=beta, игра имеет равновесие в чистых стратегиях. Оптимальные стратегии 1го и второго игроков являются максиминныи и минимаксные стратегии. Цена игры равна alpha=beta. Если alpha< beta, goto step 2

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

3. При необходимости преобразуем матрицу игры и составляем задачи линейного программирования для 1го и 2го игроков.

4. Переходим к вспомогательным переменным и решаем одну из полученных задач. Решение 2й находим по теореме двойственности.

5. Возвращаемся к исходным переменным и определяем цену игры и оптимальные стратегии с учетом возможного имевшего место исключения доминировавших стратегий.

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

1. При повторении одного и того же решения выбор с частотами равными..??

2. Чистые стратегии выбираются случайным образом с вероятностями, равными компонентам оптимальных смешанных стратегий.

3. Физическое смешение чистых значений (если возможно) в пропорциях, определенных (емых?) компоненами оптимальных смешанных стратегий.

11. Принятие решений в условиях неопределенности: понятие игры с природой, ее формализация; специфика отношений доминирования.

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

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

В играх с природой предполагается, что множество состояний природы известно, причем они образуют полную группу несовместных событий.

Информация, необходимая для ПР в условиях неопределенности:

1. Перечень возможных стратегий ЛПР Lamda_i, i=1..m

2. Перечень возможных состояний природы Teta_j, j=1..n

Выбор стратегии ЛПР и реализация состояния природы приводят к формировании игрового состояния, которое приводит к исходу (Lamda_i, Teta_j) – исходы.

3. Предполагается, что каждый исход мб количественно оценен с позиции ЛПР числом a_ij=(Lamda_i, Teta_j)

A_mxn=(a_ij) – матрица игры.

Матрица А выражает интересы ЛПР и может оказаться как матрицей выигрыша, так и матрицей проигрыша.

В играх с природой можно удалять доминирующие строки, можно применять принцип доминирования. Доминируемые стратегии не могут претендовать на звание оптимальных и исключаются из рассмотрения на этапе предварительного анализа игры.