MMP_5
.pdfАффинное правило.
Пусть p и q – оптимальные смешанные стратегии игроков А и В в
игре с платежной матрицей H aij , m n и ценой . Тогда p и q будут оптимальными стратегиями и в игре с матрицей H1 aij c m n и ценой
1 c . |
|
|
|
|
|
|
|
|
|
26 |
41 |
|
|
|
|
|
|
|
|
|
Например, игру с матрицей |
H1 |
|
29 |
23 |
|
можно заменить игрой с |
|
|
|
32 |
20 |
|
|
|
|
|
|
|
||
|
|
2 |
7 |
|
|
|
|
|
|
|
|
|
|
матрицей |
H |
3 |
1 |
|
, т.к. элементы этих матриц связаны соотношениями |
|
|
|
4 |
0 |
|
|
|
|
|
|
|
|
||
bij 3 aij |
20 : |
|
26 3 2 20; |
41 3 7 20; 29 3 3 20; 23 3 1 20; |
||
32 3 4 20 ; |
20 3 0 20 . |
При этом оптимальные стратегии игр |
||||
совпадают, а цены игр связаны соотношением 1 3 20 .
В общем случае решение игр размера m n в смешанных стратегиях
сводят к решению двух возможно двойственных ЗЛП. |
|
|
|
|
|
||||
Редукция матричных игр к ЗЛП. |
|
|
|
|
|
|
|
||
Пусть игра m n задана платежной матрицей H aij , |
|
|
|
|
|
||||
i 1, m, j 1, n . |
|||||||||
Через p p , p , , p и |
q q |
, q , , q обозначим |
соответственно |
||||||
1 2 |
m |
1 |
2 |
n |
|
|
|
|
|
оптимальные стратегии игроков А и В. Пусть – цена игры. Не умаляя общности, полагаем 0. В противном случае с помощью аффинного правила добьемся того, что все aij 0 .
Оптимальная стратегия стратегия игрока А обеспечивает ему средний выигрыш, не меньший , при любой стратегии игрока В. Поэтому все средние выигрыши игрока А можно выписать в виде системы неравенств:
80
a11 p1 a21 p2 am1 pm |
|
|||||||||
|
a22 p2 |
am2 pm |
|
|
||||||
a12 p1 |
(72) |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... . |
|
|||||||||
a p a |
2n |
p |
2 |
a |
mn |
p |
m |
|
|
|
1n 1 |
|
|
|
|
|
|
||||
Введем новые переменные:
x |
p1 |
, |
x |
|
|
p2 |
, |
, |
x |
|
|
pm |
, |
(73) |
|
2 |
|
m |
|
||||||||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
||||
Тогда после деления каждого неравенства из (71) на систему неравенств
a11 x1 a21 x2 am1 xm 1 |
||||||||
|
|
|
|
am2 xm 1 |
||||
a12 x1 a22 x2 |
||||||||
|
|
|
|
|
|
|
|
|
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... . |
||||||||
a x a |
2n |
x |
2 |
a |
mn |
x |
m |
1 |
1n 1 |
|
|
|
|
||||
Из равенства
p1 p2 pm 1
нетрудно получить соотношение для xi , i 1, m : x1 x2 xm 1 .
получим новую
(73)
Игрок А стремится максимизировать свой гарантированный выигрыш
. Максимизация равносильна минимизации 1 . Следовательно, получили следующую задачу для нахождения оптимальной стратегии игрока А:
x1 x2 xm min |
(74) |
при условиях (73) и
|
|
|
xi 0, i 1, m |
(75) |
|
Сформулированная задача (74) – (76) является ЗЛП.
81
Повторим с естественными изменениями предыдущие рассуждения для определения оптимальной стратегии игрока В.
Игрок В стремиться минимизировать гарантированный проигрыш .
Все средние проигрыши игрока В запишем в виде системы неравенст:
|
|
|
|
a11q1 a12 q2 a1n qn |
|
|
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a2n qn |
|
|
|
|
|||||||||||
|
|
|
|
a21q1 a22 q2 |
|
|
, |
(76) |
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... . |
|
|
||||||||||||||||||||||||||
|
|
|
|
a |
q a |
m2 |
q |
2 |
a |
mn |
q |
n |
|
|
|
|||||||||||||||||
|
|
|
|
|
m1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
которые следуют из того, что средний проигрыш игрока В не |
||||||||||||||||||||||||||||||||
превосходит цены игры при любой стратегии игрока А. |
|
|||||||||||||||||||||||||||||||
В обозначениях |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
z |
q1 |
|
, |
z |
|
|
q2 |
, |
|
|
, |
z |
|
|
qn |
|
|
|
|
|||||||||||||
|
|
2 |
|
|
n |
|
|
|
|
|
||||||||||||||||||||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
система неравенств (76) примет вид |
|
|||||||||||||||||||||||||||||||
|
|
|
|
a11 z1 a12 z2 a1n xn 1 |
|
|
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|||
|
|
|
|
a21 z1 a22 z2 a2n zn |
|
|
(77) |
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... . |
|
|
||||||||||||||||||||||||||
|
|
|
|
a |
z a |
m2 |
z |
2 |
a |
mn |
z |
n |
|
1 |
|
|
||||||||||||||||
|
|
|
|
|
m1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||
Применение z j , |
|
|
j 1, n удовлетворяют соотношению |
|
||||||||||||||||||||||||||||
z |
z |
|
|
z |
|
|
1 |
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
2 |
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Минимизация |
|
1 |
|
равносильна максимизации . |
|
|||||||||||||||||||||||||||
|
|
|
|
|||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Получили следующую задачу для нахождения оптимальной стратегии игрока В:
f z1 z2 zn max |
(78) |
при условиях (77) и
82
|
|
|
|
z j 0, |
j 1, n |
(79) |
|
Задача (77) – (79) также является ЗЛП.
Таким образом, игра m n свелась к двум ЗЛП, которые запишем в
матричном виде
H T Z C |
|
|
|
|
|
|
HX B |
|
|
|
||||||||||
|
|
|
|
|
|
|
I |
|
|
|
|
|
|
|
|
|
II |
|||
Z 0 |
|
|
|
|
|
|
|
X 0 |
|
|
|
|
||||||||
|
|
|
T |
Z min |
|
|
|
|
|
f |
C |
T |
X max |
|||||||
B |
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
x |
|
|
|
z |
|
|
|
1 |
|
|
1 |
||||||||
|
|
|
1 |
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
X |
x2 |
|
, |
Z |
z2 |
|
, |
B |
1 |
, |
C |
1 |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xm m 1 |
|
|
zn |
n 1 |
|
|
1 m 1 |
|
|
1 n 1 |
|||||||||
Очевидно, задачи I и II являются двойственными ЗЛП.
83
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ
1.А.В. Соколов, В.В. Токарев. Методы оптимальных решений. Т.1.
Общие положения. Математическое программирование. Москва:
ФИЗМАТЛИТ, 2010.
2.А.В. Соколов, В.В. Токарев. Методы оптимальных решений. Т.2.
Многокритериальность. Динамика. Неопределенность. Москва:
ФИЗМАТЛИТ, 2010.
3.Конюховский П.В. Математические методы исследования операций в экономике. СПб.: Питер, 2000.
4.М. Интрилигатор. Математические методы оптимизации и экономическая теория. М.: Изд. Айрис-Пресс, 2002.
5.Ф.П. Васильев. Методы оптимизации. М. Факториал Пресс, 2005.
84
ОГЛАВЛЕНИЕ |
|
Введение …………………………………………………………………….. |
3 |
ЛЕКЦИЯ 1. Исследование операций. Экономико-математические |
|
модели. ………………………………………………………………………. |
4 |
ЛЕКЦИЯ 2. Балансовые модели. Модель Леонтьева многоотраслевой |
|
экономики. Продуктивные модели…………………………………………. |
8 |
ЛЕКЦИЯ 3,4,5. Задачи математического и линейного |
|
программирования. Модели линейного программирования……………... |
15 |
ЛЕКЦИЯ 6. Динамическое программирование. Принцип оптимальности |
|
и функциональности. Функциональное уравнение Беллмана……………. |
40 |
ЛЕКЦИЯ 7. Модели потребительского выбора. Функция полезности. |
|
Линии безразличия. Оптимизация функции полезности. Функции |
|
спроса и предложения………………………………………………………. |
49 |
ЛЕКЦИЯ 8. Элементы теории игр в задачах оптимального управления |
|
экономическими процессами………………………………………………. |
58 |
ЛЕКЦИЯ 9. Методы решения матричных игр в смешанных стратегиях... |
73 |
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ …………………………… |
84 |
85
Учебное издание
Г. Н. Камышова, Н. Н. Терехова
МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ
Краткий курс лекций
Издается в авторской редакции
Корректура авторов
86