Файл: Методы оптимизации лабораторный практикум.pdf

Решение матричной игры в чистых стратегиях. Рассмотрим игру m×n с матрицей
 
,
1, ,
1,
ij
P
a
i
m Выбирая стратегию
i
A
, игрок А должен рассчитывать, что игрок В ответит на неѐ той стратегией
j
B
, при которой выигрыш игрока А будет наименьшим. Пусть
i

− наименьший выигрыш игрока А при выборе им стратегии для всех возможных стратегий игрока В, тогда
1,
min
,
i
ij
j
n
a



то есть наименьшее числовой строке платѐжной матрицы. Среди всех чисел
i

,
1,
i
m

выберем наибольшее j=1,n
1,
1,
max max Число

называется нижней ценой игры, или максиминным выигрышем (максимином). Это гарантированный выигрыш игрока А при любой стратегии игрока В. Стратегия, соответствующая максими- ну, называется максиминной стратегией. Игрок В заинтересован в том, чтобы уменьшить выигрыш игрока А, поэтому он выбирает стратегию
j
B
, учитывая при этом максимально возможный выигрыш для А. Пусть
j

− наибольший выигрыш игрока А при выборе им всех возможных стратегий, когда игрок В выбирает стратегию, тогда Одновременно является наибольшим проигрышем игрока В при выборе им стратегии
j
B
, поэтому среди всех чисел выбираем наименьшее, чтобы найти ту стратегию игрока В, при которой его проигрыш будет наименьшим. Это число обозначим

, и оно равно
1,
1,
1,
min min max
j
ij
j
n
j
n Число

