Методы возможных направлений

    Методы, входящие в эту группу методов, базируются на построении возможных и подходящих направлений, по которым осуществляется движении из одной допустимой  точки к другой допустимой точке  с "лучшим" значением целевой функции. Движение осуществляется по правилу .

Определение 1. Пусть  допустимая точка в задаче выпуклого программирования

                                 (1)

,

где  - дифференцируемая функция. Ненулевой вектор  называется возможным направлением в точке , если существует такое , что точки  являются допустимыми в задаче для всех . Вектор  называется подходящим направлением в точке , если выполняется неравенство .

Замечание. Если некоторое направление  является возможным и подходящим в точке , то существует такое , что точки  являются допустимыми в задаче и  для всех  (Доказать!).

Теорема 1. Для того, чтобы допустимая точка  была решением задачи выпуклого программирования необходимо и достаточно, чтобы в этой точке не существовало одновременно возможных и подходящих направлений.

    Рассмотрим вначале частный случай задачи (1) - задачу с линейными ограничениями

       

где  матрица размера ,  - матрица размера , -вектор размера ,  - вектор размера .

    Заметим, что, в частности, может быть задача только с ограничениями равенствами или только ограничениями неравенствами.

Утверждение 1. Пусть  допустимая точка в задаче с линейными ограничениями и предположим, что  - это подматрица матрицы , отвечающая активным ограничениям в точке . Тогда ненулевой вектор  является возможным направлением в точке  в том и только в том случае, если .

Заметим, что если в задаче отсутствуют ограничения-равенства и в рассматриваемой точке  нет активных ограничений (т.е. точка  является внутренней), то в качестве подходящего направления можно взять . В противном случае построение подходящих направлений можно осуществить в виде минимизации функции  при условиях . Однако если существует такой вектор , такой, что , , то минимальное значение функции  при такой минимизации не существует (), так как любой вектор , где  - сколь угодно большое число, также удовлетворяет условиям . Таким образом, в задачу минимизации должно быть включено условие, которое ограничивало бы вектор , например, условие . Итак, возможное и подходящее направление ищется в виде решения следующей задачи линейного программирования

, .

 

Алгоритм

Шаг 1. Задать начальную точку , характеристику точности алгоритма . Положить .

Шаг 2. Найти . Если , то вычисления прекратить и положить , иначе перейти к шагу 3.

Шаг 3. Подставить  в неравенства и определить множество индексов активных ограничений .

Шаг 4. Если  и в задаче нет ограничений равенств, то положить , иначе определить  из решения задачи линейного программирования

, .

Шаг 5. Если , то задача решена точно и . Иначе - для найденного вектора  определить

.

Шаг 6. Найти очередное приближение .

Пример 1. Решить рассмотренным методом следующую задачу

.

Решение.

1. Возьмем в качестве начальной точки . Легко проверить, что данная точка принадлежит допустимому множеству. Положим , . Изобразим графически допустимое множество и линии уровня целевой функции

2. Найдем . Так как , то перейдем к шагу 3.

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

4. Определяя  из соотношения

получим .

5.  Найдем .

6 Найдем . Так как , то перейдем к шагу 3.

7. Точка  принадлежит границе допустимого множества, второе ограничение задачи является активным для этой точки, поэтому .

8. Составим вспомогательную задачу для определения вектора :

.

Решая графически (симплексным методом) данную задачу линейного программирования, найдем .

9. Определяя  из соотношения

,

получим .

10.  Найдем .

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

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