Ирина Эланс

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

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

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

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

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

Выполнила:

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

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

Москва

2012 г.

Введение

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

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

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

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

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

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

Часть первая

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

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

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

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

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

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

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

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

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

Квадратичная форма называется положительно(отрицательно)-полуопределенной, если для любого набора значений переменных и кроме того, существует такой набор переменных , где не все значения переменных одновременно равны 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), после конечного числа шагов либо установим неразрешимость, либо получим оптимальный план исходной задачи.

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

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

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

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

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

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

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

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

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

Рис.1

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

Рис.2

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

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

Рис.3

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

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

Рис.4

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

F(С)= - 3+√3 (Рис.5)

Рис.5

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

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

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

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

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

существенно проще решения исходной, или вообще очевидным, метод

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

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

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

Часть вторая

Решение задачи квадратичного программирования

Формулировка: Найти максимальное значение функции

(16)

при условиях

(19)

Решение:

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

Система ограничений задачи представляет собой систему только линейных неравенств. Поэтому мы можем воспользоваться теоремой Куна-Таккера.

Составим функцию Лагранжа

и запишем в виде выражений (11)-(15) необходимые и достаточные условия существования седловой точки построенной функции:

(22)

Перепишем систему линейных неравенств (20) :

Введем дополнительные неотрицательные переменные . Они обратят неравенства (20) в равенства. Получаем:

Учитывая равенства (24), запишем:

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

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

при условиях

(29)

В результате решения задачи (27)-(29) с учетом условия (26) находим допустимо базисное решение системы линейных уравнений (28). См. табл.1:

i	Базис			0	0	0	0	0	0	0	0	-М	-М
i	Базис
1		- М	2	2	0	1	2	-1	0	0	0	1	0
2		- М	4	0	4	2	-1	0	-1	0	0	0	1
3		0	8	1	2	0	0	0	0	1	0	0	0
4		0	12	2	-1	0	0	0	0	0	1	0	0
5			0	0	0	0	0	0	0	0	0	0	0
6			-6	-2	-4	-3	-1	1	1	0	0	0	0

i	Базис			0	0	0	0	0	0	0	0	-М	-М
i	Базис
1		- М	2	2	0	1	2	-1	0	0	0	1	0
2		0	1	0	1	1/2	-1/4	0	-1/4	0	0	0	1/4
3		0	6	1	0	-1	1/2	0	1/2	1	0	0	-1/2
4		0	13	2	0	1/2	-1/4	0	-1/4	0	1	0	¼
5			0	0	0	0	0	0	0	0	0	0	0
6			-2	-2	0	-1	-2	1	0	0	0	0	1

i	Базис			0	0	0	0	0	0	0	0	-М	-М
i	Базис
1		0	1	1	0	1/2	1	-1/2	0	0	0	1/2	0
2		0	1	0	1					0	0
3		0	5	0	0					1	0
4		0	11	0	0					0	1
5			0	0	0					0	0

Поскольку , то ()=(1;1;0;0) является седловой точкой функции Лагранжа для исходной задачи.

Это означает, что =(1;1) – оптимальный план исходной задачи.

Подставим найденный оптимальный план в (16), получаем

Заключение

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

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

Акулич И.Л. «Математическое программирование в примерах и задачах»: Учеб. Пособие для студентов эконом. спец. вузов. – М.: Высш.шк., 1986. – 319 с., ил.
Зуховицкий С.И., Авдеева Л.И. «Линейное и выпуклое программирование» (Серия: «Экономико-математическая библиотека»), М., 1967 г., 460 стр. с илл.
Зангвилл У. «Нелинейное программирование, Единый подход», 1969 г. – Пер. с англ., под ред. Е.Г.Гольштейна, М., «Сов. радио», 1973, 312с.

Задача квадратичного программирования и её решение симплекс-методом 📙 Курсовая → 🆔 79614