стр. 1
(всего 4)

СОДЕРЖАНИЕ

>>

Министерство образования Российской Федерации
Уральский государственный университет
им. А. М. Горького




УЧЕБНОЕ ПОСОБИЕ




Екатеринбург
Издательство Уральского университета
2001




1
ВВЕДЕНИЕ В ТЕОРИЮ, МЕТОДЫ
И ЭКОНОМИЧЕСКИЕ ПРИЛОЖЕНИЯ ЗАДАЧ О
ДОПОЛНИТЕЛЬНОСТИ

Л.Д.ПОПОВ

2001 год
УДК 519.863 Печатается по решению
ББК 22.18 редакционно-издательского совета
П 58 Уральского государственного университета
им. А.М.Горького



Научный редактор профессор Вл.Д.Мазуров

Рецензенты: кафедра анализа систем и принятия решений Уральского государственного
технического университета; доктор физ.-мат. наук, профессор Н. Н. Астафьев


Попов Л.Д.
Введение в теорию, методы и экономические приложения задач о допол-
П58
нительности: Учеб. пособие. Екатеринбург: Изд-во Урал. ун-та, 2001. 124 с.
ISBN 5–7996–010–6

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


УДК 519.863
ББК 22.18




c Л.Д.Попов, 2001
ISBN 5–7996–010–6
c Уральский государственный
университет, 2001




1
Оглавление

Предисловие 3

Список обозначений 4

1 ЛИНЕЙНЫЕ ЗАДАЧИ О ДОПОЛНИТЕЛЬНОСТИ 5
1. Постановка задачи и истоки . . . . . . . . . . . . . . . . . . . . . . . . 5
2. Основные матричные классы . . . . . . . . . . . . . . . . . . . . . . . . 10
3. Метод Лемке—Хаусона . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4. Сходимость метода для матричных игр . . . . . . . . . . . . . . . . . . 17
5. Применение искусственной переменной . . . . . . . . . . . . . . . . . . 20
6. Другие условия сходимости . . . . . . . . . . . . . . . . . . . . . . . . 23
7. Матрицы с положительными главными минорами . . . . . . . . . . . . 26

2 НЕЛИНЕЙНЫЕ ЗАДАЧИ О ДОПОЛНИТЕЛЬНОСТИ И ВАРИАЦИ-
ОННЫЕ НЕРАВЕНСТВА 30
1. Постановка задач и их взаимосвязь . . . . . . . . . . . . . . . . . . . . 30
2. Теоремы существования и единственности решения . . . . . . . . . . . 36
3. Проекционные методы решения . . . . . . . . . . . . . . . . . . . . . . 46
4. Методы решения второго порядка . . . . . . . . . . . . . . . . . . . . . 52
5. Проксимальное отображение и его свойства . . . . . . . . . . . . . . . 55
6. Метод оценочных функций . . . . . . . . . . . . . . . . . . . . . . . . 57

3 ПОИСК ЭКОНОМИЧЕСКОГО РАВНОВЕСИЯ 63
1. Равновесие по Нэшу в играх n лиц . . . . . . . . . . . . . . . . . . . . 63
2. Прогнозирование потоков в транспортных сетях . . . . . . . . . . . . . 64
3. Пространственное равновесие цен . . . . . . . . . . . . . . . . . . . . . 66
4. Общее экономическое равновесие по Вальрасу . . . . . . . . . . . . . . 68
5. Многоуровневое принятие решений . . . . . . . . . . . . . . . . . . . . 70
1. Достаточные матрицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
2. Метод Данцига—Коттла . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3. Параметрический вариант метода Лемке . . . . . . . . . . . . . . . . . 84

Заключение 89

Список литературы 90




2
ПРЕДИСЛОВИЕ

Вариационные неравенства и линейные и нелинейные задачи о дополнительности
стали изучаться с середины 1960-х годов, начиная с работ Дж.Стампаккьи, К.Лемке,
Дж.Данцига, Р.Коттла и др. Эти постановки сыграли значительную роль в матема-
тическом программировании и являются центральными в моделировании, численном
решении и анализе многих задач в экономических, физических, технических и со-
циальных исследованиях.
В последние десятилетия значительно выросла активность исследований в об-
ласти конечномерных вариационных неравенств и задач о дополнительности. Эта
тенденция вызвана обновленным интересом к применению этих постановок в каче-
стве унифицированного математического аппарата изучения экономических, транс-
портных и теоретико-игровых задач о равновесии — аппарата, который позволил
развить новые, высокоэффективные алгоритмы численного определения такого сорта
равновесия. Вместе с тем в отечественной учебной литературе эта научная область
представлена недостаточно.
Предлагаемое пособие написано на основе зарубежных и отечественных жур-
нальных публикаций, а также оригинального материала и легло в основу лекций,
прочитанных автором студентам 3–4 курсов математико-механического факульте-
та Уральского госуниверситета, специализирующимся на применении математиче-
ских методов и информатики в экономике. В пособие включены основные факты из
качественной теории конечномерных вариационных неравенств и задач о дополни-
тельности, а также краткий обзор методов их решения, главным образом тех, что
используют свойства монотонности входящих в постановки отображений. Отдель-
но разобран случай линейной задачи о дополнительности и рассмотрены конечные
методы ее решения. Приведены разнообразные экономические приложения, в том
числе модели равновесия в транспортных сетях и модель общего экономического
равновесия Вальраса.
Для понимания изложенного достаточно начальных сведений по математическому
программированию и теории игр, выпуклому анализу, микро- и макроэкономике.




3
Список обозначений

Rn — n -мерное евклидово пространство векторов.

x = (x1 , . . . , xn ), y = (yj )m , z, . . . — векторы (в детальной и краткой записи), в матричных вычисле-
ниях — векторы-столбцы.

xi , yj , zk , . . . — их координаты с номерами i, j и k соответственно.

Rn = {x ? Rn : xi ? 0, i = 1, . . . , n} — неотрицательный ортант евклидова пространства.
+
n
xi yi — скалярное произведение векторов x, y.
x y= i=1
v
x x — длина (или норма) вектора x.
x=

x ? y = (x1 y1 , . . . , xn yn ) — векторное произведение Адамара.

A = (aij )n?m , B = (bij )n?n , C = (cij ), . . . — матрицы (с указанием и без указания их размерности).

Ai , Bj , Ck , . . . — их столбцы с номерами i, j и k соответственно.

— матрица, транспонированная к A.
A

diag(a1 , . . . , an ) — диагональная матрица с диагональными элементами a1 , . . . , an .

E — единичная матрица (по диагонали единицы).

A?1 — матрица, обратная к A, т.е. A?1 A = AA?1 = E.

det(A) — определитель матрицы A.

F : Rn > Rn — однозначное отображение Rn в себя.

F (x) = (?Fi (x)/?xj )n?n — матрица Якоби для отображения F (x), вычисленная в точке x.

f : Rn > R — числовая функция векторного аргумента.

f (x) — градиент числовой функции f (x) в точке x.

— частный градиент числовой функции f (x, y) по переменной x в точке (x, y).
x f (x, y)

min{f (x) : gi (x) ? 0, i = 1, . . . , m, x ? X} — задача минимизации числовой функции f (x) на
множестве, заданном системой неравенств и включений.

Arg min f (x) — точки допустимого множества X, в которых достигается наименьшее значение мини-
x?X
мизируемой функции; вообще, если P — некоторая математическая задача, то Arg P — множество
ее решений.




4
Глава 1

ЛИНЕЙНЫЕ ЗАДАЧИ О
ДОПОЛНИТЕЛЬНОСТИ

