Бескоалиционные игры в нормальной форме. Часть 1. Григорьева К.В. - 18 стр.

UptoLike

ВУЗ: 

СПбГАСУ | Санкт-Петербург

Составители: 

Рубрика: 

34 35
Теперь рассмотрим
(
)
nm
´
-МИ
A
G
¢
с произвольной матрицей
}{
ij
A
a
¢
=
¢
. Тогда существует такая константа
0
>
b
, что матрица
B
A
A
+
¢
=
– строго положительна, где
(
)
nmB
ij
´
-
b
=
}{
-матрица,
njmi
ij
,1,,1, ==b=b
. В игре
G
существует ситуация равновесия
(
)
yx,
в смешанных стратегиях, а значение игры равно
q
=
1
A
v , где q
определяется как в (4.11).
Из леммы 4.2 следует, что
(
)
(
)
A
GZyx
¢
Î,
– ситуация равновесия
в игре
G
¢
в смешанных стратегиях, а значение игры равно
=
b
-
=
¢
vv
b
-
q
=
b
1
. Теорема доказана.
Следует отметить, что не всегда в антагонистических играх суще-
ствует решение в смешанных стратегиях.
Доказательство теоремы сводит решение МИ к ЗЛП.
Алгоритм решения игры
A
G
¢
следующий.
1. По матрице А’ строится строго положительная матрица
B
A
A
+
¢
=
,
где }{
ij
B
b
=
,
0
>
b
=
b
ij
.
2. Решаются ЗЛП (4.9), (4.10). Находятся векторы
**
, yx
и число q
[см. (4.11)].
3. Строятся оптимальные стратегии игроков 1 и 2:
q=q=
**
и yyxx
соответственно.
1. Вычисляется значение игры
A
G
¢
b
-
q
=
¢
1
A
v
.
Пример 4.2. Рассмотрим МИ
G
, определенную матрицей
÷
÷
ø
ö
ç
ç
è
æ
=
32
04
A
. Соответствующие ей ЗЛП имеют следующий вид:
;0,0
,13
,124
,min
2
1
2
21
21
³x³x
³x
³x+x
x
+
x
.0,0
,132
,14
,max
21
21
1
21
³h³h
£h+h
£h
h
+
h
Введем
43
,
x
x
– базисные переменные,
2
1
,
x
x
– свободные перемен-
ные. Заметим, что эти задачи в эквивалентной форме могут быть записаны
для ограничений типа равенств:
;0,0,0,0
,13
,124
,min
4
3
2
1
42
321
21
³x³x³x³x
=x-x
=x-x+x
x
+
x
.0,0,0,0
,132
,14
,max
4321
421
31
21
³h³h³h³h
=h+h+h
=h+h
h
+
h
Таким образом, методы решения ЗЛП могут быть приспособлены
для решения МИ.
Перепишем задачу
ï
î
ï
í
ì
³xx
=x-x
=x-x+x
®
x
+
x
=
0,,
;13
;124
min;
41
42
321
21
K
F
в эквивалентном виде
=
x
+
x
-
+
x
+
x
-
x
-
=
+
=
j
4232121
31241RR
min542
4321
®
x
+
x
+
x
-
x
-
=
;
î
í
ì
=+x-x
=
+
x
-
x
+
x
.13
;124
242
1321
R
R
Составим симплекс-таблицу:
1
x
2
x
3
x
4
x
1
R
2
R
1
R
4 2 –1
0 1 0 1
2
R
0 3*
0 –1
0 1 1
j
4 5 –1
–1
0 0 2
и решим симплекс-методом (см. пример 1, стр. 59).

Страницы