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

Программирование в управлении как процесс распределения ресурсов. Определение метода и задачи квадратичного программирования. Анализ конечного алгоритма решения задачи квадратичного программирования. Применение конечного алгоритма решения на практике.

Рубрика Математика
Вид курсовая работа
Язык русский
Дата добавления 23.02.2014
Размер файла 471,8 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

2

Размещено на http://www.allbest.ru/

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

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

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

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

на тему:

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

Выполнила:

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

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

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

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

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

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

Евсеева Ю. Ю.

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

ОГЛАВЛЕНИЕ

Введение

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

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

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

Заключение

Литература

Введение

квадратичный програмирование алгоритм задача

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

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

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

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

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

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.

Размещено на Allbest.ru

...

Подобные документы

  • Форма для ввода целевой функции и ограничений. Характеристика симплекс-метода. Процесс решения задачи линейного программирования. Математическое описание алгоритма симплекс-метода. Решение задачи ручным способом. Описание схемы алгоритма программы.

    контрольная работа [66,3 K], добавлен 06.04.2012

  • Общая постановка задачи динамического программирования как метода оптимизации, приспособленного к операциям, в которых процесс принятия решения может быть разбит на этапы (шаги). Принцип оптимальности и уравнения Беллмана. Задача распределения ресурсов.

    реферат [74,6 K], добавлен 30.01.2014

  • Понятие и виды задач математического линейного и нелинейного программирования. Динамическое программирование, решение задачи средствами табличного процессора Excel. Задачи динамического программирования о выборе оптимального распределения инвестиций.

    курсовая работа [126,5 K], добавлен 21.05.2010

  • Теория математического программирования. Методы поиска глобального экстремума функции нескольких переменных. Угловые точки допустимых множеств. Постановка общей задачи нелинейного программирования. Решения уравнения f(x)=0 методом простой итерации.

    контрольная работа [775,4 K], добавлен 05.01.2013

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

    курсовая работа [281,7 K], добавлен 27.05.2013

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

    курсовая работа [86,7 K], добавлен 19.11.2010

  • Решение систем уравнений по правилу Крамера, матричным способом, с использованием метода Гаусса. Графическое решение задачи линейного программирования. Составление математической модели закрытой транспортной задачи, решение задачи средствами Excel.

    контрольная работа [551,9 K], добавлен 27.08.2009

  • Понятие линейного программирования и его основные методы. Формулировка задачи линейного программирования в матричной форме и ее решение различными методами: графическим, табличным, искусственного базиса. Особенности решения данной задачи симплекс-методом.

    курсовая работа [65,3 K], добавлен 30.11.2010

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

    курсовая работа [197,1 K], добавлен 09.04.2013

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

    курсовая работа [37,2 K], добавлен 01.05.2011

  • Методы решения задачи коммивояжера. Математическая модель задачи коммивояжера. Алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Решение задачи коммивояжера с помощью алгоритма Крускала и "деревянного" алгоритма.

    курсовая работа [118,7 K], добавлен 30.04.2011

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

    курсовая работа [1,2 M], добавлен 14.11.2010

  • Математическое программирование - область математики, в которой изучаются методы решения задач условной оптимизации. Основные понятия и определения в задачах оптимизации. Динамическое программирование – математический метод поиска оптимального управления.

    презентация [112,6 K], добавлен 23.06.2013

  • Нахождение полинома Жегалкина методом неопределенных коэффициентов. Практическое применение жадного алгоритма. Венгерский метод решения задачи коммивояжера. Применение теории нечетких множеств для решения экономических задач в условиях неопределённости.

    курсовая работа [644,4 K], добавлен 16.05.2010

  • Теоретические основы метода отсечения, его назначение и функции в решении задач целочисленного линейного программирования. Сущность и практическая реализация первого и второго алгоритма Гомори. Применение алгоритма Дальтона, Ллевелина и Данцига.

    курсовая работа [208,1 K], добавлен 12.10.2009

  • Особенности выполнения задачи минимизации функционала. Свойства билинейной формы. Формулирование обобщенного способа решения вариационной задачи для краевых задач с самосопряженным дифференциальным оператором (вследствие квадратичности функционала).

    презентация [79,5 K], добавлен 30.10.2013

  • Оптимальная настройка параметров "алгоритма отжига" при решении задачи коммивояжера. Влияние начальной температуры, числа поворотов при одной температуре и коэффициента N на результат. Сравнение и определение лучшей функции для расчётов задачи.

    контрольная работа [329,9 K], добавлен 20.11.2011

  • Методы определения объемов выпуска изделий каждой модели, при которых прибыль будет максимальна Составление математической модели задачи целочисленного программирования. Решение задачи симплекс-методом. Поиск целочисленного решения методом отсечения.

    контрольная работа [156,9 K], добавлен 30.01.2011

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

    реферат [162,8 K], добавлен 20.05.2019

  • Целочисленные задачи математического программирования. Постановка транспортной задачи по критерию стоимости в матричной форме. Задача о назначении (проблема выбора, задача о женихах и невестах). Алгоритм метода Гомори. Формирование правильного отсечения.

    курсовая работа [868,8 K], добавлен 05.12.2012

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.