Линейная задача о дополнительности возникает как обобщение классических по-
становок из линейного и квадратичного программирования и теории матричных игр
и является фундаментальной математической проблемой.

§ 1. Постановка задачи и истоки

Пусть заданы вектор q ? Rn и вещественная (n ? n) -матрица M. Линейной
задачей о дополнительности называется задача решения следующей смешанной
системы неравенств и уравнений, выписанных относительно векторов переменных
w ? Rn и z ? Rn :
w = q + M z, w ? 0, z ? 0, (1.1)
(1.2)
w z = 0.
Нетрудно видеть, что, в силу неотрицательности w и z, множество решений выпи-
санной системы не изменится, если условие (1.2) заменить требованием
wi zi = 0 при всех i = 1, . . . , n. (1.2a)
Будем обозначать сформулированную задачу LCP (q, M ).
Геометрически задача (1.1), (1.2) состоит в поиске неотрицательного вектора, образ
которого при заданном аффинном преобразовании также неотрицателен и ортогона-
лен ему.
Остановимся на некоторых источниках возникновения постановки (1.1), (1.2). В
качестве первого из них укажем на задачи линейного программирования, широкие
прикладные возможности которых при решении технических, экономических, соци-
альных проблем хорошо известны. Выпишем задачу линейного программирования
min{ c x : Ax ? b, x ? 0 } (1.3)
и двойственную к ней задачу
max{ b y : A y ? c, y ? 0 }; (1.4)
здесь x, c ? Rn ; b, y ? Rm ; A — вещественная (m ? n) -матрица. В соответствии с
теорией двойственности задачи (1.3), (1.4) одновременно разрешимы или не разреши-
мы и, если они разрешимы, их оптимальные значения совпадают. Последнее имеет

