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

    3) Определим направление движения  из стационарной точки. Пусть  стационарная точка  принадлежит плоскостям (в соответствии с таблицей (*)) . Тогда, если , то точка - решение задачи.

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

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

    

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

                                                  

                                                                                          

    Но  - независимые переменные, поэтому (в соответствии с таблицей (*))

    

    

    ……………………………….

    

 

    Далее, точка  стационарная, т.е.  , поэтому

    

.

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

    

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

                                                                                           ,

                                                          

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

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

    

где - значение , минимизирующее функцию .

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

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

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

 
 

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

Пример:

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

 

Решение:

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

 
 

    Первый  шаг.

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

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

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

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

    

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

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

    

    

    Второй  шаг.

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

    

    

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

      

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

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

    

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

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

    

    

    Третий  шаг.

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

 

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

    

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

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

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

    

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

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

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

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

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

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

    

причем

    Пятый шаг.

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

 
 

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

 

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

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

 

Заключение 

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

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

 

     Литература 
 

1. Математическое программирование в примерах и задачах: учеб. пособие / под. ред. И.Л. Акулич. – М.: Высшая школа, 2003. – 320 с. – ISBN 5-85971-052-6.
2. Ашманов, С.А. Линейное программирование / С.А. Ашманов. – М.: Наука, 1981 – 340 с. - ISBN: 978-5-406-00207-0.
3. Венцель, Е.С. Исследование операций / Е.С. Венцель. – М.: Советское Радио, 2004. – 550 с. - ISBN: 978-5-388-00530-4.
4. Зангвилл, У.И. Нелинейное программирование. Единый подход / У.И. Зангвилл. – М. : Советское Радио, 1973.– 312 с. - ISBN: 978-5-238-00907-0.
5. Зуховицкий, С.И. Линейное и выпуклое программирование / С.И. Зуховицкий, П.И. Авдеева. – М.: Наука, 1967.– 460 с. - ISBN: 5-86225-453-6.
6. Солодовников, A.C. Задача квадратичного программирования / А.С. Солодовников. – М.: Финансовая Академия, 2004. – 397 с. - ISBN 978-5-16-002869-9.