Загребаев Методы матпрограммирования 2007

X2

6

4		X2
2			l
				X0			r
0									X1
				2			4			6 X1
Рис. 4.3. Множество Χ :				X 0 , X 1 , X 2 – крайние точки; l, r						– открытые ребра
				*		*	*
Пусть для любого				X через		p( X ) обозначено множество тех из
векторов fi или b j , для которых
			( fi , X ) = 0			или	(b j , X ) =1.			(4.50)
Множество p( X )				может быть единственным образом записано
в виде матрицы
				p( X ) = ( p1 , p2 ,..., pr ) ,						(4.51)

где pl (l =1,..., r) – это соответствующий определению вектор fi или b j .

261

Предположим, что матрица B удовлетворяет условию невырожденности: пусть столбцы матрицы C являются столбцами из матрицы (I, B) , где I – единичная матрица, тогда если C = p( X )

для некоторого X Χ, то ранг матрицы C равен числу ее столбцов.

Рассмотрим следствия, вытекающие из предположения о невырожденности.

Следствие 1. Если для некоторого X Χ множество p( X ) содержит m векторов, то X полностью определяется своими векто-

рами fi и b j . В этом случае X	называется крайней точкой мно-
жества Χ .
Следствие 2. Пусть для X 0 Χ матрица p( X 0 )						имеет ранг r ,
матрица p( X 0 ) есть матрица размером				(m ×r) ( r		может быть и
равным нулю):
p( X 0 ) = ( p , p		2	,..., p	r	) .	(4.52)
1

Ввиду того, что p1 , p2 ,..., pr – линейно независимые векторы,

можно присоединить к ним векторы pr+1 , pr+2 ,..., pm матрица

D = ( p1 , p2 ,..., pm )

была невырожденной. Существует обратная матрица

(D−1 ) т = ( p1 , p 2 ,..., p m ) .

Это означает, что

1	при	i = j,
( pi , p j ) = δij =	при	i ≠ j.
0

так, чтобы

(4.53)

(4.54)

(4.55)

Теорема 4.3. Пусть	X 0 Χ и p( X 0 ) = ( p , p	2	,..., p	r	) . Сущест-
	1
вует такая постоянная K , что при
	m
	∑λ2i ≤ K ,				(4.56)

i=1

262

где λi ≥ 0 для 1 ≤ i ≤ r , точка X , определяемая соотношением

		m
X =	X 0	+ ∑λi pi ,	(4.57)
		i=1
принадлежит множеству Χ .	p – любой столбец матрицы (I, B). То-
Доказательство. Пусть
гда		m
( p, X ) = ( p, X 0 ) + ∑λi ( p, pi ) .			(4.58)

i=1

Рассмотрим два случая.

1. Если p p( X 0 ) , т.е. p = pi , 1 ≤ i ≤ r .

На основании следствия 2 имеем ( p, X ) = ( p, X 0 ) + λi . При этом

1,	если p	− столбец из B,	(4.59)
( p, X 0 ) =	если p	− столбец из I.
0,

По условию теоремы λi ≥ 0 , 1 ≤ i ≤ r , следовательно, ( p, X ) ≥

≥( p, X 0 ) и X является подмножеством Χ .

2.Если p p( X 0 ) , т.е. p – любой другой столбец из (I, B). В этом случае

	1,		если p	− столбец из B,		(4.60)
	( p, X 0 ) >		если p	− столбец из I.
	0,
Пусть	p – столбец из B , тогда ( p, X 0 ) =1 + α , где α > 0 . Вы-
брав λi ,	1 ≤ i ≤ m , достаточно малыми, такими, чтобы
		m
		∑λi ( p, pi )			≤ α,	(4.61)
		i=1

получим ( p, X ) ≥1.

По аналогии можно рассмотреть столбец матрицы I . Таким образом, при соответствующем выборе λi , 1 ≤ i ≤ m , из соотношения

