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

Реферат

Метод Зойтендейка

Банк рефератов / Радиоэлектроника

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

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

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

Метод Зойтендейка 19 ГК и ВО России НГТУ Кафедра АСУ Реферат на тему : Метод Зойтендейка Факультет : АВТ Группа : АС -513 Студент : Ефименко Д.В. Преподаватель : Ренин С.В. Новосибирск 1997 Содержание : Введение 2 Случай линейных ограничений 2 Геометрическая интерпретация возможного направления спуска 2 Построение возможных направлений спуска 3 Задачи с нелинейными ограничениями-неравенствами 9 Алгоритм метода Зойтендейка (случай нелинейных ограничений-неравенств ) 11 Учет нелинейных ограничений-равенств 14 Использование почти активных ограничений 15 Список литературы 18 Введение Я хочу описать Вам метод возможных направлений Зойтендейка. На каждой итерации метода строится возможное направлен и е спуска и затем проводится оптимизация вдоль этого направления. Следующее определение вводит понятие возможного направления спуска. ОПРЕДЕЛЕНИЕ . Рассмотрим задачу минимизации f(х ) при условии , что х Н S, где f: Е n а Е 1 , а S — непустое мно жество из Е n . Ненулевой вектор d называется возможным направлением в точке х Н S, если существует такое d > 0, что х + l x Н S для всех l Н (0, d ). Вектор d называется возможным направлением спуска в точке x Н S, если существует такое d >0, что f(х + l d) С f(х ) T d= -8d 1 +2d 2 , то он является направлением спуска . Таким образом , совокупность направлений спуска определяется откры тым полупространством ( d 1 ,d 2 : -8d 1 +2d 2 <0 . Пересече ние конуса возможных направлен и й с эт и м полупространством задает множество всех возможных направлений спуска. Рис . 1. Возможные направления спуска, 1 — конус возможных направле ний : 2 — конус возможных направ л ен и й спуска ; 3 — линии уровня целевой функции ; 4 — полупространство направлений спуска. Построение возможных направлений спуска Пусть задана допустимая точка х. Как показано в лемме , ненулевой вектор и является возможным направлением спуска . Естественный подход к построению такого направления заключается в минимизации С f(х ) T d. Заметим , однако , что если существует вектор d, такой , что С f(х ) T d < 0, А 1 d Ј 0, Е d = 0, то оптимальное значение целевой функции в сформу лированной задаче равно — Ґ , так как ограничениям этой за дачи удовлетворяет любой вектор l d, где l — сколь угодно большое число . Таким образом , в задачу должно быть вк лючено условие , которое ограничивало бы вектор и или оптимальное значение целевой функции . Такое ограничен и е обычно называют нормирующим . Ниже приведены три задачи построения возмож ного направления спуска , В каждой из этих задач используются различные формы нормировки. Задачи Р 1 и РЗ являю т ся задачами линейного программи ро вания и , следовательно , могут быть решены симплекс-методом . Задача Р 2 содержит квадратичное ограничение , но может быть рассмотрена в несколько упрощенном виде . Так как d = 0 является допустимой точкой в каждой из приведен н ых выше задач и так как значение целевой функции в этой точке равно нулю , то ее оптимальное значение в задачах Р 1, Р 2 и РЗ не может быть положительным . Если минимальное значе ние целевой функции в задачах Р 1, Р 2 или РЗ отрицательно , то по лемме построено в озможное направление спуска . С другой стороны , если минимальное значение целевой функции равно нулю , то , как показано ниже , х является точкой Куна — Таккера. ЛЕММА . Рассмотр и м задачу минимизации f(х ) при условиях Ах Ј b и Ех = е. Пусть х — допус тимая точка , для которой А 1 x=b и А 2 x 0 имеем . Следо в ательно , вектор и является возможным направлением спуска. На рис . 6 показана совокупность возможных направлений спуска в точке х . Вектор d, удовлетворяющий равенству , является касатель н ым к множеству в точке х . Посколь ку функции g i нелинейны , движение вдоль такого вектора d может привест и в недопустимую точку , что вы нуждает нас тр е бовать выполнения строгого неравенства . Чтобы найти вектор d, удовл е творяющий неравенствам для , естественно мин и мизи ровать максимум из и для . Обозначим этот макс и мум через z. Вводя нормирующие ограничен и я Для каждого j, получим следующую задачу для нахождения направления. Пусть (z, d) — оптимальное решение этой задачи линейного про граммирования . Если z< 0, то очевидно , что d — возможное направление спуска . Если же z = 0, то , как показано ниже , те кущая точка является точкой Ф. Джона. ТЕОРЕМА.. Рассмотрим задачу минимизации f(х ) при условиях g i (х ) Ј 0, i = 1,..., m. Пусть х— допустимая точка , а . Рассмотрим следую щую задачу на хождения направления : Точка х является точкой Ф . Джона для исходной задач и тогда и только тогда , когда оптимальное значение целевой функции задачи поиска направления равно нулю. Точка х является точкой Ф. Джона для и сходной задач и тогда и только тогда , когда опт и мальное значение целевой функции задачи поиска направл е ния равно нулю. Доказательство . Оптимальное значение целевой функции в сформулированной задаче нахождения направления равно нулю в том и только в том случае , если система неравенств при не и меет решения . По теореме для того , чтобы эта система н е имела решения , необход и мо и достаточно , чтобы сущест в овали такие числа u o и u i , , что Это и есть условие Ф . Джона. Алгоритм метода Зойтендейка (случай нелинейных ограничений-нера в енств ) Начальный этап . Выбрать начальную точку х 1 , для которой g i (x i ) Ј 0 пр и i= 1, ..., m. Поло ж ить k= 1 и перейти к ос новному этапу. Основной этап . Шаг 1. Положить и ре шить следующую задачу : Пусть ( z k , d k ) — оптимальное решен и е . Если z k =0 , то остано виться ; x k является точкой Ф. Джона . Если z k < 0, то перейти к шагу 2. Шаг 2. Взять в качестве ^ оптимальное решение следующей задачи одномерной минимизации : где. Положить . з аменить k на k+ 1 и перейти к шагу 1. ПРИМЕР . Рассмотрим задачу Решим э т у задачу методом Зойтендейка. Начнем процесс из точки .Отметим , что Итерация 1 Поиск направления . В точке х 1 = (0.00, 0.75 ) T и меем а множество инде ксов активных ограничений есть I= 3 . При этом Задача нахождения н аправления имеет вид Можно легко проверить , используя симплекс-метод , что оптимальным решением этой задачи является вектор Л и нейный поиск . Любая точка по направлению d 1 == (1.00, — 1.00) T из т очки x i = (0.00, 0.75 ) T может быть представлена в виде ,а соответствующее ей значение целевой функц и и равно . Макси мальное значение , для которого ост ается допустимой точкой , равно == 0.414. При этом значен ии l активным ста новится ограничение . Значение l получается и з решения следующей задачи одномерной м и нимизации : миними з ировать 6 l 2 — 2.5 l — 3.375 пр и условии 0 Ј l Ј 0.414 Оптимальное значение равно l 1 = 0.2083. Следовательно , х 2 = ( x 1 + l 1 d 1 ) -( 0.2083,0.5417 ) T . Итерация 2 Поиск направления . В точке x 2 = (0.2083, 0.5417 ) T имеем ( х 2 ) = ( — 4,2500, — 4.2500 ) T Активных ограничений в этой точке нет , и поэтому задача определения направления имеет вид минимизировать z при условиях — 4.25d 1 — 4.25d 2 — z Ј 0, -1 0 — достаточно малое ч и сло . Метод возможных направлений не обязательно сходится к точке Ф. Джона . Это следует из того , что соответствующее алгоритмическое отображение незамкнуто . При более формальном использовании введённого здесь понятия почти активного ограничения можно установить замкнутость алгоритмического от ображения и , следовательно , сходимость общего алгоритма. Список литературы : 1. М . Базара , К . Шеттл “Нелинейное программирование . Теория и алгоритмы” М .: Мир 1982 2. Д . Химмельблау “Прикладное нелинейное программирование” М .: Мир 1975
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Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Рабинович приходит домой и говорит жене с улыбкой:
- А меня с работы уволили!
- Яша, я не поняла, а что это ты радостный-то такой?
- А остальных таки посадили.
Anekdot.ru

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

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

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


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