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

UptoLike

ВУЗ: 

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

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

Рубрика: 

38 39
Самостоятельная работа № 3
Найти ситуацию равновесия и значение игры в смешанных страте-
гиях при помощи ЛП. Сделать проверку.
ЗАНЯТИЕ № 5
Графоаналитический метод решения
(
)
n
´
2
- либо
(
)
2
´
m
- матричных
игр (МИ)
Распространенный способ решения МИ путем сведения ее к ЗЛП
обладает тем недостатком, что процесс решения ЗЛП существенно ус-
ложняется для матриц большой размерности. В таких случаях обычно
используют методы декомпозиции ЗЛП, когда вместо решения задачи
с исходной матрицей строится координирующая задача с матрицей,
у которой мало строк, но много столбцов, или наоборот.
Напомним некоторые сведения из теории выпуклых множеств
и систем линейных неравенств.
Определение 5.1. Множество
m
R
M
Ì
называется выпуклым, если
вместе с любыми двумя точками этого множества
Mxx
Î
2
1
,
в нем
содержатся все точки отрезка
(
)
[
]
1,0,1
2
1
Î
xx
.
Понятие выпуклого множества можно сформулировать в более
общем, но эквивалентном виде.
Определение 5.2. Множество
m
R
M
Ì
называется выпуклым, если
вместе с точками
k
xx ,,
1
K
из
M
оно содержит все точки вида
.1,0,
1
1
=l³ll=
åå
==
k
i
ii
k
i
ii
xx
Пересечение выпуклых множеств всегда выпукло.
Определение 5.3. Рассмотрим систему линейных неравенств
b
xA
или
{
}
,,1, nNjxa
j
j
=Îb£
(5.1)
где
[
]
NjaA
j
Î= ,
–
(
)
nm
-матрица,
(
)
n
n
m
RbRx Îbb=Î ,,,
1
K
.
Обозначим
{
}
bxAxX £=
~
множество решений системы (5.1).
Непосредственно из определения следует, что
X
~
– выпуклое множество.
Множество
X
~
называется выпуклым многогранным множествомм,
заданным системой ограничений (5.1).
Определение 5.4. Точка
M
x
Î
, где
M
– выпуклое множество,о,
называется крайней точкой, если из условия
(
)
,1
2
1
l
-
+
l
=
xxx
(
)
1,0,,
2
1
Î
l
Î
Mxx
следует, что
xxx
=
=
2
1
. Содержательно определение
означает, что
M
x
Î
– крайняя точка, если не существует отрезка,
содержащего две точки из
M
, для которого
x
является внутренней.
Заметим, что крайняя точка выпуклого множества всегда является
граничной; обратное неверно.
Определение 5.5. Выпуклой оболочкой множества Р
(
)
Pconv
будем называть пересечение всех выпуклых множеств, содержащих Р.
Данное определение эквивалентно следующему. Выпуклая оболочка
множества Р состоит из всех выпуклых линейных комбинаций
всевозможных точек из Р, т. е.
()
.,0,1,conv
11
ï
þ
ï
ý
ü
ï
î
ï
í
ì
γl=ll==
åå
==
PxxxxP
ii
n
i
i
n
i
ii
Определение 5.6. Выпуклая оболочка конечного числа точек назы-
вается выпуклым многогранником, порожденным своими крайними
точками.
Определение 5.7. Напомним, что функция
1
: RM ®j
, где
m
R
M
Ì
–
выпуклое множество, называется выпуклой, если
(
)
(
)
(
)
(
)
(
)
2
1
2
1
11 xxxx
j
l
-
+
lj
£
l
-
+
l
j
(5.2)
для любых
Mxx
Î
2
1
,
и
[
]
1,0
Î
l
.
Если же в (5.2) выполняется обратное неравенство, то функция
j
называется вогнутой.
Лемма 5.1. Пусть
(
)
x
i
j
– выпуклые на М функции
ni ,1=
. Тогдада
верхняя огибающая
(
)
x
y
этого семейства функций
(
)
(
)
xx
i
ni
j
=
y
= ,1
max
(5.3)

Страницы