Решение. Антагонистические игры

Антагонистические игры

Пример 1. (Планирование посевов). Фермер, имеющий ограниченный участок земельных угодий, может его засадить тремя различными культурами A_1, A_2, A₃. Урожай этих культур зависит главным образом от погоды ("природы"), которая может находиться в трёх различных состояниях: B₁, B₂, B₃. Фермер имеет информацию (статистические данные) о средней урожайности этих культур (количество центнеров культуры, получаемого в одного гектара земли) при трёх различных состояниях погоды, которая отражена в таблице:

Виды культур	Возможные состояния погоды	Цены
	Засуха B1	Нормальная B2	Дождливая B3
A1
A2
A3

Тогда матрица доходов (платёжная матрица) фермера A имеет вид:

Элемент матрицы A - (a_ij) показывает, какой доход может получить фермер с одного гектара земли, если он посеет культуру i ( i =1, 2, 3), а погода будет находиться в состоянии j (j = 1, 2, 3).

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

Данная задача может быть сведена к антагонистической игре. В данном случае в качестве первого игрока выступает фермер, а в качестве второго игрока - природа. Будем предполагать, что природа, как игрок, может вести себя таким образом, чтобы максимально навредить фермеру, преследуя тем самым противоположные интересы (эти предположения позволяют оценить тот доход, который он может получить в том случае, если погодные условия будут для него максимально неблагоприятные). В этом случае фермер имеет в своём распоряжении три чистые стратегии:

· первая чистая стратегия предполагает, что весь участок земли буде засеян культурой A₁;

· вторая чистая стратегия предполагает, что весь участок земли будет засеян культурой A₂;

· третья чистая стратегия предполагает, что весь участок будет засеян культурой A₃.

Как игрок, природа может также использовать три возможные стратегии:

· засушливую погоду, которая соответствует первой чистой стратегии B₁;

· нормальную погоду, которая соответствует второй чистой стратегии B₂;

· дождливую погоду, которая соответствует третьей чистой стратегии B₃.

1. Проанализируем платёжную матрицу A.

Матрица A не имеет доминируемых стратегий и не может быть упрощена.

2. Проверим, имеет ли данная игра седловую точку.

Найдём нижнюю и верхнюю цену игры:

V_*=max_i min_ja_ij = 50.

V^*=min_jmax_ia_ij = 100.

Поскольку V_* ≠V^*, то данная антагонистическая игра не имеет седловой точки и решения в чистых стратегиях.

3. Решение игры следует искать в смешанных стратегиях. Сведём игровую задачу к задаче линейного программирования. Если первый игрок - фермер - применяет свою оптимальную смешанную стратегию P^*, а второй игрок - природа - применяет последовательно свои чистые стратегии, то математическое ожидание дохода, который фермер может получить со своего участка, будет не меньше цены игры V. Следовательно, должна выполняться следующая система неравенств:

Разделим каждое из неравенств, входящих в систему на V и введём новые переменные:

.

В результате получим новую систему неравенств:

Разделим равенство:

p*₁ + p*₂ + p*₃ = 1

на V, получим, что новые переменные y₁, y₂, y₃ удовлетворяют условию:

y₁ + y₂ + y₃ = 1/V

Поскольку цель первого игрока - максимизация его выигрыша, а математическое ожидание его выигрыша не меньше цены игры, то первый игрок будет стремиться максимизировать цену игры, которая эквивалентна минимизации величины 1/V.

Итак, для первого игрока (фермера) задача об определении оптимальной стратегии поведения свелась к задаче линейного программирования:

найти минимум функции F = y₁ + y₂ + y₃

при следующих функциональных ограничениях:

и прямых ограничениях:

y₁ ≥ 0, y₂≥ 0, y₃≥ 0

Переходим ко второму игроку, к природе. Если второй игрок - природа - будет применять свою оптимальную смешанную стратегию Q^*,а первый игрок - фермер будет последовательно применять свои чистые стратегии, то математическое ожидание проигрыша второго игрока будет не больше цены игры. Следовательно, должна выполняться следующая система неравенств:

Разделим каждое из неравенств, входящих в систему на V и введём новые переменные:

.

В результате получим новую систему неравенств:

Разделим равенство:

q*₁ + q*₂ + q*₃ = 1

на V, получим, что новые переменные q₁, q₂, q₃ удовлетворяют условию:

q₁ + q₂ + q₃ = 1/V

Поскольку цель второго игрока - природы - минимизация его проигрыша, а математическое ожидание его проигрыша не больше цены игры, то второй игрок будет стремиться минимизировать цену игры, которая эквивалентна максимизации величины 1/V.

Итак, для второго игрока (природы) задача об определении оптимальной стратегии поведения свелась к задаче линейного программирования:

найти максимум функции F^/ = x₁ + x₂ + x₃

при следующих функциональных ограничениях:

и прямых ограничениях:

x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0

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

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

Задача второго игрока минимизация проигрыша V	Задача первого игрока максимизация выигрыша V
Целевая функция
F^/ = x1+x2+x3 = → max	F = y1+y2+y3 = → min
Функциональные ограничения
Прямые ограничения
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0	y1 ≥ 0, y2 ≥ 0, y3 ≥ 0

Задача первого игрока решается симплекс-методом. Результаты счёта:

у1 =	0,01	p1 =	0,67
у2 =		p2 =	0,00
у3 =	0,005	p3 =	0,33
F =	0,015	V =	66,67

Задача второго игрока решается также симплекс-методом. Результаты счёта:

x1 =	0,005	p1 =	0,33
x2 =		p2 =	0,00
x3 =	0,01	p3 =	0,67
F =	0,015	V =	66,67

Выводы. В соответствии с полученными результатами фермеру гарантирован средний доход в размере 66,67 единиц с каждого гектара используемой под культурами земли при самых неблагоприятных условиях. Оптимальная стратегия для него - выращивание двух культур, A₁ и A₃, причём, под первую культуру ему следует отвести 0,67 часть всей земли, а под третью культуру 0,33 часть всей земли.

Природа "грозит" фермеру жарой 0,33 часть сезона возделывания культур и 0,67 часть сезона дождями.

Пример 2. (Планирование выпуска продукции при разных состояниях природы - рынка спроса)

Предприятие может выпускать 4 вида продукции: A₁, A₂, A₃, A₄, получая при этом прибыль. Её величина определяется состоянием спроса (природой рынка), который может находиться в одном из четырёх возможных состояний: B₁, B₂, B₃, B₄. Зависимость величины прибыли от вида продукции и состояния рынка представлено в таблице:

Виды продукции	Возможные состояния рынка спроса
B1	B2	B3	B4
A1
A2
A3
A4

Платёжная матрица имеет вид:

Элемент матрицы A - { a_ij } характеризует, какую прибыль может получить предприятие, если оно будет выпускать i - й вид продукции(i =1, 2, 3, 4) при j-м спросе(j = 1, 2, 3, 4).

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

Эта задача может быть сведена к антагонистической игре.

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

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

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

· первую чистую стратегию, соответствующую выпуску предприятием только продукции A₁

· вторую чистую стратегию, соответствующую выпуску предприятием только продукции A₂

· третью чистую стратегию, соответствующую выпуску предприятием только продукции A₃

· четвёртую чистую стратегию, соответствующую выпуску предприятием только продукции A₄

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

· первую чистую стратегию, при которой реализуется состояние спроса B₁;

· вторую чистую стратегию, при которой реализуется состояние спроса B₂;

· третью чистую стратегию, при которой реализуется состояние спроса B₃;

· четвёртую чистую стратегию, при которой реализуется состояние спроса B₄.

Дата добавления: 2014-01-15