Курсовая Квадратичное программирование
Работа добавлена на сайт bukvasha.net: 2015-10-25Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего
от 25%

Подписываем
договор
Федеральное агентство по образованию РФ
Государственное образовательное учреждение высшего профессионального образования
«Владимирский государственный гуманитарный университет»
КУРСОВАЯ РАБОТА
на тему:
«Квадратичное программирование»
Выполнила:
студентка группы ММ-31
очной формы обучения ТЭФ
Коротеева А. А.
Научный руководитель:
доцент кафедры
алгебры и теории чисел
Евсеева Ю. Ю.
Владимир, 2010 г.
О Г Л А В Л Е Н И Е
Введение……………………………………………………………………............... | 3 | |
| | |
Глава 1. | Постановка задачи квадратичного программирования……………….. | 5 |
| | |
Глава 2. | Конечный алгоритм решения задачи квадратичного программирования………………………………………………………….. | 8 |
| | |
Глава 3. | Применение алгоритма квадратичного программирования на практике …………………………………………………………………....... | 14 |
| | |
Заключение…………………………………………………………………………….. | 19 | |
| | |
Литература …………………………………………………………………………….. | 20 |
Введение
Квадратичное программирование – область математического программирования, посвященная теории решения задач, характеризующихся квадратичной зависимостью между переменными.
Программирование в управлении можно представить как процесс распределения ресурсов. Существует ряд различных методов, основанных на идеях математического программирования, среди которых широкое применение нашел метод квадратичного программирования.
Применение метода квадратичного программирования актуально в сегодняшнее время, так как использование математических моделей является важным направлением совершенствования планирования и анализа деятельности компании. Представление данных в виде математической модели позволяет конкретизировать информацию, создавать и моделировать варианты, выбирать оптимальные решения.
Целью курсовой работы является изучение метода квадратичного программирования.
Для того, чтобы достичь данной цели необходимо решить следующие задачи:
определить задачу квадратичного программирования;
проанализировать конечный алгоритм решения задачи квадратичного программирования;
применить конечный алгоритм на практике.
Объектом исследования является метод квадратичного программирования.
Предметом исследования является пример, рассмотренный в третьей главе данной курсовой работы.
Курсовая работа состоит из введения, трех глав, заключения и списка литературы.
Постановка задачи квадратичного программирования
Пусть задана квадратичная функция


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

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


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

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


Задача квадратичного программирования формулируется так: отыскать точку


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



где








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





Кроме того, портфель вкладов







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



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






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





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

Конечный
алгоритм решения задачи квадратичного программирования
Приведем теперь изложение одного конечного алгоритма для решения задачи (1) – (3) квадратичного программирования.
1) Составим таблицу из ограничений (2*) и частных производных минимизируемой функции


Найдем единственную точку











до значений


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



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













Действительно, если мы меняем местами




а)


где


б)



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


2) Определим единственную точку





В качестве направления спуска из точки






Если




Если


Действительно, в этом случае градиент функции










Если же


Действительно, в этом случае градиент функции








Если же







3) Определим направление движения из стационарной точки. Пусть стационарная точка




Если же









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

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




Но



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

Далее, точка



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

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




(так как

Если









где



После получения точки



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

Применение алгоритма квадратичного программирования на практике
Применение алгоритма квадратичного программирования рассмотрим на конкретном примере.
Пример:
Задана функция


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

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

получим точку


Находим какую-нибудь точку




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


3)Определение





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


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




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

найдем условную экстремальную точку функции




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


3) Определение





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


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



Решив уравнение





так что

Получив стационарную точку, опускаем операции 2) и 3).
4) Определение новых уклонений.

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


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

Для


3) Определение







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

причем

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


найдем условную экстремальную точку





так что

Так как




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