<<

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

СОДЕРЖАНИЕ

m?1 m?1
?k (Fi (xk ), k
?k (Fi (x), x ? xk ) ? 0
? x?x )? ?x ? Xm?1 ,
i i
i=1 i=1

здесь использовались неравенства (Fi (x), x ? xk ) ? 0, которые верны благодаря
определению множеств Xi и их последовательной вложенности друг в друга.

В качестве примера условий, при которых решения задач VI (X, F? ) существуют
и ограничены при малых ?2 , . . . , ?m в совокупности, приведем следующее:
6 . Существует точка x0 ? X и окружающий ее компакт D такие, что (F1 (x), x?
x0 ) > 0 при всех x ? D ? X.
Напомним, что множество D окружает точку x0 , если для любого l существует
? = ?(l) > 0 такое, что x0 + ?l ? D (простейшим примером окружающего множества
является сфера {x : x ? x0 = r} с центром в точке x0 и радиусом r > 0 ).

Теорема 5.3. Пусть выполнены условия 1, 2 и 6. Тогда при постоянном ?1 >
0 и всех достаточно малых ?2 > 0, . . . , ?m > 0 задачи VI (X, F? ) разрешимы и их
решения ограничены в совокупности.




74
Д о к а з а т е л ь с т в о. Для обоснования разрешимости задачи VI (X, F? ) по-
кажем, что для всех достаточно малых ?2 > 0, . . . , ?m > 0 существует ограниченное
множество M (?), обладающее свойством: для любой точки x ? X \ M (?) найдется
точка y ? M (?) со свойством
(F ? (x), x ? y) > 0

(это достаточные условия существования решения монотонного вариационного нера-
венства с непустым выпуклым замкнутым исходным множеством X и с непрерыв-
ным оператором, каковым при сделанных предположениях является F ? ).
В самом деле, можно взять M (?) = M = conv D и y = x0 . Выполнимость нера-
венства (F ? (x), x ? x0 ) > 0 для всех x ? X \ M следует из монотонности F ? и
того, что это неравенство при достаточно малых ?2 > 0, . . . , ?m > 0 выполняется для
любой точки из D, в том числе точки, принадлежащей отрезку, соединяющему x0
и x . Действительно, пусть z — такая точка. Тогда при некоторых µ1 > 0, µ2 > 0
имеем
x ? x0 = µ1 (x ? z) = µ2 (z ? x0 ),
и потому
(F ? (x), x ? x0 ) = µ1 (F ? (x), x ? z) ? µ1 (F ? (z), x ? z) =
= µ2 (F ? (z), z ? x0 ) > 0.
Ограниченность множеств решений вытекает из того, что все они лежат в M, а M
в нашем случае не зависит от ? .

Легко привести и другие примеры необходимых условий.




75
ПРИЛОЖЕНИЕ



В этом разделе приведен дополнительный материал по строчно- и столбцово-
достаточным матрицам и методу Данцига—Коттла главных исключений для решения
линейных задач о дополнительности. Последний в ряде случаев оказывается более
предпочтительным по сравнению с методом Лемке.

§ 1. Достаточные матрицы

Введем операцию умножения векторов по Адамару:

x ? y = Xy = (x1 y1 , . . . , xn yn ) .

Напомним, что матрица M называется строчно(столбцово)-достаточной, если x ?
(M x) ? 0 ? x ? (M x) = 0 (соответственно x ? M x ? 0 ? x ? M x = 0. )
Рассмотрим ряд свойств операции умножения векторов по Адамару и строчно(столбцово)-
достаточных матриц (часть этих свойств носит тривиальный характер и отмечалась
ранее).
Свойство 1. Пусть u, v ? Rn и P — произвольная перестановочная (n ? n)-
матрица. Тогда
P (u ? v) = (P u) ? (P v).
Свойство 2. Пусть M — произвольная (n ? n)-матрица и P — произвольная
перестановочная (n ? n)-матрица. Тогда

P (x ? (M x)) = (P x) ? ((P M P ) (P x)) ?x ? Rn .

Следует из свойства 1 и того, что P P = E.
Под главным переупорядочением матрицы M будем понимать любую матрицу
вида P M P, где P — перестановочная матрица.
Любое главное переупорядочение строчно(столбцо-
Свойство 3.
во)-достаточной матрицы также строчно(столбцово)-достаточно.
Следует из свойства 2 и определения классов RS, CS.
Свойство 4. Пусть M — произвольная (n?n)-матрица и D = = diag (?1 , . . . , ?n ).
Тогда
x ? ((DM D)x) = (Dx) ? (M (Dx)) ?x ? Rn .
В самом деле,
(x ? ((DM D)x))i = xi (DM Dx)i =
n n
= xi (?i mij ?j xj ) = (?i xi ) mij (?j xj ) =
j=1 j=1

= ((Dx) ? (M (Dx)))i .
Свойство 5. Если M — строчно(столбцово)-достаточная матрица, то такой же
будет и матрица DM D, где матрица D — диагональная.
Свойство 6. Каждая главная подматрица строчно(столбцово)-достаточной мат-
рицы сама строчно(столбцово)-достаточна.


76
Свойство 7. Все главные миноры строчно(столбцово)-достаточной матрицы не
отрицательны.
Свойство 8. Пусть a и b — произвольные вещественные числа, произведение
которых отрицательно. Тогда (2 ? 2)-матрица

0a
M=
b0
является достаточной.
В самом деле,
x1 ax2 a
X ? (M x) = ? = x1 · x2 ?0
x2 bx1 1

только при x1 · x2 = 0. Но тогда и x ? (M x) = 0.
Свойство 9. Пусть a ? 0, b = 0 — вещественные числа. Тогда матрицы

a0 0b
M1 = , M2 =
b0 0a

