Шаг 4.Рисунок 13.6

13.2.2. Метод Топкиса-Вейнотта

Рассмотренные в начале параграфа 13.2 основной алгоритм метода возможных направлений и пример 13.1 в последовательно получаемых подзадачах выбора направления на каждой итерации используют множества активных ограничений . С вычислительной точки зрения для постановки задачи (шаг 4 основного этапа) удобнее использовать только часть ограничений, так как ЗЛП выбора направления оказывается меньшей размерности. А учитывая только активные ограничения для данной доступной точки, получим зигзагообразный процесс, ухудшающий сходимость. Рассмотрим пример такого ухудшения, решая задачу с использованием основного алгоритма.

Пример 13.3

при условиях

,

.

Определим функции:

.

Начальный этап. .

Основной этап.

Итерация 1

.

, следовательно, для нахождения возможного направления подъёма функции в точке решаем ЗЛП при условиях:

.

Иначе:

.

Решение этой задачи: , , .

Решаем одномерную задачу:

.

Очевидно, что . Отсюда .

Итерация 2

.

, следовательно, переходим к решению задачи

решение этой задачи: , , и т. д. Ход решения задачи представлен на рис. 13.7.

Шаг 5.Рисунок 13.7

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

Таким образом, учёт лишь множества активных ограничений может не только замедлить процесс поиска решения, но и привести к сходимости к различным точкам. Такая ложная сходимость называется явлением заедания в методе возможных направлений. Это явление обусловлено тем, что получаемый на каждой итерации шаг становится всё короче и короче, а вектор направления колеблется между близлежащими границами. Шаги становятся короче не потому, что в результате одномерного поиска находится оптимальное решение, а потому, что пересекается близлежащее ограничений, которое не учитывалось в подзадаче выбора направления.

Как один из способов устранения явления заедания применяется подход, в котором активные ограничения вовсе не участвуют. Такой подход используется в методе Топкиса-Вейнотта.

Алгоритм метода Топкиса-Вейнотта

Начальный этап. Выбрать начальную точку . положить .

Основной этап.

Шаг 1. Решить ЗЛП:

(13.18)

при условиях

,

, , (13.19)

, ,

- решение этой задачи.

Шаг 2. Если , то - решение задачи.

Шаг 3. Определить , решая задачу одномерной оптимизации:

,

где .

Шаг 4. Положить , и перейти к шагу 1.

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

Рассмотрим решение примера 3.3 с помощью метода Топкиса-Вейнотта.

Пример 13.4.

.

Начальный этап. , .

Основной этап.

Шаг 1. , , , , .

Решаем задачу:

при условиях

.

Решение этой задачи:

, , .

Шаг 2. Так как , то переходим к шагу 3.

Шаг 3. Решаем задачу:

.

Определим :

.

Решение задачи: , .

Шаг 4. Положить . и перейти к шагу 1 на итерацию 2.

Продолжая итерационный процесс, на третьей итерации получаем оптимальное решение. Ход решения этой задачи изображён на рис. 13.8.

Рисунок 13.8

Очевидно, что скорость сходимости в этом случае значительно лучше, чем скорость сходимости в примере 13.3, где использовался основной алгоритм метода возможных направлений.