Задача квадратичного программирования и её решение симплекс-методом

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Курсовая  работа на тему:

«Задача квадратичного программирования и  её решение симплекс-методом»

 

 

 

 

 

 

 

 

 

 

 

Выполнила:

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

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

 

 

 

 

 

 

 

 

 

Москва

2012 г.

Оглавление

Введение…………………………………………………………………………...3

Часть первая……………………………………………………………………….5

    Области применении нелинейного  программирования…………………......5

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

    Геометрическая интерпретация  задачи нелинейного программирования...13

    Метод оптимизации на  многообразиях…..………………………………….17

Часть вторая...……………………………………………………………………18

    Решение задачи квадратичного  программирования симплекс-методом… 18

Заключение……………………………………………………………………….22

Список литературы………………………………………………………………23

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

Общая задача о нахождении экстремумов функции  на множестве называется задачей математического программирования. Как и в теории линейного программирования, функция называется целевой функцией, а множество − допустимым множеством.

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

Задачи  такого типа  рассмотрим подробнее.

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Часть первая

Области применении нелинейного программирования

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

Метод «затраты-эффективность». Метод был разработан для использования при принятии решений в управлении государством, когда вместо функции прибыли имеется общая функция эффективности – благосостояния. Здесь возникают две задачи НЛП: либо максимизация эффекта при ограниченных затратах, либо минимизация затрат при условии, чтобы эффект был выше некоторого минимального уровня. При огромном количестве данных, имеющихся в распоряжении различных государственных учреждений, конкретные задачи метода «затраты-эффективность» часто могут быть решены с помощью НЛП.

Решения уравнений. Важность применения НЛП в математике, физике и общественных науках объясняется тем, что НЛП является, возможно, самым мощным методом решения систем уравнений.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Постановка задачи

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

Квадратичной формой относительно переменных называется числовая функция от этих переменных, имеющая вид:

 

 

Квадратичная форма называется положительно(отрицательно)-определенной, если для всех значений переменных , кроме .

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

Скажем несколько слов о важной теореме:

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

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

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

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

Рассмотрим задачу нелинейного программирования:

,                 (1)

(2)

,                            (3)

где и – некоторые функции n-переменных .

Для решения сформулированной задачи в такой общей постановке не существует универсальных методов. Однако для отдельных классов задач, в которых сделаны дополнительные ограничении относительно свойств функций и , разработаны эффективные методы их решения. В частности, ряд таких методов имеется для решения задач нелинейного программирования (1)-(3) при условии, что – вогнутая (выпуклая) функция и область допустимых решений, определяемая ограничениями (2)-(3) – выпуклая.

Функция , заданная на выпуклом множестве , называется выпуклой, если для любых двух точек из и любого

0 λ1 выполняется соотношение

 

Функция , заданная на выпуклом множестве , называется вогнутой, если для любых двух точек из и любого 0 λ1 выполняется соотношение

.

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

Задача (1)-(3) называется задачей выпуклого программирования, если функция является вогнутой (выпуклой), а функция – выпуклой.

Задача, состоящая в определении максимального(минимального) значения функции

 

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

,

,

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

Функцией Лагранжа задачи выпуклого программирования (1)-(3) называется функция

 

где  - множители Лагранжа.

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

 

Точка ()=() называется седловой точкой функции Лагранжа,

если 

для всех .

Теорема Куна-Таккера.

Для задачи выпуклого программирования (1)-(3), множество допустимых решений которой обладает свойством регулярности, является оптимальным планом тогда и только тогда, когда существует такой вектор

, (), что () – седловая точка функции Лагранжа.

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

 

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

Если  функция L имеет седловую точку ()=(), то в этой точке выполняются соотношения (5)-(10).

Введем дополнительные переменные и , обращающие неравенства (5) и (8) в равенства, перепишем выражения (5)-(10), записанные для задачи квадратичного программирования, следующим образом:

 

  (15)

Таким образом, чтобы найти решение разбираемой  нами задачи квадратичного программирования, нужно определить неотрицательное решение систем линейных уравнений (11) и (12), удовлетворяющее условиям (13) и (14). Это решение можно найти с помощью метода искусственного базиса, примененного для нахождений максимального значения функции

 

при условиях (11), (12) и (15), с учетом (13) и (14).

Здесь - искусственные переменные, введенные в уравнения (11) и (12).

Используя метод искусственного базиса и дополнительно учитывая условия (13) и (14), после конечного числа шагов либо установим неразрешимость, либо получим оптимальный план исходной задачи.

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

1. Составляют функцию Лагранжа.
2. Записывают в виде выражений(11)-(15) необходимые и достаточные условия существования седловой точки для функции Лагранжа.
3. Используя метод искусственного базиса, либо устанавливают отсутствие седловой точки для функции Лагранжа, либо находят ее координаты.
4. Записывают оптимальное решение исходной задачи и находят значение целевой функции.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Геометрическая интерпретация  задачи нелинейного программирования

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

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

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

Пусть у  нас даны четыре функции:

 

 

 

 

 

 

 

 

 

 

Построим  в одной системе координат  графики первых трех функций.

Построение  представлено на Рисунке 1.

Рис.1

На Рис.2 представлена область D – область  допустимых решений.

Рис.2

 

 

 

 

 

Точка А(1,2) не является точкой локального или глобального минимума.

F(A)=2 (Рис. 3)

Рис.3

Точка В(4,3) является точкой локального, но не глобального минимума.

F(В)=0 (Рис.4)