не могут быть строчно-достаточными. Соответственно M1 и M2 не могут быть
столбцово-достаточными.
Действительно, для вектора x = (1, ?ab?1 ? ?) , где ? > 0, верно x ? (M1 x) ? 0,
но x1 (M1 x)1 < 0. Аналогично для M2 .
Свойство 10. Пусть M — строчно-достаточная матрица. Если mii = 0 при
некотором i, причем mji ? 0 для всех j = 1, . . . , n, то mij ? 0 для всех j =
1, . . . , n.
В самом деле, в силу свойства 6 достаточно доказать это утверждение при n = 2.
По свойству 3 без ограничения общности можно считать i = 1. В силу свойства 7,
m22 ? 0. Поэтому случай, когда m21 = 0, вытекает из свойства 9. Если же m21 > 0,
то по свойству 7 неравенство m12 > 0 невозможно. Тем самым всегда m12 ? 0.
Выпишем линейную задачу о дополнительности LCP (q, M ) : найти векторы
z, w ? Rn такие, что
z ? 0, w ? 0, (1.1)
(1.2)
w = q + M z,
(1.3)
z w = 0;
здесь матрица M = (mij )n?n и вектор q ? Rn заданы.
Метод главных исключений основан на идее перебора базисных решений системы
(1.2), удовлетворяющих условиям дополнительности (1.3), но, возможно, не удовле-
творяющих условиям (1.1).
Рассмотрим систему (1.2). Пусть для некоторого набора индексов ? ? {1, . . . , n}
главная подматрица M?? матрицы M не вырождена. Прибегая в случае необходи-
мости к подходящему главному переупорядочению M, можно считать M?? ведущей
главной подматрицей. Уравнения (1.2) примут вид

w? = q? + M?? z? + M?? z? ,
??
(1.4)
w? = q? + M?? z? + M?? z? ,
? ? ? ?? ?

здесь ? = {1, . . . , n}\?.
?

77
В представлении (1.4) будем говорить о переменных w как о базисных, а о пере-
менных z — как о независимых (небазисных).
Поскольку по предположению det (M?? ) = 0, то в (1.4) можно поменять ролями
переменные z? и w? . Применяя стандартную процедуру исключения, получаем
z? = q? + M?? w? + M?? z? ,
??
(1.5)
w? = q? + M?? w? + M?? z? ,
? ?? ?
? ?

где
?1 ?1
q? = ?M?? q? , q? = q? ? M?? M?? q? ,
? ?
?
?1 ?1
M?? = M?? , M?? = ?M?? M?? ,
?
?
?1 ?1
M?? = M?? M?? , M?? = M?? ? M?? M?? M?? .
? ?? ? ?
? ??

Система (1.5) называется преобразованной системой для задачи LCP (q, M ).
Матрица M?? называется ведущим блоком. Чтобы показать, что матрица M по-
лучена из M при помощи главного преобразования с ведущим блоком M?? , будем
писать
M = ?? (M ).
Сделаем еще замечание о матрице смены знаков. Под последней будем понимать
диагональную матрицу S? = diag (?1 , . . . , ?n ), где

1, если i ? ?;
?i =
?1, если i ? ?.
?
Свойство 11. Пусть M?? — невырожденная подматрица матрицы M. Тогда
(?? (M )) = S? (?? (M )) S? .
Следует из того, что матрица S? меняет знаки только у внедиагональных блоков,
и того, что (M )?? = (M?? ) , (M?? ) = (M?? )?1 и (M?? ) = (M )?? .
?1


Вообще говоря, нас интересуют только строчно-достаточные матрицы. Однако нам
удобнее получить следующий результат вначале для столбцово-достаточных матриц.
Теорема 1.1. Пусть M?? — невырожденная подматрица матрицы M. Если M
столбцово-достаточна, то такой же будет и M = = ?? (M ).
Д о к а з а т е л ь с т в о. Не ограничивая общности, можно считать матрицу
M?? ведущей (т. е. ? = {1, . . . , k}, k < n ). Обозначим w = = M z и предложим,
что z ? w ? 0. Имеем
w? M?? M?? z?
?
= .
w? M?? M?? z?
? ?
? ??

Условие z ? w ? 0 означает, что
z? ? w? w? ? z?
z? w?
? ? 0.
= =
z? ? w? z? ? w?
z? w?
? ? ? ? ? ?

Поскольку M = ?? (M ), то

z? M?? M?? w?
?
= .
w? M?? M?? z?
? ? ?? ?


78
Но M ? CS, откуда
w? z?
? = 0.
z? w?
? ?

Следовательно, и z ? w = 0, т. е. M ? CS также.
Перейдем теперь к тому результату, который нам действительно нужен.

Теорема 1.2. Пусть M?? — невырожденная главная подматрица матрицы M.
Если M строчно-достаточна, то такой же будет и M = ?? (M ).
Д о к а з а т е л ь с т в о. Мы уже отмечали, что M ? RS тогда и только тогда,
когда M ? CS. Поэтому достаточно показать, что (M ) — столбцово-достаточна.
По предположению столбцово-достаточной является M . Теорема 1.1 утверждает,
что ?? (M ) столбцово-достаточна. Но по определению M и свойству 11
(M ) = (?? (M )) = S? (?? (M )) S? .
Остается применить свойство 5.
Таким образом, классы строчно- и столбцово-достаточных матриц оказываются
инвариантными относительно преобразования ?? .

§ 2. Метод Данцига—Коттла

Метод Данцига—Коттла, подобно другим конечным методам решения линейных
задач о дополнительности, использует симплексные преобразования системы урав-
нений
(2.1)
w = q + M z.
Ниже мы будем использовать верхний индекс k как счетчик итераций. Начальное
значение этого счетчика k = 0, и система (2.1) может быть переписана как

w0 = q 0 + M 0 z 0 . (2.2)

После k симплексных преобразований система будет выглядеть так:

wk = q k + M k z k . (2.3)

Каждый из векторов wk и z k системы (2.3), первый из которых мы будем называть
вектором базисных, а второй — небазисных переменных, вообще говоря, скомпонован
как из переменных wi , так и zj .
Система (2.3) может быть также представлена в наглядной табличной форме:
k k
z1 ... zn
k k
mk mk
w1 qn ...
11 1n
. . . .
. . . .
. . . .
k k
mk mk
wn qn ...
n1 nn



Метод Данцига—Коттла опирается на главные симплексные преобразования (по-
рядка 1 и 2) с целью достижения одного из двух возможных конечных состояний

