Вход

Нелинейное и динамическое программирование

Курсовая работа* по программированию
Дата добавления: 23 января 2002
Язык курсовой: Русский
Word, rtf, 2.2 Мб
Курсовую можно скачать бесплатно
Скачать
Данная работа не подходит - план Б:
Создаете заказ
Выбираете исполнителя
Готовый результат
Исполнители предлагают свои условия
Автор работает
Заказать
Не подходит данная работа?
Вы можете заказать написание любой учебной работы на любую тему.
Заказать новую работу
* Данная работа не является научным трудом, не является выпускной квалификационной работой и представляет собой результат обработки, структурирования и форматирования собранной информации, предназначенной для использования в качестве источника материала при самостоятельной подготовки учебных работ.
Очень похожие работы

С о д е р ж ание 1. Введение 2. Аналитический обзор 3. Теоретическая часть 3 . Задача квадратичного программирования (непараметрический случай ). 3 .1 Постановка задачи : 3.2 Условия оптимальности в задаче ( 3 .2) 3 .3. Базис задачи квадратичного программирования . Оптимальный и невырожденный базисы. 3.4. Метод субоптимизации на многообразиях . Выпуклый случай. 3.5 Метод субоптимизации на многообразиях . Задача квадратичного программирования . 3 .6. Метод субоптимизации на многообразиях в задаче квадра тичного программирования . Теоретическое обоснование . 3 .7. Вычислительная схема алгоритма субоптимизации для задачи квадратичного программирования. 3.8. Некоторые особенности вычислительной схемы метода субоптимизации на многообразиях для задачи квадратичного программирования. 4 . Задача квадратичного программирования с параметром в правы х частях ограничений. 4.1 Постановка задачи 4.2 Некоторые свойства решения параметрической задачи квадратичного программирования. 4.3 Применение метода субоптимизации на многообразиях к решению параметрической задачи квадратичного программирования. 5.Экономическая часть 6. Библиография 7.Приложение 1........................ ..........................................................................................65 8.П Риложение 2..................................................................................................................67 9.рисунок 1..................... ................................................................................................ ......78 1. Введение В настоящей работе рассматривается применение метода субоптимизации на многообразиях к решению задачи квадратичного программирования с параметром в правых частях ограничений. Метод субоптимизации на многообразиях , предложенный У.Зангвиллом в 1968 году для решения задач выпуклого программирования представляет собой простую процедуру поиска оптимальной точки в задаче выпуклого программирования с ограничениями типа равенств . Мет о д использует подход , названный автором "выделением активных ограничений ", сводящий исходную задачу выпуклого программирования к определенным образом строящейся последовательности вспомогательных задач выпуклого программирования. В тех случаях , когда решен ие вспомогательных задач оказывается существенно проще решения исходной , или вообще очевидным , метод субоптимизации на многообразиях позволяет существенно снизить вычислительную трудоемкость процедуры решения исходной задачи , а также исследовать свойства р ешения общей задачи на основании общих свойств вспомогательных задач. В работе показано , что , в случае задачи квадратичного программирования , решение вспомогательных задач сводится к разложению определенным образом выбираемого вектора по некоторому базис у , что в свою очередь эквивалентно решению системы линейных уравнений . Таким образом решение исходной задачи оказывается эквивалентным решению конечного числа систем линейных уравнений. Показано также , что в случае задачи выпуклого программирования решени е общей задачи сводится к последовательному решению вспомогательных задач , при переходе между которыми в базисном множестве происходит замена только одного вектора. В силу этого становится возможным создание рекуррентных формул , связывающих матрицы систем ы линейных уравнений соседних вспомогательных задач . Таким образом вместо решения системы линейных уравнений на каждом шаге метода можно вычислять новое решение с помощью соответствующих рекуррентных соотношений , прибегая к непосредственному решению сист емы линейных уравнений только с целью коррекции накопившейся ошибки вычисления после значительного количества итераций. В результате вычислительная трудоемкость процедуры оказывается в лучшем случае эквивалентной решению системы линейных уравнений с после дующим конечным числом матричных преобразований типа умножения матрицы на вектор . В худшем случае задача оказывается эквивалентной решению конечного числа систем линейных уравнений. Доказаны теоремы , составляющие теоретический фундамент алгоритма , приведе но доказательство сходимости предложенной вычислительной процедуры. Рассматривается применение указанного метода к решению параметрической задачи квадратичного программирования с параметром в правых частях ограничений , путем сведения указанной задачи к ко нечному числу задач квадратичного программирования без параметра. В силу того , что решение параметрической задачи квадратичного программирования с параметром в правых частях ограничений оказывается кусочно-линейной функцией , исходная задача сводится к пок рытию области допустимых значений параметра отрезками , на которых функция решения линейна по параметру с постоянными коэффициентами , зависящими только от значения функции в левой точке отрезка . Показано , что такое разбиение состоит из конечного числа отре зков , и конечного числа точек переключения траектории решения. Построение такого покрытия в худшем случае эквивалентно решению конечного числа задач квадратичного программирования без параметра в точках переключения траектории . Показаны подходы к построен ию процедуры перестройки решения в точках переключения траектории без необходимости полного решения задачи квадратичного программирования путем сведения ее к одной или нескольким итерациям метода субоптимизации на многообразиях. Поставлена задача поиска о птимального вложения в задаче о портфеле ценных бумаг , являющаяся экономической интерпретацией параметрической задачи квадратичного программирования . Составлена и отлажена программа на языке С ++, функционирующая в среде операционных систем UNIX ( AIX , Sol aris ) а также Microsoft Windows , реализующая описанные алгоритмы . Указанная программа применена к решению задачи о поиске оптимальных инвестиций в задаче о портфеле ценных бумаг , данные решения и текст программы приведен в приложениях. Указаны возможные п ути упрощения процедуры поиска решения задачи квадратичного программирования с параметром в правых частях ограничений путем отказа от решения задачи квадратичного программирования в точках переключения траектории. 2. Аналитический обзор Для решения задач выпуклого программирования с линейными ограничениями могут применяться различные методы решения . Для построения таких методов используется как правило подход , предполагающий задачу квадратичного программ ирования в известном смысле расширением задачи линейного программирования. Результатом применения такого подхода является группа методов основанных на простроении аппроксимации исходной квадратичной задачи последовательностью задач линейного программирова ния , а также различные обобщения линейного симплекс-метода на случай выпуклой функции-критерия. Рассматриваемый в данной работе метод субоптимизации на многообразиях представляет собой результат совсем иного подхода к решению задачи квадратичного программ ирования . Процедура метода субоптимизации строится для более общего класса задач выпуклого программирования , причем указывается класс задач , для которых этот метод оказывается достаточно эффективным . При этом задача квадратичного программирования оказыва ется частным случаем задачи выпуклого программирования , для которой метод субоптимизации позволяет свести решение исходной задачи к решению конечного числа систем линейных уравнений. 3. Теоретическая часть 3 . Задача квадратичного программирования (непараметрический случай ). 3 .1 Постановка задачи : Задачей квадратичного программирования будем называть задачу следующего вида : (3.1.1) здесь x -вектор столбец размера n , C - вектор-строка размера 1 n , D - матрица размера n n , симметричная и неотрицательно определенн ая ( D 0 ). b - столбец длины m . A - матрица размера m n , ранг ее равен m ( R(A) = m ). Имеет место также условие неотрицательности компонентов вектора x : x 0. По скольку наличие компонента Cx не оказывает существенного влияния на результаты , изложенные в настоящей работе , будем без ограничения общности предполагать вектор C нулевым . В такой постановке задача принимает вид : (3.1.2) В данной постановке задача квадратичного программирования всегда имеет оптимальный вектор , и является задачей выпуклого программирования с линейными ограничениями типа равенств. 3.2 Условия оптимальности в задаче ( 3 .2) Условия оптимальности в задаче ( 3 .2) представляют собой формулировку условий Куна-Таккера для этой задачи . Будем рассматривать следующую форму записи условий Куна-Таккера для задачи выпуклого программирования : (3.2.1) В нашем случае получим : (3.2.2) Здесь A i - столбцы матрицы A длины m , D i столбцы матрицы D длины n , L k - строки матрицы A длины n , e j - n - мерные столбцы единичной матрицы . Здесь и далее x i - компоненты оптимального вектора задачи x , k и k - множители Лагранжа условий Куна-Таккера . Запишем систему 3 .2.2 в более обобщенной форме : ( 3 .2.3) где составные столбцы P0, ... Pm+2n каждый длиной m+n являются столбцами блочной матрицы P, имеющей следующий вид : ( 3 .2.4) В таком виде условия Куна-Таккера ( 3 .2.3) можно записать в еще более простом виде : ( 3 .2.5) Поскольку рассматриваемая нами задача является задачей выпуклого программирования , указанные условия существования минимума являются одновременно необходимыми и достаточными . Доказатель ство указанных условий можно найти в [1,2]. 3 .3. Базис задачи квадратичного программирования . Оптимальный и невырожденный базисы. Поскольку ранг матрицы A равен m (см 3 .1), система векторов являются линейно независимой системой векторов . В то же время , легко видно , что линейная оболочка , натянутая на систему векторов P совпадает с пространством E m+n , т.е L (P)=E n+m . Следовательно из системы векторов 3 .2.4 можно образовать конечное число базисов N евклидова пространства E n+m , содержащих в себе векторы P 1 , .. P m . Такие базисы пространства E n+m будем называть базисами задачи квадратичного программирования , и обозначать следующим образом : ( 3 .3.1) Для упрощения схемы алгоритма , запишем базис ( 3 .3.1) в следующем виде : ( 3 .3.2) Здесь 1 и 2 - наборы индексов . В случае , если 1 = 2 будем считать базис U 1, 2 порожденным одним множеством индексов = 1. ( 3 .3.3) Коэффициенты разложения вектора b по базису U 1, 2 будем называть базисными переменными , остальные коэффициенты - небазисными пер еменными. Базис U 1, 2 назовем оптимальным , если его базисные переменные удовлетворяют условиям Куна-Таккера ( 3 .2.3). Базис называется невырожденным , если все его базисные переменные , соответст вующие компонентам вектора x отличны от нуля , т.е. ( 3 .3.4) Задачу ( 3 .1.2) будем называть невырожденной , если все ее базисы невырождены . В противном случае назов ем задачу вырожденной. 3.4. Метод субоптимизации на многообразиях . Выпуклый случай. Для решения задачи ( 3 .1.2) предлагается использовать метод субоптимизации на многообразиях . Вначале рассмотрим основ ные идеи , приводящие к методу субоптимизации в случае задачи выпуклого программирования общего вида. Рассмотрим задачу выпуклого программирования с линейными ограничениями , состоящую в минимизации выпуклой функции f(x) на множестве L , задаваемом ограничен иями типа равенств. ( 3 .4.1) Предположим , что задача имеет единственное решение , т.е минимум целевой функции достигается в единственной оптимальной точке x * . В это м случае задаче ( 3 .4.1) эквивалентна задача : ( 3 .4.2) Эквивалентность этих двух задач является следствием единственности решения . Переход к задаче ( 3 .4.2) называ ется выделением активных ограничений , т.е . вместо условия неотрицательности всех переменных , мы переходим к условию равенства нулю всех компонент , решения , индексы которых не принадлежат множеству (x*). Предположим , что для задачи ( 3 .4.2) нахождение оптимального решения существенно проще , чем для исходной задачи ( 3 .4.1). В этом случае , перебирая каким-либо образом всевозможные множества индексов k , являющиеся подмножествами полного набора индек сов 1,..n , и решая для каждого из них задачу ( 3 .4.2), используя k вместо * , определить искомое множество индексов * . Предположим также , что задача ( 3 .4.2) облад ает свойством единственности , т.е система векторов L 1 , .. L m , e j ( j (x*) - линейно независима . В случае нарушения свойства единственности задача поиска оптимального вектора задачи ( 3 .4.2) усло жняется , и в дальнейшем этот случай рассматриваться не будет. Алгоритм перебора множеств индексов k основан на следующей лемме . Основная лемма : Пусть x * является оптимальной точкой задачи : ( 3 .4.3) где X - линейное многообразие , определяемое следующим образом : ( 3 .4.4) Предположим , что задача ( 3 .4.3) с условием ( 3 .4.4) обладает свойством единственности , и среди j , удовлетворяющих условиям Куна-Таккера существует отрицательное j 0 , т.е. ( 3 .4.5) Пусть ' - множество индексов , полученное из вычитанием индекса j 0 : (3.4.6) Тогда , если x * ' - оптимальный вектор задачи (3.4.7) то справедливо неравенство : f(x * ')

© Рефератбанк, 2002 - 2024