5
место только в случае совместности систем ограничений в (1.3), (1.4). Поскольку
для всех допустимых x и y верно
y b ? y Ax ? c x,
то решение исходной пары задач сводится к поиску таких допустимых x и y, что
(1.5)
y b = c x.
Ограничения-неравенства в задачах (1.3), (1.4) путем введения дополнительных
неизвестных можно конвертировать в эквивалентные системы уравнений с неотри-
цательными неизвестными. Эти системы вкупе эквивалентны системе
Ax ? v = b, x ? 0, v ? 0,
(1.6)
A y + u = c, y ? 0, u ? 0,
а сама задача линейного программирования — поиску векторов u, v, x, y таких,
что
0 ?A u ? 0, v ? 0,
u c x
(1.7)
= + ,
?b x ? 0, y ? 0,
v A0 y
и, в силу (1.5),
(1.8)
x u + y v = 0.
Нетрудно заметить, что задача (1.7), (1.8) имеет форму линейной задачи о дополни-
тельности (1.1), (1.2), где
0 ?A
u c x
(1.9)
w= , q= , M= , z= .
?b
v A0 y
Другим источником постановок вида (1.1)–(1.2) являются задачи квадратичного
программирования. Пусть задача квадратичного программирования записана в виде
1
x Dx : Ax ? b, x ? 0 }; (1.10)
min{ z(x) = c x +
2
здесь x, c ? Rn ; b ? Rm ; A — вещественная (m ? n) -матрица , D — симметричная
вещественная (n ? n) -матрица. Как известно, целевая функция в (1.10) выпукла,
если только x Dx ? 0 ?x, т. е. матрица D положительно полуопределена. В этом
случае говорят о задаче выпуклого квадратичного программирования. Ясно, что ко-
гда D – нуль-матрица, (1.10) реформируется в задачу линейного программирования
(1.3).
Для задачи (1.10) определим u и v как
u = Dx ? A y + c, v = Ax ? b. (1.11)
В соответствии с теоремой Куна—Таккера вектор x доставляет минимум функции
?
z(x), только если существуют вектор y и векторы u, v такие, что
? ??
u = D? ? A y + c ? 0, v = A? ? b ? 0, x ? 0, y ? 0,
? x ? ? x ? ?
(1.12)
x u = 0, y v = 0.
?? ??
В случае задачи выпуклого квадратичного программирования эти условия являются
и достаточными, так как
1 1
z(x) ? z(?) = c (x ? x) + x Dx ? x D? =
x ? ?x
2 2

6
1
= u (x ? x) + y (v ? v ) + (x ? x) D(x ? x) =
? ? ? ? ? ?
2
1
(x ? x) D(x ? x) ? 0
=u x+y v+
? ? ? ?
2
для любого допустимого вектора x.
Таким образом, задача квадратичного программирования приводит к поиску ре-
шения системы
u = Dx ? A y + c, x ? 0, y ? 0,
(1.13)
v = Ax ? b, u ? 0, v ? 0,
(1.14)
x u + y v = 0.
Очевидно, задача (1.13), (1.14) также имеет форму (1.1), (1.2), где
D ?A
u c x
(1.15)
w= , q= , M= , z= .
?b
v A0 y
Соотношения (1.13)–(1.15) подводят к рассмотрению матриц более общего вида
D ?A
M= ,
AG
где подматрица G, подобно D, положительно полуопределена и симметрична. Мат-
рицы такого вида возникают в связи с так называемой симметричной задачей квад-
ратичного программирования
1
x Dx + y Gy : Ax + Gy ? b, x ? 0, y ? 0 }, (1.16)
min{ c x +
2
и двойственной к ней задачей
1
max{ b y ? x Dx + y Gy : ?Dx + A y ? c, x ? 0, y ? 0 }. (1.17)
2
Все результаты по двойственности в линейном программировании распространяются
и на квадратичный случай.
В качестве последнего примера математических постановок, приводящих к ли-
нейным задачам о дополнительности, рассмотрим биматричную игру ?(A, B) (игру
двух лиц с ненулевой суммой, задаваемую парой вещественных (m ? n) матриц A
и B). Каждая из сторон обладает конечным набором согласованных с правилами
игры способов поведения или чистых стратегий, которые применяет в конкрет-
ной партии (реализации игры) втайне от другой стороны. Предполагается, что ре-
зультат партии полностью определяется выбором чистых стратегий, а именно, если
первый игрок применил свою чистую стратегию с номером i, а второй — чистую
стратегию с номером j, их ожидаемые потери, которые игроки стремятся миними-
зировать, равны величинам aij и bij соответственно. При проведении бесконечной
серии партий с применением игроками смешанных стратегий x = (x1 , . . . , xm ) ? 0,
y = (y1 , . . . , yn ) ? 0, где x 1 = m xi = 1, y 1 = n yj = 1, ожидаемые сред-
i=1 j=1
ние потери игроков составят соответственно x Ay и x By (компоненты смешанных
стратегий выступают как вероятности, с которыми игроки выбирают соответствую-
щие им чистые стратегии в той или иной конкретной партии).
Пара смешанных стратегий (?, y ) называется точкой равновесия по Нэшу в игре
x?
?(A, B), если x A? ? x A? при всех смешанных стратегиях x первого игрока
?y y

7
и x B y ? x By при всех смешанных стратегиях y второго игрока. Такие пары
???
интересны тем, что игрок, придерживающийся своей равновесной стратегии (напри-
мер, x ), фактически вынуждает другого игрока придерживаться его равновесной
?
стратегии (соответственно y ).
?
Точка равновесия в игре ?(A, B), очевидно, не изменится, если A и B заменить
на A = ( aij + a0 ) и B = ( bij + b0 ) соответственно, где a0 и b0 — произвольные
числа. Поэтому без ограничения общности можно считать A > 0, B > 0, что и
будет сделано ниже.
Обозначим через ek вектор размерности k, все компоненты которого равны 1.
Нетрудно видеть, что смешанные стратегии x, y образуют точку равновесия в игре
??
?(A, B), если и только если они предпочтительнее любой из чистых стратегий, т. е.
если
(? A?) em ? A? (1.18)
xy y (A > 0),
(? B y ) en ? B x (1.19)
x? ? (B > 0).
Эта простая характеризация точки равновесия приводит к теореме, связывающей
задачу поиска равновесной пары стратегий с решением системы вида (1.1), (1.2).
Теорема 1.1. Пусть A > 0, B > 0. Если точки x, y удовлетворяют системе
соотношений
u = Ay ? em , u ? 0, y ? 0, (1.20)
v = B x ? en , v ? 0, x ? 0, (1.21)
(1.22)
x u + y v = 0,
то точка x y
(1.23)
(?, y ) =
x? ;
x1 y 1

есть точка равновесия в игре ?(A, B). Обратно, если (?, y ) есть точка равно-
x?
весия в игре ?(A, B), то точки
x
? y
?
x= , y=
x By
?? y A?
?y
удовлетворяют соотношениям (1.20) – (1.22).
Д о к а з а т е л ь с т в о носит выкладочный характер. Пусть соотношения
(1.20)–(1.22) верны. Умножая первые два уравнения на x и y соответственно и
учитывая, что (1.22) влечет равенства x u = = y v = 0, получаем
x Ay = x em = x 1 , x By = y en = y 1 .
Заметим, что величины x 1 и y 1 отличны от нуля, так как иначе u и v из
соотношений (1.20), (1.21) оказались бы отрицательными. С учетом этого для пары
смешанных стратегий из (1.23) имеем

A? ? (? A?) em =
y xy
1 x Ay 1 u
Ay ? (Ay ? em ) = ?0
= em =
y x1 y1 y1
1


и
B x ? (? B y ) en =
? x?

8
1 x By 1 v
B x? B x ? en = ? 0,
= en =
x y1 x x
1 1 1

т. е. эти стратегии удовлетворяют условиям (1.18), (1.19).
Обратно, пусть пара смешанных стратегий (?; y ) удовлетворяет условиям (1.18),
x?
(1.19). В силу положительности платежных матриц A, B имеем x A? > 0, x B y >
?y ??
0. Деля обе части неравенств (1.18), (1.19) на x A? и x B y соответственно, убеж-
?y ??
даемся в справедливости соотношений (1.20)–(1.21). Остается проверить, что

x u + y v = x (Ay ? em ) + y (B x ? en ) =
1 1
(1 ? x em ) + (1 ? y en ) = 0,
= ? ?
x By
?? x A?
?y
т. е. равенство (1.22) также соблюдено.

Очевидно, что система (1.20)–(1.22) имеет форму (1.1), (1.2). Достаточно опреде-
лить
?em
u 0A x
w= , q= , M= , z= .
?en
v B0 y
Заметим, что неравенства A > 0, B > 0 исключают для матрицы M возможность
быть положительно полуопределенной.




9
Упражнения
1. Для симметричных задач квадратичного программирования
(1.16), (1.17) докажите слабую теорему двойственности:
1 1
x Dx + y Gy ? b u ?
c x+ v Dv + u Gu
2 2
для произвольных допустимых пар (x, y) и (u, v) задач (1.16) и (1.17) соответствен-
но. Воспользуйтесь для этого неравенствами 2x Dv ? ? x Dx + v Dv, 2u Gy ?
u Gu + y Gy.
2. Докажите, что из разрешимости задачи (1.16) вытекает разрешимость задачи
(1.17) и совпадение их оптимальных значений. Для этого проведите линеаризацию
прямой задачи в оптимальной точке и включите в рассмотрение решение задачи,
двойственной к линеаризованной.
3. Покажите, что если (?, y ) есть решение задачи (1.16), то найдется такой вектор
x?
v , что пара (?, v ) даст решение двойственной задачи (1.17). Симметрично, если (?, v )
? x? u?
— решение двойственной задачи, то найдется такой вектор x, что пара (?, v ) будет
? x?
решением задачи (1.16).
4. Покажите, что если задачи (1.16), (1.17) разрешимы, то существуют векторы x ?
и v , образующие оптимальную пару (?, v ) одновременно как для прямой, так и для
? x?
двойственной задач.

§ 2. Основные матричные классы

В связи с задачей (1.1)–(1.2) выделяют ряд матричных классов. Перечислим важ-
нейшие из них (все матрицы ниже предполагаются квадратными):
P — класс матриц, все главные миноры которых положительны;
P0 — класс матриц с неотрицательными главными минорами;
P D — класс положительно определенных матриц, т. е. матриц M таких, что
x M x > 0 ?x = 0 ;
P SD — класс положительно полуопределенных матриц, т. е. матриц M таких,
что x M x ? 0 ?x ;
CP — класс коположительных матриц; матрица M коположительна, если x M x ?
0 ?x ? 0 ;
SCP — класс строго коположительных матриц; матрица M строго коположи-
тельна, если x M x > 0 ?x ? 0, x = 0 ;
BG — класс матриц вида
0C
M= ,
B0
где подматрицы B > 0, C > 0, возникает в биматричных играх;
BS — класс бисимметричных матриц, т. е. матриц вида
DG
M= ,
?G F
где подматрицы D и F симметричны и положительно полуопределены;
SS — класс кососимметричных матриц; матрица M кососимметрична, если
M = ?M ;
RS — класс строчно-достаточных матриц; матрица M называется строчно-достаточной,
если XM x ? 0 ? XM x = 0, где X = diag (x1 , . . . , xn ) ;

10
CS — класс столбцово-достаточных матриц; матрица M называется столбцово-
достаточной, если XM x ? 0 ? XM x = 0 ;
— класс достаточных матриц; представляет собой пересечение
S
классов RS и CS.
Связь перечисленных классов по включению показана на рисунке.
Важным (хотя и простым) свойством классов P, P SD, SS, RS, CS и S явля-
ется их полнота в следующем смысле: перечисленные классы содержат все главные
подматрицы своих членов. Напомним также, что для симметричных матриц эквива-
лентны условия:
1) матрица положительно (полу)определена;
2) все ее главные миноры положительны (неотрицательны);
3) все ее собственные значения положительны (неотрицательны).
Поясним включение P D в P и RS и CS в P0 . В силу полноты этих классов до-
статочно установить, что M ? P D ? det (M ) > 0 и M ? RS(CS) ? det (M ) ? 0.
Пусть, от противного, M ? P D и det (M ) ? 0. Поскольку определитель произ-
вольной матрицы равен произведению ее собственных значений, среди последних
найдется ? ? 0 — вещественное и неположительное. Для соответствующего соб-
ственного вектора x(?) = 0 верно x(?) M x(?) = ? x(?) 2 ? 0, что противоречит
положительной определенности M.




11
PD


? ? ?

CP BS - P SD P

6 6
?

SCP SS S - CS

6
? ?
P0
BG RS - 




Связь основных матричных классов


Аналогично пусть M ? CS и det (M ) < 0. Теперь среди собственных значений
матрицы M найдется ? < 0 — вещественное и отрицательное. Для соответствую-
щего собственного вектора x(?) = 0 имеем

X(?)M x(?) = ? diag (x(?)2 , . . . , x(?)2 ) ? 0,
1 n

причем хотя бы одна координата этого вектора отрицательна, что противоречит опре-
делению достаточности M по столбцам.
Наконец, пусть M ? RS. Тогда M ? CS и по доказанному имеем M ? P0 . Но
определитель матрицы при транспонировании не меняется. Поэтому также M ? P0 .
Перечисленные классы матриц и их свойства применяют при выводе теорем суще-
ствования и единственности решения линейной задачи о дополнительности. Часть
этих теорем будет представлена как следствие более общих результатов из раздела,
посвященного нелинейным задачам. Другая часть будет получена ниже конструк-
тивным образом из анализа метода Лемке—Хаусона и различных его обобщений.
В связи с линейными задачами о дополнительности рассматривают еще два важ-
ных матричных класса, определяемых не конструктивно. Это класс Q, состоящий
из матриц, порождающих разрешимые задачи о дополнительности вне зависимости
от выбора вектора свободных членов, и класс Q0 матриц, для которых свойство
разрешимости задачи LCP (q, M ) эквивалентно свойству совместности системы ее
ограничений.
Рассмотрим класс Q0 подробнее. Выпишем условия линейной задачи о дополни-
тельности
w = q + M z, w ? 0, z ? 0, (2.1)
(2.2)
w z = 0,
где матрица M фиксирована, а вектор q меняется. Определим множества

K(M ) = {q : задача (2.1)–(2.2) имеет решение},
K0 (M ) = {q : система условий (2.1) совместна }.


12
Эти множества, очевидно, не пусты (содержат неотрицательный ортант простран-
ства переменых) и являются конусами. При этом K0 (M ) представляет собой конус,
порожденный векторами-столбцами расширенной матрицы
? ?M
M= E ,
n?2n

составленной из матриц E и ?M, так как
q ? K0 (M ) ?? q = w ? M z, где w ? 0, z ? 0.
Множество K(M ) устроено чуть сложнее. Поскольку в любом решении линейной
задачи о дополнительности в каждой паре дополнительных переменных (wi , zi ) по
крайней мере одна из переменных обращается в нуль, то вектор свободных членов
такой задачи лежит в конусе KS , порожденном векторами набора

{Ei : i ? S} {?Mi : i ? S},
/

где S = {i ? {1, . . . , n} : wi = 0}. При этом само множество K(M ) представимо как
объединение таких конусов KS по всем подмножествам S индексного множества
{1, . . . , n}, т. е.
K(M ) = KS .
S?{1,...,n}

Разумеется, K0 (M ) ? K(M ), так как разрешимая задача всегда допустима. Об-
ратное, вообще говоря, не верно.
Теорема 2.1. Множества K(M ) и K0 (M ) совпадают в том и только в том
случае, когда множество K(M ) выпукло.
Д о к а з а т е л ь с т в о. Необходимость вытекает из очевидной выпуклости
конуса K0 (M ). Обратимся к достаточности. Пусть множество K(M ) выпукло. Бу-
дучи объединением конусов, оно само является конусом и по определению выпуклого
конуса содержит все неотрицательные линейные комбинации своих элементов, т. е.
содержит все векторы вида
q = w ? M z, где z ? 0, w ? 0,
так как содержит слагаемые w ? K{1,...,n} и ?M z ? K{?} .
Свойства других матричных классов будут рассматриваться по мере необходимо-
сти.

Упражнения
1. Приведите примеры P -матриц, не являющихся положительно определенными,
и примеры P0 -матриц, не являющихся положительно полуопределенными.
2. Приведите примеры SCP -матриц, не являющихся положительно определенны-
ми.
3. Матрица M называется полумонотонной ( SM -матрицей), если для любого
0 = x ? 0 найдется индекс k такой, что xk > 0 и Mk x ? 0. Покажите, что CP - и
Po -матрицы являются SM -матрицами.
4. Матрица M называется коположительной-плюс, если
x M x ? 0 при всех x ? 0,

13
x ? 0, x M x = 0 ? (M + M )x = 0.
Покажите, что матрица
M1 ?A
M=
A M2
будет коположительной-плюс тогда и только тогда, когда такими будут матрицы M1
и M2 .
5. Покажите, что класс коположительных-плюс матриц включает в себя: а) класс
строго коположительных матриц, б) класс положительно полуопределенных матриц,
в) класс положительных матриц.
6. Покажите, что матрица
? ?
0 ?1 2
M = ? 2 0 ?2 ?
?1 1 0
строчно-достаточна, но не является ни P - ни P D -, ни даже P SD-матрицей.
7. Приведите примеры P0 -матриц, не являющихся строчно(столбцово)-достаточными.

§ 3. Метод Лемке—Хаусона

Рассмотрим итеративную технику Лемке—Хаусона, первоначально разработанную
для нахождения точек равновесия в биматричных играх и в дальнейшем распростра-
ненную Лемке на общий случай линейной задачи о дополнительности.
Выпишем отдельно систему линейных уравнений
(3.1)
w = q + M z,
здесь, как и ранее, n-вектор q и (n ? n)-матрица M заданы, z и w — n-векторы
неизвестных. Неизвестные zi и wi принято называть дополнительными друг к
другу. Решение уравнений (3.1) удовлетворяет условиям дополнительности, если
(3.2)
zi wi = 0, i = 1, . . . , n.
Таким образом, решение задачи LCP (q, M ) есть просто неотрицательное реше-
ние системы (3.1), удовлетворяющее условиям (3.2).
Будем говорить, что решение системы (3.1) почти удовлетворяет условиям до-
полнительности, если zi wi = 0 только для одного значения индекса i, скажем
i = i0 (т. е. zi0 = 0, wi0 = 0 ).
Рассмотрим выпуклое многогранное множество
P = {(w, z) : w = q + M z, z ? 0, w ? 0}.
Напомним, что его крайними точками (вершинами) называют точки, не являющие-
ся внутренними ни для одного из лежащих в нем нетривиальных отрезков. Крайние
точки множества P тесно связаны с допустимыми базисными решениями систе-
мы (3.1), т. е. решениями, ненулевым компонентам которых соответствуют линейно
независимые столбцы матрицы ее коэффициентов. Понятно, что такие решения не
могут содержать более n ненулевых компонент. Если число ненулевых компонент
равно n, базисное решение принято называть невырожденным. Невырожденной на-
зывается и система уравнений, все базисные решения которой не вырождены. При

