ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.07.2021
Просмотров: 711
Скачиваний: 2
36
Другой
вариант
игры
2x2
получается
,
если
использовать
стратегии
А
2
и
А
6
.
В
этом
случае
платежная
матрица
имеет
вид
:
B
j
A
i
B
1
B
2
A
2
4 2
A
6
1,5 3
Тогда
7
3
2
1
3
4
1
3
2
1
2
1
1
p
;
7
4
2
p
;
7
2
2
1
3
4
2
3
2
1
1
q
;
7
5
2
q
;
7
18
2
1
3
4
1
2
3
4
2
1
2
1
v
.
Ответ
:
7
4
,
0
,
0
,
0
,
7
3
,
0
A
S
;
7
5
,
7
2
B
S
;
7
18
v
.
Естественно
,
что
цена
игры
для
обоих
вариантов
одинакова
.
В
заключение
наметим
общую
схему
решения
матричных
игр
2xn
и
mx2
:
1.
Определяется
наличие
седловой
точки
,
т
.
е
.
возможность
решения
игры
в
чистых
стратегиях
.
Если
нижняя
цена
игры
не
равна
верхней
цене
игры
,
то
осуществляется
поиск
решения
в
смешанных
стратегиях
.
2.
Производится
упрощение
матричной
игры
путем
исключения
дублирующих
и
доминируемых
стратегий
.
Если
упрощенная
игра
имеет
размерность
не
2x2
,
то
переходим
к
этапу
3.
3.
Строится
графическое
изображение
игры
и
определяется
две
активные
стратегии
игрока
,
имевшего
в
исходной
задаче
число
стратегий
больше
двух
.
4.
Решается
матричная
игра
2x2
.
ТЕСТЫ
(
В
–
Верно
,
Н
–
Неверно
)
1.
Если
в
игре
2xn
нет
оптимального
решения
в
чистых
стратегиях
,
то
оптимальное
решение
в
смешанных
стратегиях
содержит
две
активные
стратегии
у
каждого
из
игроков
.
2.
В
игре
mx2
число
активных
стратегий
в
оптимальной
стратегии
каждого
из
игроков
может
быть
равно
или
единице
,
или
двум
.
3.
Оптимальное
решение
в
игре
двух
лиц
с
нулевой
суммой
всегда
является
устойчивым
независимо
от
того
,
смешанные
или
чистые
стратегии
используют
игроки
.
4.
Если
оптимальная
цена
матричной
игры
отрицательна
,
то
конечный
результат
игры
будет
убыточным
для
игрока
А
.
5.
Прибавление
одного
и
того
же
числа
ко
всем
элементам
платежной
матрицы
не
влияет
на
цену
игры
.
6.
Умножение
всех
элементов
платежной
матрицы
на
одно
и
тоже
положительное
число
не
изменяет
оптимальных
стратегий
игроков
.
37
7.
Цена
матричной
игры
изменится
,
если
из
платежной
матрицы
исключить
строки
и
столбцы
,
соответствующие
дублирующим
и
доминируемым
стратегиям
.
8.
Любая
матричная
игра
2xn
или
mx2
может
быть
сведена
к
игре
2
х
2.
(
Ответы
:
1-
В
; 2-
В
; 3-
В
; 4-
В
; 5-
Н
; 6-
В
; 7-
Н
; 8-
В
).
ЗАДАЧИ
Решить
следующие
матричные
игры
:
1.
8 1 7 2. -4 -8 -7 -3 3.
5 1 3
3 0 7
-5 -9 -8 -4 7 8 2
4. 6 13 19 25 19 15 16 18 5.
3 3 4 5
19 25 19 18 16 12 13 15 5 4 3 3
6. 0,
4
0,5
1 7. 1 2 3
8. 11 8 12 1
1
0,5
0,3
4 3 0 -7 -1 -8 2
9. 10 -4 6 14 0
10.
2 -6 10 -14 18
0 10 4 4 12
-4 8 -12 16 -20
11. 3 7 -1 11 -5
12.
9 -5 7 1 -3
6 2 10 -4 14
-10
4 -8 -6 2
13.
24 0 18 21
14.
7 9 0
9
18
9 3
6
0
10
15.
-1
8 7 6 3 1
9
0 1 2 5 7
16. 1 3 17. 2 10 18.
-3 -9 19
.
1 3
5 7
4 8 -15
-21
5 7
9 11
6 6
-27 -33
9 11
8
4
10
2
20. -1 5 21
.
11 3 22. 2 2 3 -1 23. 4
8
-3 1
9 7 4 3 2 6
4 6
0
-3
10 5
6 4
-3
0
7 11
-2 12
1
-3
8
9
5
-1
38
24. 1 3 25
.
2 4 -2 8 26
.
1 2 27. 5 9
1
4 3 6 5 -5
5 6 5 7
2
1
-7 9 7 5
-1 5 -4 -3 -1 13
2 1
28. 3 8 12 29
.
0 8
30
.
-2 10
6 10 14 2 6 -6 2
4 4
0
-6
6 2
-6
0
8 0
1 1
2
-6
10
-2
2.8.
Решение
игр
m
х
n.
Эквивалентные
задачи
линейного
программирования
Пусть
имеется
матричная
игра
mxn
без
седловой
точки
с
матрицей
выигрышей
||a
ij
||.
Допустим
,
что
все
выигрыши
a
ij
положительны
(
этого
всегда
можно
добиться
,
прибавляя
ко
всем
элементам
матрицы
достаточно
большое
число
С
;
от
этого
,
как
уже
отмечалось
,
цена
игры
увеличится
на
C,
а
оптимальные
решения
S
A
и
S
B
не
изменятся
).
Если
все
aij
положительны
,
то
и
цена
игры
при
оптимальной
стратегии
тоже
положительна
,
т
.
к
.
.
В
соответствии
с
основной
теоремой
матричных
игр
,
если
платежная
матрица
не
имеет
седловой
точки
,
то
имеется
пара
оптимальных
смешанных
стратегий
S
A
=||p
1
, p
2
, ..., p
m
||
и
S
B
=||q
1
, q
2
, ..., q
n
||,
применение
которой
обеспечивает
игрокам
получение
цены
игры
.
Найдем
вначале
S
A
.
Для
этого
предположим
,
что
игрок
В
отказался
от
своей
оптимальной
смешанной
стратегии
S
B
и
применяет
только
чистые
стратегии
.
В
каждом
из
этих
случаев
выигрыш
игрока
А
будет
не
меньше
,
чем
:
.
...
...
..........
..........
..........
,
...
,
...
2
2
1
1
2
2
22
1
12
1
2
21
1
11
v
p
a
p
a
p
a
v
p
a
p
a
p
a
v
p
a
p
a
p
a
m
mn
n
n
m
m
m
m
(2.25)
Разделив
левую
и
правую
часть
каждого
из
неравенств
(2.25)
на
положительную
величину
v
и
введя
обозначения
:
,
...,
;
;
2
2
1
1
v
p
x
v
p
x
v
p
x
m
m
(2.26)
запишем
неравенства
(2.25)
в
следующем
виде
:
1
...
...
..........
..........
..........
1
...
1
...
2
2
1
1
2
2
22
1
12
1
2
21
1
11
m
mn
n
n
m
m
m
m
x
a
x
a
x
a
x
a
x
a
x
a
x
a
x
a
x
a
, (2.27)
39
где
x
1
, x
2
, ... x
m
–
неотрицательные
переменные
.
В
силу
того
,
что
p
1
+p
2
+...+p
m
=1,
переменные
x
1
, x
2
, ... x
m
удовлетворяют
условию
x
x
x
v
m
1
2
1
...
. (2.28)
Учитывая
,
что
игрок
А
стремится
максимизировать
,
получаем
следующую
задачу
линейного
программирования
:
найти
неотрицательные
значения
переменных
x
1
, x
2
, ... x
m
такие
,
чтобы
они
удовлетворяли
линейным
ограничениям
–
неравенствам
(2.27)
и
обращали
в
минимум
линейную
функцию
этих
переменных
:
min
L
(x)=x
1
+x
2
+ ... +x
m
. (2.29)
Из
решения
задачи
линейного
программирования
находим
цену
игры
и
оптимальную
стратегию
Sa
по
формулам
:
m
i
i
x
v
1
1
(2.30) ,
v
x
x
x
p
i
n
i
i
i
i
1
,
i
m
1,
. (2.31)
Аналогично
находим
оптимальную
стратегию
S
В
игрока
В
.
Предположим
,
что
игрок
А
отказался
от
своей
оптимальной
стратегии
S
A
и
применяет
только
чистые
стратегии
.
Тогда
проигрыш
игрока
В
в
каждом
из
этих
случаев
будет
не
больше
,
чем
:
.
...
...
..........
..........
..........
,
...
,
...
2
2
1
1
2
2
22
1
21
1
2
12
1
11
v
q
a
q
a
q
a
v
q
a
q
a
q
a
v
q
a
q
a
q
a
n
mn
m
m
n
n
n
n
. (2.32)
Разделив
левую
и
правую
части
каждого
их
неравенств
(2.32)
на
положительную
величину
и
введя
обозначения
:
v
q
y
v
q
y
v
q
y
n
n
...,
;
;
2
2
1
1
, (2.33)
запишем
неравенство
(2.32)
в
следующем
виде
:
.
1
...
...
..........
..........
..........
,
1
...
,
1
...
2
2
1
1
2
2
22
1
21
1
2
12
1
11
n
mn
m
m
n
n
n
n
y
a
y
a
y
a
y
a
y
a
y
a
y
a
y
a
y
a
, (2.34)
где
y
1
, y
2
, ..., y
n
–
неотрицательные
переменные
.
В
силу
того
,
что
q
1
+q
2
+...+q
n
=1,
переменные
y
1
, y
2
, ..., y
n
удовлетворяют
условию
v
y
y
y
n
1
...
2
1
. (2.35)
Учитывая
,
что
игрок
В
стремится
минимизировать
положительную
цену
v
(
свой
проигрыш
),
получаем
задачу
линейного
программирования
:
найти
неотрицательные
значения
переменных
y
1
, y
2
, ..., y
n
такие
,
чтобы
они
удовлетворяли
линейным
ограничениям
(2.34)
и
обращали
в
максимум
линейную
функцию
этих
переменных
:
max
L
(y)=y
1
+y
2
+ ... +y
m
. (2.36)
40
Эта
задача
является
двойственной
по
отношению
к
задаче
,
представленной
условиями
(2.27)
и
(2.29).
Оптимальная
стратегия
S
B
=||q
1
, q
2
, ..., q
n
||
игрока
В
определяется
из
решения
двойственной
задачи
линейного
программирования
по
формулам
:
v
y
y
y
q
j
n
j
j
j
j
1
,
n
j
,
1
. (2.37)
Таким
образом
,
оптимальные
стратегии
S
A
=||p
1
, p
2
, ..., p
m
||
и
S
B
=||q
1
, q
2
,
..., q
n
||
матричной
игры
mxn
с
платежной
матрицей
||a
ij
||
могут
быть
найдены
путем
решения
пары
двойственных
задач
линейного
программирования
:
Прямая
(
исходная
)
задача
Двойственная
задача
m
i
i
x
x
L
1
min
,
m
i
i
ij
x
a
1
1
,
n
j
,
1
;
0
i
x
,
m
i
,
1
.
n
j
j
y
y
L
1
)
(
max
,
n
j
j
ij
y
a
1
1
,
m
i
,
1
;
0
j
y
,
n
i
,
1
.
При
этом
)
(
max
1
)
(
min
1
1
1
1
1
y
L
x
L
y
x
v
n
j
j
m
i
i
, (2.38)
n
j
v
y
q
m
i
v
x
p
j
j
i
i
,
1
;
;
,
1
;
.
Пример
.
Найти
решение
и
цену
матричной
игры
,
платежная
матрица
которой
имеет
вид
B
j
A
i
B
1
B
2
B
3
A
1
1 2 3
A
2
3 1 1
A
3
1 3 1
Решение
:
1.
Так
как
=1
не
равно
=3,
то
игра
не
имеет
седловой
точки
.
2.
В
данной
игре
нет
дублирующих
и
доминируемых
стратегий
.
3.
Решаем
игру
путем
решения
пары
двойственных
задач
линейного
программирования
.
Математические
модели
пары
двойственных
задач
линейного
программирования
будут
выглядеть
следующим
образом
: