4329
.pdf21
Рис. 3
Уравнение прямой b1 , проходящей через точки (0; 1) и (1; 6), имеет вид
|
|
|
|
|
y 6 |
|
x 1 |
|
или |
|
y 5x 1. |
||||||||||
|
|
|
|
|
|
|
0 1 |
|
|||||||||||||
|
|
|
|
|
1 6 |
|
|
|
|
|
|
|
|
|
|
|
|||||
Уравнение прямой |
b2 , проходящей через точки (0; 5) и (1; 3) |
||||||||||||||||||||
|
|
|
|
y 3 |
|
x 1 |
|
|
или |
y 2x 5 . |
|||||||||||
|
|
|
|
5 3 |
|
0 1 |
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
Вычислив координаты точки N |
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
||||
|
5x 1 |
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
, |
7 |
|
, получаем оптимальную стратегию игрока А |
|||||||||||||||||
y |
|
|
|
|
|||||||||||||||||
y 2x 1 |
y |
27 |
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
p 1 x |
|
1 |
4 |
3 , |
|
|
p |
x |
|
4 , y |
|
|
27 |
. |
|||||||
N |
7 |
|
|
N |
N |
|
|||||||||||||||
1 |
|
7 |
|
|
|
2 |
|
|
7 |
|
|
|
|
7
Далее геометрически определяем оптимальную стратегию второго игрока.
22 |
|
|
|
|
|
Так как точка N является пересечением прямых b1 |
|
и |
b2 , то активными |
||
стратегиями игрока В будут стратегии B1 |
и |
B2 . |
На оси абсцисс |
||
откладываем единичный отрезок B1 B2 . В точках B1 |
и B2 |
проведем оси I и II |
|||
на которых отметим выигрыши при стратегиях B1 |
и |
B2 |
соответственно. |
Пусть второй игрок придерживается стратегии B1 . Если 1-й игрок примет стратегию A1 , то она дает выигрыш a11 1 . Отложим по оси I отрезок длины a11 1 вверх от точки B1 , получим точку с координатами (0;1) .
Пусть второй игрок придерживается стратегии B2 . Если 1-й игрок примет стратегию A1 , то она дает выигрыш a12 5. Отложим по оси II отрезок длины a12 5 вверх от точки B2 и получим точку с координатами (1;5) .
Через точки (0;1) и (1;5) проведем прямую a1 (рис. 4). Аналогично строим прямую a2 соответствующую применению первым игроком стратегии A2 .
Выделяем верхнюю границу a2 Na1 и видим, что точка N является ее минимумом.
Рис. 4
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
23 |
|
|
|
|
|
|
|
|
|
Найдем координаты точки N , как точки пересечения прямых a1 |
и a2 . |
|||||||||||||||||||||||||||||||||||||
Прямая |
|
|
a1 |
проходит через точки (0;1) и (1;5) ,поэтому ее уравнение |
||||||||||||||||||||||||||||||||||
имеет вид: |
|
|
|
y 1 |
|
x 0 |
|
|
|
или |
y 4 x 1. |
|
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
5 1 |
|
|
|
|
1 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
Прямая |
|
|
a2 |
|
проходит через точки (0;6) и (1;3) ,поэтому ее уравнение |
|||||||||||||||||||||||||||||||||
имеет вид: |
|
|
|
y 6 |
|
|
x 0 |
|
|
или |
y 3 x 6 . |
|
|
|
|
|
||||||||||||||||||||||
|
|
|
3 6 |
1 0 |
|
|
|
|
|
|
||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
Координаты точки N находятся из системы |
|
|
|
|
|
|||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
y 4x 1 |
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B |
||||||||||||||
|
|
|
|
, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
, |
|
получаем оптимальную стратегию игрока |
|||||||||||||||||
y 3x |
6 |
|
|
|
|
y |
27 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
q 1 x |
|
|
|
1 5 |
|
2 , |
q x |
|
5 , |
y |
|
|
27 |
. |
|
|||||||||||||||||||||||
N |
N |
N |
|
|
||||||||||||||||||||||||||||||||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
7 |
2 |
|
|
7 |
|
7 |
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
О т в е т : |
S* |
|
|
3 |
; |
|
4 |
– оптимальная смешанная стратегия игрока А, |
|
|||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||
|
|
A |
|
|
|
7 |
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
S* |
|
|
2 |
|
|
5 |
|
|
|
|
|
|
|
– оптимальная смешанная стратегия игрока В, |
|||||||||||||||||||||||
|
|
|
|
|
|
|
; |
|
|
|
|
;0;0 |
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||
|
|
B |
|
|
|
7 |
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
27 |
|
|
|
– цена игры. |
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Пример 2.2. |
|
|
|
|
|
Пусть игра задана матрицей |
|
|
|
|
|
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11 |
2 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
P |
|
9 |
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
10 |
|
|
|
|
|
Найти оптимальные стратегии игроков и определить цену игры графическим методом.
24
Решение. Игрок B имеет две стратегии, игрок А – четыре, поэтому на
оси абсцисс откладываем единичный отрезок |
B1B2 , |
на концах которого |
|
восстанавливаем перпендикулярные оси I и II. |
|
|
|
Пусть второй игрок придерживается стратегии B1 . Если 1-й игрок примет |
|||
стратегию A1 , то она дает выигрыш a11 11 . |
Отложим по оси I отрезок |
||
длины a11 11 вверх от точки B1 , получим точку с координатами (0;11) . |
|||
Пусть второй игрок придерживается стратегии |
B2 . Если 1-й игрок |
||
примет стратегию A1 , то она дает выигрыш |
a12 2 . |
Отложим по оси II |
|
отрезок длины a12 2 вверх от точки B2 |
и получим точку с координатами |
||
(1; 2) . Через точки (0;11) и (1; 2) проведем прямую a1 . Аналогично строим |
прямые ai , соответствующие применению первым игроком стратегий |
Ai |
(i 2,3,4) . Выделяем верхнюю границу a1PNMa4 и видим, что точка |
N |
(точка пересечения прямых a2 и a3 ) является ее минимумом (рис. 5). |
|
Рис. 5
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
25 |
|
|
|
|
|
|
|
|||
|
Прямая |
a2 |
проходит через точки |
|
(0;9) |
и |
(1;6). Следовательно, ее |
|||||||||||||||||||||
уравнение имеет вид |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
y 9 |
|
|
x 0 |
|
|
или y 3x 9. |
|||||||||||||
|
|
|
|
|
|
|
|
|
6 9 |
1 0 |
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
Прямая |
a3 |
проходит через точки |
|
(0;6) |
и |
|
(1;8). Уравнение этой |
||||||||||||||||||||
прямой будет иметь вид |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
y 6 |
|
x 0 |
|
или |
y 2x 6. |
||||||||||||||||
|
|
|
|
|
|
|
|
|
1 0 |
|||||||||||||||||||
|
|
|
|
|
|
|
8 6 |
|
|
|
|
|
|
|
|
|
||||||||||||
Координаты точки N находятся из системы |
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
x |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
y 3x 9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
5 |
|
|
|
, получаем оптимальную стратегию игрока В |
||||||||||||||||||||||
|
y 2x 6 |
, |
|
|
|
36 |
|
|
||||||||||||||||||||
|
|
|
|
|
|
y |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
q 1 x |
|
1 |
3 |
2 |
, q x |
|
3 |
, y |
|
|
36 |
. |
||||||||||||||||
N |
5 |
N |
N |
|
||||||||||||||||||||||||
1 |
|
|
|
5 |
|
|
2 |
|
|
|
|
5 |
|
|
|
5 |
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Далее геометрически определяем оптимальную стратегию первого игрока. Так
как активными стратегиями игрока |
А |
являются стратегии A2 |
и |
A3 , то |
||||
S* (0; p*; p*;0) и |
p* |
p* 1. |
На оси абсцисс откладываем единичный |
|||||
A |
2 3 |
2 |
3 |
|
|
|
|
|
отрезок |
A2 A3 , на концах которого восстанавливаем перпендикулярные оси I |
|||||||
и II. |
|
|
|
|
|
|
|
|
Пусть первый игрок придерживается стратегии |
A2 . Если 2-й |
игрок |
||||||
примет стратегию B1 , |
то она дает выигрыш a21 9 . |
Отложим по |
оси I |
|||||
отрезок длины a21 9 |
вверх от точки |
A2 , получим точку с координатами |
||||||
(0;9) . |
|
|
|
|
|
|
|
|
Пусть первый игрок придерживается стратегии |
A3 . Если 2-й |
игрок |
||||||
примет стратегию B1 , |
то она дает выигрыш a31 6. |
Отложим по оси II |
||||||
отрезок длины a31 6 вверх от точки |
A3 и получим точку с координатами |
26
(1;6) . Через точки (0;9) и (1; 6) проведем прямую b1 . Аналогично строим прямую b2 , соответствующую применению вторым игроком стратегии B2 .
Выделяем нижнюю границу b2Mb1 , в которой точка М соответствует максимуму (рис. 6).
Рис. 6
Уравнение прямой b1 , проходящей через точки (0; 9) и (1; 6), имеет
вид
|
y 9 |
|
x 0 |
|
или |
y 3x 9 . |
|
|||
|
6 9 |
1 0 |
|
|||||||
|
|
|
|
|
|
|||||
Уравнение прямой |
b2 , проходящей через точки (0; 6) |
и (1; 8), имеет |
||||||||
вид |
|
|
|
|
|
|
|
|
||
|
|
y 6 |
|
x 0 |
или |
y 2x 6. |
|
|||
|
|
8 6 |
1 0 |
|
||||||
|
|
|
|
|
|
|
||||
Координаты точки М, |
как точки пересечения прямых b1 |
и b2 , находим |
||||||||
из системы |
|
|
|
|
|
|
|
|
27
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
3 |
|
|
|
|
|
||
|
|
|
|
|
y 2x 6 |
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
5 . |
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
3x 9 |
, |
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
y |
|
|
|
y |
36 |
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Получаем оптимальную стратегию игрока А: |
|
|
|
|
|
|
|
||||||||||||||||||||||||
p 1 x |
|
1 3 |
|
|
2 |
|
, |
|
p |
x |
|
3 , |
y |
|
|
36 |
. |
||||||||||||||
M |
5 |
|
M |
M |
|
||||||||||||||||||||||||||
2 |
|
|
5 |
|
|
|
|
|
|
|
|
3 |
|
|
5 |
|
|
|
|
|
5 |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
* |
|
|
|
|
|
2 |
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
О т в е т : |
|
SA |
0; |
|
|
|
; |
|
|
|
;0 |
– оптимальная стратегия игрока А, |
|||||||||||||||||||
|
|
|
|
|
|
|
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
5 |
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
* |
|
|
2 |
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
S |
|
|
|
|
; |
|
|
|
|
– оптимальная стратегия игрока В, |
|||||||||||||||||||
|
|
|
5 |
|
|
|
|
||||||||||||||||||||||||
|
|
|
B |
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
36 |
– |
|
|
цена игры. |
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2.3. Индивидуальные задания
Решить графическим методом игру с платежной матрицей P.
1. Р 8 |
5 3 6 7 , |
|
2. |
Р 2 |
4 0 3 5 |
, |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
3. |
4 |
7 9 5 8 |
, |
4. |
6 |
3 8 4 2 |
|
||||
Р 5 |
3 |
6 4 5 |
Р 3 |
5 1 4 6 |
, |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
6 |
8 1 2 |
|
|
7 |
4 9 5 3 |
|
|
||
|
2 |
5 |
|
|
|
6 |
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
1 |
|
|
|
|
4 |
6 |
|
|
|
5. |
Р |
|
, |
|
|
6. |
Р |
|
, |
|
|
|
3 |
7 |
|
|
|
2 |
7 |
|
|
|
|
7. |
4 |
6 |
|
, |
8. |
1 |
8 |
|
|
|
|
Р 4 |
7 1 2 |
Р 2 |
3 1 5 , |
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
9. |
0 |
3 4 |
2 |
|
10. |
4 |
1 6 0 |
|
|
||
Р 3 |
4 |
5 4 |
, |
|
Р 8 |
0 |
6 7 , |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
6 |
4 5 |
|
|
|
3 |
6 3 1 |
|
|
|
|
|
|
|
|
|
28 |
|
|
|
|
|
|
2 |
5 |
|
|
|
|
6 |
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
1 |
|
|
|
|
4 |
6 |
|
|
|
|
11. |
Р |
|
|
, |
|
|
12. |
Р |
|
|
, |
|
|
3 |
7 |
|
|
|
|
2 |
7 |
|
|
||
13. |
4 |
6 |
0 |
3 , |
14. |
1 |
8 |
3 4 |
, |
|||
Р 4 |
6 |
Р 2 |
2 |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 0 7 |
2 |
|
4 |
3 2 2 |
|
||||||
|
|
2 |
7 |
3 |
4 |
|
|
|
|
|
|
|
15. |
Р |
5 |
1 |
9 |
6 |
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3. |
СВЕДЕНИЕ МАТРИЧНОЙ ИГРЫ К ЗАДАЧЕ ЛИНЕЙНОГО |
|
ПРОГРАММИРОВАНИЯ |
|
|
3.1. Теоретическая часть |
|
|
Рассмотрим матричную игру |
m n без седловой точки с платежной |
|
матрицей Р. |
|
|
Допустим, что все выигрыши |
ai j ( i = 1, 2, 3, … , m ; j = 1, 2, 3, … , n ) |
положительны (этого всегда можно добиться, прибавляя ко всем элементам матрицы достаточно большое число С, от этого, как уже отмечалось, цена игры
увеличится на С, а оптимальные стратегии игроков S* |
и |
S* |
не изменятся). |
|
|
А |
|
B |
|
Если все |
ai j положительны, то и цена игры |
|
при оптимальной |
|
стратегии тоже |
положительна, так как . |
|
|
|
В соответствии с основной теоремой матричных игр, если платежная матрица не имеет седловой точки, то имеется пара оптимальных смешанных
стратегий S* |
и |
S* , применение которых обеспечивает игрокам получение |
||
А |
|
B |
|
|
цены игры . |
|
|
|
|
Найдем в начале S* |
, для этого предположим, что игрок В отказался от |
|||
|
|
А |
|
|
своей оптимальной |
смешанной стратегии S* |
и применяет только чистые |
||
|
|
|
B |
|
29
стратегии. В каждом из этих случаев выигрыш игрока А будет не меньше, чем. Иными словами, выполняются следующие соотношения
m |
|
|
m |
|
|
|
|
|
|
|
|
aij |
pi v ( j 1, 2, ... , n ) ; |
pi |
1, |
|
pi |
0 |
(i 1, 2, ... , m), |
||||
i 1 |
|
|
i 1 |
|
|
|
|
|
|
|
|
которые с учетом обозначений |
|
|
|
|
|
|
|
|
|
||
|
x |
pi |
( i 1, 2, ... , m) |
|
|||||||
|
|
|
|||||||||
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
можно записать так |
|
|
|
|
|
|
|
|
|
||
m |
|
|
m |
|
1 |
|
|
|
|
|
|
aij xi |
1 ( j 1, 2, ... , n) ; |
xi |
|
|
, |
xi |
0 |
(i 1, 2, ... , m). |
|||
v |
|||||||||||
i 1 |
|
|
i 1 |
|
|
|
|
|
Поскольку игрок А стремится сделать гарантированный выигрыш максимально возможным, то задача отыскания решения матричной игры сводится к следующей задаче линейного программирования:
найти неотрицательные величины x1, x2 , … ,
неравенствам
m
aij xi 1 ( j 1, 2, ... , n),
i1
итакие, что их сумма минимальна
m
L(x) xi min .
i 1
Решив эту задачу ЛП, получим оптимальную стратегию S*А .
Аналогично находим оптимальную |
стратегию |
S* |
игрока |
В. |
|
|
B |
|
|
Предположим, что игрок А отказался от своей оптимальной стратегии S* |
и |
|||
|
|
|
А |
|
применяет только чистые стратегии. Тогда проигрыш игрока |
В |
в каждом из |
||
этих случаев будет не больше, чем . |
Иными словами, |
выполняются |
следующие соотношения
30
n |
|
|
n |
|
|
|
|
|
|
|
|
aij q j |
v (i 1, 2, ... , m) ; q j |
1, |
|
q j 0 |
( j 1, 2, ... , n), |
||||||
j 1 |
|
|
j 1 |
|
|
|
|
|
|
|
|
которые с учетом обозначений |
|
|
|
|
|
|
|
|
|
||
|
y j |
q j |
( j |
1, 2, ... , n) |
|
||||||
|
|
|
|||||||||
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
||
можно записать так |
|
|
|
|
|
|
|
|
|
||
n |
|
|
n |
|
|
1 |
|
|
|
|
|
aij y jk |
1 (i 1, 2, ... , m) ; y j |
|
|
, |
y j 0 |
( j 1, 2, ... , n). |
|||||
v |
|||||||||||
j 1 |
|
|
j 1 |
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
Поскольку игрок В стремится сделать свой гарантированный проигрыш минимально возможным, то задача отыскания решения матричной игры сводится к следующей задаче линейного программирования:
найти неотрицательные величины y1, y2 , … , yn , удовлетворяющие
неравенствам
n
aij y j 1 ( i 1,2,..., m ),
j 1
и такие, что их сумма максимальна
n
L( y) y j max
j 1
Эта задача является двойственной по отношению к предыдущей задаче.
Решая двойственную задачу ЛП, получим оптимальную стратегию SB* .
Таким |
образом, |
оптимальные стратегии S* |
p*, p*, ... , |
p* |
и |
||
|
|
|
|
A |
1 2 |
m |
|
S* |
q*, q*, ... , q* |
матричной игры m n |
с платежной матрицей |
Р |
|||
B |
1 |
2 |
n |
|
|
|
|
могут быть найдены |
путем решения пары двойственных задач линейного |
||||||
программирования: |
|
|
|
|
|