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

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

«Владимирский государственный гуманитарный университет»
КУРСОВАЯ РАБОТА

на тему:
«Квадратичное программирование»
Выполнила:

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

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

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

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

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

Евсеева Ю. Ю.
Владимир, 2010 г.

О Г Л А В Л Е Н И Е

Введение……………………………………………………………………...............		3
Глава 1.	Постановка задачи квадратичного программирования………………..	5
Глава 2.	Конечный алгоритм решения задачи квадратичного программирования…………………………………………………………..	8
Глава 3.	Применение алгоритма квадратичного программирования на практике ………………………………………………………………….......	14
Заключение……………………………………………………………………………..		19
Литература ……………………………………………………………………………..		20

Введение

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

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

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

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

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

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.