Реферат Дипломная работа содержит 78 страниц, 2 приложения, 1 рисунок. Список ключевых слов: программирование, квадратичное,параметрическое icon

Реферат Дипломная работа содержит 78 страниц, 2 приложения, 1 рисунок. Список ключевых слов: программирование, квадратичное,параметрическое



НазваниеРеферат Дипломная работа содержит 78 страниц, 2 приложения, 1 рисунок. Список ключевых слов: программирование, квадратичное,параметрическое
Дата конвертации13.07.2012
Размер213,42 Kb.
ТипРеферат
Задача квадратичного программирования с параметром в правых частях ограничений и ее применение при формировании портфеля ценных бумаг


Реферат Дипломная работа содержит 78 страниц, 2 приложения, 1 рисунок. Список ключевых слов: программирование, квадратичное,параметрическое. В данной работе рассматривается применение метода субоптимизации намногообразиях к решению задачи параметрического квадратичногопрограммирования с параметром в правых частях ограничений, и решению спомощью указанного метода задачи об оптимальном выборе портфеля ценныхбумаг. Рассматриваются свойства алгоритма, и обосновывается егоприменимость к задаче квадратичного программирования. Содержание1. Введение 42.Аналитический обзор 93. Теоретическая часть 113. Задача квадратичного программирования (непараметрический случай).11 3.1 Постановка задачи: 11 3.2 Условия оптимальности в задаче (3.2) 12 3.3. Базис задачи квадратичного программирования. Оптимальный и невырожденный базисы. 15 3.4. Метод субоптимизации на многообразиях. Выпуклый случай. 18 3.5 Метод субоптимизации на многообразиях. Задача квадратичного программирования. 26 3.6. Метод субоптимизации на многообразиях в задаче квадратичного программирования. Теоретическое обоснование. 34 3.7. Вычислительная схема алгоритма субоптимизации для задачи квадратичного программирования. 44 3.8. Некоторые особенности вычислительной схемы метода субоптимизации на многообразиях для задачи квадратичного программирования. 474. Задача квадратичного программирования с параметром в правых частяхограничений. 514.1 Постановка задачи 51 4.2 Некоторые свойства решения параметрической задачи квадратичного программирования. 51 4.3 Применение метода субоптимизации на многообразиях к решению параметрической задачи квадратичного программирования. 545.Экономическая часть 566.Библиография 637.Приложение1..................................................................................................................658.ПРиложение2..................................................................................................................679.рисунок1...........................................................................................................................78 1. Введение В настоящей работе рассматривается применение метода субоптимизациина многообразиях к решению задачи квадратичного программирования спараметром в правых частях ограничений. Метод субоптимизации на многообразиях, предложенный У.Зангвиллом в1968 году для решения задач выпуклого программирования представляет собойпростую процедуру поиска оптимальной точки в задаче выпуклогопрограммирования с ограничениями типа равенств. Метод использует подход,названный автором "выделением активных ограничений", сводящий исходнуюзадачу выпуклого программирования к определенным образом строящейсяпоследовательности вспомогательных задач выпуклого программирования. В тех случаях, когда решение вспомогательных задач оказываетсясущественно проще решения исходной, или вообще очевидным, методсубоптимизации на многообразиях позволяет существенно снизитьвычислительную трудоемкость процедуры решения исходной задачи, а такжеисследовать свойства решения общей задачи на основании общих свойстввспомогательных задач. В работе показано, что, в случае задачи квадратичногопрограммирования, решение вспомогательных задач сводится к разложениюопределенным образом выбираемого вектора по некоторому базису, что в своюочередь эквивалентно решению системы линейных уравнений. Таким образомрешение исходной задачи оказывается эквивалентным решению конечного числасистем линейных уравнений. Показано также, что в случае задачи выпуклого программированиярешение общей задачи сводится к последовательному решению вспомогательныхзадач, при переходе между которыми в базисном множестве происходит заменатолько одного вектора. В силу этого становится возможным создание рекуррентных формул,связывающих матрицы системы линейных уравнений соседних вспомогательныхзадач. Таким образом вместо решения системы линейных уравнений на каждомшаге метода можно вычислять новое решение с помощью соответствующихрекуррентных соотношений, прибегая к непосредственному решению системылинейных уравнений только с целью коррекции накопившейся ошибки вычисленияпосле значительного количества итераций. В результате вычислительная трудоемкость процедуры оказывается влучшем случае эквивалентной решению системы линейных уравнений споследующим конечным числом матричных преобразований типа умножения матрицына вектор. В худшем случае задача оказывается эквивалентной решениюконечного числа систем линейных уравнений. Доказаны теоремы, составляющие теоретический фундамент алгоритма,приведено доказательство сходимости предложенной вычислительной процедуры. Рассматривается применение указанного метода к решениюпараметрической задачи квадратичного программирования с параметром в правыхчастях ограничений, путем сведения указанной задачи к конечному числу задачквадратичного программирования без параметра. В силу того, что решение параметрической задачи квадратичногопрограммирования с параметром в правых частях ограничений оказываетсякусочно-линейной функцией, исходная задача сводится к покрытию областидопустимых значений параметра отрезками, на которых функция решения линейнапо параметру с постоянными коэффициентами, зависящими только от значенияфункции в левой точке отрезка. Показано, что такое разбиение состоит из конечного числа отрезков, иконечного числа точек переключения траектории решения. Построение такого покрытия в худшем случае эквивалентно решениюконечного числа задач квадратичного программирования без параметра в точкахпереключения траектории. Показаны подходы к построению процедурыперестройки решения в точках переключения траектории без необходимостиполного решения задачи квадратичного программирования путем сведения ее кодной или нескольким итерациям метода субоптимизации на многообразиях. Поставлена задача поиска оптимального вложения в задаче о портфелеценных бумаг, являющаяся экономической интерпретацией параметрическойзадачи квадратичного программирования. Составлена и отлажена программа на языке С++, функционирующая в средеоперационных систем UNIX (AIX, Solaris) а также Microsoft Windows,реализующая описанные алгоритмы. Указанная программа применена к решениюзадачи о поиске оптимальных инвестиций в задаче о портфеле ценных бумаг,данные решения и текст программы приведен в приложениях. Указаны возможные пути упрощения процедуры поиска решения задачиквадратичного программирования с параметром в правых частях ограниченийпутем отказа от решения задачи квадратичного программирования в точкахпереключения траектории. 2.Аналитический обзор Для решения задач выпуклого программирования с линейнымиограничениями могут применяться различные методы решения. Для построениятаких методов используется как правило подход, предполагающий задачуквадратичного программирования в известном смысле расширением задачилинейного программирования. Результатом применения такого подхода является группа методовоснованных на простроении аппроксимации исходной квадратичной задачипоследовательностью задач линейного программирования, а также различныеобобщения линейного симплекс-метода на случай выпуклой функции-критерия. Рассматриваемый в данной работе метод субоптимизации на многообразияхпредставляет собой результат совсем иного подхода к решению задачиквадратичного программирования. Процедура метода субоптимизации строитсядля более общего класса задач выпуклого программирования, причемуказывается класс задач, для которых этот метод оказывается достаточноэффективным. При этом задача квадратичного программирования оказывается частнымслучаем задачи выпуклого программирования, для которой метод субоптимизациипозволяет свести решение исходной задачи к решению конечного числа системлинейных уравнений. 3. Теоретическая часть3. Задача квадратичного программирования (непараметрический случай).3.1 Постановка задачи: Задачей квадратичного программирования будем называть задачуследующего вида:|[pic] | || |(3.1.1) |здесь x-вектор столбец размера n, C- вектор-строка размера 1(n, D - матрицаразмера n(n, симметричная и неотрицательно определенная (D ( 0). b -столбец длины m. а- матрица размера m(n, ранг ее равен m (R(A) = m). Имеет место также условие неотрицательности компонентов вектора x: x ( 0.Поскольку наличие компонента Cx не оказывает существенного влияния нарезультаты, изложенные в настоящей работе, будем без ограничения общностипредполагать вектор C нулевым. В такой постановке задача принимает вид:|[pic] | || |(3.1.2) | В данной постановке задача квадратичного программирования всегдаимеет оптимальный вектор, и является задачей выпуклого программирования слинейными ограничениями типа равенств.3.2 Условия оптимальности в задаче (3.2) Условия оптимальности в задаче (3.2) представляют собой формулировкуусловий Куна-Таккера для этой задачи. Будем рассматривать следующую формузаписи условий Куна-Таккера для задачи выпуклого программирования:|[pic] | || | || | || | || |(3.2.1) | В нашем случае получим:|[pic] | || | || | || | || |(3.2.2) | Здесь Ai- столбцы матрицы адлины m, Di столбцы матрицы D длины n, Lk- строки матрицы адлины n, ej - n-мерные столбцы единичной матрицы. Здесьи далее xi - компоненты оптимального вектора задачи x, (k и (k - множителиЛагранжа условий Куна-Таккера. Запишем систему 3.2.2 в более обобщеннойформе:|[pic] | || | || |(3.2.3) | где составные столбцы P0, ... Pm+2n каждый длиной m+n являютсястолбцами блочной матрицы P, имеющей следующий вид:|[pic] | || |(3.2.4) | В таком виде условия Куна-Таккера (3.2.3) можно записать в еще болеепростом виде:|[pic] | || | || |(3.2.5) | Поскольку рассматриваемая нами задача является задачей выпуклогопрограммирования, указанные условия существования минимума являютсяодновременно необходимыми и достаточными. Доказательство указанных условийможно найти в [1,2].3.3. Базис задачи квадратичного программирования. Оптимальный иневырожденный базисы. Поскольку ранг матрицы аравен m (см 3.1), система векторов [pic]являются линейно независимой системой векторов. В то же время, легко видно,что линейная оболочка, натянутая на систему векторов P совпадает спространством Em+n, т.е L(P)=En+m. Следовательно из системы векторов 3.2.4 можно образовать конечноечисло базисов N евклидова пространства En+m, содержащих в себе векторы P1,.. Pm. Такие базисы пространства En+m будем называть базисами задачиквадратичного программирования, и обозначать следующим образом:|[pic] |(3.3.1) | Для упрощения схемы алгоритма, запишем базис (3.3.1) в следующемвиде:|[pic] |(3.3.2) | Здесь (1 и (2 - наборы индексов. В случае, если (1=(2 будем считатьбазис U(1,(2 порожденным одним множеством индексов (=(1.|[pic] |(3.3.3) | Коэффициенты разложения вектора b по базису U(1,(2 будем называтьбазисными переменными, остальные коэффициенты - небазисными переменными. Базис U(1,(2 назовем оптимальным, если его базисные переменныеудовлетворяют условиям Куна-Таккера (3.2.3). Базис называется невырожденным, если все его базисные переменные,соответствующие компонентам вектора x отличны от нуля, т.е.|[pic] | || | || |(3.3.4) | Задачу (3.1.2) будем называть невырожденной, если все ее базисыневырождены. В противном случае назовем задачу вырожденной.3.4. Метод субоптимизации на многообразиях. Выпуклый случай. Для решения задачи (3.1.2) предлагается использовать методсубоптимизации на многообразиях. Вначале рассмотрим основные идеи,приводящие к методу субоптимизации в случае задачи выпуклогопрограммирования общего вида. Рассмотрим задачу выпуклого программирования с линейнымиограничениями, состоящую в минимизации выпуклой функции f(x) на множествеL, задаваемом ограничениями типа равенств.|[pic] | || |(3.4.1) | Предположим, что задача имеет единственное решение, т.е минимумцелевой функции достигается в единственной оптимальной точке x*. В этомслучае задаче (3.4.1) эквивалентна задача:|[pic] | || | || |(3.4.2) | Эквивалентность этих двух задач является следствием единственностирешения. Переход к задаче (3.4.2) называется выделением активныхограничений, т.е. вместо условия неотрицательности всех переменных, мыпереходим к условию равенства нулю всех компонент, решения, индексы которыхне принадлежат множеству ((x*). Предположим, что для задачи (3.4.2) нахождение оптимального решениясущественно проще, чем для исходной задачи (3.4.1). В этом случае,перебирая каким-либо образом всевозможные множества индексов (k, являющиесяподмножествами полного набора индексов 1,..n, и решая для каждого из нихзадачу (3.4.2), используя (k вместо (*, определить искомое множествоиндексов (*. Предположим также, что задача (3.4.2) обладает свойствомединственности, т.е система векторов L1, .. Lm, ej (j( ((x*)- линейнонезависима. В случае нарушения свойства единственности задача поискаоптимального вектора задачи (3.4.2) усложняется, и в дальнейшем этот случайрассматриваться не будет. Алгоритм перебора множеств индексов (k основан на следующей лемме. Основная лемма: Пусть x* является оптимальной точкой задачи:|[pic] |(3.4.3) | где X( - линейное многообразие, определяемое следующим образом:|[pic] |(3.4.4) | Предположим, что задача (3.4.3) с условием (3.4.4) обладает свойствомединственности, и среди (j, удовлетворяющих условиям Куна-Таккерасуществует отрицательное (j0, т.е.|[pic] |(3.4.5) | Пусть ( ' - множество индексов, полученное из ( вычитанием индексаj0:|[pic] |(3.4.6) | Тогда, если x*' - оптимальный вектор задачи|[pic] |(3.4.7) |то справедливо неравенство:|f(x*')




Нажми чтобы узнать.

Похожие:

Реферат Дипломная работа содержит 78 страниц, 2 приложения, 1 рисунок. Список ключевых слов: программирование, квадратичное,параметрическое iconКурсовая работа Анализ прибыли ао «Саранский хлебокомбинат» Реферат. Данная курсовая работа содержит 38 страниц, 9 таблиц, 23 формулы, 30 источников
Перечень ключевых слов: прибыль, рентабельность, себестоимость, коэффициент, фонд
Реферат Дипломная работа содержит 78 страниц, 2 приложения, 1 рисунок. Список ключевых слов: программирование, квадратичное,параметрическое iconРеферат 2 Введение 3 I. Основная часть 5
Дипломная работа содержит 51 страницу, 14 таблиц, 4 рисунка, 12 первоисточников, 5 приложений
Реферат Дипломная работа содержит 78 страниц, 2 приложения, 1 рисунок. Список ключевых слов: программирование, квадратичное,параметрическое iconДиплом по психологии Отражение построения индивидуального жизненного пути в портфолио учеников 8-9 классов
Данный диплом объемом страниц содержит Введние, 2 главы, Заключение, список использованной литературы и приложения. В первой главе...
Реферат Дипломная работа содержит 78 страниц, 2 приложения, 1 рисунок. Список ключевых слов: программирование, квадратичное,параметрическое iconН. И. Лобачевского экономический факультет кафедра менеджмента курсовая
Данная курсовая работа содержит 43 страниц машинописного текста, состоит из двух глав(имеющих свои подглавы), Введения и Заключения,...
Реферат Дипломная работа содержит 78 страниц, 2 приложения, 1 рисунок. Список ключевых слов: программирование, квадратичное,параметрическое iconРеферат 2 Введение 3 I. Основная часть 5 Финансовые ресурсы предприятия и принципы их организации. 5 Финансовый механизм. 7
Дипломная работа содержит 51 страницу, 14 таблиц, 4 рисунка, 12 первоисточников, 5 приложений
Реферат Дипломная работа содержит 78 страниц, 2 приложения, 1 рисунок. Список ключевых слов: программирование, квадратичное,параметрическое iconРеферат (требования к содержанию, оформлению и представлению)
Перечень ключевых слов (не более 5 слов или словосочетаний; приводятся в именительном падеже и печатаются прописными буквами в строку...
Реферат Дипломная работа содержит 78 страниц, 2 приложения, 1 рисунок. Список ключевых слов: программирование, квадратичное,параметрическое iconРеферат (требования к содержанию, оформлению и представлению)
Перечень ключевых слов (не более 5 слов или словосочетаний; приводятся в именительном падеже и печатаются прописными буквами в строку...
Реферат Дипломная работа содержит 78 страниц, 2 приложения, 1 рисунок. Список ключевых слов: программирование, квадратичное,параметрическое iconОтчет по производственной (преддипломной) практике Выполнил студент гр
Реферат. Реферат содержит количественную характеристику отчета (число страниц, рисунков, таблиц, количество использованных литературных...
Реферат Дипломная работа содержит 78 страниц, 2 приложения, 1 рисунок. Список ключевых слов: программирование, квадратичное,параметрическое iconРеферат курсовая работа "Ресурсосбережение и определение оптимального соотношения ресурсов для конкретного предприятия" содержит 65 печатных страниц, 15 рисунков, 7 таблиц, 44 источника литературы
Охватывает не только факторы производства, но и продукцию, поскольку продукция одной отрасли потребляется в другой, связанной с ней...
Реферат Дипломная работа содержит 78 страниц, 2 приложения, 1 рисунок. Список ключевых слов: программирование, квадратичное,параметрическое iconДокументи
1. /Приложения/Группа БЕРИЯ.doc
2. /Приложения/Диаграммы...

Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©rushkolnik.ru 2000-2015
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы