Материал: Теория_игр_УП_ЭК_ЭлРесурс
41
Прямая
(
исходная
)
задача
:
Найти
неотрицательные
переменные
х
1
,
х
2
,
х
3
,
минимизирующие
функцию
min
L
(
x
)=
х
1
+
х
2
+
х
3
,
при
ограничениях
:
х
1
+3
х
2
+
х
3
1;
2
х
1
+
х
2
+3
х
3
1;
3
х
1
+
х
2
+
х
3
1;
x
i
0,
3
,
1
i
.
Двойственная
задача
:
Найти
неотрицательные
переменные
у
1
,
у
2
,
у
3
,
максимизирующие
функцию
max
L
(
x
)=y
1
+y
2
+y
3
,
при
ограничениях
:
y
1
+2y
2
+3y
3
1;
3y
1
+y
2
+y
3
1;
y
1
+3y
2
+y
3
1;
y
j
0,
3
,
1
j
.
Данные
задачи
решаются
,
например
,
симплекс
–
методом
.
Поскольку
в
двойственной
задаче
ограничения
имеют
вид
“
“,
то
эту
задачу
решать
проще
(
не
нужно
вводить
искусственные
переменные
).
Оптимальное
решение
исходной
задачи
можно
будет
непосредственно
получить
из
данных
симплекс
–
таблицы
для
оптимального
решения
двойственной
задачи
.
Начальная
симплекс
–
таблица
двойственной
задачи
имеет
вид
БП
у
1
у
2
у
3
у
4
у
5
у
6
Решен
ие
у
4
1 2 3 1 0 0 1
у
5
3 1 1 0 1 0 1
у
6
1 3 1 0 0 1 1
L
-1 -1 -1 0 0 0
0
ведущий
столбец
Последующие
симплекс
-
таблицы
приведены
ниже
:
БП
у
1
у
2
у
3
у
4
у
5
у
6
Решение
у
4
0
3
2
1
3
2
2
1
3
1
0
3
2
у
1
1
3
1
3
1
0
3
1
0
3
1
у
6
0
3
2
2
3
2
0
3
1
1
3
2
L
0
3
2
3
2
0
3
1
0
3
1
ведущий
столбец
БП
у
1
у
2
у
3
у
4
у
5
у
6
Решение
у
4
0 0
4
9
1
8
1
8
5
4
1
у
1
1 0
4
1
0
8
3
8
1
4
1
у
2
0 1
4
1
0
8
1
8
3
4
1
L
0 0
2
1
0
4
1
4
1
2
1
ведущий
столбец
И
,
наконец
,
получаем
симплекс
-
таблицу
,
которая
соответствует
оптимальному
решению
двойственной
задачи
:
ведущая
строка
ведущая
строка
ведущая
строка
42
БП
у
1
у
2
у
3
у
4
у
5
у
6
Решение
у
3
0 0 1
9
4
18
1
18
5
9
1
у
1
1 0 0
9
1
18
7
18
1
9
2
у
2
0 1 0
9
1
9
1
9
4
9
2
L
0 0 0
9
2
9
2
9
1
9
5
Оптимальное
решение
двойственной
задачи
линейного
программирования
следующее
:
у
1
=
2
9
;
у
2
=
2
9
;
у
3
=
1
9
; max L (y)=
9
5
.
Находим
оптимальную
смешанную
стратегию
игрока
В
в
соответствии
с
формулами
(2.37)
и
(2.38):
5
9
1
1
9
1
9
2
5
2
3
1
j
j
y
v
;
5
1
5
9
9
1
;
5
2
5
9
9
2
;
5
2
5
9
9
2
3
3
2
2
1
1
v
y
q
v
y
q
v
y
q
.
Следовательно
,
5
1
;
5
2
;
5
2
B
S
.
Оптимальное
решение
исходной
задачи
находим
,
используя
двойственные
оценки
,
из
симплекс
-
таблицы
для
оптимального
решения
двойственной
задачи
:
коэффициент
при
начальной
базисной
переменной
в
оптимальном
уравнении
прямой
задачи
равен
разности
между
правой
и
левой
частями
ограничения
двойственной
задачи
,
ассоциированного
с
данной
начальной
переменной
.
Получаем
x
1
=
9
2
; x
2
=
9
2
; x
3
=
9
1
; max L (x)=
9
5
.
Отсюда
определим
вероятности
применения
своих
стратегий
игроком
А
:
5
1
5
9
9
1
;
5
2
5
9
9
2
;
5
2
5
9
9
2
3
3
2
2
1
1
v
x
p
v
x
p
v
x
p
.
Следовательно
:
5
1
;
5
2
;
5
2
A
S
.
Таким
образом
,
решение
игры
mxn
сводится
к
решению
задачи
линейного
программирования
.
Нужно
заметить
,
что
и
наоборот
–
для
любой
задачи
линейного
программирования
может
быть
построена
эквивалентная
ей
задача
теории
матричных
игр
.
Эта
связь
задач
теории
матричных
игр
с
задачами
линейного
программирования
оказывается
полезной
не
только
для
теории
игр
,
но
и
для
линейного
программирования
.
Дело
в
том
,
что
существуют
приближенные
численные
методы
решения
матричных
игр
,
которые
при
большой
размерности
задачи
могут
оказаться
проще
,
чем
симплекс
–
метод
.
43
ТЕСТЫ
(
В
–
Верно
,
Н
–
Неверно
)
1.
Если
все
элементы
платежной
матрицы
в
матричной
игре
положительны
,
то
и
цена
игры
положительна
.
2.
Любую
матричную
игру
можно
свести
к
паре
двойственных
задач
линейного
программирования
.
3.
В
прямой
задаче
линейного
программирования
,
к
которой
сводится
матричная
игра
,
целевая
функция
подлежит
максимизации
.
4.
В
обратной
задаче
линейного
программирования
,
к
которой
сводится
матричная
игра
,
ограничения
получаются
со
знаком
«
».
5.
Цена
матричной
игры
,
получаемая
из
решения
прямой
и
обратной
задач
может
быть
различна
.
(
Ответы
:
1 -
В
; 2 -
В
; 3 -
Н
; 4 -
В
, 5 -
Н
).
ЗАДАЧИ
Решить
следующие
матричные
игры
:
1. 2 4 6 2. -7 4 2 3. -5 6 4
6 2 2 0 2 1 2 4 3
2 6 2 6 -5
-1
8 -3 1
4. 1 3 2 5. 2 1 0 6. 4 6 1
3 1 3 1 2 1 4 4 1
2 3 1 0 1 2 1 1 6
7. -4 -6 -1 8. -2 -5 2 9. 5 7 1
-4
-4
-1
-1
1
-5 5 5 1
-1
-1
-6
-2
-1
-2 2 2 6
1
0.
2 6 4 1
1.
3 6 9 1
2.
0 1 2
6
2
6
9
3
3
2
0
0
4
6
2
3
9
3
0
2
1
2.9.
Приближенный
метод
решения
матричных
игр
mxn
Рассмотрим
приближенный
метод
решения
матричных
игр
–
метод
Брауна
-
Робинсон
(
метод
итераций
).
Идея
его
заключается
в
следующем
.
Разыгрывается
эксперимент
,
в
котором
игроки
А
и
В
поочередно
применяют
друг
против
друга
свои
чистые
стратегии
.
Каждый
из
игроков
стремится
увеличить
свой
выигрыш
,
предполагая
,
что
будущее
будет
походить
на
прошлое
;
при
этом
считается
,
что
ни
один
из
них
не
знает
своей
оптимальной
стратегии
.
Такой
принцип
приводит
к
некоторой
последовательности
партий
игры
,
для
каждой
из
которых
можно
подсчитать
приближенные
оптимальные
стратегии
каждого
из
игроков
,
а
также
верхнюю
и
нижнюю
цены
игры
.
44
Вместо
того
,
чтобы
вычислять
каждый
раз
средний
выигрыш
,
можно
пользоваться
суммарным
за
все
предыдущие
ходы
выигрышем
и
выбирать
ту
свою
стратегию
,
при
которой
этот
накопленный
выигрыш
максимален
.
Доказано
,
что
такой
метод
сходится
:
при
увеличении
числа
партий
средний
выигрыш
на
одну
партию
будет
стремиться
к
цене
игры
,
а
частоты
применения
стратегий
–
к
их
вероятностям
в
оптимальных
смешанных
стратегиях
игроков
.
Объясним
этот
метод
на
примере
игры
3x3
,
платежная
матрица
которой
приведена
ниже
.
Игра
начинается
с
произвольно
выбранной
стратегии
игрока
А
, –
например
стратегии
А
1
(
выбранные
стратегии
обозначаются
звездочкой
).
Платежные
элементы
этой
строки
переписываются
под
платежной
матрицей
.
Игрок
В
,
предполагая
,
что
будущее
будет
походить
на
прошлое
,
выберет
стратегию
В
1
,
при
которой
его
проигрыш
минимален
.
Соответствующий
этой
стратегии
проигрыш
обозначен
звездочкой
.
Платежные
элементы
стратегии
В
1
переписываются
справа
от
платежной
матрицы
.
Игрок
А
,
также
предполагая
,
что
будущее
будет
походить
на
прошлое
,
выбирает
стратегию
А
2
(
наибольшее
число
обозначено
звездочкой
).
Платежные
элементы
,
соответствующие
стратегии
А
2
,
прибавляются
поочередно
к
элементам
предыдущей
строки
,
записанной
под
матрицей
.
Далее
выбирается
наименьший
элемент
суммарной
строки
.
Ему
соответствует
стратегия
В
2
.
Тогда
к
столбцу
,
записанному
справа
от
платежной
матрицы
,
поочередно
прибавляются
платежные
элементы
стратегии
В
2
.
Этот
процесс
продолжается
до
тех
пор
,
пока
разрыв
между
нижней
и
верхней
оценками
игры
станет
небольшим
.
Если
при
выборе
стратегий
на
некотором
шаге
есть
несколько
альтернатив
,
то
выбирается
любая
из
равноценных
стратегий
.
В
рассматриваемом
примере
сделано
20
шагов
.
За
эти
двадцать
шагов
игрок
А
применил
свою
первую
стратегию
(
количество
звездочек
в
суммарных
выигрышах
,
соответствующей
первой
стратегии
) 7
раз
;
вторую
– 8
раз
;
третью
– 5
раз
.
Игрок
В
применил
стратегию
В
1
восемь
раз
;
вторую
– 8
раз
;
третью
– 4
раза
.
Следовательно
,
приближенные
оценки
оптимальных
стратегий
,
полученные
за
20
итераций
,
равны
:
20
4
;
20
8
;
20
8
;
20
5
;
20
8
;
20
7
B
A
S
S
.
Эти
оценки
не
так
уж
сильно
отличаются
от
точного
решения
данной
матричной
игры
,
которое
равно
2
.
0
;
4
.
0
;
4
.
0
;
2
.
0
;
4
.
0
;
4
.
0
B
A
S
S
.
B
i
A
i
B
1
B
2
B
3
1 2 3 4 5 6 7 8 9 10
A
1
1 2 3 * 1 3 5 8* 9* 10 12 14
17* 20*
A
2
3 1 1 3* 4* 5 6 9 12* 13*
14 15 16
A
3
1 3 1 1 4 7* 8 9 10 13 16* 17 18
11 12 13 14 15 16 17 18 19 20
1 1* 2 3 21* 22 24* 25 27 29 31 32 33 36*
2 4 3* 4 19 22* 23 26* 27* 28 29 32 35* 36
3 7 4* 5 19 20 23 24 27 30* 33* 34* 35 36
45
4 8 7 6*
5
9* 9 9
6 10* 11 12
7 13 12* 13
8 16 13* 14
9 17 16 15*
10 18 13 18*
11 19* 20 21
12 20* 22 24
13 23 23* 25
14 24* 25 28
15 27 26* 29
16 30 27* 30
17 31 30* 31
18 32* 33 32
19 33* 36 33
20 36 37 34*
Приближенную
цену
игры
определяют
как
среднеарифметическое
между
нижней
оценкой
игры
,
равной
минимально
накопленному
выигрышу
min
игрока
А
,
деленному
на
число
шагов
k,
и
верхней
оценкой
игры
,
равной
максимальному
суммарному
проигрышу
max
игрока
В
,
деленному
на
k:
k
2
2
max
min
.
В
рассматриваемом
примере
82
.
1
40
73
20
2
37
36
.
Точная
цена
игры
v
= 1,8.
Разрыв
между
и
отражает
неточность
оценок
относительно
оптимальных
смешанных
стратегий
.
В
примере
05
.
0
20
36
20
37
составляет
2,8%
от
цены
игры
v
=1,8.
Увеличивая
число
итераций
k,
можно
найти
еще
более
точные
оценки
оптимальных
смешанных
стратегий
.
Преимуществом
итерационного
метода
решения
матричных
игр
является
то
,
что
объем
вычислений
с
увеличением
размерности
игры
mxn
растет
существенно
медленнее
,
чем
в
методах
линейного
программирования
(
в
частности
,
в
симплекс
–
методе
).
2.10.
Качественная
оценка
элементов
платежной
матрицы
Очевидной
трудностью
при
использовании
теории
игр
является
задание
элементов
платежной
матрицы
с
требуемой
точностью
.
Вместе
с
тем
эту
задачу
не
нужно
и
переоценивать
.
Использование
,