5 SKFM9S83
.pdfчисло неизвестных k>r, т.е. система (5.7) имеет нетривиальное решение
(α 1 p10 ,...,α k pk 0 ). Так как множество решений однородной системы является под-
пространством, то (− α 1 p10 ,...,− α k pk 0 ) также есть решение системы (5.7) и
α = max |
|
α |
i |
|
> 0 можно сделать сколь угодно малым. |
|
|
||||
1≤ i≤ k |
|
|
|
|
|
|
|
|
|
Возьмем такое α |
, что |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
α |
< 1,α |
= |
max ∑n |
|
aij |
pi 0 |
|
≤ ε . |
||||||
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
r |
+ 1≤ j≤ m |
|
|
|
|
|
|
2 |
|||
|
|
|
|
|
|
|
|
|
i= 1 |
|
|
|
|
|
|
|
|
Тогда (1 + α i ) pi |
0 |
≥ 0, i = |
1,2,..., k и в силу (5.6) справедливо неравенство |
||||||||||||||
|
|
∑k |
aij (1 ± α i ) pi 0 ≥ ν + ε , j > r. |
||||||||||||||
|
|
i= 1 |
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
В то же время из (5.4) и (5.7) вытекают равенства |
|||||||||||||||||
∑n |
aij (1 ± α i )pi 0 = ν , j = |
|
n |
||||||||||||||
1, r, ∑ (1 ± α i )pi 0 = 1. |
|||||||||||||||||
i= 1 |
|
|
|
|
|
|
|
|
|
|
i= 1 |
|
|
|
|
||
Значит, по теореме о необходимых и достаточных условиях оптимальности |
|||||||||||||||||
стратегии векторы |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
p1 |
= |
((1 + |
α |
1) p1 |
0 ,...,(1 + |
α |
k) |
pk |
0 ,0,...,0), |
||||||
|
|
p 2 |
= |
((1 + |
α |
1) p1 |
0 ,...,(1 − |
α |
k) |
pk |
0 ,0,...,0) |
||||||
являются оптимальными для игрока 1. Но p 0 = |
|
|
(1 |
|
)(p1 + p 2 ), т.е. пришли к про- |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
тиворечию, так как р0 - крайняя оптимальная стратегия. |
Аналогично, если предположить, что k< r, то придем к противоречию
для q0. Итак, k =r.
Покажем теперь, что если ν ≠ 0 , то
|
|
a11 |
... |
|
a1r |
|
|
|
|
... |
... |
... |
≠ |
0. |
|
|
|
ar1 |
... |
|
arr |
|
|
Доказательство снова от противного. Предположим, что |
|||||||
|
a11 ... |
a1r |
|
= 0. |
|
|
|
|
|
|
|
||||
|
... ... |
... |
|
|
(5.10) |
||
|
ar1 ... |
arr |
|
|
|
|
Так какν ≠ 0 , то из (5.9) следует, что последняя строка матрицы (5.8) яв-
ляется линейной комбинацией остальных строк. Если справедливо (5.10), то чис-
ло независимых строк матрицы (5.8),где k = r, не больше r-1. Тогда в системе
(5.7) при k = r число неизвестных r больше числа независимых уравнений и, сле-
довательно, существует нетривиальное решение. Далее приходим к про-
тиворечию совершенно так же, как при предположении k > r. Если учесть, что системы (5.4), (5.5) получены после соответствующей перестановки строк и столбцов матрицы aij , то все утверждения теоремы доказаны.
По теореме Шепли-Сноу полное решение матричной игры сводится к пере-
бору всех квадратных подматриц матрицы игры и решению соответствующих систем линейных уравнений (5.1),(5.2). Если v≠0 , то эти системы, очевидно, либо имеют единственное решение, либо не имеют решения. Полученное решение на-
до проверить на неотрицательность и на выполнение условий оптимальности
(3.18), (3.19) для вычеркнутых строк и столбцов. Если условия выполнены, то ре-
шения системы, дополненные нулями на местах, соответствующих вычеркнутым строкам и столбцам, являются оптимальными стратегиями (но необязательно крайними, так как условия теоремы необходимые, но не достаточные). Полный перебор приведет к нахождению всех крайних оптимальных стратегий. Так как трудоемкость решения по методу Шепли-Сноу растет с увеличением размерности матрицы игры, то имеет смысл предварительно вычеркнуть в соответствии с принципом доминирования лишние строки и столбцы (если ищется полное реше-
ние, то при строгом доминировании), которые входят в оптимальные стратегии с нулевой вероятностью; цена игры при этом, очевидно, не меняется. Так как при решении системы линейных уравнений (5.1), (5.2) удобнее оперировать с невы-
рожденной подматрицей ais jt , то исходную игру следует свести к игре с заведо-
мо не равной нулю ценой. Проще всего это сделать следующим образом: приба-
вить к каждому элементу матрицы aij одну ту же достаточно большую кон-
станту так,
ная матрица была положительной; тогда в новой игре цена, очевидно, больше ну-
ля, причем она отличается от цены исходной игры на величину этой константы, а
множества оптимальных стратегий игроков в обеих играх совпадают.
Метод Брауна
При достаточно большой размерности матрицы игры метод Шепли-Сноу приводит к решению больших систем линейных уравнений, что представляет со-
бой весьма трудоемкий и не просто реализуемый вычислительный процесс. Ме-
тод Брауна является более простым и удобным для численной реализации. Идея метода Брауна, с помощью которого можно получить лишь приближенное част-
ное решение игры (т.е. по одной оптимальной стратегии игроков), состоит в сле-
дующем.
Рассмотрим фиктивный процесс обучения игроков в многократно повто-
ряющейся матричной игре со следующими простыми правилами.
На первом шаге игроки выбирают произвольные чистые стратегии i1 и j1, ничего не зная о выборе противника.
На втором шаге игроки узнают предыдущий выбор противника и считают,
что он и на втором шаге будет придерживаться той же стратегии. Тогда игрок 1 в
соответствии со своим критерием выберет такую чистую стратегию i2,
что
ai2 j1 = max≤ ≤ aij1 , 1 i n
а игрок 2 выберет такую чистую стратегию j2, что
ai1 j2 = 1min≤ ≤ ai1 j . j m
На третьем шаге игрок 1 считает, что игрок 2 может использовать чистые стратегии j1 и j2 с равной вероятностью, и выбирает чистую стратегию i3, которая максимизирует математическое ожидание выигрыша
1 |
(ai j |
+ ai j |
) = |
max |
1 |
(aij |
+ aij ). |
|
2 |
|
|||||||
3 |
1 |
3 |
2 |
1≤ i≤ n 2 |
1 |
2 |
||
|
|
|
Аналогично, игрок 2 считает, что игрок 1 может использовать чистые страте-
гии i1 и i2 с равной вероятностью, и выбирает чистую стратегию j3, которая мини-
мизирует математическое ожидание проигрыша: |
|
||||||||
|
1 |
(ai j |
|
+ ai |
j ) = |
min |
1 |
(ai j + |
ai j ). |
2 |
|
|
|||||||
1 |
3 |
2 |
3 |
1≤ j≤ m 2 |
1 |
2 |
|||
|
|
|
|
На последующих шагах каждый игрок ориентируется на накопленную про-
тивником смешанную стратегию и выбирает свою чистую стратегию из условия максимума или минимума соответствующего математического ожидания. Обо-
значим через pi (k) и q j |
(k) частоты появления i -й и j –й чистых |
|||
стратегий игроков в k |
повторениях; |
pi (k) = |
ri k , |
где ri - число появлений i-й |
стратегии игрока 1 (i = |
1,..., n) , q j (k) = |
l j k, |
где l j |
- число появлений j -й страте- |
гии игрока 2 ( j = 1,..., m) . Тогда на k+1шаге игрок 1 считает, что игрок 2 будет ис-
пользовать смешанную стратегию q(k) = (q1( k) ,..., qm( k) ) и выбирает чистую стра-
тегию ik+1 такую, что |
|
|
|
|
|
|
|
|
|
|
|
|
h(ik + 1 , q(k)) |
= max h(i, q( k) ). |
|
|
|
|
|||||||
|
|
|
|
|
|
1≤ i≤ n |
|
|
|
|
|
|
Аналогично, игрок 2 считает, что первый будет использовать смешанную |
||||||||||||
стратегию p(k) = ( p1( k) ,..., pn( |
k) ) и выбирает чистую стратегию jk+1 такую, что |
|||||||||||
h( p(k), jk + 1) |
= min h( p( k) , j). |
|
|
|
|
|||||||
|
|
|
|
|
1≤ j≤ m |
|
|
|
|
|
|
|
Далее пересчитывают частоты по формулам |
|
|
|
|
|
|
||||||
|
|
kpi |
(k) + 1 |
kp |
(k) |
|
|
|||||
pik + 1 (k + 1) = |
|
k + 1 |
|
|
|
, pi (k + 1) = |
|
i |
|
|
, i ≠ ik + 1 , |
|
|
k + 1 |
|
|
|
k + |
|
1 |
|||||
|
|
kq jk + 1 (k) + 1 |
|
kq j |
(k) |
|||||||
q jk + 1 (k + 1) = |
|
|
|
|
, q j (k + 1) = |
|
|
|
, j ≠ jk + 1 |
|||
|
k + 1 |
|
|
k + 1 |
|
|||||||
и переходят к следующей (k+2)-й итерации. |
|
|
|
|
|
|
||||||
Обозначим |
|
|
|
|
|
|
|
|
|
|
|
|
ν |
1 (k) = |
max h(i, q( k) ); |
|
|
|
|
(5.11) |
|||||
|
|
|
1≤ i≤ n |
|
|
|
|
|
|
|
|
|
ν |
|
2 (k) |
= min h( p( k) , j). |
|
|
|
|
(5.12) |
||||
|
|
|
1≤ j≤ |
m |
|
|
|
|
|
|
Тогда из (3.21) следует, что |
|
|
ν 1 (k) |
≥ ν ≥ ν 2( k) k , |
|
где ν - цена игры, причем если ν |
1 (k) = ν 2( k) , то это общее значение есть цена иг- |
|
ры, a p(k) и q(k) - оптимальные смешанные стратегии игроков. |
|
|
Основное утверждение, на котором базируется метод Брауна, заключается в |
||
сходимости сформулированного итеративного процесса: |
|
|
limν |
1 (k) = limν 2( k) = ν . |
(5.13) |
k → ∞ |
k → ∞ |
|
Доказательство этого утверждения достаточно сложное и мы его не при-
водим. Сходимость в (5.13), вообще говоря, не монотонная, поэтому практически вычисления по методу Брауна производят следующим образом. Задают точность решения ε > 0 и прекращают процесс после k шагов, если
0 ≤ ∆ (k) = minν 1( s) |
− maxν 2( s) |
≤ ε . |
||
1≤ s≤ k |
1≤ s≤ k |
|
||
При этом в качестве приближенного значения цены игры принимают ве- |
||||
личину |
|
|
||
|
1 |
[minν |
1 (s) + maxν |
2( s) ,] |
|
|
|||
|
2 1≤ s≤ k |
1≤ s≤ k |
|
а ε - оптимальными стратегиями игроков являются p(s1) , где s1 определяется из
условия
ν |
2 (s1) |
= |
maxν |
2( s) |
|
|
|
1≤ s≤ k |
|
и q(s2 ), где s2 определяется из условия |
|
|
|
|
ν |
1 (s2 ) |
= |
minν |
1( s) , |
|
|
|
1≤ s≤ k |
|
что вытекает из (5.11),(5.12) и (3.21).
Скорость сходимости итеративного процесса по методу Брауна уменьшается с увеличением размерности матрицы игры; ее порядок
∆ (k) = ck − 1(n+ m− 2) .
Если после конечного числа шагов выполняется равенство ∆ (k) = 0 , то решение игры найдено точно.
Связь матричных игр с линейным программированием
Существует тесная связь между матричными играми и линейным про-
граммированием. Решение любой матричной игры можно свести к решению пары двойственных задач линейного программирования специального вида (соответст-
вующий результат будет сформулирован для игр с положительными матрицами,
но любую матричную игру, как уже было сказано, можно свести к игре с положи-
тельной матрицей прибавлением достаточно большой константы к каждому эле-
менту матрицы). С другой стороны, любую задачу линейного программирования,
имеющую решение, можно свести к матричной игре специального вида.
Определение 5.1. Матричная игра называется симметричной, если ее пла-
тежная матрица aij кососимметрическая, т.е aij = − a ji i, j.
Так как кососимметрическая матрица квадратная, то размерности векторов в смешанных стратегиях обоих игроков одинаковы (m=n), а множества всех сме-
шанных стратегий совпадают. Свойство симметричных игр сформулированы в следующей лемме.
Лемма 5.1. Цена симметричной матричной игры равна нулю, а множества оптимальных стратегий игроков совпадают.
Доказательство. Справедлива цепочка равенств
ν |
= |
max min h(p, j) = |
max min |
∑n |
aij pi = |
− min max ∑n |
aij pi = |
− min max ∑n |
aij q j = |
|
|
|
p Sn 1≤ j≤ n |
p sk 1≤ j≤ n |
i= 1 |
|
p sn 1≤ j≤ n |
|
q sn |
1≤ i≤ n |
|
|
|
min max h(i, q) = |
|
|
i= 1 |
|
|
j = 1 |
|
|
= |
− |
− ν , следовательно,ν |
= 0 |
|
|
|
|
q sk 1≤ i≤ n
(при доказательстве равенств производится перемена обозначений р на q и i
на j).
Пусть p 0 - оптимальная стратегия игрока 1. Тогда
h(p 0 , j) = ∑n |
aij pi 0 ≥ 0, j = |
|
; |
|
|
|
|
1, n |
|
|
|
||||
i= 1 |
|
|
|
|
|
|
|
h(i, p 0 ) = ∑n |
aij p j 0 = − ∑n |
a ji p j 0 = − ∑n |
aij pi 0 ≤ 0, j = |
|
. |
||
1, n |
|||||||
j = 1 |
j = 1 |
|
|
i= 1 |
|
|
|
Следовательно, p0 – оптимальная стратегия игрока 2. Аналогично, любая оп-
тимальная стратегия игрока 2 является оптимальной стратегией игрока 1.
Теорема 5.2. Решение матричной игры с матрицей
|
a11 |
... |
a1m |
, aij > 0 i, j |
A = |
... |
... |
... |
|
|
an1 |
... |
anm |
|
эквивалентно решению пары двойственных задач ЛП:
|
|
|
∑n |
xi |
→ |
||
|
|
|
i= 1 |
|
|
||
|
|
|
∑m |
y j |
→ |
||
|
|
|
j = 1 |
|
|
||
Точнее, если x0 = |
(x1 |
0 |
,..., xn |
||||
задачи (5.15), тоν |
= |
|
|
1 |
|
= |
|
|
|
|
|
|
|||
|
∑n |
|
xi |
0 |
i= 1
|
min, xi ≥ |
0, i = |
|
|
, ∑n |
aij xi ≥ |
1, j = |
|
|
; |
|
|
|||||
1, n |
1, m |
(5.14) |
|||||||||||||||
|
|
|
|
|
|
|
i= 1 |
|
|
|
|
|
|
|
|
|
|
|
max, y j ≥ |
0, j = |
|
, ∑m |
|
≤ |
1, i = |
|
. |
|
|||||||
1, m |
aij y j |
1, n |
(5.15) |
||||||||||||||
|
|
|
|
|
|
|
|
|
j = 1 |
|
|
|
|
|
|
|
|
0 ) - решение задачи (5.14), |
y 0 |
= (y1 |
0 ,..., ym |
0 ) -решение |
|||||||||||||
1 |
|
- цена игры с матрицей А. |
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|||||||||||
|
∑m y j |
0 |
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
j = 1
р0 = vx0 - оптимальная стратегия игрока 1, q0 = vy0- оптимальная стратегия игрока 2.
|
Обратно, если р0 и q0 - оптимальные стратегии игроков, v - цена игры, то |
||||
|
p 0 |
- решение задачи (5.14), а у° = |
q 0 |
||
х° = |
|
ν |
- решение задачи (5.15). |
||
ν |
|||||
|
|
|
|
Доказательство. Задачи (5.14) и (5.15) имеют хотя бы по одному допус-
тимому вектору (для (5.15) нулевой вектор, а для (5.14) вследствие положи-
тельности матрицы А вектор с достаточно большими компонентами), значит, они обе имеют решения.
Пусть х° - решение (5.14), у°- решение (5.15), тогда по теореме двойственности
|
|
|
|
|
|
|
|
|
∑n |
xi 0 = ∑m |
|
y j 0 > 0 |
|
|||||
|
|
|
|
|
|
|
|
|
i= 1 |
|
j = 1 |
|
||||||
(положительность этих сумм следует из того, что х° ≠ 0 ). |
|
|||||||||||||||||
Положим |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ν |
= |
|
|
1 |
|
|
|
= |
|
1 |
|
|
, p 0 = ν x0 , q 0 = |
ν y 0 , |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
∑n |
xi |
0 |
|
|
|
∑m y j |
0 |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
i= 1 |
|
|
|
|
|
j = 1 |
|
|
|
|
|
|
|||
тогда |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
pi 0 ≥ 0, i = |
|
, ∑n |
pi 0 = 1, |
|
q j 0 ≥ 0, j = |
|
, ∑m |
q j 0 = 1; |
||||||||||
1, n |
|
1, m |
||||||||||||||||
|
|
|
|
|
|
|
i= 1 |
|
|
|
|
|
|
j= 1 |
|
|||
∑n |
aij pi 0 ≥ ν ≥ ∑m |
aij q j 0 i, j |
|
|
|
|
|
|
||||||||||
i= 1 |
|
|
|
|
|
j = 1 |
|
|
|
|
|
|
|
|
|
|
Значит, по следствию из теоремы 3.4 получаем, что v - цена игры, р0 и q° - оп-
тимальные стратегии игроков.
Пусть теперь ν - цена игры с матрицей А, р0 и q0- оптимальные стратегии игро-
ков. Так как матрица А положительная, то ν |
>0. Положим х° = |
p 0 |
, |
||||||||||||||||
ν |
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
y 0 = |
q 0 |
,тогда xi |
0 ≥ 0, i = |
|
|
|
0 ≥ |
0, j = |
|
|
, и из (3.18), (3.19) |
следуют неравенст- |
|||||||
1, n, q j |
1, m |
||||||||||||||||||
ν |
|||||||||||||||||||
ва |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
∑n |
|
aij xi 0 ≥ 1, j = |
|
, ∑m |
aij y j 0 ≤ 1, i = |
|
|
|
|
|
||||||
|
|
|
|
1, m |
1, n, |
|
|
|
|||||||||||
|
|
|
i= 1 |
|
|
|
|
j = 1 |
|
|
|
т.е. x0 - допустимый вектор задачи(5.14); у0- допустимый вектор задачи(5.15). При этом
∑n |
xi 0 = ∑m |
y j 0 = 1, |
i= 1 |
j = 1 |
|
следовательно, х0 - решение (5.14), у0 - решение (5.15). Теорема доказана.
Теорема 5.3. Решение пары двойственных задач линейного программи-
рования
∑n |
|
→ |
max, x j ≥ |
0, j = |
|
|
, ∑n |
|
≤ bi , i = |
|
|
|
|
|
|
|
c j x j |
1, n |
aij x j |
|
1, m; |
(5.16) |
|||||||||||
j = 1 |
|
|
|
|
|
|
|
j= 1 |
|
|
|
|
|
|
|
|
∑m |
|
→ |
min, yi ≥ |
0, i = |
|
, ∑m |
aij yi ≥ |
c j , j = |
|
|
|
|
||||
bi yi |
1, m |
1, n |
(5.17) |
|||||||||||||
i= 1 |
|
|
|
|
|
|
|
i= 1 |
|
|
|
|
|
|
|
|
эквивалентно решению симметричной матричной игры с матрицей
|
|
|
|
0 |
... |
0 |
− |
a11 ... |
− |
am1 |
|
c1 |
|
|
|
|
|||||||||||
|
|
|
|
... ... ... |
|
... ... |
|
... |
|
... |
|||
|
|
|
|
0 |
... |
0 |
− |
a1n ... |
− |
amn |
|
cn |
|
D = |
|
|
|
a11 |
... |
a1n |
|
0 |
... |
|
0 |
− |
b1 |
|
|
|
|
... ... ... |
|
... ... |
|
... |
|
... |
|||
|
|
|
|
am1 |
... |
amn |
|
0 |
... |
|
0 |
− |
bm |
|
|
|
|
− c1 |
... |
− cn |
|
b1 |
... |
|
bm |
|
0 |
Точнее, если z 0 = (µ1 |
0 ,..., µn |
0 ,ν 1 |
0 ,...,ν n |
0 , λ0 ) - оптимальная стратегия любого |
||||||||
|
|
0 |
|
|
|
0 |
|
µ 0 |
|
µ 0 |
|
|
|
|
|
|
x |
= |
|
1 |
,..., |
n |
|
||
игрока в игре с матрицей D и λ >0 , то |
|
|
λ0 |
λ0 |
- решение задачи |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
,...,ν |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
(5.16), y 0 = |
ν |
1 |
|
m |
|
-решение задачи (5.17). Обратно, если х0 = (x1 |
0 ,..., xn |
0 )- |
||||||||||
|
|
0 |
|
0 |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
λ |
|
|
λ |
|
|
|
|
|
|
|
|
|
|
|
|
решение задачи (5.16), у0 |
= (y1 |
0 ,..., yn |
0 ) - решение задачи (5.17), то |
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
z 0 = |
(λ0 x1 |
0 ,..., λ0 xn |
0 , λ0 y1 |
0 ,.., λ0 ym |
0 , λ0 ), |
|
|
||
где λ0 = |
|
|
|
|
1 |
|
|
|
является оптимальной стратегией любого игрока в |
|||||||||
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
x j 0 +∑ m |
|
|
||||||||||||
1 + ∑n |
yi 0 |
|
|
|
|
|
|
|
|
|||||||||
|
|
|
j = 1 |
|
|
i= 1 |
|
|
|
|
|
|
|
|
|
|
|
игрес матрицей D. Пара двойственных задач (5.16) ,(5.17) имеет решение тогда и только тогда, когда существует такая оптимальная стратегия в игре с матрицей D
z 0 |
= |
(µ |
|
0 ,.., µ |
0 ,ν |
1 |
0 ,...,ν |
n |
0 , λ0 ), |
|
|
1 |
n |
|
|
|
|||
для которой λ0 >0. |
|
(µ1 |
|
|
|
|
|
|
0 , λ0 ) - оптимальная стратегия, |
Доказательство. Пусть z0 |
= |
0 ,..., µn |
0 ,ν 1 |
0 ,...,ν m |
λ0 > 0. Так как игра симметричная, то цена игры с матрицей D равна нулю. По-
этому необходимые условия оптимальности (3.18) применительно к матрице D
дают следующие соотношения:
∑m |
aijν i |
0 − c j λ0 ≥ 0, j = |
|
; |
|
1, n |
(5.18) |
||||
i= 1 |
|
|
|
|
|
∑n |
aij µj |
0 |
+ |
bi λ0 ≥ 0, i = |
|
; |
|
|||
1, m |
(5.19) |
|||||||||
j = 1 |
|
|
|
|
|
|
|
|
|
|
∑n |
c j µj |
0 |
− |
∑m |
bi yi |
0 = 0 |
|
|
(5.20) |
|
j = 1 |
|
|
|
i= 1 |
|
|
|
|
|
(в (5.20) имеет место равенство по теореме о свойствах оптимальных стратегий,
так как λ0 >0). Положим
|
|
|
0 |
|
|
µj 0 |
|
|
|
|
|
|
|
|
|
0 |
|
ν |
i 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
= |
, j = |
|
1, n, yi |
= |
, i = 1, m. |
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||
|
|
|
x j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
λ0 |
|
|
λ0 |
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
Тогда |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x j 0 ≥ 0, j = |
|
, ∑n |
|
aij x j 0 ≤ bi , i = |
|
, yi 0 ≥ 0, i = |
|
, |
|
|
|
|
|
|
|||||||||||||||||||||||||||
|
|
1, n |
1, m |
1, m |
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
j = 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
∑m |
aij y j 0 ≥ c j , j = |
|
, ∑n |
c j x j 0 = ∑m |
bi yi 0 . |
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||
|
|
1, n |
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||
|
|
i= 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
j = 1 |
|
|
|
|
|
|
i= 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Следовательно, x0 = (x1 |
0 ,..., xn |
0 )- |
|
решение задачи (5.16) , y 0 |
= (y1 |
0 ,..., yn |
0 ) -ре- |
||||||||||||||||||||||||||||||||||||
шение задачи (5.17). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Пусть |
теперь |
x0 |
= |
|
(x1 |
0 ,..., xn |
0 )- решение задачи (5.16), |
y 0 = |
(y1 |
0 ,..., yn |
0 )- |
||||||||||||||||||||||||||||||||
решение задачи (5.17). Положим |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
λ0 = |
|
|
|
|
|
|
|
|
|
|
|
|
|
, µj 0 = λ0 x j 0 , j = 1, n,ν i 0 = λ0 yi 0 , i = 1, m. |
|
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||
|
|
|
1 + ∑n |
|
x j 0 +∑ m yi 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
j = 1 |
|
|
|
|
|
|
i= |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Тогда |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
λ0 > 0, µj 0 ≥ 0, j = |
|
,ν i 0 ≥ 0, i = |
|
, ∑n |
µj 0 +∑ m |
ν i 0 + λ0 = 1, |
|
|
|
|
|
|
|||||||||||||||||||||||||||||||
1, n |
1, m |
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
j = 1 |
|
|
|
|
|
i= 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
т.е. вектор z0 |
= (µ1 |
0 ,..., µn |
0 ,ν 1 |
0 ,...ν n |
0 , λ0 )- смешанная стратегия в игре с мат- |
|
|||||||||||||||||||||||||||||||||||||
рицей D размерности (n+m+l)× |
(n+m+l). Ограничения задач (5.16), (5.17) и соот- |
||||||||||||||||||||||||||||||||||||||||||
ношение двойственности |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
∑n |
c j x j 0 =∑ m |
|
bi yi 0 |
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
j = 1 |
|
|
|
|
|
i= 1 |
|
|
|
|
|
|
|
|
|
|
|
|
дают для z 0 соотношения (5.18)-(5.20), которые являются достаточными условиями оптимальности (см. (3.18)) для игры с матрицей D. Следовательно, z 0 -оптимальная стратегия (любого игрока) в игре с матрицей D.