Исследование операций. Основы теории игр

Основы теории игр

1. Основные понятия теории игр, матричные игры

2. Решение матричных игр. Принцип

1. Основные понятия теории игр, матричные игры

Игра - математическая модель

Каждая взятая из практики конфликтная ситуация очень сложна, а ее

От реальной конфликтной ситуации игра отличается тем, что ведется по

Например, при определении объема выпуска продукции на одном предприятии нельзя

Таким образом, теория игр занимается исследованием конфликтных ситуаций.
В

По характеру выигрышей выделяют игры
с нулевой суммой и с

В качестве одного из признаков классификации игр часто выбирают множество

Если в антагонистической игре
игрок 1 стремится максимизировать свой выигрыш g1,

В играх с ненулевой суммой
сумма выигрышей отлична от нуля.

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

В зависимости от количества стратегий игры делятся на конечные и

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

Рассмотрим стратегическую парную игру с нулевой суммой. Пусть в игре участвуют

Например, игрок А имеет m чистых стратегий (А1, А2,…, Аm), а

Платежная функция задается либо аналитическим выражением, либо таблично,
т. е. с

Элемент платёжной матрицы aij, который находится на пересечении строки i и

Платежная матрица игры

Например, величина a21 показывает выигрыш игрока А и,

Пример 1

Правила игры
Игроки считают вместе вслух «Камень... Ножницы... Бумага... Раз... Два...

Победитель определяется по правилам:
Камень побеждает ножницы («камень затупляет или ломает ножницы»);
Ножницы

Если игроки показали одинаковый знак, то засчитывается ничья и игра

Платежная матрица этой игры

Пример 2. В игре принимают участие два игрока. Каждый из

Необходимо составить платежную матрицу игры.
Решение
У игрока А имеется три стратегии:
А1

Поэтому платежная матрица будет иметь три строки
Платёжная матрица для