79
исходной таблицы. Первое из них характеризуется неотрицательностью столбца сво-
бодных членов q k ? 0. Второе — наличием в таблице строки со свойством
qr < 0 и mk ? 0, j = 1, . . . , n.
k
rj

Первое состояние говорит о достижении решения исходной задачи, второе устанав-
ливает факт пустоты множества ее допустимых точек.
Строго говоря, второе состояние не проверяется явно. В случае, когда M явля-
ется P -матрицей, оно вообще не наступает. Когда M является строчно-достаточной
матрицей, второе состояние проявляет себя в наличии столбца со свойством
qr < 0, mk = 0 и mk ? 0 ?i = r.
k
rr ir

Наличие такого столбца обнаруживается в алгоритме при проведении теста на ми-
нимальное отношение.
Метод состоит в серии главных итераций, каждая из которых начинается с выбора
отмеченной переменной — переменной, чье текущее значение отрицательно. Отме-
ченная переменная остается таковой на протяжении всей главной итерации. Цель
операций, реализуемых внутри главной итерации, — рост отмеченной переменной
до нуля, если это вообще осуществимо. Каждая такая операция дает прирост одной
из небазисных переменных, способных вывести отмеченную переменную на нулевой
уровень. Наращиваемая небазисная переменная называется ведущей. В соответствии
с соглашениями метода все переменные, текущие значения которых неотрицатель-
ны, должны оставаться таковыми. Начальная точка имеет вид (w, z) = (q 0 , 0). Это
значит, что вначале по крайней мере n переменных неотрицательны. Для перемен-
0
ных с отрицательным начальным значением qi < 0 вводится произвольная нижняя
граница
0
? < min {qi },
1?i?n

она также отрицательна и остается неизменной в течение всех вычислений. Эта ис-
кусственно вводимая в условия задачи граница используется всегда, за исключением
случая, когда M ? P. По соглашениям метода переменные, текущие значения кото-
рых отрицательны, не должны принимать значения, меньше ?. Мы также расширим
понятие небазисной переменной, разрешив ей принимать не только нулевое значение,
но и значение ?. Решение системы (2.1) будем называть невырожденным, если не
более n ее переменных принимает значения 0 или ?. В противном случае решение
называется вырожденным.
Для большей ясности введем различие между названием переменной и ее значе-
нием. Последнее будем отмечать черточкой сверху над именем переменной. Так, в
начале главной итерации мы всегда будем иметь zik = 0 или zik = ?, i = 1, . . . , n.
? ?
Мы будем также пользоваться обозначением
W k (z k ) = M k z k + q k
(хотя численно это то же, что и wk , но подчеркивает роль z k как аргумента).
С учетом сказанного опишем правила выбора ведущей переменной.
Если в самом начале главной итерации отмеченная переменная выбрана среди
базисных, первая ведущая переменная должна быть к ней дополнительной. Так,
k k
пусть wr — отмеченная переменная, тогда zr — ведущая переменная на первом
шаге. Однако отмеченная переменная не обязана быть базисной. В соответствии с
используемой здесь более широкой трактовкой базисного решения текущее решение

80
(wk , z k ) может иметь в начале главной итерации отрицательную небазисную компо-
??
k k
ненту zr = ? < 0. В этом случае переменная zr будет одновременно и отмеченной, и
ведущей. Ее рост всегда ограничен сверху тем, что некоторая базисная переменная,
k
убывая, достигнет своей нижней границы ( 0 или ? ), или тем, что zr в процессе
роста достигнет нуля (в этом случае главная итерация завершается).
Опишем перечисленные соглашения формально в виде последовательности шагов
алгоритма.
Шаг 0. Полагаем k = 0 и (w0 , z 0 ) = (q 0 , 0). Определяем нижнюю отрицатель-
??
0
ную границу ? < min {qi }.
(i)

Шаг 1. Если q k ? 0 или выполнено неравенство (wk , z k ) ? (0, 0), то рабо-
??
та алгоритма завершается получением решения задачи — вектора (q k , 0). В
?k
противном случае определяем номер r такой, что zr = ?, или (если такой
?k
переменной нет) такой, что wr < 0.
k
Шаг 2. Определяем — максимальное значение переменной
?r
k k
zr ? zr , удовлетворяющее следующим условиям:
?
k
?k
(1) zr ? 0, если zr = ?.
(2) Wrk (?1 , . . . , zr?1 , zr , zr+1 , . . . , zn ) ? 0, если wr < 0.
zk ?k k
?k ?k ?k
(3) Wik (?1 , . . . , zr?1 , zr , zr+1 , . . . , zn ) ? 0, если wi > 0.
zk ?k k
?k ?k ?k
(4) Wrk (?1 , . . . , zr?1 , zr , zr+1 , . . . , zn ) ? ?, если wi < 0.
zk ?k k
?k ?k ?k

k
Шаг 3. Если ?r = +?, то задача не имеет допустимых точек и работа
алгоритма завершается. Если ?r = 0, полагаем zr = 0, zik+1 = zik при все i = r
k
?k+1 ? ?
и
wk+1 = W k+1 (?k+1 ) ? W k (?k+1 ).
? z z
k
Возвращаемся к шагу 1, меняя k на k + 1. Если 0 < ?r < +?, выделяем един-
ственный номер s, определяемый условиями (2) ? (4) шага 2.

Шаг 4. Если mk > 0, проводим изменение базиса порядка 1: вводим в него
ss
k k
переменную zs и выводим переменную ws . Полагаем

zs = Wsk (?1 , . . . , zr?1 , ?r , zr+1 , . . . , zn ),
?k+1 zk ?k k
?k ?k

wk+1 = W k+1 (?k+1 ).
? z
Если s = r, возвращаемся к шагу 1, меняя k на k + 1. В противном случае
возвращаемся к шагу 2, меняя k на k + 1.

Шаг 5. Если mk = 0, проводим преобразование порядка 2: переменные zr и zs
k k
ss
k k
вводятся в базис, а переменные wr и ws его покидают. Полагаем
wr = zs , ws = ?r , zik+1 = zik
? k+1 ?k ? k+1 k
? ?
при всех i ? {r, s}. После этого вычисляем wi = Wik+1 (?k+1 ) для всех i ? {r, s}.
? k+1
/ z /
Возвращаемся к шагу 2, меняя k на k + 1 и r на s.



