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

3. Выбираем множество H s , в котором будет производиться поиск ситуации равновесия. Определяем исходную точку

(X 0 ,Y 0 ) :

точкой множества Ζ . Согласно теореме 2.6 (X 0 ,Y 0 ) H s , где H s состоит из точек множества Χ ×Υ , удовлетворяющих уравнениям

( fi , X )((ai ,Y ) −1) = 0 , i =1,..., m ,

(e j ,Y )((b j , X ) −1) = 0 , j =1,..., n , j ≠ s ,

и, возможно, уравнению (es ,Y * )((bs , X * ) −1) = 0 .

4. Если последнее уравнение выполнено для точки (X 0 ,Y 0 ) , то

это – ситуация равновесия. Переходим к шагу 13. В противном случае переходим к следующему шагу.

5. Изменяем базисы p0 и q0 , для этого найдем множества p(X 0 ) ={ fi , b j | ( fi , X 0 ) = 0, (b j , X 0 ) =1} ,

q(Y 0 ) ={e j , ai | (e j ,Y 0 ) = 0, (ai ,Y 0 ) =1}.

126

6. Выписываем таблицы AN и B N ( N – номер итерации) для новых базисов так же, как в симплекс-методе []. Чтобы получить

таблицу AN , надо исключить из базиса вектор es и ввести вектор ai* . Для этого из всех строк таблицы необходимо вычесть s-ю

строку, умноженную на множители, подобранные таким образом, чтобы во всех строках, кроме s-й, i*-й элемент обратился в нуль. Затем разделить s-ю строку на ai*s .

Таблица AN

В таблицу AN добавляется снизу строка и справа один столбец. Значения ξi = (ai ,Y 0 ) , причем ai берется из таблицы, полученной на предыдущем шаге вычислений; y0j – j -я компонента вектора

2) так как (X 0 ,Y 0 ) – крайняя точка, можно показать, что либо λ* , либо λ** равно нулю. В столбец λ в качестве λ j добавляет-

127

ся то из чисел λ* и λ** , которое отлично от нуля. Если они оба равны нулю, добавляется нуль.

Аналогично формируется таблица B N . Из базиса исключается fi* и на его место вводится b j* . В нижней строке таблицы поме-

Таким образом,

(ak ,Y 0 ) + λk (ak , q j ) = ξk + λ j αkj ,

причем правую часть равенства преобразуем следующим образом:

128

Точка Y определена так, что она является крайней точкой множества Υ . Ввиду того, что Y – конец ребра, другим концом которого

является Y 0 , числа λ* и λ** не могут одновременно отличаться от нуля, так как в противном случае

(Y 0 + λ*q j ) Υ , (Y 0 + λ**q j ) Υ , λ* > 0 , λ** < 0 ,

вопреки тому, что Y 0 – крайняя точка.

Таким образом, на данном шаге алгоритма рассчитываем край-

Точки (X 0 ,Y j ) и (X i ,Y 0 ) являются смежными с точкой

(X 0 ,Y 0 ) .

8.Находим q(Y j ) и p(X i ) в соответствии с определением базиса (п. 5 настоящего алгоритма).

9.Для каждой пары (X 0 ,Y j ) и (X i ,Y 0 ) формируем множество

M :

129

Переходим к шагу 13.

Если такой пары не найдется, то переходим к следующему шагу. 11. Выбираем точку Z = (X ,Y ) , для которой в M (X ,Y ) недос-

тает вектора es . Тогда (X ,Y ) H s . По теореме 2.7 найдется пара таких точек Z1, Z2 , являющихся концами ребер, которые пересе-

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

12. Выбираем ту из найденных точек Z1, Z2 , которая не была

включена в s -путь на предыдущих итерациях, изменяем базис p(X ) или q(Y ) и возвращаемся на шаг 6. (При этом на шаге 6 ме-

няется лишь одна из таблиц A или B .)

Согласно теореме 2.8 через конечное число шагов процесс закончится или в ситуации равновесия, или в исходной точке

(X 0 ,Y 0 ) , если произойдет зацикливание. В последнем случае выбираем новое s и начинаем поиск сначала.

130