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

Федеральное агентство по образованию РФ

Государственное образовательное учреждение высшего  профессионального образования

«Владимирский государственный гуманитарный университет» 
 
 
 
 

КУРСОВАЯ  РАБОТА

на тему: 

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

Выполнила:

студентка группы ММ-31

очной формы обучения ТЭФ

Коротеева А. А. 

Научный руководитель:

                    доцент кафедры

алгебры и теории чисел

Евсеева Ю. Ю. 
 

Владимир, 2010 г.

О Г Л А В Л  Е Н И Е 
 

 

 

     Введение

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

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

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

    Целью курсовой работы является изучение метода квадратичного программирования.

    Для того, чтобы достичь данной цели необходимо решить следующие задачи:

1. определить задачу квадратичного программирования;
2. проанализировать конечный алгоритм решения задачи квадратичного программирования;
3. применить конечный алгоритм на практике.

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

    Предметом исследования является пример, рассмотренный в третьей главе данной курсовой работы.

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

 

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

 
 

    Пусть задана квадратичная функция

                                                       (1*)

или в  векторно-матричной форме

                                                                                        (1)

и линейные неравенства

       ,                          (2*)

которые в векторно-матричной форме запишем  так:

,                                                                                                     (2)

и пусть  неравенства  (2) определяют некоторую  область Ω, содержащую внутренние точки.

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

    Задача  квадратичного программирования формулируется так:  отыскать точку , для которой достигается минимум функции (1) при ограничениях (2):

    

                                                                                   (3)

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

    

 при  ,

где - -мерный вектор, - симметричная матрица , - -мерный вектор и - матрица . 

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

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

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

    Подход  к решению задачи с позиций линейного  программирования:

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

    

 при .

    Формулировка  квадратичного программирования:

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

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

    Другая  формулировка задачи финансиста заключается в выборе портфеля вкладов, который минимизирует дисперсию и ещё обеспечивает ожидаемую прибыль не менее некоторого фиксированного количества . В итоге мы приходим к задаче квадратичного программирования:

    

 при  ,

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

 

2. Конечный  алгоритм решения задачи квадратичного программирования

 
 

    Приведем  теперь изложение одного конечного алгоритма для решения задачи (1) – (3) квадратичного программирования.

    1) Составим таблицу из ограничений  (2*)  и частных производных минимизируемой функции (1*):

    

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

    

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

    Пусть для удобства значение достигается при т.е.

    

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

    Действительно, если мы меняем местами  и (разрешающий элемент ), то , следовательно,

а)

,

где - новая строка и - также новая строка;

б)

      .

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

    Пусть после  последовательных шагов жордановых исключений пришли к таблице

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

    

    

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

    

 

    Если  , то и . Такую точку будем называть стационарной.

    Если  , то стационарная точка является решением.

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

    Если  же , то стационарная точка может не являться решением.

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

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

    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.