Квадратичное программирование

    После получения точки перебрасываем на верх таблицы столько аннулировавшихся из числа , сколько окажется возможным, и с полученной таблицей производим действия п. 2). Вычисления продолжаем до получения новой стационарной точки, с которой производим действия п. 3), и т.д.

    Так как алгоритм монотонный, а стационарных точек – конечное число, то после конечного числа шагов получим решение .

3. Применение алгоритма квадратичного программирования на практике

 
 

    Применение  алгоритма квадратичного программирования рассмотрим на конкретном примере.

Пример:

Задана  функция  . Необходимо минимизировать заданную функцию при ограничениях:

 

Решение:

Предварительный шаг. Составляем таблицу: 

 
 

    Первый  шаг.

    1) Определение точки  минимума. Решив систему линейных уравнений

получим точку  , в которой достигается .

    Находим какую-нибудь точку , например . Действительно,   

    2) Определение  .

    

    3)Определение . Двигаемся вдоль луча , т.е. В итоге для шага получим: .

    4) Определение новой  точки и новых  уклонений.

    

    

    Второй  шаг.

    1) Определение точки  условного минимума функции. Производим шаг жорданова исключения в таблице с разрешающим элементом . Получим таблицу

    

    

    Решив систему линейных уравнений

      

найдем  условную экстремальную точку функции (при условии ) в новых координатах :

    2) Определение  .

    

    3) Определение  . Двигаемся вдоль луча , т.е. Для шага получим: .

    4) Определение новой  точки и новых  отклонений.

    

    

    Третий  шаг.

    1) Определение точки условного минимума функции. Производим шаг жорданова исключения в таблице с разрешающим элементом . Получим таблицу

 

     Решив уравнение  , найдем условную экстремальную точку функции (при условии ) в новых координатах :

    

так что  - стационарная точка.

    Получив стационарную точку, опускаем операции 2) и 3).

    4) Определение новых уклонений.

    

    Четвертый шаг. Опускаем операцию 1).

    2) Определение . Для выхода из стационарной точки решаем следующую задачу линейного программирования: минимизировать форму

при ограничениях

Для получим:  .

    3) Определение  . Двигаемся вдоль луча , т.е. Для шага получим: где минимизирует функцию

    4) Определение новой  точки и новых  уклонений.

    

причем

    Пятый шаг.

    1) Определение точки  условного минимума  функции . Решив систему линейных уравнений

 
 

найдем  условную экстремальную точку  функции (при условии ) в новых координатах : 

 

так что  - стационарная точка.

    Так как  , то и будет являться решением, т.е.  функция в точке будет принимать своё минимальное значение.