14
предположении о невырожденности системы (3.1) крайние точки множества P нахо-
дятся с допустимыми базисными решениями системы (3.1) во взаимно-однозначном
соответствии.
Процедура Лемке основана на переборе крайних точек множества P. Она от-
талкивается от начала некоторого луча (неограниченного ребра множества P ), со-
стоящего из точек ? = (w, z), почти удовлетворяющих условиям дополнительности,
т. е. точек, у которых zi wi = 0 для всех i = 1, . . . , n за исключением некоторого
i = i0 . Для произвольной матрицы M найти такую стартовую точку не просто.
Исключение составляют, пожалуй, только два важных случая: первый связан с би-
матричными играми (они будут рассмотрены ниже), второй — с наличием в матрице
M положительного столбца. Этот положительный столбец, впрочем, всегда можно
ввести в задачу искусственно, что является полезным приемом при инициировании
процедуры Лемке и ей подобных в общем случае.
Каждая итерация метода Лемке соответствует (как и в обычном симплекс-методе
в линейном программировании) движению из крайней точки ? (k) многогранного
множества P вдоль некоторого его ребра, почти удовлетворяющего условиям допол-
нительности. Если это ребро ограничено, такое движение заканчивается в смежной
крайней точке ? (k+1) , которая или также почти удовлетворяет условиям дополни-
тельности, или удовлетворяет им точно. Процесс прекращается, если текущее ребро
не ограничено, или точка ? (k+1) уже генерировалась ранее, или она удовлетворяет
условиям дополнительности точно (т. е. является решением исходной задачи).
Как уже оговаривалось, при стандартном предположении о невырожденности си-
стемы (3.1) крайние точки множества P находятся во взаимно-однозначном соот-
ветствии с допустимыми базисными решениями (3.1). При этом же предположении
допустимое базисное решение будет удовлетворять условиям (3.2), только если из
каждой дополнительной пары неизвестных (zi , wi ) ровно одна является небазисной
(свободной). Цель алгоритма — получить допустимое базисное решение с указанным
свойством.
В невырожденном допустимом базисном решении, почти удовлетворяющем усло-
виям дополнительности, имеется ровно одна пара неизвестных, скажем zi0 и wi0 ,
из которых обе являются базисными. Будем называть эту пару базисной. Соот-
ветственно существует ровно одна дополнительная пара (zj0 , wj0 ) такая, что обе
ее неизвестные свободны. Будем называть ее небазисной (свободной) парой неиз-
вестных. Ребро, точки которого почти удовлетворяют условиям дополнительности,
получается из текущего допустимого базисного решения путем наращивания зна-
чения одной из неизвестных, входящих в небазисную пару. Все прочие небазисные
неизвестные остаются на нулевом уровне. Поэтому для каждой крайней точки, свя-
занной с базисным решением, почти удовлетворяющим условиям дополнительности,
существует ровно два ребра, исходящих из нее и обладающих тем же свойством
[т. е. почти удовлетворяющих условиям (3.2)].
Пусть zj0 — наращиваемая неизвестная небазисной пары. Вместе с ее ростом
будут линейно изменяться и значения всех базисных неизвестных. При достаточно
малых положительных значениях zj0 свойство допустимости решения будет сохра-
няться. Это является следствием предположения о невырожденности системы (3.1).
Однако при значительном росте zj0 допустимость может быть утеряна.
Если значение zj0 может быть сделано сколь угодно большим без того, чтобы
какая-либо базисная неизвестная приняла отрицательное значение, перед нами луч
— неограниченное ребро множества P. В этом случае процесс завершается (без
получения решения исходной задачи). Если же рост неизвестной zj0 блокирует-

15
ся некоторой базисной неизвестной (той, что в процессе убывания первой достигает
нулевого уровня), мы приходим к новому базисному решению. Если неизвестная, по-
кинувшая базис, принадлежит базисной паре, перед нами решение исходной задачи.
В противном случае имеем очередную крайнюю точку множества P, почти удовле-
творяющую условиям дополнительности. В этой точке наращиваемая и блокирующая
неизвестные поменялись ролями: первая вошла в число базисных, а вторая — в число
свободных неизвестных.
Главное правило метода Лемке касается выбора очередной наращиваемой (вво-
димой в базис) неизвестной. А именно, наращивается значение той неизвестной,
которая является дополнительной к неизвестной, покинувшей базис на предыдущем
шаге (итерации).
Генерируемая последовательность крайних точек, почти удовлетворяющих усло-
виям (3.2), образует своего рода путь (путь Лемке) по границе множества P.

Теорема 3.1. Вдоль пути, почти удовлетворяющего условиям дополнительно-
сти, только исходное базисное решение может встретиться дважды.
Д о к а з а т е л ь с т в о с очевидностью следует из того, что каждое допустимое
базисное решение, почти удовлетворяющее условиям дополнительности, связано не
более чем с двумя другими такими точками. Поэтому, войдя и выйдя из такой точки,
мы уже не можем в нее вернуться.

Следствие 3.1. Если путь Лемке был начат из конца луча, почти удовлетво-
ряющего условиям дополнительности, то метод прервется или на другом таком
луче (называемом альтернативным), или на решении исходной задачи.

ПРИМЕР. Рассмотрим задачу LCP (q, M ), где
? ? ? ?
1 121
q = ? ?1 ? , M = ? 1 1 2 ? .
1 211
Ее уравнения имеют вид

w1 = 1 + z1 + 2z2 + z3 ,
w2 = ?1 + z1 + z2 + 2z3 ,
w3 = 1 + 2z1 + z2 + z3
или в табличной форме
z1 z2 z3
w1 1121 2
?1 1 1 2
w2 0
w3 1211 3
100
Начальный луч отвечает зафиксированному значению переменных z2 = z3 = 0 и
свободному изменению переменной z1 в диапазоне от 1 до +?. Значение z1 = 1
является минимальным, при котором базисные переменные w1 , w2 , w3 неотрица-
тельны, причем w2 обращается в нуль. Меняем ролями переменные z1 и w2 . Пер-
вая из них становится базисной, вторая — свободной. Разрешая исходную систему


16
относительно переменных w1 , z1 , w3 , приходим к эквивалентной системе

w1 = 2 + w2 + z2 ? z3 ,
z1 = 1 + w2 ? z2 ? 2z3 ,
w3 = 3 + 2w2 ? z2 ? 3z3
или в табличной форме
w2 z2 z3
2 ?1 2
w1 2 1
1 ?1 ?2 1
z1 1
2 ?1 ?3 3
w3 3
0 0 0
Далее вводим в базис переменную z2 , которая является дополнительной к пе-
ременной w2 , покинувшей базис на предыдущем шаге. Рост значения переменной
z2 блокируется базисной переменной z1 , которая, убывая, раньше других базисных
переменных обращается в нуль. Поэтому переменная z1 покидает базис, а исходная
система приобретает вид

w1 = 3 + 2w2 ? z1 ? 3z3 ,
z2 = 1 + w2 ? z1 ? 2z3 ,
w3 = 2 + w2 + z1 ? z3
или в табличной форме
w2 z1 z3
2 ?1 ?3 3
w1 3
1 ?1 ?2 1
z2 1
1 ?1 2
w3 2 1
0 0 0
Полученное базисное решение (w, z) = (3, 0, 2; 0, 1, 0) удовлетворяет условиям
дополнительности, т. е. является решением исходной задачи.
В принципе, если в качестве начальной точки брать не конец некоторого луча, в
методе Лемке можно столкнуться с явлением зацикливания. Зацикливание означает,
что после некоторого числа шагов метод возвращается к исходной точке. Вместе с
тем даже если исходная задача разрешима, метод с правильно выбранной точки
может тем не менее завершиться на альтернативном луче.

§ 4. Сходимость метода для матричных игр

Дадим алгебраическую интерпретацию завершению метода на альтернативном лу-
че.

Лемма 4.1. Пусть (w, z) — допустимое базисное решение системы (3.1), по-
чти удовлетворяющее условиям дополнительности. Если оно инцидентно лучу,
точки которого также почти удовлетворяют условию (3.2), то существуют
n -векторы w и z такие, что
? ?
w = M z , w ? 0, z ? 0, z = 0, (4.1)
? ?? ? ?


17
причем точки луча имеют вид

(w + ?w, z + ??), ? ? 0, (4.2)
? z

и удовлетворяют условию

(wi + ?wi )(zi + ??i ) = 0 при всех i = 1, . . . , n, i = i0 . (4.3)
? z

Д о к а з а т е л ь с т в о очевидно. Подчеркнем, что индекс i0 не меняется
вдоль всего пути Лемке. Смена его означала бы, что одна из неизвестных исходной
базисной пары покинула базис, что является признаком получения искомого решения
и завершения работы алгоритма в целом.
Лемма 4.1 позволяет сформулировать первый результат о существовании решения
линейной задачи о дополнительности.
Теорема 4.1. Если M > 0, то система (3.1) при любом q имеет хотя бы одно
допустимое базисное решение, удовлетворяющее условиям дополнительности.