называется верхней ценой игры, или минимаксным выигрышем (минимаксом. Это гарантированный проигрыш игрока В. Гарантированный в том смысле, что средний проигрыш игрока В при многократном повторении игры не будет больше этого значения. Также и выигрыш игрока Ане превысит верхней цены игры. Стратегия, соответствующая минимаксу, называется минимаксной стратегией. Принцип, диктующий игрокам выбор наиболее осторожных минимаксной и максиминной стратегий, называется принципом минимакса.

Этот принцип следует из того, что в антагонистической игре каждый игрок стремится достичь цели, противоположной цели его противника. Если верхняя и нижняя цены игры совпадают, то их общее значение называют чистой ценой игры, или ценой игры, при этом справедливо равенство
  
 
Минимаксные стратегии, соответствующие цене игры, являются оптимальными, а их совокупность – оптимальным решением, или решением игры. В этом случае оптимальной для игрока А является максиминная стратегия, а оптимальной стратегией для игрока В − ми- нимаксная. Говорят, что решение игры обладает устойчивостью, те. если один из игроков придерживается своей оптимальной стратегии, то для другого не может быть выгодным отклоняться от своей оптимальной стратегии Пара чистых стратегий и
j
B
даѐт оптимальное решение игры тогда и только тогда, когда соответствующий ей элемент является одновременно наибольшим в своем столбце и наименьшим в своей строке. Такая ситуация, если она существует, называется седловой точкой. Игра, для которой
 

, называется игрой с седловой точкой. Таким образом, решение игры в чистых стратегиях существует тогда и только тогда, когда платѐжная матрица имеет седловую точку. Однако наличие седловой точки в игре − это далеко не правило, скорее − исключение. Большинство матричных игр, не имеет седловой точки, а, следовательно, не имеет оптимальных чистых стратегий. Впрочем, есть разновидность игр, которые всегда имеют седловую точку и, значит, решаются в чистых стратегиях. Это − игры с полной информацией. Теорема 1. Каждая игра с полной информацией имеет седловую точку, а, следовательно, решается в чистых стратегиях, те. имеется пара оптимальных чистых стратегий, дающая устойчивый выигрыш, равный Решение матричной игры в смешанных стратегиях. Возникает вопрос как найти решение игры, платежная матрица которой не имеет седловой точки Применение максиминного принципа каждым из игроков обеспечивает игроку А выигрыш не менее

, игроку − проигрыш не больше

. Учитывая что
 

, естественно для игрока А желание увеличить выигрыша для игрока В − уменьшить проигрыш. Поиск такого решения приводит к необходимости применять

смешанные стратегии чередовать чистые стратегии с какими-то частотами. Случайная величина, значениями которой являются чистые стратегии игрока, называется его смешанной стратегией. Таким образом, задание смешанной стратегии игрока состоит в указании тех вероятностей, с которыми выбираются его чистые стратегии. Будем обозначать смешанные стратегии игроков Аи В соответственно, где
i
p
− вероятность применения игроком А чистой стратегии
i
A
,
1 1
m
i
i
p



;
j
q − вероятность применения игроком В чистой стратегии
j
B ,
1 Итак, если матричная игра не имеет седловой точки, то игрок должен использовать оптимальную смешанную стратегию, которая обеспечит максимальный выигрыш

. Естественно возникает вопрос какими соображениями нужно руководствоваться при выборе смешанных стратегий Оказывается принцип максимина сохраняет свое значение ив этом случае. Основная теорема матричных игр (Теорема Неймана). Любая матричная игра имеет, по крайней мере, одно оптимальное решение, в общем случаев смешанных стратегиях и соответствующую цену

. Из теоремы следует, что любая матричная игра имеет цену Цена игры

− средний выигрыш, приходящийся на одну партию, всегда удовлетворяет условию
  
 
, те. лежит между нижней

и верхней

ценами игры. Оптимальное решение игры в смешанных стратегиях, также как и решение в чистых стратегиях, обладает тем свойством, что каждый из игроков не заинтересован в отходе от своей оптимальной смешанной стратегии, если его противник применяет свою оптимальную смешанную стратегию, так как это ему невыгодно. Эта пара стратегий образует в игре положение равновесия один игрок хочет обратить выигрыш в максимум, другой − в минимум, каждый тянет в свою сторону и, при оптимальном поведение обоих, устанавливается равновесие и устойчивый выигрыш Те из чистых стратегий игроков Аи В, которые входят в их оптимальные смешанные стратегии с вероятностями, неравными нулю, называются активными стратегиями.

Существует теорема об активных стратегиях, применение которой позволяет упрощать решение некоторых матричных игр. Теорема об активных стратегиях. Если один из участников матричной игры, придерживается своей оптимальной смешанной стратегии, то это обеспечивает ему максимальный средний выигрыш, равный цене игры

, независимо оттого, какие действия предпринимает другой игрок, если только он не выходит за пределы своих активных стратегий (те. пользуется любой из них в чистом виде или смешивает их в любых пропорциях. Эта теорема имеет большое практическое значение – она дает конкретные модели нахождения оптимальных стратегий при отсутствие седловой точки. Решение игры 2×2. Рассмотрим игру 2×2 с матрицей
11 12 21 22 2 2
a
a
P
a
a



 



без седловой точки. Решением игры являются смешанные стратегии игроков
*
1 2
(
,
)
A
S
p p

и
*
1 2
( ,
)
B
S
q q

. Очевидно, что
1 2
1 2
1, Использование игроком А своей оптимальной стратегии гарантирует ему получение среднего выигрыша не меньшего, чем цена игры. При этом, если игрок В использует свою оптимальную стратегию, то средний выигрыш игрока будет равен

, если игрок Вне использует свою оптимальную стратегию, то средний выигрыш игрока А будет больше Для решения матричных игр 2×2 можно использовать анали-
тическийи геометрическийметоды. Аналитический метод решения игры 2×2. Чтобы найти оптимальную смешанную стратегию игрока Аи соответствующую цену игры

, необходимо решить систему уравнений
11 1
21 2
12 1
22 2
1 2
,
,
1.
a p
a p
v
a p
a p
v
p
p











(8.1) Первое уравнение определяет математическое ожидание выигрыша игрока А при использовании им стратегии
*
1 2
(
,
)
A
S
p p

против стратегии
1
B
; второе уравнение определяет математическое ожидание выигрыша игрока А при использовании им стратегии
*
1 2
(
,
)
A
S
p против стратегии
2
B
; третье уравнение – свойство компонентов смешанной стратегии игрока.

Приравнивая выражения для

из уравнений системы и учитывая, что
1 2
1,
p
p


получим
22 21 1
11 22 12 21 11 12 2
11 22 12 21 11 22 12 21 11 22 12 21
,
,
a
a
p
a
a
a
a
a
a
p
a
a
a
a
a a
a a
v
a
a
a
a















(8.2) Аналогично для игрока В. Чтобы найти оптимальную смешанную стратегию игрока В
*
1 2
( ,
)
B
S
q q

и соответствующую цену игры

, решаем систему уравнений
11 1 12 2
21 1 22 2
1 2
,
,
1.
a q
a q
v
a q
a q
v
q
q











(8.3) Получим
22 12 1
11 22 12 21 11 21 2
11 22 12 21
,
a
a
q
a
a
a
a
a
a
q
a
a
a
a










(8.4) Цена игры

общая для обоих игроков. Решение игры
2

n. Игра задана матрицей
11 12 1
21 22 2
2
n
n
n
a
a
a
P
a
a
a



 Для каждой из п стратегий игрока Встроит- ся соответствующий ей отрезок на плоскости. Находится нижняя граница выигрыша, получаемого игроком Аи определяется точка на нижней границе, соответствующая наибольшему выигрышу. Выделяются две активные стратегии игрока В, отрезки которых проходят через данную точку. Далее рассматриваются только эти две стратегии игрока В. Игра сводится к игре с матрицей 2 Решение игры m

2. Рассмотрим игру m

2 с матрицей
11 12 21 22 1
2 2
m
m
m
a
a
a
a
P
a
a
















Решение игры может быть получено аналогично предыдущему случаю. Для каждой из т стратегий игрока А строится

соответствующий ей отрезок на плоскости. Находится верхняя граница проигрыша, получаемого игроком В, и определяется точка на нижней границе, соответствующая наименьшему проигрышу. Выделяются две активные стратегии игрока А, отрезки которых проходят через данную точку. Далее рассматриваются только эти две стратегии игрока А. Игра сводится к игре с матрицей 2 Решение игр m×n сведением к задаче линейного программирования. Пусть имеется матричная игра m×n без седловой точки с матрицей выигрышей
 
ij
a
. Допустим, что все выигрыши
ij
a положительны (этого всегда можно добиться, прибавляя ко всем элементам матрицы достаточно большое число Сот этого цена игры увеличится на C, а оптимальные решения
*
A
S
и
*
B
S
не изменятся. Если все
ij
a
положительны, то и цена игры

при оптимальной стратегии тоже положительна, т.к.
  
 В соответствии с основной теоремой матричных игр, если платежная матрица не имеет седловой точки, то имеется пара оптимальных смешанных стратегий


*
1 2
,
,...,
A
m
S
p p
p

,


*
1 2
,
,...,
B
n
S
q q
q

, применение которой обеспечивает игрокам получение цены игры Найдем вначале
*
A
S
. Для этого предположим, что игрок В отказался от своей оптимальной смешанной стратегии
*
B
S
и применяет только чистые стратегии. В каждом из этих случаев выигрыш игрока А будет не меньше, чем

:
11 1
21 2
1 12 1
22 2
2 1
1 2
2
,
,
m
m
m
m
n
n
mn
m
a p
a p
a p
v
a p
a p
a
p
v
a p
a p
a p
v

 




 






 


(8.5) Разделив левую и правую часть каждого из неравенств (8.5) на положительную величину

и введя обозначения
1 2
1 запишем неравенства (8.5) в следующем виде
11 1 21 2 1
12 1 22 2
2 1
1 2
2 1,
1,
1,
m
m
m
m
n
n
mn
m
a x
a x
a x
a x
a x
a x
a x
a x
a x

 




 






 


(8.7) где
1 2
,
,...,
m
x x
x
− неотрицательные переменные.

В силу того, что
1 2
1
m
p
p
p

 

, переменные
1 2
,
,...,
m
x удовлетворяют условию
1 2
1
m
x
x
x
v

 

(8.8) Учитывая, что игрок А стремится максимизировать

, получаем следующую задачу линейного программирования найти неотрицательные значения переменных
1 2
,
,...,
m
x x
x
такие, чтобы они удовлетворяли линейным ограничениям − неравенствами обращали в минимум линейную функцию этих переменных
1 2
1
min
m
Z
x
x
x
v
 
 
 
(8 . 9 ) Из решения задачи линейного программирования находим цену игры

и оптимальную стратегию
*
A
S
по формулам 1
m
i
i
v
x



,
(8.10)
1
i
i
i
n
i
i
x
p
x v
x


 

,
1,
i
m

(8.11) Аналогично находим оптимальную стратегию
*
B
S
игрока В. Предположим, что игрок А отказался от своей оптимальной стратегии
*
A
S и применяет только чистые стратегии. Тогда проигрыш игрока В в каждом из этих случаев будет не больше, чем

:
11 1 12 2
1 21 1 22 2
2 1 1 2
2
,
,
n
n
n
n
m
m
mn
n
a q
a q
a q
v
a q
a q
a q
v
a q
a q
a q
v

 




 






 


(8.12) Разделив левую и правую части каждого их неравенств (8.12) на положительную величину

и введя обозначения
1 2
1 2
,
,...,
n
n
q
q
q
y
y
y
v
v
v



,
(8.13) запишем неравенство (8.12) в следующем виде
11 1 12 2
1 21 1 22 2
2 1 1 2
2 1,
1,
1.
n
n
n
n
m
m
mn
n
a y
a y
a y
a y
a y
a y
a y
a y
a y

 




 






 


(8.14)

где
1 2
,
,...,
n
y y
y
− неотрицательные переменные. В силу того, что
1 2
1
n
q
q
q

 

, переменные
1 2
,
,...,
n
y удовлетворяют условию
v
y
y
y
n
1 2
1




(8 . 1 5 ) Учитывая, что игрок В стремится минимизировать положительную цену

(свой проигрыш, получаем задачу линейного программирования найти неотрицательные значения переменных
1 2
,
,...,
n
y такие, чтобы они удовлетворяли линейным ограничениями обращали в максимум линейную функцию этих переменных
1 2
max
n
L
y
y
y


 

(8 . 1 6 ) Эта задача является двойственной по отношению к задаче, представленной условиями (8.9) и (8.7). Оптимальная стратегия
*
B
S игрока В определяется из решения двойственной задачи линейного программирования по формулам
1
j
j
j
n
j
j
y
q
y
v
y





,
1,
j
n

(8.17) Таким образом, оптимальные стратегии и матричной игры с платежной матрицей
 
ij
a
могут быть найдены путем решения пары двойственных задач линейного программирования Прямая (исходная) задача Двойственная задача
1
min,
m
i
i
Z
x







m
i
i
ij
x
a
1 1
,
1,
j
n

;
0

i
x
,
m
i
,
1

1
max,
n
j
j
L
y







n
j
j
ij
y
a
1 1
,
m
i
,
1

;
0
j
y

, При этом
1 1
1 1
1 1
m
n
i
j
i
j
v
Z
L
x
y








,
(8.18)
,
1, ;
,
1,
i
i
j
j
p
x v i
m q
y v j
n





Пример 1. Предприятие может выпускать три вида продукции А, Б и В, получая при этом прибыль, зависящую от спроса. Спрос в свою очередь может принимать одно из четырех состояний (I, II, III,
IV). В следующей матрице элементы
ij
a характеризуют прибыль, которую получит предприятие при выпуске й продукции им состоянии спроса. Определить оптимальные пропорции выпускаемой продукции, считая состояние спроса полностью неопределенным, гарантируя при этом среднюю величину прибыли при любом состоянии спроса.
I
II
III
IV А
8 3
6 2 Б
4 5
6 5 В
1 7
4 7 Решение Игра не имеет седловой точки. Оптимальное решение следует искать в области смешанных стратегий. Пусть пропорции выпускаемой продукции
1 2
3
,
,
p p p ,
1 2
3 1
p
p
p



. Введем переменные
,
1,3
i
i
p
x
i



,

‒ гарантированная прибыль. Для определения оптимальных пропорций выпускаемой продукции составляем следующую задачу линейного программирования
1 2
3 1
2 3
1 2
3 1
2 3
1 2
3 1
2 3
1 2
3 1
( ,
,
)
min,
8 4
1,
3 5
7 1,
6 6
4 1,
2 5
7 1,
0,
0,
0.
L x x x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x

 

 
  


  
  
  
  
  
  Решение данной задачи симплекс методом процесс трудоемкий, поэтому покажем, как данную задачу можно решить, используя математические пакеты. Решение задачи в пакете Maple
1. Подключаем пакет