263

( p, X 0 ) ≥ 0 следует, что ( p, X ) ≥ 0 , а из соотношения ( p, X 0 ) ≥1 следует, что ( p, X ) ≥1. Следовательно, X Χ.

Теорема доказана.

Таким образом, доказана возможность перемещения вдоль границы многогранника Χ или Υ от одной крайней точки к другой. Именно в таком перемещении и проверке в каждой крайней точке условий (4.37) и (4.38) и заключается суть алгоритма Лемке – Хоусона поиска ситуации равновесия.

Обратимся вновь к рис. 4.3. Точка X 0 является крайней точкой множества Χ . Поскольку выполняются условия

0.5x0		+ 0.33x0	=1	и	0.2x0 + x0				=1 ,	(4.62)
	1	2					1	2
матрица p( X 0 )	невырождена:
		p( X	0 ) = ( p , p			2	) ,			(4.63)
				1
где
		0,5					0,2
				p2						(4.64)
	p1 =		, а			=		.
		0,33					1
Согласно соотношению (4.57) точки
		X = X 0 + λ1 p1 + λ2 p2								(4.65)
при малых положительных λi принадлежат Χ .
Пусть λ2 = 0 . Для
		X = X 0 + λ1 p1 ,				λ1 > 0				(4.66)
матрица p( X )	получается из p( X 0 )				вычеркиванием только одно-

го столбца, а именно p1 . Такие точки образуют открытое ребро

многогранника Χ с концом X 0 . На рис. 4.3 оно обозначено буквой r .

Для X 1 Χ матрица p( X 1 ) = ( p1 ) . При достаточно малом λ2 точки

264

X = X 1 + λ2 p2

(4.67)

принадлежат множеству Χ и для них p( X ) = p( X 1 ) . Такие точки

образуют открытое ребро 1, содержащее X 1 . В общем случае матрица p( X ) , где X принадлежит открытому ребру Χ , имеет ранг,

равный (m −1) .

На рис. 4.3 показаны два неограниченных ребра, каждое из которых обладает лишь одной концевой точкой X = kfi с соответст-

вующим k . Таким образом, у многогранника Χ имеется ровно m неограниченных ребер, а остальные ребра имеют по две концевые точки, которые называются смежными крайними точками. Для

смежных крайних точек, например X 2 и X 0 , отличаются лишь одним столбцом. В нашем примере

	2	0,5		1				0	0,5		0,2
p( X						, а	p( X						(4.68)
		) =	0,33	0					) =	0,33	1	.

Аналогичные рассуждения можно провести для множества Υ . Пусть q(Y ) – матрица, подобная рассматривавшейся для эле-

ментов X множества Χ матрице p( X ) . Предположим также, что

матрица A удовлетворяет условию невырожденности, аналогично тому, которое было наложено на B.

Рассмотрим Ζ = Χ×Υ . Точка Z = (X ,Y ) из Ζ называется край-

ней для Ζ , если X – крайняя точка многогранника Χ , а Y – крайняя точка Υ . Очевидно, такая точка должна удовлетворять (m + n)

условиям из системы

( fi , X ) = 0,				i =1,..., m,
			= 0,	j =1,..., n,
(b j , X ) −1					(4.69)
				j =1,..., n,
(e j ,Y ) = 0,
(a		,Y ) −1 = 0,		i =1,..., m.
	i

Будем говорить, что Z = (X ,Y ) лежит на открытом ребре много-

гранника Ζ , если одна из ее координат является крайней точкой Χ или Υ , а другая лежит на открытом ребре. Для точек, принадле-

265

жащих открытому ребру, выполняются (m + n −1) из указанных

выше соотношений.

Теорема 4.4. Любая ситуация равновесия для невырожденной

