14.3. АЛГОРИТМ ОПОРНОЙ ГИПЕРПЛОСКОСТИ

Рассмотрим задачу (14.15), в которой вогнуто, квазивогнуты. Как было отмечено при обсуждении вогнутого метода, мы можем преобразовать задачу к другому виду с линейной целевой функцией. Поэтому рассмотрим задачу

где квазивогнуты и непрерывно дифференцируемы (упр. 4). Следует обратить внимание на то, что благодаря квазивогнутости допустимая область задачи (14.23) является выпуклым множеством.

Алгоритм опорной гиперплоскости разработан для решения задачи (14.23). Он аналогичен вогнутому методу, за исключением отображения и отсекаемого полупространства Здесь полупространство будет построено по некоторой граничной точке выпуклой допустимой области причем точка и считается граничной точкой если

Предположения. В алгоритме предполагается, что все функции непрерывно дифференцируемы, а выпуклое допустимое множество содержится в компактном множестве

Кроме того, предполагается, что существует точка а, для которой для всех и что если и находится на границе и то

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

Рис. 14.3. Вторая итерация.

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

Пусть точка а находится внутри , а — это точка границы на прямой, соединяющей (упр. 6). Для данного Воспользовавшись точкой выразим множество в виде

где — любой индекс, для которого

Из выпуклости следует, что (упр. 5)

Следует разъяснить связь этой процедуры с вогнутым методом. В обоих методах начинают с точки 2 и решают подзадачу для определения Если — допустимая точка, то оба метода завершают поиск. Если не является допустимой, то в методе опорной гиперплоскости в отличие от вогнутого метода определяется граничная точка и, лежащая на прямой между внутренней точкой а и недопустимой точкой Далее, по точке и строится полупространство и последующая точка находится как пересечение

Доказательство сходимости.

Условие 1. Все которое по предположению является компактным. Кроме того, из соотношения следует, что но все входят в

Условие 2. Очевидно, выполняется.

Условие 3. Мы должны доказать, что замкнуто. Пусть

Так как находится на отрезке прямой между то существует такое 0, что

Поскольку существует такое что Следовательно,

находится на отрезке прямой между и а.

Теперь нужно убедиться в том, что является граничной точкой. Так как имеется лишь конечное число

ограничений, то должны существовать такие у и при которых

и

Из непрерывности функций

т. е. находится на границе. Отсюда и отображение А замкнуто.

Ясно, что непрерывны, так как

Условие 4 (упр. 7). Если то

Далее из Таким образом, метод сходится.

Интерпретация сходимости. Из выражения (14.25) известно, что, как и в вогнутом методе, для всех к. Поэтому, если проходит тест решения, то — оптимальная точка для задачи (14.23). Значит, метод опорной гиперплоскости определяет решение задачи (14.23).

14.3.1. Геометрия алгоритма опорной гиперплоскости в Е2

Пусть прямоугольник (рис. -исходная область Допустимой областью является стрелка указывает направление, в котором максимизируется целевая функция кроме того, показана точка а. Решением первой подзадачи является

Точка которая находится на отрезке прямой между а и у, показана на рис. 14.5. Следует обратить внимание на то, как гиперплоскость

Рис. 14.4. Первая подзадача.

Рис. 14.5. Вторая подзадача.

Рис. 14.6 Третья подзадача.

касается множества или опирается на него в точке Новое множество представляет собой четырехугольник ; решением второй подзадачи является точка

Точка показана на рис. 14.6. Множество представляет собой пятиугольную фигуру и решением третьей подзадачи является точка о. Процедура продолжается указанным образом.