Материал: 3082
11
Решение одной из пары двойственных задач можно найти симплексным методом (графически для 2-х переменных). Цену игры и оптимальные стратегии находим по формулам:
1 , , , 1, ; 1, , (1.15)
∑
1.3.2. Если в матричной игре (aij)mxn строки (столбцы) с одними и теми же элементами, то эти строки (столбцы), соответственно и стратегии игроков называются дублирующими.
Если для двух стратегий Ak и At с элементами akj и atj (j = |
|
) |
|
выполняются условия: akj > atj, то стратегия Ak называется |
доминирующей, а |
||
|
1, |
|
|
стратегия At, — доминируемой.
Вматричнойигредоминируемыеидублирующиестроки(столбцы) можно опускать, что не влияет на решение задачи (игры).
Пример 1.2. Найти решение игры, определяемой матрицей
A = |
2 |
5 |
1 . |
|
3 |
4 |
6 |
|
4 |
3 |
4 |
Решение. Сведем данную матричную игру к паре симметричных
двойственных задач линейного программирования. |
|
|
|
|
|
|
||||
Прямая задача: Найти минимум функции F = x1 + х2 + x3 |
— min, при |
|||||||||
ограничениях |
4 |
|
1, |
|
|
|
|
|
|
|
2 |
3 |
|
|
|
|
|
|
|
||
5 |
4 |
3 |
1, |
|
|
|
|
|
|
|
xi ≥ 06(i = |
4 |
). |
1, |
1 |
|
2 |
|
3 |
|
|
|
|
1,3 |
|
+ у |
+ y |
— max при |
||||
Двойственная задача: Найти максимум функции Z = y |
|
|
|
|||||||
ограничениях |
|
|
1, |
|
|
|
|
|
|
|
2 |
5 |
6 |
|
|
|
|
|
|
||
3 |
4 |
1, |
|
|
|
|
|
|
||
4 |
3 |
4 |
1, |
|
|
|
|
|
|
|
yj ≥ 0 (j = 1,3).
Находим оптимальные планы пары двойственных задач (табл.1.2).
12
Таблица 1.2
№ |
Б |
|
СБ |
А0 |
1 |
|
1 |
|
1 |
|
0 |
|
0 |
|
0 |
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
А1 |
|
А2 |
|
А3 |
|
А4 |
|
А5 |
|
А6 |
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
A4 |
|
0 |
1 |
|
2 |
|
5 |
|
1 |
|
1 |
|
0 |
|
0 |
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
A5 |
|
0 |
1 |
|
3 |
|
4 |
|
6 |
|
0 |
|
1 |
|
0 |
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
A6 |
|
0 |
1 |
|
|
4 |
|
3 |
|
4 |
|
0 |
|
0 |
|
1 |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
m+1 |
|
j = Zj - cj |
0 |
|
-1 |
|
-1 |
-1 |
|
0 |
|
0 |
|
0 |
|
|||||||||||||
1 |
A4 |
|
|
1 |
|
0 |
|
|
|
7 |
|
-1 |
|
1 |
|
0 |
|
|
1 |
|
|
|||||||
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
2 |
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
||||
2 |
A5 |
|
0 |
|
1 |
|
0 |
|
|
7 |
|
3 |
|
0 |
|
1 |
|
|
3 |
|
|
|||||||
|
|
|
|
4 |
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
||||
3 |
A1 |
|
1 |
|
1 |
|
1 |
|
|
3 |
|
1 |
|
0 |
|
0 |
|
|
1 |
|
||||||||
|
|
|
|
4 |
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|||||
m+1 |
|
j = Zj - cj |
|
1 |
|
0 |
|
|
1 |
|
0 |
|
0 |
|
0 |
|
|
1 |
|
|||||||||
|
|
|
|
4 |
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|||||
1 |
A2 |
|
1 |
|
1 |
|
0 |
|
1 |
|
|
2 |
|
|
2 |
|
0 |
|
|
1 |
|
|
||||||
|
|
|
|
7 |
|
|
|
|
|
|
|
|
7 |
7 |
|
|
|
|
|
7 |
|
|
||||||
2 |
A5 |
|
0 |
0 |
|
0 |
|
0 |
|
|
7 |
|
|
|
1 |
|
1 |
|
|
1 |
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
2 |
|
|
|
|
|
2 |
|
|
||||
3 |
A1 |
|
1 |
|
1 |
|
1 |
|
0 |
|
|
17 |
|
|
3 |
|
0 |
|
|
5 |
|
|||||||
|
|
|
|
7 |
|
|
|
|
|
|
|
|
14 |
14 |
|
|
|
|
14 |
|||||||||
m+1 |
|
j = Zj - cj |
|
2 |
|
0 |
|
0 |
|
|
1 |
|
1 |
|
0 |
|
|
3 |
|
|||||||||
|
|
|
|
7 |
|
|
|
|
|
|
|
|
14 |
14 |
|
|
|
|
14 |
|||||||||
1 |
A2 |
|
1 |
|
1 |
|
0 |
|
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
2 |
|
|
1 |
|
|
|
2 |
A3 |
|
1 |
0 |
|
0 |
|
0 |
|
1 |
|
|
|
|
|
|
|
|
|
|||||||||
3 |
A1 |
|
1 |
|
1 |
|
1 |
|
0 |
|
0 |
|
7 |
|
7 |
|
7 |
|
|
|||||||||
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
1 |
|
|
10 |
|
||||
m+1 |
|
j = Zj - cj |
|
2 |
|
0 |
|
0 |
|
0 |
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
49 |
49 |
49 |
||||||||||
13
Из таблицы 1.2 видно, что двойственная задача имеет оптимальный план
Y*= ( |
|
;0; |
|
), |
|
а |
прямая задача |
— |
оптимальный |
план X* |
= ( |
; |
|
; |
). |
|||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||
Следовательно, цена игры |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
1 |
|
|
|
|
|
|
|
|
3 |
|
1 |
|
|
|
|
|
|
|
|
|
49 |
|
|
7 |
, |
|
а оптимальные стратегии игроков |
|
|
||||||||||||||||||||||||||||
|
p |
* |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
10 |
|
14 |
|
|
2 |
|
|
|
|
|
|
|
* |
|
|
|
|
1 |
|
2 3 |
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
|
= (p1, p249, 3 |
49 |
|
i 49 |
|
|
|
|
i |
|
|
|
|
1,3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||
|
qj |
= ν · yj |
(j = |
|
|
|
). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
) и q |
|
|
= (q , q , q ), где |
|
|
|
|
|
|
|||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
p ), где p = ν · x (i = |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||
|
p1 = |
|
|
|
|
|
|
|
|
|
|
1,3 |
|
|
p2 = |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
p3 = |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
0;) и q* |
|
|
|
|
).. |
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||
|
Таким образом;, p* |
= ( |
|
|
|
|
|
|
|
= ( |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||
|
q1 |
= |
|
|
|
|
|
|
|
|
|
|
|
|
q;2 = |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
q3 |
=; |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. |
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
; |
|
|
|
|
; |
|
|
|
|
|
|
|
|
; |
|
0; |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
1.4. Статистические игры. Критерии для принятия решений
1.4.1. Во многих задачах, приводящихся к игровым, например, в управленческих задачах для принятия решения необходима информация о состоянии объекта управления в условиях его работы. В большинстве случаев полная информация о состоянии объекта отсутствует и возникает необходимость принятия решения в зависимости от объективной действительности, которую принято называть природой. Такие игры называют играми с природой. Человек статистик в играх с природой — действует осмотрительно, второй игрок (природа) действует совершенно случайно. В некоторых задачах для состояния природы может быть задано состояние приро-
дыраспределением вероятностейеесостояний, в другихзадачахоно неизвестно.
…
Условия игры также задаются матрицей A = |
… |
… … = (aij)mxn |
|||||||
1.4.2. Условимся множество состояний природы |
обозначать через П или |
||||||||
… |
|||||||||
Пj, где Пj |
П (j = |
|
). Множество стратегий статистика обозначим через А, его |
||||||
|
стратегии (решения) — A , где A |
|
A (i= |
|
). |
||||
отдельные |
|
1, |
i |
i |
|
матрица рисков R. |
|||
Иногда при решении игры рассматривается |
|||||||||
|
1, |
|
|||||||
14
Элементы матрицы rij представляют собой разность между выигрышем, который получил бы игрок А, если бы знал состояние
природы Пj, и выигрышем, который он получит в тех же условиях, применяя
стратегию Ai, то есть |
|
|
|
rij = βj - αij, где βj = max αij. |
|
|
(1.16) |
1.4.3. При решении игр с природой применяется ряд критериев |
|
||
1. Если известно распределение вероятностей |
1, |
, |
1 |
различных состояний природы Пj, то применяется критерий Байеса: критерием принятия решения является максимум математического ожидания выигрыша (минимум математического ожидания риска).
Запишемплатежнуюматрицу (aij) иматрицурисков rij ввидетаблицы1.3 и таблицы 1.4.
|
|
|
|
|
Таблица 1.3 |
|
|
|
|
|
|
|
|
Стратегии Ai |
Состояния природы |
Средний выигрыш ai |
||||
|
|
|
|
|||
П1 |
П2 |
… |
Пn |
|||
|
|
|||||
A1 |
a11 |
a12 |
… |
a1n |
a1 |
|
|
|
|
|
|
a2 |
|
A2 |
a21 |
a22 |
… |
a2n |
||
|
|
|
|
|
… |
|
… |
… |
… |
… |
… |
||
|
|
|
|
|
am |
|
Am |
am1 |
am2 |
… |
amn |
||
qi |
q1 |
q2 |
… |
qn |
|
|
|
|
|
|
|
Таблица 1.4 |
|
|
|
|
|
|
|
|
Стратегии Ai |
Состояния природы |
Средний риск rij |
||||
|
|
|
|
|||
П1 |
П2 |
… |
Пn |
|||
|
|
|||||
|
|
|
|
|
|
|
A1 |
r11 |
r12 |
… |
r1n |
r1 |
|
A2 |
r21 |
r22 |
… |
r2n |
r2 |
|
|
|
|
|
|
|
|
… |
… |
… |
… |
… |
… |
|
|
|
|
|
|
|
|
Am |
rm1 |
rm2 |
… |
rmn |
rm |
|
qi |
q1 |
q2 |
… |
qn |
|
|
15
По критерию Байеса за оптимальную принимается та стратегия Ai, при которой максимизируется средний выигрыш, то есть обеспечивается
α |
max , где |
i |
1, |
(1.17) |
и минимизируется средний риск, то есть обеспечивается r = min ri, где |
|
|||
ri= |
. |
|
|
(1.18) |
2. Если все состояния природы равновероятны, то есть q1=q2=…qn=1/n, то используется принцип недостаточного основания Лапласа. Оптимальной считается стратегия, обеспечивающая максимум среднего выигрыша.
3. Максимальный критерий Вальда совпадает с критерием выбора максимальной стратегии, позволяющей получить нижнюю цену α игры для двух лиц с нулевой суммой, то есть
4.max |
min |
(1.19 |
|
|
Критерий минимального риска Сэвиджа рекомендует выбирать стратегию, при которой величина риска принимает наименьшее значение в
наихудших условиях, то есть обеспечивается |
|
maxmin |
(1.20) |
КритерииВальдаиСэвиджавыражаютпессимистическуюоценкуситуации. 5. Критерий Гурвица рекомендует принимать решение о выборе
стратегии, при которой имеет место
max min |
1 |
max |
, где 0 ≤ λ ≤ 1. |
Значения λ выбираются исходя из опыта или по субъективным соображениям. При λ = 0 имеет место критерий крайнего оптимизма, при λ = 1 – критерий пессимизма Вальда.
Пример 1.3. Руководство фирмы рассматривает возможность строительства одной из трех автозаправочных станций (АЗС): А1, А2, А3. Эффективность работы каждой из них в основном зависит от трех основных автомагистралей, стоимости топлива и его доставки, удаленности от населенных пунктов. Предположим, что вероятности трех указанных факторов, влияющих на эффективность работы АЗС, известны и составляют соответственно 0,3; 0,5;