81
Перейдем к обсуждению того, что, собственно, делает алгоритм и почему он
решает произвольную линейную задачу о дополнительности, матрица M которой
строчно-достаточна.
Все главные итерации алгоритма начинаются с шага 1, где производится про-
верка, не получено ли уже решение исходной задачи. Этому соответствует слу-
чай (wk , z k ) ? (0, 0), поскольку (wk , z k ) будет неотрицательным решением (2.1) при
?? ??
z k = 0. Как будет ниже проиллюстрировано на примере, может произойти так, что
?
столбец свободных членов q k станет неотрицательным раньше, чем z k . И в этом
случае, переопределяя z k как z k = 0, получаем искомое решение. Если же ни одна
?
?k
из этих ситуаций не реализовалась, существует номер r такой, что zr < 0 или
?k
wr < 0. Такая переменная объявляется отмеченной.
Напомним, что исходная задача (2.1)–(2.3) имеет 2n переменных. Число отрица-
тельных компонент в решении системы (2.1) назовем индексом недопустимости.
Условия, включенные в шаг 2, не допускают роста этого индекса. Следовательно,
с каждым возвратом к шагу 1 алгоритм продуцирует базисное решение с меньшим
индексом недопустимости по сравнению с предыдущим. Поскольку число базисных
решений конечно, конечно и число возвратов к шагу 1. Доказательство конечно-
сти алгоритма упирается, таким образом, в необходимость показать конечность всех
операций внутри главной итерации.
k
Прекращение вычислений предусмотрено и в шаге 3. Оно происходит при ?r =
k
+?, что возможно только, если wr — отмеченная переменная. Также должны вы-
полняться условия
mk = 0 и mk ? 0 ?i = r.
rr ir

По свойству 10 отсюда вытекает, что mkj ? 0, j = 1, . . . , n. Кроме того, небазисные
r
?k
переменные zj ? 0 при всех j и
n
?k k
mk zj < 0.
k
wr = qr + rj ?
j=1

k
Следовательно, qr < 0, и уравнение
n
k k
mkj zj
k
wr = qr + r
j=1

не имеет неотрицательных решений.
k
Другой исход шага 3 — ?r = 0. В этом случае, в силу предположения о невырож-
денности системы (2.1), отмеченная и ведущая переменные совпадают: это некоторая
k
небазисная переменная zr , которая возрастает со значения ? до нуля. Главная ите-
рация завершается без смены базиса.
k
Наконец, последняя возможность 0 < ?r < +? означает, что некоторая базисная
k
переменная блокирует рост ведущей переменной zr . Возникающие здесь альтерна-
тивы разбираются в шаге 4.
А именно, если mk > 0, то переменные zs и ws меняются ролями: первая из них
k k
ss
вводится в базис, а вторая — выводится. Пересчет таблицы требует конечного числа
операций. Если к тому же r = s, то отмеченная переменная выходит на нулевой
уровень, что приводит к возврату на шаг 1 и уменьшению индекса недопустимости
по крайней мере на единицу. Если же r = s, после смены базиса рост ведущей
k
переменной zr продолжается (в соответствии с правилами шага 2).

82
Если mk = 0, то заведомо r = s. Факт блокировки zr переменной ws означает,
k k
ss
что mk < 0. В этом случае проводят главное симплексное преобразование порядка 2
sr
с ведущим блоком
mk mk
rr rs
.
k k
msr mss
Это можно сделать, так как, в силу строчной достаточности M, отрицательность
mk влечет положительность mk > 0 (см. свойство 9). Значения всех переменных
sr rs
сразу после смены базиса будут такими, какими они были в момент блокировки.
k k+1
При возврате на шаг 2 переменная wr занимает небазисную позицию zs , а пере-
k k+1
менная ws — позицию zr . Естественный порядок восстанавливается их главным
переупорядочением (одновременно меняются местами строки r и s и небазисные
k+1 k+1
переменные zr и zs ).
Как уже отмечалось, нужно показать, что число возвращений к шагу 2 будет
конечным. Это следует из того, что число всех главных преобразований порядка 2
конечно и конечно число различных конфигураций значений небазисных перемен-
ных (вариантов их распределения между значениями 0 и ? ). Что касается ведущей
k
небазисной переменной zr , ее значение, как и значение дополнительной к ней пере-
k
менной wr , монотонно растет, а их сумма растет строго монотонно на протяжении
k k+1
главной итерации. Отсюда определение ?r и ?r (k > 0) делает невозможным
ситуацию, при которой

zik = zik+t (i = 1, . . . , n) и zik = zik+t (i = r)
? ?

и которая возникала бы, если число возвратов к шагу 2 было бесконечным.
ПРИМЕР. Вновь рассмотрим задачу LCP (q, M ) из главы 1 §5, где
? ? ? ?
?3 0 ?1 2
q = ? 6 ? , M = ? 2 0 ?2 ? .
?1 ?1 1 0
Матрица M не является ни P - , ни P D - , ни даже P SD-матрицей. Но она строчно-
достаточна, как нетрудно проверить. Прямой подстановкой легко убедиться, что век-
тор (w, z ) = (2, 0, 0; 0, 1, 3) является решением поставленной задачи. Применим к ней
??
метод Данцига—Коттла.
Запишем данные задачи в табличной форме:

z1 z2 z3
?3 0 ?1 2 ?3
w1
0 ?2
w2 6 2 6
?1 ?1 0 ?1
w3 1
0 0 0
Нижней границей отрицательных значений переменных wi может служить число
? = ?4. Выберем w1 в качестве отмеченной переменной.
Дополнительно к ней переменная z1 будет ведущей. Блокирующей переменной,
мешающей неограниченному росту z1 , будет w3 . Убывая, эта переменная достигнет
нижней границы ?4 при z1 = 3. Поскольку m33 = 0, необходимо поменять ролями
две пары переменных — w3 с z1 и w1 с z3 . Новая таблица примет вид