Д о к а з а т е л ь с т в о. В качестве начальных базисных неизвестных выбе-
рем w1 , . . . , wn . Если q ? 0, этот базис немедленно дает решение исходной задачи,
а именно вектор (q; 0). В противном случае присоединим к множеству ненулевых
неизвестных неизвестную z1 . Поскольку M > 0, то при достаточно большом зна-
чении z1 > 0 все wi , где i = 1, . . . , n, также будут положительны. Постепенно
снижая значение z1 , остановимся на таком его значении, при котором одна из базис-
ных неизвестных, единственная в силу предположения о невырожденности системы
(3.1) , обратится в нуль. Стартовая крайняя точка пути Лемке получена.
Строим путь Лемке, применяя описанные выше правила. По следствию 3.1 из
теоремы 3.1 процесс прервется или по достижении решения исходной задачи, или
по выходу на неограниченное ребро (луч) множества P. Покажем, что последнее
невозможно. В самом деле, если бы это было так, мы столкнулись бы с выполнением
условий (4.1)—(4.3), где i0 = 1. Поскольку M > 0 и z ? 0, то w > 0. Отсюда,
? ?
в силу (4.3), zi = zi = 0 при всех i = 1. Следовательно, z1 — единственная
?
изменяющаяся вместе с ? неизвестная (наряду с компонентами w1 , . . . , wn ). Но это
значит, что конечный луч совпадает с начальным, что по следствию 3.1 невозможно.

Обоснование следующего факта требует модификации схемы выбора начальной
точки.

Теорема 4.2. Биматричная игра ?(A, B) разрешима, и ее решение можно по-
лучить методом Лемке.
Д о к а з а т е л ь с т в о. Инициируем алгоритм, выбрав наименьшее положи-
тельное значение неизвестной z1 , при котором
v = ?en + B1 z1 ? 0, (4.4)

здесь B1 — первый столбец матрицы B . Из стандартного предположения о невы-
рожденности системы уравнений задачи о дополнительности, ассоциированной с иг-
рой ?(A, B), следует, что вектор v имеет ровно одну нулевую компоненту, скажем
vr . Требуемый луч формируется путем ввода в базис неизвестной z1 и всех допол-
нительных неизвестных u и v, кроме vr . Дополнительная к vr неизвестная wr

18
выбирается в качестве той небазисной неизвестной, которая может расти неограни-
ченно. Очевидно, что при достаточно большом ее значении все базисные неизвестные
также положительны, причем точки луча почти удовлетворяют условиям оптималь-
ности. Единственная пара неизвестных, которая может дать ненулевое произведение,
— это (z1 , u1 ). Понижая постепенно значение неизвестной wr , при некотором ее по-
ложительном значении получаем начальную крайнюю точку пути Лемке.
Покажем, что реализация шагов рассматриваемого алгоритма не может завер-
шиться на альтернативном луче. В самом деле, если бы это было так, мы получили
бы точки вида
?em
u + ??
u 0A z + ??
z
(4.5)
= + ,
?en
v + ??
v B0 w + ?w
?
где ? ? 0 — любое и
при всех i = 1, (4.6)
(ui + ??i )(zi + ??i ) = 0
u z

при всех j. (4.7)
(vj + ??j )(wj + ?wj ) = 0
v ?
Предположим, что z = 0. Тогда v = B z > 0. В силу (4.7), wj + ?w = 0 при всех
? ? ? ?
j и всех ? ? 0. Но тогда u + ?? = ?em < 0, чего не может быть. Поэтому z = 0.
u ?
Пусть далее w = 0. Тогда u = Aw > 0. В силу (4.6), zi = 0 при всех i = 1 и zi = 0
? ? ? ?
при всех i. Отсюда v = B z = 0 и v есть то же самое, что и в (4.4), поскольку
? ?
начальное значение z1 выбиралось наименьшим среди тех, для которых (u, v, z, w)
— крайняя точка. По предположению невырожденности только vr = 0, а все прочие
vj > 0, j = r. Следовательно, условие (4.7) влечет равенство wj + ?wj = 0 при всех
?
j = r. В результате мы установили, что конечный луч совпадает с начальным, что
по следствию 3.1 невозможно. Значит, алгоритм не может завершиться на луче. Он
завершается на решении исходной задачи.
ПРИМЕР. Рассмотрим задачу LCP (q, M ), где
? ? ? ?
?1 012
q = ? ?1 ? , M = ? 0 2 1 ? .
?1 100
Ее уравнения имеют вид

w1 = ?1 + z2 + 2z3 ,
w2 = ?1 + 2z2 + z3 ,
w3 = ?1 + z1
или в табличной форме
z1 z2 z3
?1 0 1 2
w1 1
?1 0 2 1
w2 0
?1 1 0 0
w3 0
101
Устанавливая свободные переменные z1 , z2 , z3 в нуль, получаем отрицательные
значения базисных переменных w1 = w2 = w3 = ?1. Наращивая далее z1 до зна-
чения z1 = 1, обеспечиваем неотрицательность переменной w3 . Далее, поскольку

19
w3 = 0, следует наращивать дополнительную к ней переменную z3 . Наращиваем ее
до значения z3 = 1, при котором остальные базисные переменные w1 , w2 становятся
также неотрицательными. Поскольку вторая из них фактически обращается в нуль,
она заменяется в базисе на переменную z3 . Разрешая исходные уравнения относи-
тельно нового набора базисных переменных w1 , z1 , z3 , получаем эквивалентную
систему
w1 = 1 + 2w2 ? 3z2 ,
z3 = 1 + w2 ? 2z2 ,
z1 = 1 + w3
или в табличной форме
w2 z2 w3
2 ?3
w1 1 01
1 ?2
z3 1 01
z1 1 0 0 11
0 0 0
Вводим в базис переменную z2 , дополнительную к последней покинувшей ба-
зис переменной w2 . Рост значения переменной z2 блокируется базисной переменной
w1 , которая, убывая, первой из базисных переменных обращается в нуль. Разре-
шая уравнения задачи относительно нового набора базисных уравнений, получаем
систему
1
+ 2 w2 ? 1 w1 ,
z2 = 3 3 3
1
? 1 w2 + 2 w1 ,
z3 = 3 3 3
z1 = 1 + w3
или в табличной форме
w2 w1 w3
1 2
?1 1
z2 0
3 3 3 3
1
?1 2 1
z3 0
3 3 3 3
z1 1 0 0 11
0 0 0
Эта таблица последняя, так как соответствующее ей базисное решение (w, z) =
(0, 0, 0; 1 , 1 , 1) допустимо и удовлетворяет условиям дополнительности.
33
При доказательстве приведенных выше утверждений использовалось предполо-
жение о невырожденности системы уравнений в (3.1). Это предположение можно
обойти за счет лексикографического правила выбора неизвестной, покидающей ба-
зис, так же, как это делается в линейном программировании при обосновании ко-
нечности симплекс-метода

§ 5. Применение искусственной переменной

Перейдем к изучению линейной задачи о дополнительности с матрицами более
общего вида. Нам придется ввести в систему ее уравнений дополнительную пере-
менную z0 :
w = q + en z0 + M z, где en = (1, 1, . . . , 1) . (5.1)
n




