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

UptoLike

ВУЗ: 

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

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

Рубрика: 

30 31
Задача нахождения
cx
x
min
при ограничениях
,
0
,
³
£
x
b
xA
(4.5)
где А –
(
)
nm
´
-матрица,
nm
RbRxc ÎÎ ,,
, называется прямой
стандартной ЗЛП, а задача, заключающаяся в определении
by
y
max
при
ограничениях
,
0
,
³
³
y
c
(4.6)
где
n
Ry Î
называется двойственной ЗЛП.
Прямая задача (ПЗ) Двойственная задача (ДЗ)
;max
1
å
=
®
m
i
ii
xc
;min
1
å
=
®
n
j
jj
yb
;,1,
1
sjbxa
j
m
i
iij
=£
å
=
;,1,
1
kicya
i
n
j
jij
=³
å
=
;,1,
1
nsjbxa
j
m
i
iij
+==
å
=
;,1,
1
mkicya
i
n
j
jij
+==
å
=
;,1,0 kix
i
=³
.,1,0 sjy
j
=³
Вектор
m
R
x
Î
, удовлетворяющий системе (4.5), называется
допустимым решением задачи (4.5). Аналогично вводится понятие
допустимого решения
n
Ry Î
задачи (4.6). Допустимое решение
(
)
yx
называется оптимальным решением задачи (4.5) ((4.6)), если на нем
достигается минимум (максимум) функции
(
)
bycx
на множестве всехх
допустимых решений.
Справедливо следующее утверждение.
Теорема 4.1 (двойственности). Если задачи (4.5), (4.6) имеют
допустимые решения, то они имеют оптимальные решения
x
и
y
соответственно, при этом
y
b
x
c
=
.
Напомним, что множество всех ситуаций равновесия в МИ мы
обозначили как
(
)
.
A
GZ
Лемма 4.1 (о масштабе). Пусть
A
G
и
A
G
¢
– две антагонистические
игры, причем
,
const
,
0
,
=
a
>
a
+
a
=
¢
B
A
A
(4.7)
а
},const{ jiB
ij
"
=
b
=
b
=
. Тогда
(
)
(
)
.,
b
+
a
=
=
¢
¢
A
G
A
GAA
vvGZGZ
(4.8)
Иными словами, оптимальность поведения игроков не изменится,
если в игре множества стратегий остаются прежними, а функция выиг-
рыша умножается на положительную константу или (и) к ней прибавля-
ется постоянное число.
Содержательно данная лемма говорит о стратегической эквивален-
тности двух игр, отличающихся лишь началом отсчета выигрышей,
а также масштабом их измерения.
Замечание 4.1. Если две МИ
A
G
и
A
G
¢
находятся в условиях этойой
леммы, то смешанные расширения также стратегически эквивалентны.
Лемма 4.2. Пусть
A
G
и
A
G
¢
– две матричные
(
)
nm
´
-игры, причем
,
const
,
0
,
=
a
>
a
+
a
=
¢
B
A
A
а
},const{ jiB
ij
"
=
b
=
b
=
. Тогда
(
)
(
)
AA
GZGZ =
¢
,
b
+
a
=
¢
A
A
vv
,
где
A
G
¢
и
A
G
– смешанные расширения игр
A
G
¢
и
A
G
соответственно,
a
A
A
vv ,
¢
– значения игр
A
G
¢
и
A
G
.
Пример 4.1. Проверим, что стратегии
(
)
,41,41,21
=
y
(
)
41,41,21
=
x
оптимальны, а
0
=
A
v
– значение игры
A
G
с матрицей
.
131
311
111
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
--
--
-
-
=A
Упростим матрицу А (в целях получения максимального числа ну-
лей). Прибавляя ко всем элементам матрицы А единицу, получим матрицу
.
040
400
002
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
=
¢
A

Страницы