задачи является крайней точкой множества Ζ .
Доказательство.	Если	Z * = ( X * ,Y * )	удовлетворяет условиям
постановки задачи,	то для i =1,..., m		или	( fi , X * ) = 0 , или
(ai ,Y * ) −1 = 0 , и	для	j =1,..., n	или	(e j ,Y * ) = 0 ,	или
(b j , X * ) −1 = 0 . Из условия невырожденности следует, что					X Χ
может удовлетворять не более, чем m соотношениям вида:
( fi , X * ) = 0		или (b j , X * ) −1 = 0 ,			(4.70)

а Y Υ может удовлетворять не более, чем n соотношениям вида:

(e j ,Y * ) = 0 или (ai ,Y * ) −1 = 0 .	(4.71)
Но ( X * ,Y * ) должны удовлетворять по меньшей мере	(m + n)

таким соотношениям. Таким образом, удовлетворяются в точности

(m + n) соотношений, т.е. для			X *	выполнены ровно m из соотно-
шений		( fi , X ) = 0,		i =1,..., m,
								(4.72)
		(b j , X ) −1 = 0,		j =1,..., n.
Следовательно,		X * – крайняя точка Χ . Аналогично Y *						– край-
няя точка Υ ,	а Z * = ( X * ,Y * )		– крайняя точка			Z , что и требова-
лось доказать.
Одновременно		получен	следующий			критерий:		если
Z * = ( X * ,Y * )	–	ситуация	равновесия,		то	для	любого s ,
1 ≤ s ≤ m + n ,	или	s -й столбец		матрицы	(I, B)		принадлежит

p( X * ) , или s -й столбец матрицы ( Aт , I ) принадлежит q(Y * ) , но

не тот и другой одновременно. Подчеркнем, что это утверждение имеет силу только для ситуаций равновесия.

266

4.1.4.3. Метод Лемке – Хоусона. Теоретические основы

Механизм алгоритма Лемке – Хоусона заключается в том, чтобы, последовательно двигаясь от одной крайней точки множества Ζ к другой крайней точке, за конечное число шагов найти одну из ситуаций равновесия. Необходимо доказать несколько теорем, на основании которых строится схема движения. Прежде всего нужно получить само множество путей движения. Для этого рассмотрим точки Z = ( X ,Y ) Ζ , удовлетворяющие хотя бы (m + n −1) из ус-

ловий
( fi , X * ) ((ai ,Y * ) −1) = 0 ,	i =1,..., m ,
(e j ,Y * ) ((b j , X * ) −1) = 0 ,	j =1,..., n .	(4.73)
Пусть через H s обозначено множество точек Z Ζ ,		удовле-
творяющих всем этим уравнениям, кроме, возможно, уравнения
(es ,Y * ) ((bs , X * ) −1) = 0 .		(4.74)
Пример 4.2. Построить H1 для биматричной игры, рассмотрен-
ной в примере 4.1. Для Z = (X ,Y ) H1	одновременно должны вы-
полняться соотношения:
y2 = 0 или 0,2x1 + x2 −1 = 0	(прямая 4),
x1 = 0 или 0,25y1 + 0,5y2 −1 = 0	(прямая 1),
x2 = 0 или 0,34 y1 + 0,2 y2 −1 = 0	(прямая 2),
а соотношение
y1 = 0 или 0,5x1 + 0,33x2 −1 = 0	(прямая 3)

может не выполняться.

На рис. 4.4 и 4.5 показаны точки (X ,Y ) (X Χ,Y Υ), принадлежащие множеству H1 . Множество H1 состоит из:

открытого ребра с концом в крайней точке ( X 0 ,Y 0 ) , образо-

ванного точками ( X ,Y 0 ) , где X удовлетворяет условию

0,2x1 + x2 −1 = 0 ;

267

Y2
6
		Многогранник Y
	Y1=0
4
	2
2
		Y0
		1
		Y1	Y2=0
0	2	4	6	Y1
	Рис. 4.4. Проекция s -пути на плоскость Y
X2
6
		Многогранник X