В случае, если игрок А запишет число 4 (стратегия А1

Отрицательный выигрыш означает на самом деле проигрыш. Так, a23 =

Пример 3. Конструкторские бюро КБ-1 и КБ-2 участвуют в конкурсе

Кроме одного балла, получаемого за лучший проект, КБ дополнительно начисляется столько

Решение
Игрок А - КБ-1, игрок В - КБ-2. Запишем стратегии

Стратегия А1 состоит в том, чтобы все 4 отдела занять 1-м

Платежная матрица этой игры:
Приведем рассуждения при расчете элементов этой платежной

Элемент a11 и есть выигрыш игрока А, который он получит, если

Итого по первому проекту игрок А выиграет 4 балла. По второму

По первому проекту выигрывает игрок А – 3 балла (один

Элемент а42 представляет собой выигрыш игрока А при условии, что

Тогда по первому проекту выигрывает игрок В (так как у

По второму проекту выигрывает игрок А и получает 1 дополнительный

2. Решение матричных игр. Принцип минимакса

Пусть дана парная игра с

Поэтому каждый игрок должен рассчитывать на самое неблагоприятное для себя

Пример 4. Найдем решение игры для примера 2. Будем записывать

Если игрок А выбирает чистую стратегию А1 (записывает число 4), то

Нижней цене игры соответствует стратегия А3. Таким образом, если игрок А

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

Верхней цене игры соответствует стратегия B3. Таким образом, если игрок

Если платежная матрица не имеет седловой точки, т.е. α<β, то решением

Однако, применение игроками смешанных стратегий имеет смысл только тогда, когда данная

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

Чистые стратегии игроков, имеющие ненулевые вероятности в его смешанной стратегии, называются

Расчет нижней и верхней цены игры для примера 3

Минимальный выигрыш игрока А при применении им стратегии А1 составит αi

Максимальный проигрыш игрока В при применении им стратегии В1 будет равен:
β1

В случае игры с седловой точкой игрокам выгодно придерживаться максиминной

Чаще встречаются матричные игры без седловой точки, когда α <

Справедливы теоремы:
Теорема 1 - Основная теорема теории матричных игр.

Теорема 2.
Если один из игроков применяет оптимальную смешанную стратегию, то

3. Решение игры в смешанных стратегиях путем сведения к ЗЛП

Пусть

Здесь aij – элементы матрицы игры; pi (i =1, 2, …,

Тогда неравенства выше можно записать в следующем виде:

Учитывая соотношение , получим:

pi – вероятности, с которыми игрок А выбирает одну из своих

Пример 6.
Решим в смешанных стратегиях игру о двух

Платежная матрица для примера 3

Цена игры при этом увеличится на 2. Получим платежную матрицу:
Преобразованная платежная

Таким образом, у игрока А активными являются первая, третья и пятая

Очевидно, это лучший результат, чем при применении перестраховочной стратегии, дающей

Еще один пример перехода к ЗЛП – Моделирование конкурентной борьбы

Фирма А ищет такую стратегию SA=(x1, х2,…, х6), чтобы обеспечить себе

Аналогично составим уравнения фирмы В (на каждую из шести стратегий фирмы

Для примера пусть платежная матрица ||aij|| имеет вид:

Начертим эти 6 прямых в системе координат ν 0 y1

Из рис. ясно, что наименьшая величина v находится на пересечении прямых

В результате рынок сбыта между фирмами будет поделен следующим образом:

В итоге, если фирма А выполняет стратегию А2 с вероятностью 1/15

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

Игра с природой – игровая модель, в которой

В играх с природой растет неопределенность при принятии решения сознательным

Примеры задач, которые могут быть сведены к играм с природой:
Доход

Для отопления производственных помещений предприятие закупает топливо. Расход топлива в

Если имеющихся данных недостаточно для принятия полностью обоснованного решения, то

Пример 7. Туристическая фирма «Топ Тур» реализует туристические путевки. Объем

Если количество путевок превышает спрос, то потери за невостребованную путевку

Решение
Построим платежную матрицу игры. Сознательный игрок А имеет 4 возможные стратегии:
А1

Потребительский спрос выступает в качестве второго игрока (природы). Возможны следующие

Результаты расчета платежной матрицы игры показаны в таблице:
Платежная матрица игры с

Поясним расчеты некоторых элементов платежной матрицы.
Элемент а11 означает прибыль сознательного игрока

Элемент а11 есть выигрыш игрока А (прибыль фирмы), если будет

Элемент а21 платежной матрицы есть выигрыш игрока А, если будет заказано

Особенность игр с природой - решение достаточно найти только для

Стратегия является заведомо невыгодной, если в соответствующей строке платежной матрицы

Как правило, игры с природой решают, используя разные критерии, основанные

Критерий Байеса-Лапласа (BL-критерий)
В отдельных случаях может иметь место

Тогда, полагая

Условия применения BL-критерия:
1) вероятности внешних состояний pj
(j=1, 2…n) известны

4.2. Критерии, используемые в условиях полной неопределенности, т. е. когда вероятности

Критерий Вальда выражает позицию «крайнего пессимизма»,
и принимаемое решение носит

Максиминный критерий Вальда
(ММ-критерий) иногда называют «позицией крайнего пессимизма».
Идея

Применение ММ-критерия оправдано в тех случаях, когда:
1) о вероятностях появления

Риск игрока А при применении им стратегии Аi в условиях

Согласно критерию Сэвиджа выбирается та стратегия, которая в наихудших условиях

Идея применения критерия Сэвиджа (S-критерия) базируется на использовании вспомогательной функции

Матрицу элементов || ri,j || иногда называют матрицей рисков или

Равенство нулю значения ri,j указывает на то, что решение Ei

Условия применения S-критерия:
1) о вероятностях внешних состояний Fj ничего неизвестно;
2)

Критерий Гурвица
Оптимальной считается чистая стратегия Ai, найденная из условия:
S

При λ = 1 критерий Гурвица превращается в критерий Вальда

Величина λ выбирается исходя из опыта и здравого смысла. Чем

Наибольший средний выигрыш соответствует стратегии A2.
Таким образом, сознательному

3. Если о вероятностях состояния спроса вообще ничего не известно, то

Расчеты для критериев Вальда и Гурвица

Вычислим значения показателя Si для критерия Гурвица, задав параметр λ=0,7:
S1=0,7∙60+0,3∙75=64,5;
S2=0,7∙54+0,3∙80=61,8;
S3=0,7∙48+0,3∙85=59,1;
S4=0,7∙42+0,3∙90=56,4.
Так как

Матрица рисков игры с природой

Для каждой стратегии Аi рассчитаем максимальный риск и запишем в

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

Пример 9

Постановка задачи. Для обеспечения содержания автомобильных дорог в зимний

Очевидно, что на будущую зиму имеет смысл заготавливать ПГМ в

С другой стороны, если весь объем ПГМ не израсходуется в

Решение. Составим матрицу принятия решений. Внешние условия Fj (j = 1,2,…n)

В соответствии с этим возможны 4 варианта принимаемых решений:
Е1 - заготовить

Вычислим значения элементов матрицы принятия решений ei,j. В данном случае

Рассмотрим, например, ситуацию (E1,F1).
Она соответствует тому, что осенью ДРСУ

Ситуация (E1,F2) означает, что в осенний период было заготовлено 3

Подобным образом вычисляются все значения остальных элементов матрицы принятия решений:
e1,3=-(c∙3+d∙2)=-(10∙3+13∙2)=-56;
e1,4=-(c∙3+d∙3)=-(10∙3+13∙3)=-69;
e2,2=-c∙4=-10∙4=-40;
e2,3=-(c∙4+d∙1)=-(10∙4+13∙1)=-53;
e2,4=-(c∙4+d ∙2)=-(10

e3,3=-c∙5=-10 ∙5=-50;
e3,4=-(c∙5+d ∙1)=-(10 ∙5+13 ∙1)=-63;
e4,1=-(c∙6+f ∙3)=-(10 ∙6+2 ∙3)=-66;
e4,2=-(c∙6+f ∙2)=-(10 ∙6+2 ∙2)=-64;
e4,3=-(c∙6+f

Матрица принятия решений имеет следующий вид:

Применим к анализу рассматриваемой ситуации указанные в задании критерии.
1. Проанализируем ситуацию,

Максимум значения ei,r будет достигнут при реализации решения E3.

2. Для применения критерия Сэвиджа составим матрицу рисков ri,j. В каждом

Для каждого из вариантов решений Ei определим максимальное значение риска

Результаты вычислений приведены в следующей
таблице:

Использованная литература
1. Еськова О. И. Экономико-математические методы и модели: курс лекций

2. Вентцель Е. С. Исследование операций. М., «Советское радио», 1972, 552