83
w3 z2 w1
3
01 1
z3 0
2 2 2
1
1 ?2 1 ?1
w2 2
?1 ?1 1
z1 0 3
?4 0 ?3
Теперь отмеченной переменной становится небазисная переменная w1 , которая
может наращиваться сама, выступая в роли ведущей. Она блокирует сама себя. В
результате первая главная итерация завершается таблицей

w3 z2 w1
3
01 1 3
z3 2 2 2 2
1 ?2 1 ?1
w2 9
?1 ?1 1
z1 0 3
?4 0 0
Для следующей главной итерации имеется единственный кандидат на отмеченную
переменную — w3 . Она становится и ведущей переменной, рост которой блокирует
переменная z1 ; она обращается в ноль при w3 = ?1. Снова необходимо поменять
ролями две пары переменных — w2 с z3 и w3 с z2 . Это приводит к таблице

z1 w3 w2
2 1 ?1 ?1 3
w1
0 ?1 3
z3 31 2
z2 11 1 00
0 ?1 0
Отмеченная переменная все еще w3 , чье текущее значение равно ?1. Будучи
использована в качестве ведущей, w3 блокирует сама себя. В результате получаем
решение. Еще лучше сразу заметить, что вектор свободных членов неотрицателен.
В любом случае решением служит вектор (w, z ) = (2, 0, 0; 0, 1, 3).
??

§ 3. Параметрический вариант метода Лемке

Вернемся к методу Лемке из главы 1 и дадим иную интерпретацию его искус-
ственной переменной. Будем трактовать ее как параметр, начальное положительное
значение которого в ходе вычислений постепенно доводится до нуля. Такой под-
ход позволяет более тесно увязать вопросы сходимости метода с типом матрицы в
линейной задаче о дополнительности.
Выпишем линейную задачу о дополнительности: найти w, z ? Rn такие, что
w = q + M z ? 0, z ? 0, (3.1)
(3.2)
w z = 0;
здесь (n ? n)-матрица M и n-вектор q заданы, w и z — векторы неизвестных.
Поместим задачу (3.1), (3.2) в параметрическое семейство задач того же типа :
найти w, z ? Rn такие, что
w = q + f z0 + M z ? 0, z ? 0, (3.3)

84
(3.4)
w z = 0.
Здесь z0 ? 0 — числовой параметр; f = (f1 , . . . , fn ) > 0 — произвольный вектор
(например, единичный). При z0 = 0 задача (3.3), (3.4) совпадает с задачей (3.1),
(3.2).
Как обычно, будем предполагать, что системы уравнений в (3.1) и (3.3) невырож-
дены, т. е. любое их базисное решение содержит ровно n ненулевых компонент.
Организуем исходные данные задачи (3.3), (3.4) в таблицу
z0 z1 . . . zn
w1
(3.5)
.
.
. qq
? f M
wn

Здесь q = q (z0 ) = q + f z0 . Будем называть переменные w1 , . . . , wn базисными, а
??
переменные z1 , . . . , zn — свободными (небазисными). Каждая базисная переменная
соответствует своей строке, а свободная переменная — своему столбцу матрицы M.
Еще раз подчеркнем, что z0 играет роль параметра.
Как и раньше, метод будет состоять из конечной последовательности итераций,
в ходе которых одни переменные будут вводиться в базис, другие — покидать его.
Столбцы q и f будут переопределяться отдельно и, если z0 обозначает текущее
?
значение параметра z0 , столбец q таблицы (3.5) определяется как q = q + f z0 .
? ? ?
Итерации делятся на большие и малые. Каждая большая итерация начинается
с определения нового значения параметра z0 . Затем следует серия малых итера-
ций, во время которых значение z0 не меняется. Цель малых итераций — создать
условия для возможного снижения этого значения. Ввод и вывод из базиса пере-
менных производится так, чтобы поддерживать неотрицательность вектора q . Эта ?
неотрицательность поддерживается и при переопределении z0 .
Таблицу, получаемую на k -й итерации, будем записывать так:
k k
z0 z1 . . . zn
k
w1
(3.5.k)
.
. k k k k
. q
? q f M
k
wn

k k k k
Здесь, как и раньше, компоненты вектора (w1 , . . . , wn , z1 , . . . , zn ) представляют
собой некоторую перестановку компонент исходного вектора (w1 , . . . , wn , z1 , . . . , zn ),
определяемую порядком смены базисных и свободных переменных задачи на преды-
дущих итерациях.
Пусть таблица (3.5.k) соответствует большой итерации; при k = 0 она совпадает
с таблицей (3.5). Таблица большой итерации должна удовлетворять условиям:
1) из каждой пары переменных, связанных условиями дополнительности, ровно
одна является базисной и ровно одна — свободной;
2) параметр z0 принимает такое неотрицательное значение, при котором среди
компонент вектора q = q+f z0 ровно одна равна нулю, а остальные — положительны.
?
Очевидно, что в самом начале условие 1 выполняется автоматически. Выполне-
ния условия 2 добиваются следующим образом. Поскольку f > 0, то при достаточно
большом z0 сумма q = q +f z0 также будет положительной. Постепенно снижая зна-
?
чение параметра z0 , останавливаются в тот момент, когда одна из компонент вектора