20
Переменная z0 называется искусственной и призвана обеспечить наличие стар-
тового допустимого базисного решения. Она играет роль своеобразного параметра,
начальное положительное значение которого в ходе вычислений будет доведено до
нуля. Решение параметризованной системы (5.1) будем называть почти удовлетво-
ряющим условиям дополнительности, если zi wi = 0 при всех i = 1, . . . , n, и
удовлетворяющим условиям дополнительности точно, если также z0 = 0. Обо-
значим
P0 = {(w, z0 , z) : w = q + en z0 + M z z0 ? 0, z ? 0, w ? 0}.
Пусть вначале неизвестные w1 , . . . , wn составляют базис, а прочие неизвестные
z0 , z1 , . . . , zn остаются свободными Придавая неизвестной z0 достаточно большое
положительное значение ?, можно добиться того, чтобы выполнялось неравенство
w = q + en z0 > 0.
При снижении значения z0 значения неизвестных wi также будут понижаться. На-
чальная для метода Лемке крайняя точка множества P0 получится при минимальном
значении z0 ? 0, обеспечивающем неравенство w = q + en z0 ? 0. Если z0 = 0, то
q ? 0 и исходная задача имеет очевидное решение — вектор (q; 0). В противном
случае z0 > 0 и среди компонент вектора w ровно одна, скажем wr , обращена
в нуль. Вводим z0 в базис на место неизвестной wr , которая переходит в разряд
свободных.
Далее применяем правило Лемке выбора очередной вводимой в базис неизвестной,
т. е. на очередном шаге вводим в базис неизвестную, которая является дополнитель-
ной к неизвестной, покинувшей базис на предыдущем шаге. Покидающая базис неиз-
вестная определяется стандартным образом как неизвестная, которая, убывая, первой
достигает нулевого уровня. Если все старые базисные неизвестные при наращивании
вводимой в базис свободной неизвестной не убывают, алгоритм завершает работу на
альтернативном луче без получения решения исходной задачи. Если покидающей
базис неизвестной оказывается z0 , алгоритм завершается по причине получения ис-
комого решения (оно получается, если все свободные неизвестные приравнять нулю,
а прочие определить из системы уравнений w = q+M z ). Если, наконец, покинувшая
базис неизвестная отлична от z0 , алгоритм переходит к следующей итерации.
ПРИМЕР. Рассмотрим задачу LCP (q, M ), где
? ? ? ?
?3 0 ?1 2
q = ? 6 ? , M = ? 2 0 ?2 ? .
?1 ?1 1 0
Ее уравнения (вместе с включенной в них искусственной переменной z0 ) имеют вид
w1 = ?3 + z0 ? z2 + 2z3 ,
? 2z3 , (5.2)
w2 = 6 + z0 + 2z1
w3 = ?1 + z0 ? z1 + z2 .
Далее для краткости будем использовать только их табличное представление
z0 z1 z2 z3
?3 1 0 ?1
w1 20
0 ?2 9 (5.3)
w2 61 2
?1 1 ?1
w3 1 02
3 0 0 0

21
Пусть z1 = z2 = z3 = 0. Минимальное значение искусственной переменной z0 ,
при котором базисные переменные w1 , w2 , w3 оказываются неотрицательными, рав-
но 3. При этом w1 = 0.
Вводим искусственную переменную z0 в базис на место переменной w1 . Табли-
ца, отвечающая системе (5.2), разрешенной относительно нового набора базисных
переменных z0 , w2 , w3 , служит начальной для метода Лемке
w1 z1 z2 z3
1 ?2 3
z0 31 0
1 ?4 9
w2 91 2
2 1 ?1 2 ?2 2
w3
00 0 0
Следующей в базис будет вводиться переменная z1 , которая является дополни-
тельной к покинувшей базис переменной w1 . Переменная w3 , чье место займет z1 ,
определяется по единственному отрицательному элементу столбца при вводимой в
базис переменной. Преобразованная таблица примет вид
w1 w3 z2 z3
0 1 ?2 3
z0 3 1
13 3 ?2 5 ?8 13
w2
1 ?1 2 ?2 2
z1 2
0 00 0
Теперь в базис следует ввести переменную z3 . Блокирующая ее рост переменная
z1 покидает базис. В результате приходим к таблице
w1 w3 z2 z1
1 ?1
z0 10 11
5 ?1 2 ?3
w2 45
1
?1 1 ?1
z3 1 1
2 2 2

0 0 0 0
Продолжая следовать правилам алгоритма, вводим в базис переменную w1 , кото-
рая заменяет там переменную w2 . Разрешая уравнения (5.2) относительно z0 , w1 , z0 ,
получаем четвертую таблицу
w2 w3 z2 z1
?1
z0 1 01 1 1
?1 2 ?3
w1 5 4 5
7
?1 1
?1 3 7
z3 2 2 2 2 2 2

0 0 0 0
Завершает работу смена ролей переменных z0 и z2 :
w2 w3 z0 z1
1 ?1 1
z2 1 0 1
?1 ?1
w1 2 31 2
3 ?1 1
z3 0 1 3
2 2

0 0 0 0

22
Поскольку искусственная переменная покинула базис, вектор
z0
(w, z) = (2, 0, 0; 0, 1, 3) дает решение исходной задачи.

§ 6. Другие условия сходимости

Рассмотрим теперь вопрос, какой должна быть матрица M, чтобы описанный
выше процесс заканчивался на альтернативном луче только в случае неразрешимости
исходной задачи.
Теорема 6.1. Завершение метода Лемке на луче влечет существование такого
ненулевого неотрицательного вектора z , что
?
zi (M z )i ? 0, i = 1, . . . , n. (6.1)
? ?
Д о к а з а т е л ь с т в о. Ясно, что завершение алгоритма на альтернативном
луче возможно только, если мы получаем допустимое базисное решение (w, z0 , z)
системы (5.1), которое соответствует крайней точке множества P0 , и для которой
существует определяющее этот луч направление (w, z0 , z ) такое, что
?? ?
w = en z0 + M z , (w, z0 , z ) ? 0, (6.2)
? ? ? ?? ?
и при всех ? ? 0 выполняются условия
(6.3)
w + ?w = q + en (z0 + ??0 ) + M (z + ??),
? z z
(6.4)
(wi + ?wi ) (zi + ??i ) = 0, i = 1, . . . , n.
? z
Случай z = 0 невозможен, так как иначе z0 и затем w > 0 (поскольку (w, z0 , z ) =
? ? ? ?? ?
0 ). Последнее, в силу (6.4), значило бы, что z + ?? = z = 0, т. е. конечный луч
z
совпадает с начальным.
Далее, так как все точки луча почти удовлетворяют условиям дополнительности,
то
(6.5)
zi wi = zi wi = zi wi = zi wi = 0, i = 1, . . . , n.
? ? ??
Выпишем уравнения системы (6.2) отдельно в виде
(6.6)
wi = z0 + (M z )i , i = 1, . . . , n.
? ? ?
Умножение (6.6) почленно на zi приводит, в силу (6.5), к равенствам
?
(6.7)
0 = zi z0 + zi (M z )i , i = 1, . . . , n.
?? ? ?
Отсюда вытекает искомое неравенство.
Опираясь на теорему 6.1, можно выделить классы матриц, для которых из условий
(6.1) вытекала бы неразрешимость исходной задачи (например, несовместность си-
стемы ее ограничений). Одним из таких классов является класс коположительных-
плюс матриц, другим — уже упоминавшийся класс строчно-достаточных матриц.
Матрица M называется коположительной-плюс, если она удовлетворяет услови-
ям
x M x ? 0 при всех x ? 0, (6.8)
при всех x ? 0, x M x = 0. (6.9)
(M + M )x = 0
Класс таких матриц достаточно широк и, в частности, включает в себя

