ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 25.03.2025
Просмотров: 1100
Скачиваний: 2
§6. Графоаналитический метод решения матричныхигр2× n иm×2
Для некоторых классов матричных игр практический интерес представляет графоаналитический метод. Этот метод состоит из двух частей. Вначале в матричной игре графически выявляются качественные особенности решения, затем полная характеристика решения находится аналитически.
В основе метода лежит утверждение 4.2, которое остаётся верным и в смешанном расширении игры. Седловая точка в матричной игре существует тогда и только тогда, когда выполняется равенство
max |
min |
f (x,y) = min |
max f (x,y) = ν*, |
x X |
y Y |
y Y |
x X |
причём седловую точку составляют стратегии, доставляющие внешние экстремумы в последнем равенстве.
Пример 6.1. Найти седловую точку матричной игры, заданной матрицей
2 |
3 |
11 |
|||
A = A2×3 |
|||||
= |
7 |
5 |
2 |
||
Здесь первый игрок имеет две чистые стратегии, а второй игрок три стратегии. Решаем игру с позиций первого игрока, т.е. с позиций игрока, имеющего две чистые стратегии.
Пусть его смешанная стратегия x = (α, 1−α), 0 ≤α ≤1. Вычислим
2 3 |
11 |
|||
= (2α +7(1 −α), 3α +5(1−α), |
||||
xA = (α, 1−α) |
7 5 |
2 |
||
11α + 2(1−α)) = (7 −5α, 5 − 2α, 2 −9α).
Обозначим
f1 (α) = 7 −5α,
41
f2 (α) = 5 − 2α,
f3 (α) = 2 +9α.
Найдём
max min ( f1(α), f2 (α), f3 (α)) =
0≤α≤1 i {1,2,3}
max ( min (7 −5α, 5 - 2α, 2 +9α )).
0≤α≤1 i {1,2,3}
Для нахождения максимина приведём геометрическую иллюстрацию на рис.6.1.
f
7 |
f3 (α) |
||||
E |
|||||
5 |
49 C |
f2 (α) |
|||
3 |
|||||
B |
, |
||||
2 A |
11 |
11 |
D |
||
f1 (α) |
||
0 |
1 |
α |
Рис. 6.1. |
||
Вначале для каждого α [0,1] |
найдём |
min (7 −5α, 5 -2α, 2 +9α ).
i {1,2,3}
На рис.6.1 такие минимумы для каждого α [0,1] образуют
ломаную – нижнюю огибающую АВСD. Затем на огибающей находим наибольшее значение, которое достигается в точке В.
Эта точка реализуется при α [0,1] , которое является решением
42
уравнения |
f2 = f3 , т.е. |
5-2 α = 2+9 α. Здесь |
α = |
311. Вторая |
||||||||||
координата точки В будет 5 −2 |
3 |
= |
49 |
. Итак В( |
3 |
, |
49 |
). В |
||||||
11 |
11 |
|||||||||||||
11 |
11 |
|||||||||||||
смешанном расширении данной игры |
||||||||||||||
max ( min (7 −5α, 5 - 2α, 2 +9α )) =49 . |
||||||||||||||
0≤α≤1 i {1,2,3} |
11 |
|||||||||||||
Максиминная стратегия первого игрока xн |
= ( α, 1- α) = |
|||||||||||||
(3/11, 8/11). |
||||||||||||||
По аналогичной схеме найдём минимаксную стратегию |
||||||||||||||
второго |
игрока. |
Его |
стратегию |
обозначим |
||||||||||
y = (0, β, 1 − β), 0 ≤ β ≤1. Первая компонента вектора y равна
0, т.к. максиминная стратегия определяется вторым и третьим столбцом матрицы А. В этом случае в максиминной стратегии
первая компонента равна 0. Для нахождения β [0, 1] в матрице
А оставим только второй и третий столбцы. Вычислим
× |
T |
3 11 |
β |
|||
A y |
= (3β +11(1− β), 5β + 2(1 − β)) = |
|||||
= |
5 2 |
|||||
1 |
− β |
|||||
(11 −8β, 2 +3β) .
Обозначим
f1 (β) =11 −8β ,
f1 (β) = 2 +3β.
Найдём
min max ( f1(β), f2 (β)) =
0≤β≤1 i {1,2}
min (max (11−8β, 2 +3β)).
0≤β≤1 i {0,1}
Для нахождения минимакса приведём геометрическую иллюстрацию на рис.6.2.
43
f
K
11 f1(β)
9 |
49 |
||||
L |
, |
||||
11 |
11 |
||||
M
2 f2 (β)
0 |
1 β |
|
Рис. |
6.2. |
|
Вначале для каждого β [0,1] найдём
min (11−8β, 2 +3β).
i {1,2}
На рис.6.2 такие минимумы для каждого β [0,1] образуют
ломаную – верхнюю огибающую KLM. Затем на огибающей находим наименьшее значение, которое достигается в точке L.
Эта точка появляется при β [0,1] , |
которое является решением |
|||||||||
уравнения f1 = f2 , т.е. 11-8 β = 2+3 β . Здесь |
β = 911. Вторая |
|||||||||
координата точки L будет 11−8 9 |
11 |
= 49 |
11 |
. Итак L( |
9 |
, |
49 |
). В |
||
11 |
11 |
|||||||||
смешанном расширении данной игры |
||||||||||
min (max (11−8β, 2 +3β)) =49 . |
||||||||||
0≤β≤1 i {1,2} |
11 |
|||||||||
Минимаксная стратегия второго игрока yB = (0, |
β, 1-β) = (0, 9/ |
|||||||||
11, 2/11).
В примере выполнены условия утверждения 4.2. В самом деле, минимакс и максимин существуют и выполнено равенство
νB = νН = 49/11.
44
Значит цена игры ν * = 49/11 и седловая точка (x*, y*) = ((3/11, 8/ 11), (0, 9/11, 2/11)).
Витоговой проверке следует продемонстрировать
выполнение равенства |
(x*)T A( y*) =v *. |
В данном случае |
||||||
получаем |
||||||||
0 |
||||||||
2 |
3 11 |
|||||||
( 3 , 8 |
9 |
= 49 . |
||||||
) |
||||||||
11 |
11 |
7 |
11 |
11 |
||||
5 2 |
||||||||
2 |
||||||||
11 |
||||||||
Это верное равенство.
Ответ : (x*, y*) = ((3/11, 8/11), (0, 9/11, 2/11)), ν * = 49/11 .
Пример 6.2. Найти седловую точку матричной игры, заданной матрицей
1 4 A3×2 = 3 - 20 5
Здесь игрок 1 имеет три чистые стратегии, а второй игрок две стратегии. Решаем игру с позиций второго игрока, т.е. с позиций игрока, имеющего две чистые стратегии.
Пусть стратегия второго игрока |
y = (β, 1− β), 0 ≤ β ≤1. |
|||||||
Вычислим |
||||||||
1 4 |
β |
4 |
−3β |
|||||
3 - 2 |
5β − 2 |
|||||||
A yT = |
− |
= |
. |
|||||
0 5 |
1 |
β |
5 |
−5β |
||||
Обозначим
f1 (β) = 4 −3β , f2 (β) = 5β −2, f3 (β) = 5 −5β.
45