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

Рис.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	-М	-М
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	-М	-М
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	-М	-М
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), получаем

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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