23
1) класс строго коположительных матриц, т. е. таких матриц M, для которых
x M x > 0 при всех 0 = x ? 0 ;
2) класс положительно полуопределенных матриц, т. е. таких M, что x M x ? 0
при всех x.
Положительные матрицы очевидно строго коположительны. Однако, как показы-
вают примеры, матрицы вида
0A
, где A > 0, B > 0,
M=
B0
не обязательно удовлетворяют условиям (6.9). Из матриц M1 и M2 , удовлетворяю-
щим условиям (6.8),(6.9), можно составить блочные матрицы вида
M1 0
M= ,
0 M2
которые также оказываются коположительными-плюс. Более того, если S — косо-
симметричная матрица, то M +S также будет коположительной-плюс. Следователь-
но, блочная матрица вида
M1 ?A
M=
A M2
будет коположительной-плюс тогда и только тогда, когда такими будут M1 и M2 .
При доказательстве следующей теоремы будет использоваться факт, что система
w = q + M z, z ? 0, w ? 0,
не имеет решений, если найдется вектор v такой, что
v M ? 0, v q < 0, v ? 0 (6.10)
(иначе получаем противоречие 0 ? v w = v q + v M z < 0 ).
Теорема 6.2. Пусть матрица M — коположительная-плюс и метод Лемке
завершается на луче. Тогда исходная задача не имеет допустимых решений.
Д о к а з а т е л ь с т в о. Завершение на луче означает, что достигнуто некоторое
допустимое базисное решение (w, z0 , z), удовлетворяющее условиям (6.2)–(6.4), где
(6.11)
0 = z w = z en z0 + z M z .
?? ? ? ? ?
Поскольку M — коположительная-плюс и z ? 0, оба слагаемых в правой части
?
(6.11) неотрицательны и потому равны нулю. Скаляр z0 = 0, потому что z en > 0.
? ?
Равенство нулю квадратичной формы по предположению
z Mz
? ?
означает, что
M z + M z = 0.
? ?
В силу (6.2), равенство z0 = 0 влечет w = M z ? 0, т. е. по предыдущему M z ? 0
? ? ? ?
или, что то же, z M ? 0. Далее, уже в силу (6.5),
?
0 = z w = z M z = z (?M z ) = z M z
? ? ? ?
и снова, в силу (6.5),
0 = z w = z q + z en z0 + z M z = z q + z en z0 .
? ? ? ? ? ?

24
Поэтому z q < 0, так как z en z0 > 0. Следовательно, имеет место (6.10) при
? ?
v = z , и исходная задача о дополнительности не имеет допустимых точек.
?
Анализ проведенного доказательства позволяет усилить последний результат для
строго коположительных матриц, поскольку для них равенство нулю квадратичной
формы z M z на неотрицательном ортанте возможно лишь при z = 0.
? ? ?
Следствие 6.1. Если M строго коположительна, метод Лемке завершается
получением допустимого базисного решения системы (5.1), которое удовлетво-
ряет условиям дополнительности.
Это следствие обобщает, очевидно, результат теоремы 4.1.
В заключение заметим, что в методе Лемке искусственный столбец не обязан
состоять из единиц. Достаточно, чтобы он просто был положителен. Более того,
удачный выбор искусственного столбца гарантирует сходимость метода Лемке не
более чем за n + 1 итерацию.
Теорема 6.3. Пусть M — невырожденная (n?n)-матрица. Предположим, что
существует положительный вектор p, удовлетворяющий условиям
(MLL )?1 pL ? 0 ?L ? {1, . . . , n}; (6.12)
здесь MLL — главная подматрица, получаемая из M удалением строк и столб-
цов с номерами, не входящими в L; то же касается pL . Тогда метод Лемке
с p, взятым в качестве столбца при искусственной неизвестной, завершится
получением решения LCP (q, M ) не более чем через n + 1 итерацию.
Д о к а з а т е л ь с т в о. Рассмотрим очередную (после первой) итерацию метода
Лемке. Пусть индексное множество L состоит из номеров базисных z -переменных
и пусть индекс t ? L обозначает текущую небазисную пару (wt , zt ), а K — допол-
/
нение {t}?L до {1, . . . , n}. Предположим, что неизвестная wt только что покинула
базис и потому следующая вводимая в базисе неизвестная — zt . Преобразованная
система уравнений имеет следующую структуру:
? ?
? wL
? ????
zL F
? ? wt ? .
? ?
? z0 ? = ? ? + ? f0 ? zt ?
wK
zK
zL
В этом представлении нас интересует (и показан) только -блок ведущего
z0
столбца
?1
F MLL pL MLt
=? .
f0 MtL pt Mtt
Более аккуратные вычисления дают нам
?1
Mtt ? MtL MLL MLt ?1 ?1
MLL pL ? MLL MLt . (6.13)
F= ?1
pt ? MtL MLL pL
?1
Здесь знаменатель отличен от нуля, в силу существования MLL и невырожденности
базисной матрицы
MLL pL
B= .
MtL pt

25
По условию (6.12)
?1
pL
? MLL MLt pL
? 0.
=
pt
? MtL Mtt pt
Более точно
?1
pt ? MtL MLL pL
?1 ?1
pL ?
pL =
? MLL MLL MLt ,
?1
Mtt ? MtL MLL MLt
?1 ?1
pL = (pt ? MtL MLL pL ) / (Mtt ? MtL MLL MLt ).
?
Снова невырожденность M гарантирует здесь неравенство нулю знаменателя.
Таким образом, (6.13) показывает, что интересующие нас zL -элементы ведущего
столбца равны
F = pL /?t ? 0.
?p
Следовательно, рост вводимой в базис неизвестной zt не повлечет убывания zL -
неизвестных, уже находящихся в базисе, и очередное исключение может иметь место
или в z0 -строке (в этом случае мы получаем решение исходной задачи), или в
одной из wK -строк (в этом случае множество L пополняется новым номером и все
рассуждения можно повторить сначала). Завершение на луче невозможно, так как
по крайней мере один элемент ведущего столбца отрицателен, а именно
f0 = ?1/?t < 0.
p
Подытожим сказанное. Метод начинает работу, когда неизвестные z и z0 ле-
жат вне базиса. Первая итерация состоит в вводе в базис неизвестной z0 (в итоге
получается первое допустимое базисное решение, почти удовлетворяющее условиям
дополнительности). На каждой последующей итерации множество L, первоначаль-
но пустое, пополняется номером вводимой в базис z -неизвестной. Поскольку таких
неизвестных n, решение будет получено не более чем через n + 1 итерацию.
Разумеется, поиск подходящего вектора при искусственной переменной в методе
Лемке сам может потребовать значительных вычислительных затрат.

§ 7. Матрицы с положительными главными минорами

Обратимся к другому важному матричному классу — классу матриц, все главные
миноры которых положительны.
Лемма 7.1. Пусть M — P -матрица. Тогда система неравенств
M z ? 0, z ? 0, (7.1)
имеет единственное решение z = 0.
Д о к а з а т е л ь с т в о. Утверждение очевидно при n = 1. Предполагая,
что оно верно при размерности M, меньшей некоторого n, покажем, что оно верно
и для n. Пусть z = (z1 , . . . , zn ) удовлетворяет системе (7.1). Так как M — P -
матрица, то M не вырождена и диагональные элементы обратной к ней матрицы
M ?1 = (?ij ) положительны. Поэтому каждый столбец матрицы M ?1 , в том числе
первый (обозначим его через b ), имеет хотя бы одну положительную компоненту.
Пусть
zi
по всем ?i1 > 0
? = min
?i1

стр. 1
(всего 4)

СОДЕРЖАНИЕ

>>