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

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ

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

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

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

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

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

1. определить задачу квадратичного программирования;
2. проанализировать конечный алгоритм решения задачи квадратичного программирования;
3. применить конечный алгоритм на практике.

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

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

 

1 ПОСТАНОВКА ЗАДАЧИ КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ

Пусть задана квадратичная функция

    (1.1)

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

        (1.2)

и линейные неравенства

       ,     (1.3)

которые в векторно-матричной  форме запишем так:

    (1.4)                                                   

и пусть  неравенства  (1.4) определяют некоторую область Ω, содержащую внутренние точки.

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

 

Задача квадратичного программирования формулируется так:  отыскать точку , для которой достигается минимум функции (1.1) при ограничениях (1.4):

         (1.5)                                  

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

 при  ,

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

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

 

Пример

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

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

 

Подход к решению  задачи с позиций линейного программирования

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

 при .

 

Формулировка квадратичного программирования

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

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

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

 при  ,

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

 

 

 

 

2 КОНЕЧНЫЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ

Приведем теперь изложение одного конечного алгоритма для решения задачи (1.1) – (1.5) квадратичного программирования.

1) Составим таблицу из ограничений  (1.3)  и частных производных минимизируемой функции (1.1):

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

.

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

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

.

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

Действительно, если мы меняем местами  и (разрешающий элемент ), то , следовательно,

а)

,

где - новая строка и - также новая строка;

б)

      .

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

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

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

 

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

 

Если  , то и . Такую точку будем называть стационарной.

Если  , то стационарная точка является решением.

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

Если же , то стационарная точка может не являться решением.

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

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

3) Определим направление движения  из стационарной точки. Пусть  стационарная точка  принадлежит плоскостям (в соответствии с таблицей (*)) . Тогда, если , то точка - решение задачи.

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

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

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

                                           

                                                                                    

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

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

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

.

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

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

                                                                                  ,

                                                   

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

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

где - значение , минимизирующее функцию .

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

Так как алгоритм монотонный, а стационарных точек – конечное число, то после конечного числа шагов получим решение .

 

3 ПРИМЕНЕНИЕ АЛГОРИТМА  КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ НА ПРАКТИКЕ

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

Пример:

Задана функция

.

Необходимо минимизировать заданную функцию при ограничениях:

Решение:

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

 

 

Первый шаг

1. Определение точки минимума.

Решив систему линейных уравнений

получим точку  , в которой достигается .

Находим какую-нибудь точку , например . Действительно,   

2) Определение  .

3)Определение .

Двигаемся вдоль луча , т.е.

В итоге для шага получим: .

4) Определение новой  точки и новых уклонений.

Второй шаг

1. Определение точки условного минимума функции.

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