Курсовая: Нелинейное и динамическое программирование - текст курсовой. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Курсовая

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

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Курсовая работа
Язык курсовой: Русский
Дата добавления:   
 
Скачать
Microsoft Word, 2284 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной курсовой работы

Узнайте стоимость написания уникальной работы

С о д е р ж ание 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 * ')

1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
В теле взрослого человека около 75 километров нервов — мотать не перемотать!
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, курсовая по программированию "Нелинейное и динамическое программирование", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru