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

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

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

при малых положительных λi принадлежат Χ . Пусть λ2 = 0 . Для

го столбца, а именно р1. Такие точки образуют открытое ребро многогранника Х с концом Х0. На рис. 2.3 оно обозначено буквой r.

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

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

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

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

116

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

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

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

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

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

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

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

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

гранника Ζ , если одна из ее координат является крайней точкой Χ или Υ , а другая лежит на открытом ребре. Для точек, принадлежащих открытому ребру, выполняются (m + n −1) из указанных

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

Теорема 2.4. Любая ситуация равновесия для невырожденной задачи является крайней точкой множества Ζ .

(b j , X * ) −1 = 0 . Из условия невырожденности следует, что X Χ может удовлетворять не более чем m соотношениям вида:

117

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

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

Z* = (X * ,Y * ) – ситуация равновесия, то для любого s, 1 ≤ s ≤ m + n , или s -й столбец матрицы (I, B) принадлежит p(X * ) , или s-й

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

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

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

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

ловий

118

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

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

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

0.2x1 + x2 −1 = 0 ;

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

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

0.25y1 + 0.5y2 −1 = 0 ;

– неограниченного ребра (X ,Y 1 ) с концом (X 1,Y 1 ) .

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

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

или лежит на открытом ребре Ζ .

Доказательство. Если Z H s удовлетворяет всем (m + n) со-

119