85
q , убывая, обратится в нуль [в силу предположения о невырожденности системы (3)
?
она окажется единственной]. Если этого не случилось, т. е. в процессе снижения z0
до нуля все компоненты вектора q остались положительными, то q = q ? f z0 = q > 0
? ? ?
и задача (3.1), (3.2) имеет очевидное решение (w, z) = (q, 0). То же самое можно
сказать и о большой итерации, на которой параметр z0 обратился в нуль: вектор,
свободные компоненты которого равны нулю, а базисные — соответствующим ком-
понентам вектора q ? 0, является решением задачи (3.1), (3.2).
?
Пусть зафиксированное на большой итерации значение z0 параметра z0 поло-
?
жительно. Обозначим через r номер единственной нулевой компоненты вектора
k
q = q + f z0 (все остальные положительны). Переменную wr назовем отмеченной.
? ?
Цель последующих малых итераций — заставить отмеченную переменную покинуть
k
базис. Для этого на первой малой итерации в базис вводится переменная zr , до-
k
полнительная к wr . Если отмеченная переменная не покинула базис, применяется
основное правило метода Лемке: на каждой следующей малой итерации в базис
вводится переменная, дополнительная к той, что покинула базис на предыдущей
итерации.
Переходя к описанию содержания малой итерации, будем считать, что табли-
ца (3.5.k) соответствует ее началу и что s — номер вводимой в базис свободной
k
переменной zs .
Если mk = 0, производится смена ролей переменных wr и zs , т. е. первая
k k
rs
?k
из них покидает базис, а вторая — входит в него. Поскольку qr = 0, при про-
ведении операции исключения Жордана—Гаусса с ведущим элементом mk вектор rs
k
q не изменится. При этом новая таблица будет удовлетворять условию 1, т. е. из
?
каждой пары переменных, связанных условием дополнительности, ровно одна ока-
жется в базисе и ровно одна — свободной. Более того, появляется возможность
переопределить значение параметра z0 , т. е. перейти к большой итерации. Действи-
k
тельно, в силу невырожденности системы уравнений (3.1), qr = 0. Поэтому также
k ?1
k k
fr = ?qr z0 = 0, и при fr > 0 параметр z0 можно неограниченно наращивать, а
?
k
при fr < 0 — уменьшать без потери свойства неотрицательности qr . ?
Поскольку остальные компоненты вектора q были положительны, они останут-
?
?k
ся таковыми и при малом отклонении z0 от предыдущего значения z0 . С ростом
k k
этого отклонения (ростом z0 при fr > 0 и его уменьшением при fr < 0 ) одна из
компонент вектора q = q k + f k z0 , уменьшаясь, может обратиться в нуль [в силу
?
невырожденности системы (3.3) она окажется единственной]. Если это случится, со-
ответствующее значение параметра z0 фиксируется, и мы получаем таблицу, удовле-
творяющую условиям 1, 2, т. е. можно переходить к следующей большой итерации.
Если же параметр z0 неограниченно растет, а все компоненты вектора q = q k + f k z0
?
остаются неотрицательными, метод завершается на так называемом z0 -луче (без
получения решения исходной задачи). Наконец, если параметр z0 , убывая, достиг
нуля, а q = q k ? 0, мы получаем решение задачи (3.1), (3.2), а именно вектор,
?
все свободные компоненты которого равны нулю, а базисные — соответствующим
компонентам вектора q k .
Рассмотрим теперь случай, когда на малой итерации mk = 0. В этой ситуа-
rs
k
ции базис покидает базисная переменная wt с номером t, на котором достигается
? = min {??i /mk по всем i : mk < 0}. В соответствии с этим преобразованный
q k is is
столбец свободных членов q остается неотрицательным, а условие mk = 0 сохра-
? rs
k k
нит равенство qr = 0 (переменная wr остается отмеченной). Можно переходить к
?
следующей малой итерации.
И наконец, если величину ? определить нельзя, т. е. все mk ? 0, i = 1, . . . , n,
is


86
метод завершает работу на альтернативном луче (также без получения решения
исходной задачи).
Завершая параметрическое изложение метода Лемке, заметим, что последователь-
ности таблиц, получаемые обычным методом и его параметрическим вариантом, сов-
падают в следующем смысле: если в таблице параметрического метода поменять ро-
лями отмеченную и искусственную переменные, получим соответствующую таблицу
k
обычного метода [это можно сделать, поскольку в (3.5.k) всегда fr = 0 ].
ПРИМЕР. Вернемся к задаче, решение которой с применением метода Лемке уже
было разобрано в главе 1 §5 (она же была решена в предыдущем параграфе с при-
менением метода Данцига—Коттла). Начальная таблица для нее в параметрическом
изложении имеет вид
z0 z1 z2 z3
0 ?3 1 0 ?1
w1 2
0 ?2
w2 9 61 2
2 ?1 1 ?1
w3 1 0
3 0 0 0

Начальное значение параметра z0 равно 3 (минимальное значение, обеспечива-
ющее неотрицательность базисных переменных w1 , w2 , w3 ). Поскольку базисная
переменная w1 = 0, она объявляется отмеченной. Вводим в базис дополнительную
к отмеченной переменную z1 . Выводимая переменная определяется по обычному те-
сту минимального отношения. Это w3 . Выполняя операцию исключения, приходим
к таблице
z0 w3 z2 z3
w1 0 ?3 1 0 ?1 2
4 3 ?2 2 ?2
w2 13
z1 2 ?1 1 ?1 1 0
3 0 0 0
Далее вводим в базис переменную z3 , которая является дополнительной к только
что покинувшей базис переменной w3 . Поскольку элемент, стоящий на пересечении
z3 -столбца отмеченной строки, отличен от нуля, отмеченная переменная покидает
базис. Получаем таблицу

z0 w3 z2 w1
3
?1 01 1
z3 1 2 2 2 2
4 ?2 ?1
w2 5 1 1
0 ?1 1 ?1
z1 1 0
1 0 0 0

Новое значение параметра z0 равно 1 (снизилось), а z1 становится новой отмечен-
ной переменной. Вводим в базис дополнительную к z1 переменную w1 . Поскольку
в w1 -столбце элемент из отмеченной строки равен нулю, применяем тест на мини-
мальное отношение. В соответствии с ним базис покидает переменная w2 . Получаем




87
очередную преобразованную таблицу

z0 w3 z2 w2
7 3
?1
?1 1
z3 2
2 2 2
4 ?2 ?1
w1 5 1 1
?1 1 ?1
z1 0 1 0
1 0 0 0
Теперь следует ввести в базис переменную z2 . Так как элемент z2 -столбца, ле-
жащий в отмеченной строке, отличен от нуля, выводим из базиса переменную z1 и
переопределяем значение параметра z0 . Получаем завершающую таблицу

z0 w3 z1 w2
1
?1
z3 33 01
2 2
3 ?1 ?1
w1 22 1
1 1 ?1
z2 1 1 0
0 0 0 0

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




88
ЗАКЛЮЧЕНИЕ

Мы познакомили читателя лишь с кратким введением в теорию, методы и эконо-
мические приложения конечномерных вариационных неравенств и задач о допол-
нительности. Естественно, что многие важные и интересные аспекты обсуждаемой
проблематики остались неосвещенными или освещенными недостаточно.
Так, изложение ограничено однозначными отображениями, в то время как многие
приложения приводят к задачам с отображениями точечно-множественного харак-
тера, анализ которых более сложен и требует большого числа новых понятий. Не
рассмотрены также спорные и не до конца проработанные вопросы двойственности
для перечисленных математических постановок, а также вопросы их устойчивости
и параметрического анализа. Из всего разнообразия вычислительных методов реше-
ния нелинейных задач в основном отобраны те, что апеллируют к свойствам мо-
нотонности тех или иных отображений. Не описаны другие (кроме метода Лемке и
Данцига—Коттла) конечные методы решения линейной задачи о дополнительности и
матричные классы, связанные с ними. Не отмечены важные в прикладном отношении
методы декомпозиции задач большой размерности.
Познакомиться более глубоко с теорией конечномерных вариационных неравенств
и задач о дополнительности поможет предлагаемый ниже список литературы.




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

1. Антипин А.С. О сходимости и оценках скорости сходимости проксимальных методов к непо-
движным точкам экстремальных отображений // Журн. вычисл. математики и мат. физики.
1995. Т.35, N5. С.688–704.
2. Астафьев Н.Н. Линейные неравенства и выпуклость: Учеб.пособие. Свердловск: УрГУ, 1980.
3. Бакушинский А.Б. Методы решения монотонных вариационных неравенств, основанные на
принципе итеративной регуляризации // Журн. вычисл. математики и мат. физики. 1977. Т. 17,
N 6. С. 1350–1362.
4. Бакушинский А.Б., Гончарский А.В. Итеративные методы решения некорректных задач. М.:
Наука, 1989.
5. Булавский А.А. Методы релаксации для систем неравенств: Учеб. пособие. Новосибирск: НГУ,
1981.
6. Булавский А.А. Обобщенные решения и регуляризация систем неравенств // Вычисл. методы
линейной алгебры. Новосибирск: Наука, 1985. С. 161–174.
7. Вайнберг М.М. Вариационный метод и метод монотонных операторов. М.: Наука, 1972.
8. Васильев Ф.П. Методы решения экстремальных задач. М.: Наука, 1981.
9. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1988.
10. Введение в нелинейное программирование / Эльстер К.-Х., Рейнгард Р., Шойбле М., Донат Г.;
Пер. с нем. под ред. И.И.Еремина. М.: Наука, 1985.

11. Гловински Р., Лионс Ж.-Л., Тремольер Р. Численное исследование вариационных неравенств.
М:. Мир. 1979.
12. Гольштейн Е.Г., Третьяков Н.В. Модифицированные функции Лагранжа. Теория и методы
оптимизации. М.: Наука, 1989. (Сер. Экономико-мат. б-ка ).
13. Еремин И.И. О задачах последовательного программирования // Сиб. мат. журн. 1973. Т. 14,
N 1. С. 124–129.
14. Еремин И.И. Противоречивые модели оптимального планирования. М.: Наука, 1988.
15. Кокурин М.Ю. Операторная регуляризация и исследование нелинейных монотонных задач.
Йошкар-Ола: Мар. гос. ун-т, 1998.

16. Коннов И.В. Методы решения конечномерных вариационных неравенств: Курс лекций. Казань:
ДАС, 1998.
17. Корпелевич Г.М. Экстраградиентный метод для отыскания седловых точек и других задач //
Эконом. и мат. методы. 1976. Т.12, N4. С.747–756.

18. Панин В.М., Скопецкий В.В., Лаврина Т.В. Модели и методы конечномерных вариационных
неравенств // Кибернетика и системный анализ. 2000. N 2.
С.47–64.


90
19. Попов Л.Д. Модификация метода Эрроу—Гурвица поиска седловых точек // Мат. заметки. 1980.
Т. 28, вып.5. С.777–784.
20. Попов Л.Д. Метод обобщенного градиентного спуска для задачи последовательного програм-
мирования // Методы аппроксимации несобственных задач математического программирования.
Свердловск: УНЦ АН СССР, 1984.
С. 76–82.
21. Попов Л.Д. Аппроксимационные корни неразрешимых уравнений с монотонными отображения-
ми в левой части // Изв. высш. учеб. заведений. Математика. 1993. N 12. С. 70–80.
22. Попов Л.Д. Применение метода проекции для нахождения аппроксимационных корней монотон-
ных отображений // Там же. 1995. N 12. С. 74–80.
23. Aganagic M., Cottle R.W. A constructive characterization of Q0 -matrices with nonnegative principal
minors // Math. Progr. 1987. Vol.37, N 2. P.223–231.
24. Ahn B.H. Computation of Market Equilibria for Policy Analysis: The Project Independed Evaluation
Study (PIES) Approach. Garland, N.Y, 1979.
25. Aubin J.P. Mathematical methods of game and economic theory. North-Holland, Amsterdam, 1979.
26. Bertsekas D.P., Gafni E.M. Projection methods for variational inequalities with application to the
traffic assignment problem // Math. Prog. Study. 1982. Vol. 17. P. 139–159.
27. Cottle R.W. The principal pivoting problem // Math. Progr. Ser. B. 1990. Vol.48, N3. P.369–386.

28. Cottle R.W., Dantzig G.B. Complementarity pivote theory of mathematical programming // Linear
Algebra and its Applications. 1968. Vol.1, N1. P.103–125.
29. Cottle R.W., Habetler G.J., Lemke C.E. Quadratic forms semidefinite over convex cone // Kuhn
H.W., ed. Proc. of the Princeton Symp. on Math. Progr. Princeton University Press, Princeton.
N.J. 1970, P. 551–565.
30. Dafermos S. Traffic equilibria and variational inequalities // Transportation Science. 1980. 14.
P. 42–54.
31. Eaves B.C. On the basic theorem of complementarity // Math. Progr. 1971. N 1. P.68–75.
32. Eaves B.C. The linear complementarity problem // Management Science. Theory ser. 1971. Vol.17,
N 9. P.612–634.
33. Eaves B.C. Homotopies for computation of fixed points // Math. Progr. 1972. Vol.3. P. 1–22.
34. Ferris M.C., Meeraus A., Rutherford T.F. Computing Wardropian equilibria in a complementarity
framework // Optimization: methods and software. 1999. Vol.10. N5. P.669–686.

