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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


Реферат/Курсовая Квадратичное программирование

Информация:

Тип работы: Реферат/Курсовая. Добавлен: 04.06.13. Сдан: 2012. Страниц: 11. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Федеральное агентство по образованию РФ
Государственное образовательное учреждение высшего  профессионального образования
«Владимирский государственный гуманитарный университет» 
 
 
 
 

КУРСОВАЯ  РАБОТА
на тему: 

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

Выполнила:
студентка группы ММ-31
очной формы обучения ТЭФ
Коротеева А. А. 

Научный руководитель:
                    доцент кафедры
алгебры и теории чисел
Евсеева Ю. Ю. 
 

Владимир, 2010 г.
О Г Л А В Л  Е Н И Е 
 

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

     Введение
    Квадратичное  программирование – область  математического  программирования, посвященная теории решения задач, характеризующихся квадратичной зависимостью между переменными.
    Программирование  в управлении можно представить  как процесс распределения ресурсов. Существует ряд различных методов, основанных на идеях математического  программирования, среди которых  широкое применение нашел метод квадратичного программирования.
    Применение  метода квадратичного программирования актуально в сегодняшнее время, так как использование математических моделей является важным направлением совершенствования планирования и  анализа деятельности компании. Представление данных в виде математической модели позволяет конкретизировать информацию, создавать и моделировать варианты, выбирать оптимальные решения.
    Целью курсовой работы является изучение метода квадратичного программирования.
    Для того, чтобы достичь данной цели необходимо решить следующие задачи:
    определить задачу квадратичного программирования;
    проанализировать конечный алгоритм решения задачи квадратичного программирования;
    применить конечный алгоритм на практике.
    Объектом  исследования является метод квадратичного программирования.
    Предметом исследования является пример, рассмотренный в третьей главе данной курсовой работы.
    Курсовая  работа состоит из введения, трех глав, заключения и списка литературы.
 

    Постановка задачи квадратичного программирования
 
 
    Пусть задана квадратичная функция
                                                       (1*)

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

и линейные неравенства
       ,                          (2*)
которые в векторно-матричной форме запишем  так:
,                                                                                                     (2)
и пусть  неравенства  (2) определяют некоторую  область ?, содержащую внутренние точки.
    Будем предполагать, что матрица  симметричная и положительно определенная, так что - выпуклая функция.
    Задача  квадратичного программирования формулируется так:  отыскать точку , для которой достигается минимум функции (1) при ограничениях (2):
    
                                                                                   (3)

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

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

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

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

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

 

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

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

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

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

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

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

    

    

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

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

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

    

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

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

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

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

где - значение , минимизирующее функцию .
    После получения точки  перебрасываем на верх таблицы столько аннулировавшихся из числа , сколько окажется возможным, и с полученной таблицей производим действия п. 2). Вычисления продолжаем до получения новой стационарной точки, с которой производим действия п. 3), и т.д.
    Так как алгоритм монотонный, а стационарных точек – конечное число, то после конечного числа шагов получим решение .
    Применение алгоритма квадратичного программирования на практике
 
 
    Применение  алгоритма квадратичного программирования рассмотрим на конкретном примере.
Пример:
Задана  функция  . Необходимо минимизировать заданную функцию при ограничениях:
 

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

 
 

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

и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.