Кулик Елементы теории принятия решений 2010
.pdfПример 1.13 (см. и ср. [47,с . 26-27])
Проверить наличие седловой точки и решить игру, т.е. найти оптимальные стратегии для двух игроков A и B. Платёжная матрицаизвестна и представленав следующем виде:
Платёжнаяматрица игры 2 ×2
СтратегииAi |
Стратегии B i |
||
дляигрока B |
|||
дляигрока A |
|||
B1 |
B2 |
||
|
|||
A1 |
1 |
–1 |
|
A2 |
–1 |
1 |
|
Решение
1). Найдём нижнююцену игры α (максимин) по формуле
α= max1≤i≤m (1min≤ j≤n {aij }).
В даннойзадаче m=2 и n=2.
2). Вычислимминимум Mi по каждой строке платёжной матрицы.
Для1йстроки:
M1= min{ +1, −1} = −1 .
Для2йстроки:
M2= min{ −1, +1}= −1 .
3). Запишем полученный результат Mi в дополнительный столбец справаплатёжной матрицы.Получим следующую таблицу:
Платёжнаяматрица игры 2 ×2
Стратегии Ai |
Стратегии B i |
Mi |
||
дляигрока B |
||||
дляигрока A |
||||
B1 |
B2 |
|
||
|
|
|||
A1 |
1 |
–1 |
–1 |
|
A2 |
–1 |
1 |
–1 |
|
Тогда нижняяцена игры α = max{−1, −1} = −1.
101
4). Найдём верхнюю цену игры β (минимакс) по следующей форму-
ле( n=2 и m=2):
β= 1min≤ j≤n (max1≤i≤m {aij }).
5). Вычислиммаксимум Dj в каждом столбце платёжной матрицы:
Dj = max≤ ≤ = {akj }.
1 k m 2
Для1- |
гостолбца: |
D1= max{+1, −1}= +1 . |
|
|
|||||
|
|
|
|
|
|||||
Для2- |
гостолбца: |
D2= max{−1, +1}= +1 . |
|
|
|||||
|
|
|
|
|
|||||
6). Запишем полученный результат |
Dj в дополнительную строку |
||||||||
снизу платёжной матрицы. Получим следующуютаблицу |
: |
|
|||||||
|
|
Платёжнаяматрица игры 2 ×2 |
|
|
|||||
|
|
Стратегии Ai |
СтратегииB i |
|
Mi |
|
|||
|
|
дляигрока B |
|
|
|||||
|
|
дляигрока A |
|
|
|||||
|
|
B1 |
|
B2 |
|
|
|
||
|
|
|
|
|
|
|
|
||
|
|
A1 |
|
1 |
|
–1 |
|
–1 |
|
|
|
A2 |
|
–1 |
|
1 |
|
–1 |
|
|
|
Dj |
|
+1 |
|
+1 |
|
— |
|
Тогда верхняяцена игры β = min{+1, +1} = +1 .
7). Установлениеналичияседловойточки |
. |
Так как для (1.1) α ≠ β, поскольку α = |
−1 , β = +1 , то нет седло- |
вой точки. Поэтому далее решение игры будем искать среди смешанных стратегийдля игроков A и B.
8). Поиск смешанныхстратегий в игребез седловойточки. Замечаем (см. табл. 1.1), что в данной игре для платёжной матрицысправедливо следующее:
a11 =1; a12 = –1; a21 = –1; a22 =1.
102
Из формулы (1.2) находимp1:
|
|
|
|
|
|
p = |
|
|
|
|
|
(a22 −a21 ) |
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
(a11 +a22 −a12 −a21 ) |
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
или |
|
1−(−1) |
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
1+1 |
|
|
|
|
2 |
|
1 |
|
|
|
|
|
1 |
|
1 |
|
||||||||||
p = |
|
( |
|
|
|
|
|
|
|
= |
|
|
= |
= |
|
, p =1− |
= |
. |
|||||||||||||||||
( |
|
( |
) |
( |
|
|
)) |
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
1 |
+1− |
|
|
|
|
1+1+1+1 4 2 |
2 |
2 2 |
|
||||||||||||||||||||||||||
1 |
|
−1 − |
|
−1 |
|
|
|
|
|||||||||||||||||||||||||||
Из формулы (1.5) находимq1: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
q |
= |
|
|
|
|
|
(a22 −a12 ) |
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
(a11 +a22 −a12 −a21 ) |
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
или |
|
|
−(−1) |
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
1 |
|
|
|
|
|
|
|
1+1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
q = |
|
( |
|
|
|
|
|
|
|
|
= |
|
|
= 2 = 1 |
|
, q =1− 1 = 1 . |
|||||||||||||||||||
( |
|
( |
) |
( |
|
|
)) |
|
|
|
|
||||||||||||||||||||||||
1 |
+1− |
|
|
|
|
1+1+1+1 4 2 |
2 |
2 2 |
|
||||||||||||||||||||||||||
1 |
|
−1 − |
|
−1 |
|
|
|
|
|||||||||||||||||||||||||||
Из формулы (1.4) находимцену игры ν: |
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
ν = |
|
|
|
(a11a22 −a21a12 ) |
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
(a11 +a22 −a12 −a21 ) |
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
или |
|
|
|
( |
|
|
|
−1) |
(−1) |
) |
|
|
|
|
1−1 |
0 |
|
|
|
|
|
|
|||||||||||||
|
|
ν = |
|
1 1−( |
|
= |
|
|
|
|
|
|
|
|
|
|
= |
|
= 0 |
|
|
|
|
|
|||||||||||
|
|
|
1+1− |
( |
−1 |
− |
( |
−1 |
|
1+1+1+1 |
4 |
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
( |
|
|
|
|
) |
|
|
)) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Тогда решениюигры в смешанных стратегияхсоответствуют
|
|
|
|
A |
A |
|
||
оптимальное решение стороны |
|
* |
= |
|
1 |
2 |
|
|
игрокаA — SA |
1 |
1 |
, |
|||||
|
|
|
|
2 |
2 |
|
||
|
|
|
|
B |
B |
|
|
|
оптимальное решениестороны |
игрока B — |
* |
|
|
1 |
2 |
|
|
SB = |
|
1 |
1 |
. |
||||
|
|
|
|
2 |
2 |
|
||
Оптимальная стратегия каждого игрока — случайным образом (с частотой 0.5) чередоватьобе своичистые стратегии.
9). Итем самым задача решена▄
103
Пример 1.14
Проверить наличие седловой точки и решить игру, т.е. найти оптимальные стратегии для двух игроков A и B. Платёжная матрицаизвестна и представленав следующем виде:
Платёжнаяматрица игры 2 ×2
СтратегииAi |
Стратегии B i |
||
дляигрока B |
|||
дляигрока A |
|||
B1 |
B2 |
||
|
|||
A1 |
4 |
2 |
|
A2 |
6 |
1 |
|
Решение
1). Найдём нижнююцену игры α (максимин) по формуле
α= max1≤i≤m (1min≤ j≤n {aij }).
В даннойзадаче m=2 и n=2.
2). Вычислимминимум Mi по каждой строке платёжной матрицы.
Для1йстроки:
M1= min{ 4, 2}= 2 .
Для2йстроки:
M2= min{6, 1}=1 .
3). Запишем полученный результат Mi в дополнительный столбец справаплатёжной матрицы.Получим следующую таблицу:
Платёжнаяматрица игры 2 ×2
Стратегии Ai |
Стратегии B i |
Mi |
||
дляигрока B |
||||
дляигрока A |
||||
B1 |
B2 |
|
||
|
|
|||
A1 |
4 |
2 |
2 |
|
A2 |
6 |
1 |
1 |
|
Тогда нижняяцена игры α = max{2,1}= 2 .
104
4). Найдём верхнюю цену игры β (минимакс) по следующей форму-
ле( n=2 и m=2):
β= 1min≤ j≤n (max1≤i≤m {aij }).
5). Вычислиммаксимум Dj в каждом столбце платёжной матрицы:
|
|
|
Dj = max1≤k ≤m=2 |
{akj }. |
|
|
|||
Для1- |
гостолбца: |
D1= max{4, 6} = 6 . |
|
|
|||||
|
|
|
|
|
|||||
Для2- |
гостолбца: |
D2= max{2,1} = 2 . |
|
|
|||||
|
|
|
|
|
|||||
6). Запишем полученный результат |
Dj в дополнительную строку |
||||||||
снизу платёжной матрицы. Получим следующуютаблицу |
: |
|
|||||||
|
|
Платёжнаяматрица игры 2 ×2 |
|
|
|||||
|
|
Стратегии Ai |
|
СтратегииB i |
|
Mi |
|
||
|
|
|
дляигрока B |
|
|
||||
|
|
дляигрока A |
|
|
|
||||
|
|
|
B1 |
|
B2 |
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
A1 |
|
4 |
|
2 |
|
2 |
|
|
|
A2 |
|
6 |
|
1 |
|
1 |
|
|
|
Dj |
|
6 |
|
2 |
|
— |
|
Тогда верхняяцена игры β = min{6, 2} = 2 . |
|
|
7). Установлениеналичияседловойточки |
. |
|
Так как для (1.1) выполнимо α = β, поскольку α= 2, |
β = 2, то |
|
имеется в наличии для данной игры седловая точка a12 |
= 2 , кото- |
|
рой соответствует стратегия A1 для игрока A и стратегия B2 для игрокаB.
Оптимальному решению соответствует стратегия A1 для игрока A и стратегияB 2 для игрокаB.
8). Итем самым задача решена▄
105
Пример 1.15 (см. и ср. [34,с . 216-217])
Проверить наличие седловой точки и решить игру, т.е. найти оптимальные стратегии для двух игроков A и B. Платёжная матрицаизвестна и представленав следующем виде:
Платёжнаяматрица игры 2 ×2
СтратегииAi |
Стратегии B i |
||
дляигрока B |
|||
дляигрока A |
|||
B1 |
B2 |
||
|
|||
A1 |
2 |
2 |
|
A2 |
1 |
3 |
|
Решение
1). Найдём нижнююцену игры α (максимин) по формуле
α= max1≤i≤m (1min≤ j≤n {aij }).
В даннойзадаче m=2 и n=2.
2). Вычислимминимум Mi по каждой строке платёжной матрицы.
Для1йстроки:
M1= min{ 2, 2}= 2 .
Для2йстроки:
M2= min{ 1, 3}=1 .
3). Запишем полученный результат Mi в дополнительный столбец справаплатёжной матрицы.Получим следующую таблицу:
Платёжнаяматрица игры 2 ×2
Стратегии Ai |
Стратегии B i |
Mi |
||
дляигрока B |
||||
дляигрока A |
||||
B1 |
B2 |
|
||
|
|
|||
A1 |
2 |
2 |
2 |
|
A2 |
1 |
3 |
1 |
|
Тогда нижняяцена игры α = max{2,1}= 2 .
106
4). Найдём верхнюю цену игры β (минимакс) по следующей форму- |
|||||
ле( n=2 и m=2): |
|
|
|
|
|
|
β= |
1min≤ j≤n (max1≤i≤m {aij }). |
|
|
|
5). Вычислиммаксимум Dj в каждом столбце платёжной матрицы: |
|||||
|
|
Dj = max1≤k ≤m=2 |
{akj }. |
|
|
Для1- |
гостолбца: |
D1= max{2,1} = 2 . |
|
|
|
|
|
|
|
||
Для2- |
гостолбца: |
|
|
|
|
|
D2= max{2, 3} = 3 . |
|
|
||
6). Запишем полученный результат |
Dj в дополнительную строку |
||||
снизу платёжной матрицы. Получим следующуютаблицу |
|
: |
|||
|
Платёжнаяматрица игры 2 ×2 |
|
|
||
|
Стратегии Ai |
СтратегииB i |
Mi |
|
|
|
дляигрока B |
|
|||
|
дляигрока A |
|
|||
|
B1 |
B2 |
|
|
|
|
A1 |
2 |
|
||
|
2 |
2 |
|||
|
A2 |
1 |
3 |
1 |
|
|
Dj |
2 |
3 |
— |
|
|
|
|
|
Тогда верхняяцена игры |
min{2, 3} = 2 . |
||
7). Установление |
наличия |
точки. |
|
Так как |
для |
(1.1) |
α = β, поскольку α= 2, β = 2, |
то седловая |
точка a11 = 2 имеется, и ей соответствует стратегия |
||
A1 для игрока A и стратегия B1 для игрока B.
Оптимальному решению соответствует стратегия A1 для игрока A и стратегияB 1 для игрокаB.
8). Итем самым задача решена▄
107
Пример 1.16
Проверить наличие седловой точки и решить игру, т.е. найти оптимальные стратегии для двух игроков A и B. Платёжная матрицаизвестна и представленав следующем виде:
Платёжнаяматрица игры 1 ×1
Стратегии B i дляигрока B
B1
18
(максимин) по формуле
α= max1≤i≤m (1min≤ j≤n {aij }).
В даннойзадаче m=1 и n=1.
2). Вычислимминимум Mi по каждой строке платёжной матрицы.
Для1йстроки:
M1= min{18} =18 .
3). Запишем полученный результат Mi в дополнительный столбец справаплатёжной матрицы.Получим следующую таблицу:
Платёжнаяматрица игры 1 ×1
Стратегии Ai |
Стратегии B i |
Mi |
|
дляигрока B |
|||
дляигрока A |
|||
B1 |
|
||
|
|
||
A1 |
18 |
18 |
Тогда нижняяцена игры α = max{18}=18 .
108
4). Найдём верхнюю цену игры β (минимакс) по следующей форму- |
||||||||
ле( n=1 и m=1): |
|
|
|
|
|
|
||
|
|
|
|
β= 1min≤ j≤n (max1≤i≤m {aij }). |
|
|
||
5). Вычислиммаксимум |
Dj в каждом столбце платёжной матрицы: |
|||||||
|
|
|
|
Dj = max1≤k ≤m=2 |
{akj }. |
|
|
|
Для1- |
гостолбца: |
|
|
|
|
|||
|
|
|
|
D1= max{18}=18 . |
|
|
||
6). Запишем полученный результат |
Dj в дополнительную строку |
|||||||
снизу платёжной матрицы. Получим следующуютаблицу |
: |
|
||||||
|
|
Платёжнаяматрица игры 1 ×1 |
|
|
||||
|
Стратегии Ai |
СтратегииB i |
Mi |
|
||||
|
дляигрока B |
|
||||||
|
дляигрока A |
|
||||||
|
|
B1 |
|
|
||||
|
|
|
A1 |
|
|
|
|
|
|
|
|
|
|
18 |
18 |
||
|
|
|
Dj |
|
|
18 |
— |
|
|
|
|
|
|
|
|
|
|
Тогда |
верхняя |
цена |
|
{18} =18 . |
|
|
||
7). Установление |
наличия |
|
точки. |
|
|
|||
Так как |
α = β = 18, то |
|
выполнимо α = β, |
а зна- |
||||
чит есть седловая |
точка a11 =18 , |
которой соответствует стратегия |
||||||
A1 для игрока A и стратегия B1 для игрока B. |
|
|
||||||
Оптимальному решению соответствует стратегия A1 для игрока |
||||||||
A и стратегияB |
1 для игрокаB. |
|
|
|
|
|||
Понятно, что данный пример — вырожденный случай. В общем- |
||||||||
то, и без приведённого расчёта ясно, что только единственная стра- |
||||||||
тегияи есть оптимальная. |
|
|
|
|
||||
8). Итем самым задача решена▄ |
|
|
|
|
||||
|
|
|
|
109 |
|
|
|
|
Вопросы изадания для самопроверки и контроля
Вопросы
1.Как Вы понимаете,что такое гипотеза (поясните на примерах)?
2.Как Вы понимаете, что такое детерминированная гипотеза (поясните на примерах)?
3.Какие три причины неопределённости Вы знаете?
4.В чем состоит метод решения МКЗ оптимизации с использованием обобщенного( интегрального) критерия?
5.Какие этапы подготовки и принятия решений Вы знаете (охарактеризуйте их и поясните на примерах)?
6.Как Вы понимаете,что такое эффективность (поясните на примерах)?
7.Как Вы понимаете, что такое эффективность операции (поясните на примерах)?
8.Как Вы понимаете, что такое техническая эффективность (поясните на примерах)?
9.Как Вы понимаете,что такое параметр системы (поясните на примерах)?
10.Как Вы понимаете, что такое показатель эффективности (поясните на примерах)?
11.Как Вы понимаете критерий эффективности (поясните на примерах)?
12.Как Вы понимаете, что такое Парето-предпочтительность (ПП) поясните( на примерах)?
13.Как Вы понимаете, что такое Парето-несравнимость (ПН) поясните( на примерах)?
14.Что понимается под Парето-эффективностью (ПЭф)?
15.Как Вы понимаете Парето-оптимальность (поясните на примерах)?
16.Как Вы понимаете, что такое конфликтные ситуации, личный ход, случайный ход, конечная игра (поясните на примерах)?
17.Как Вы понимаете,что такое стратегия игрока (поясните на примерах)?
18.Как Вы понимаете, что такое оптимальная стратегия игрока( поясните на примерах)?
19.Как Вы понимаете, что такое игра с нулевой суммой( поясните на примерах)?
20.Как Вы понимаете, что такое платёжная матрица игры (поясните на примерах)?
21.Как Вы понимаете, что такое чистая стратегия игрока, смешанная стратегия игрока, решение игры, нижняя цена игры, верхняя цена игры, цена игры,
седловая точка (поясните на примерах)?
22.Как Вы понимаете, что такое минимаксная стратегия, максиминная стратегия (поясните на примерах)?
23.Как находят решение игры с седловой точкой (поясните на примерах)?
24.Как находят решение игры без седловой точки (поясните на примерах)?
25.Как следует выполнять упрощение игр (поясните на примерах)?
110