35. Friesz T.L, Tobin R.L., Smith T.E. and Harker P.T. A nonlinear complementary formulation and
solution procedure for the general derived demand network equilibrium problem // J. of Regional
Science. 1983. 23. P. 337–359.
36. Fukushima M. Equivalent differentiable optimization problems and descent methods for asymmetric
variational inequality problems // Math. Progr. 1992. Vol.53, N 1. P.99–110.

37. Gabay D. and Moulin H. On the uniqueness and stability of Nashequilibria in noncooperative games
// Bensoussan A., Kleindorfer P., Tapiero C.S., eds. Applied Stochastic Control in Econometrics
and Managment Science. Amsterdam, 1980. P. 271–292.
38. Garcia C.B., Zangwill W.I. Pathways to Solutions, Fixed Points and Equilibria. Prentice-Hall,
Englewood Cliffs, N.J, 1981.

39. Harker P.T. A variational inequality approach for the determination of oligopolistic market equilibrium
// Math. Progr. 1984. Vol.30. P. 105–111.


91
40. Harker P.T. Predicting Intercity Freight Flows. VNU Science Press, Utrecht, The Netherlands,
1987.
41. Harker P.T., Pang J.-S. Finite-dimensional variational inequalities and nonlinear complementarity
problems: a survey of theory, algorithms and applications // Math. Progr. Ser. B. 1990. Vol.48, N2.
P.161–220.
42. Karamardian S. Generalized complementarity problem // J. Optimiz. Theor. & Appl. 1971. N 8.
P. 161–167.
43. Karamardian S. The complementarity problem // Math. Progr. 1972. Vol.2, N 1. P.103–129.
44. Kuhn H.W. Simplicial approximation of fixed points // Proc. of the National Academy of Sciences
U.S.A. 1968. 61. P. 1238–1242.
45. Kuhn H.W., Tucker A.W. Nonlinear programming. Proceedings of the Second Symposium on
Mathematics Statistics and Probability. Berkeley, University of California Press, 1951. P. 481–492.
46. Lawphongpanich S., Hearn D.W. Benders decompozition for variational inequalities // Math. Progr.
1990. Vol.48. N 2. P.231–248.
47. Lemke C.E. Some pivote schemes for linear complementarity problem // Math. Progr. Study. 1978.
Vol.27. P.15–35.
48. Lemke C.E. and Howson J.T. Equilibrium points of bimatrix games // SIAM Review. 1964. 12.
P. 45–78.
49. Lions J.L. and Stampacchia G. Variational inequalities // Communications on Pure and Applied
Mathematics. 1967. 20. P. 493–519.
50. Mathiensen L. Computation of economic equilibria by a sequence of linear complementarity problems
// Math. Progr. Study. 1985. Vol.23. P. 144–162.

51. Megiddo N. A monotone complementarity problem with feasible solutions but no complementary
solutions // Math. Progr. 1977. Vol. 12. P. 131–132.
52. Megido N., Kojima M. On the existence and uniqueness of solutions in nonlinear complementarity
theory // Math. Progr. 1977. Vol. 12. P. 110–130.
53. Minty G.J. On the Maximal Domain of a Monotone Function // The Michigan Math. J. 1961.
Vol.8. N2. P. 135–138.
54. Moreau J.J. Proximite et dualite dans un espace Hilberiten // Bull. of Soc. of Math. of France. 1965.
93. P. 273–299.
55. Murty Linear Complementarity, Linear and Nonlinear Programming.
K.G.
B., 1988.
56. Nash J.F. Equilibrium points in n -person games // Proc. of the Nat. Acad. of Sciences. 1950.
Vol. 36. P. 48–49.
57. Neumann J., Morgenstern O. Theory of games and economic behavior. 3th ed., Princeton, 1953.
58. Pang J.S. Solution of the general multicommodity spatial equilibrium problem by variational and
complemetarity methods // J. of Regional Science. 1984. 24.
P.403–414.
59. Pang J.S., Chan D. Iterative methods for variational and complementarity problems // Math. Progr.
1982. Vol. 24. P. 284–313.

60. Pang J.-S., Chandrasekaran R. Linear complementarity problem solvable by a polynomial bounded
pivoting algorithm // Math. Progr. Study. 1987. Vol.25. Pt.2. P.13–27.
61. Peng J.-M. Equivalence of variational inequality problems to unconstrained minimization // Math.


92
Progr. 1997. Vol.78, N3. P.347–355.
62. Rockafellar R.T. Monotone operators and the proximal point algorithm // SIAM J. on Control and
Optimization. 1976. Vol.14. P. 877–898.
63. Scarf H.E. and Hansen T. Computation of Economic Equilibriua. Yale University Press, New Haven,
CT, 1973.
64. Stone J.C. Sequential optimization and complementarity techniques for computing economics equilibria
// Math. Progr. Study. 1985. Vol. 23. P. 173–191.
65. Todd M.J. The Computation of Fixed Points and Applications. Springer, B., 1976.

66. Variational Inequalities and Network Equilibrium Problems. Edited by F.Giannessi and A.Maugeri.
Plenum Press, N.Y., 1995.




93
Учебное издание

Попов Леонид Денисович

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

Учебное пособие




Редактор Т. А. Сасина
Компьютерная верстка — Л. Д. Попов



ЛР. N 020257 от 22.11.96 г. Подписано в печать 18.06.2001.
Формат 60 ? 84 1/16. Бумага для множительных аппаратов.
Усл. печ. л. 5,2. Уч.-изд. л. 5,6. Тираж 100 экз. Заказ .
Издательство Уральского университета. Екатеринбург, пр. Ленина, 51.

Отпечатано на ризографе в Гос. целевом фонде высш. шк. Свердл. обл.
Екатеринбург, Тургенева, 4.

<<

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

СОДЕРЖАНИЕ