Материал: Бородакий Нелинейное программирование в современных задачах оптимизации 2011

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

	n			≤ i ≤ m;
H (i,Y ) = ∑aij y* j ≤ v, 1				≤ i ≤ m;
	j=1			(2.3)
	m			(2.3)
	m	*	i ≥ v, 1	≤ j ≤ n.
		*
H (X , j) = ∑aij x
	i=1

Под решением матричной игры будем понимать нахождение векторов X и Y , а также значения цены игры v .

2.1.2. Основы метода фон Неймана

Данный метод представляет собой итеративный метод приближенного решения матричных игр размерности ( m ×n ), обладающий достаточно хорошей скоростью сходимости.

Пусть дана платежная матрица

a	a		.	a
11	12			1n
A = .		. .		.	.
am1	am1 .			amn

Положим, что решения в чистых стратегиях нет. Будем искать решение игры (m ×n) в смешанных стратегиях в виде

X = (x , ..., x

)т ,

≥ 0,

i =

1, m

(2.4)

Y = ( y , ..., y

)т ,

≥ 0,

j =

1, n

при ограничениях

∑xi

=1,

∑y j =1.

i=1

j=1

Тогда, если X * ,Y * – оптимальные смешанные стратегии первой

и второй стороны, то в соответствии с соотношениями (2.3) выполняются неравенства

n
n	≤ v,	i =1, m;
∑aij y*j	≤ v,	i =1, m;
j=1		(2.5)
m		(2.5)
∑aij xi* ≥ v,		j =		,
∑aij xi* ≥ v,		j =	1, n	,
i=1

где v – цена игры.

101

Суть метода фон Неймана состоит в численном решении системы линейных неравенств (2.5) путем сведения этой задачи к задаче минимизации функции:

			n		m
f (X ,Y ,v) = ∑[z j (X ,v)]2 +∑[ui (Y ,v)]2 ,						(2.6)
			j=1		i=1
где
			при		m
		0	при	v − ∑aij xi ≤ 0;
z j =					i=1	(2.7)
z j =			m		m	(2.7)
		v − ∑aij xi			при v − ∑aij xi ≥ 0;
			i=1		i=1
			при	n
	0		при	∑aij x j − v ≤ 0;
ui				i=1		(2.8)
ui	=	n			n	(2.8)
	∑aij y j − v				при ∑aij y j − vl ≥ 0.
	i=1				i=1

Функция (2.6) представляет собой сумму квадратов невязок правых частей неравенств (2.5).

Точное решение матричной игры соответствует таким значениям аргументов, при которых достигается минимум функции f ( X ,Y , v) , т.е.

f (X * ,Y * , ν) = min f (X ,Y , ν) = 0 .

Задача минимизации функции (2.6) относится к области нелинейного программирования и представляет собой задачу минимизации функции многих переменных с ограничениями. Ограничения наложены на компоненты векторов X и Y в соответствии с определением смешанной стратегии.

Дж. фон Нейманом предложена своя процедура решения данной задачи нелинейного программирования, близкая к градиентным методам, но учитывающая особую структуру ограничений.

102

2.1.3. Алгоритм фон Неймана

Алгоритм заключается в следующем.

1. Начальные оценки векторов X и Y и цены игры ν задаются в виде

xi(0) =	1	,	i =				;
				1, m
	m

y(j0) =	1	,	j =			;		(2.9)
					1, n
	n

v(0) = max(aij ) + min(aij ) . 2

2. На (l +1) -й итерации новые значения оценок определяются на основании соотношений

l+1

~l+1

− θ

), i =1, m ;

= xi

(xi − xi

l+1

~l+1

j =1, n;

(2.10)

y j

= y j − θ

( y j

− y j

l+1

= v

− θ

l+1

~l+1

− v

где

θl+1 =

f (X l ,Y l , vl )

f (X

, v

~ l+1

~l+1

)

) + f (X

, v

~l+1

(i =1, m;

j =1, n)

представляют собой оценку

Значения xi

, y j

величин xi* , y*j

на шаге ( l +1). Эти значения рассчитываются с

учетом соотношений (2.7) и (2.8) по формулам:

~ l+1

при sl

≠ 0,

= ∑uil ;

(2.11)

i=1

при

= 0;

103

(l)

max aij +min aij

tl = 0

~l +1

, y j

=n,v

z j

y j

∑

−v

aij y j

~l +1

= v

y j

z j

− ∑ aij xi

i=1

~l+1

+1~l+1

= ∑

∑ a

=1i

=1 ij i

= max(0, ui )

~l+1

∑

z j

= max(0, z j )

=1 aij y j

−v

~l+1

∑

)

∑

( z

)

−

j =1

= v

∑ a x

i=1

=1 ij i

~l +1

)

= ∑ (ui

+ ∑

( z j

f l

i=1

= ∑ ul

i=1

θl

+ 1 =

+ 1

~l +1

= 0

l +1

~l +1

+ θ

)

( xi

− xi

l +1

+ θ

l +1

−

~l +1

)

y j

( y j

y j

l +1

= v

+ θ

l +1

~l +1

)

~l +1

− v

∑

j =1

l ≤ N + 1

Рис. 2.1. Структурная схема алгоритма фон Неймана

104

~ l+1 y j

zlj

=t lylj

	n
при t l	≠ 0, t l = ∑zlj ;	(2.12)
	j=1	(2.12)
при t l	= 0.

Оценки цены игры на ( l +1)-шаге вычисляются по формуле

~l+1	~ l+1	~ тl+1	,
v	= X	AY	,

которая в скалярной форме имеет вид

~l+1	m n	~l+1	~l	+1	.	(2.13)

v	= ∑ ∑aij xi		y j

i=1 j=1

3. Итерационный процесс заканчивается, когда значение функции (2.6) становится достаточно малым, т.е. когда выполняется соотношение

f l ≤ ε ,

(2.14)

где ε – заданная точность вычисления.

Структурная схема алгоритма фон Неймана приведена на рис. 2.1.

2.1.4.Математическое программирование

втеории биматричных игр

2.1.4.1.Биматричные игры. Основные теоретические сведения

Матричная игра является антагонистической игрой [25], т.е. игрой двух лиц с нулевой суммой. Однако на практике часто встречаются такие ситуации, когда интересы сторон не являются прямо противоположными. В этом случае игра имеет произвольную сумму, отличную от нуля, и является неантагонистической.

Конечную игру двух игроков с произвольной суммой можно описать парой матриц, поэтому она называется биматричной.

Биматричная игра определяется следующим образом. Два игрока обозначены буквами A и B . Игрок A имеет в своем распоряжении m чистых стратегий, а B – n чистых стратегий. Если A выбирает свою i -ю чистую стратегию, а B – j -ю чистую страте-

гию, то выигрыш игрока A есть aij , а выигрыш игрока B есть bij .

105

Источник: https://studfile.net/preview/16708738/

Смотрите также:



_1966(~1
_Антонян Ю.М., Сексуальные преступления. Чикатило и другие
_РГР № 1 (2)
- Габариты и масса 27
'Образ–Я' и его развитие средствами диалога
"Логистическая технология JIT"
"Особенности правовой системы Российской Федерации" по дисциплине "Теория государства и права"
«Анализ ликвидности и платежеспособности предприятия» (на материалах ОАО Московская кондитерская фабрика «Красный Октябрь»)