Понятие теории игр

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

    Предположим, что цена игры положительна (u > 0). Если это не так, то согласно свойству 6 всегда можно подобрать такое число  с, прибавление которого ко всем элементам  матрицы выигрышей даёт матрицу  с положительными элементами, и следовательно, с положительным значением цены игры. При этом оптимальные смешанные  стратегии обоих игроков не изменяются.

    Итак, пусть дана матричная игра с матрицей А порядка m х n. Согласно свойству 7 оптимальные  смешанные стратегии х = (х1, ..., хm), y = (y1, ..., yn) соответственно игроков 1 и 2 и цена игры u должны удовлетворять  соотношениям.

                            (1)

                            (2)

    Разделим  все уравнения и неравенства  в (1) и (2) на u (это можно сделать, т.к. по предположению u > 0) и введём обозначения :

         ,       ,

    Тогда (1) и (2) перепишется в виде :

     ,   ,   ,   ,

     ,   ,   ,   .

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

     ,  .                      (3)

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

     ,  .                      (4)

    Формулы (3) и (4) выражают двойственные друг другу  задачи линейного программирования (ЛП).

    Решив эти задачи, получим значения pi , qj  и u.Тогда смешанные стратегии, т.е. xi и yj получаются по формулам :

                                 (5) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    II. Практическая часть.

    2.1. Постановка задачи.

    Задача  о замене оборудования (модели принятия решения).

Задача  заключается в следующем. После  нескольких лет эксплуатации автопарк АТП оказывается в одном из следующих состояний:

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

В зависимости  от сложившейся ситуации руководство  предприятия в состоянии принять  такие решения:

1. отремонтировать транспортное средство силами своих специалистов, что потребует затрат в зависимости от состояния машины, равных а₁, а₂, а₃ ден. ед.;
2. пригласить специальную бригаду механиков для ремонта, расходы в этом случае составят b₁, b₂, b₃ ден. ед.;
3. заменить машину новой. Совокупные затраты в результате этого мероприятия будут равны, соответственно, с₁, с₂, с₃ ден. ед.

 

Требуется:

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

а) накопленный  опыт показывает, что вероятности  указанных выше состояний транспортного  средства равны, соответственно q₁, q₂, q₃;

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

в) о  вероятностях состояния транспортного  средства ничего определенного сказать  нельзя.

В задаче использовать критерии Байеса, Лапласа, Вальда, Сэвиджа, Гурвица.

Замечание: указанные выше затраты включают кроме ремонта и убытки, вызванные  ухудшением качества обслуживания.

 

    2.2. Критерии для принятия  решений.

    Для решения данной задачи необходимо рассмотреть  матрицу рисков R и ряд критериев, которые применяются для решения игр с природой. Элементы матрицы r_ij представляют собой разность между выигрышем, который получил бы игрок А, если бы знал состояние природы П_ij, и выигрышем, который он получит в тех же условиях, применяя стратегию А_i, то есть

    r_ij = β_j - α_ij, где β_j = max α_ij. 

    При решении игр с природой применяется  ряд критериев.

    1. Если известно распределение вероятностей q_j (j = ), ∑q_j=1 различных состояний природы П_j, то применяется критерий Байеса: критерием принятия решения является максимум математического ожидания выигрыша (минимум математического ожидания риска).

    Запишем платежную матрицу (α_ij) и матрицу рисков г_ij в виде таблицы 1.1. и таблицы 1.2. 

^{Таблица 1.1.}

 

    ^{Таблица 1.2.}

 

    По  критерию Байеса за оптимальную принимается  та стратегия А_i, при которой максимизируется средний выигрыш, то есть обеспечивается

    а = max а_i, где ∑ a_ijq_j( ) и минимизируется средний риск, то есть обеспечивается г = min r_i, где r_i=∑ a_ijq_j.

    2. Если все состояния природы равновероятны, то есть q₁=q₂=…q_n =l/n, то используется принцип недостаточного основания Лапласа. Оптимальной считается стратегия, обеспечивающая максимум среднего выигрыша.

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

    а = max min a_ij 

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

    Критерии  Вальда и Сэвиджа выражают пессимистическую оценку ситуации.

    5. Критерий Гурвица рекомендует принимать решение о выборе стратегии, при которой имеет место max(λ min a_ij + (1-λ) max a_ij), где 0 ≤ λ ≤ 1

    Значения  λ выбираются исходя из опыта или по субъективным соображениям. При λ = 0 имеет место критерий крайнего оптимизма, при λ = 1 — критерий пессимизма Вальда.

    2.3. Решение задачи.

    В качестве «статистика» выступает руководство предприятия, обладающее тремя стратегиями: A₁, A₂ и А₃. Второй игрок «природы» П — комплекс всех факторов и условий, в которых будет функционировать АТП. «Выигрышами» статистика будут затраты, связанные с реализацией стратегий A₁, А₂ и А₃ и составляющие платежную матрицу (табл. 1.3).

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

    ^{Таблица 1.3.}