4	X1=0
	X2
2	3
	X0	4
0		X1	X2=0	X2
	2	4	6	X1
	Рис. 4.5. Проекция s -пути на плоскость Χ
		268

открытого ребра с концом в крайней точке ( X 1 ,Y 1 ) , образован-

ного точками ( X 1 ,Y ) , где	Y удовлетворяет условию
0,25y1 + 0,5y2 −1 = 0 ;
неограниченного ребра ( X ,Y 1 )	с концом ( X 1 ,Y 1 ) .

Полученный результат можно обобщить, доказав теоремы 4.5 и 4.6.

Теорема 4.5. Любая точка из H s или является крайней для Ζ , или лежит на открытом ребре Ζ .

Доказательство. Если Z H s удовлетворяет всем (m + n) соотношениям, то она является крайней. Если же она удовлетворяет (m + n −1) из уравнений

( fi , X ) ((ai ,Y ) −1) = 0 ,	i =1,..., m ,
(e j , Y ) ((b j , X ) −1) = 0 ,	j =1,..., n ,

то в силу условий невырожденности выполнены также из соотношений

( fi , X ) = 0,				i =1,..., m,
			= 0,	j =1,..., n,
(b j , X ) −1
				j =1,..., n,
(e j ,Y ) = 0,
(a		,Y ) −1 = 0,		i =1,..., m.
	i

(4.75)

(m + n −1)

(4.76)

Следовательно, эта точка лежит на ребре.

Теорема 4.6. Точка множества H s образует единственное неограниченное ребро многогранника Ζ .

Доказательство. Рассмотрим множество H1 . Пусть Y 1 = k0e1 . При соответствующем k0 точка Y 1 будет крайней для Υ (см. рис. 4.4). Так как (e j ,Y 1 ) = 0 при j ≠1 и этих соотношений всегда

(n −1), то так как Y 1 – крайняя точка Υ , следует, что она должна быть определена еще одним соотношением, например

(ar ,Y 1 ) −1 = 0 . Итак,

269

			q(Y 1 ) = (e2 ,..., en , ar ) .			(4.77)
Для случая, рассмотренного в примере 4.2,					r =1 . При достаточ-
но больших		k точки X = kfr принадлежат			Χ . Пусть	k1 таково,
что	X 1 = k f	r	является крайней точкой	Χ . Поскольку соотноше-
ния	1
			(e j ,Y 1 ) ((b j , X ) −1) = 0 ,	j = 2,..., n ,
			( fi , X ) ((ai ,Y 1 ) −1) = 0 ,	i =1,..., m ,		(4.78)
где	X = kfr ,	(k ≥ k1 ) , выполняются, то можно утверждать, что па-

ры ( X ,Y 1 ) составляют открытое ребро многогранника Ζ , лежащее

в H1 . Точка ( X 1 ,Y 1 ) является концом этого ребра.

Докажем единственность этого ребра. Рассмотрим любое другое неограниченное ребро многогранника Ζ , например ( X ,Y 0 ) , где X = kfl , (l ≠ r) , а Y 0 – крайняя точка множества Υ . Такое ребро

не принадлежит H1 в силу того, что либо условие
( fl , X ) ((al ,Y 0 ) −1) = 0 .	(4.79)
либо одно из условий
(e j ,Y 0 ) ((b j , X ) −1) = 0 , j = 2,..., n ,	(4.80)

не выполняется. Теорема доказана.

Два открытых ребра многогранника Ζ называются смежными, если они имеют общий конец. Последовательность смежных открытых ребер из H s вместе с их концевыми точками называется

s -путем.

При решении задачи, рассмотренной в примере 4.2 (см. рис. 4.4 и 4.5), можно двигаться по следующему s -пути с началом в точке

( X 2 ,Y 1 ) :

двигаемся вдоль неограниченного ребра ( X ,Y 1 ) до точки

( X 1 ,Y 1 ) ;

270