ответы трпр_2. 1. Постановка Любой зада4и оптимизации на4инаеться с определения набора независимых
 Скачать 4.88 Mb.
|
1.Постановка Любой зада4и оптимизации на4инаеться с определения набора независимых переменых и обы4но вклю4ает условия , которые характерезуют их преемлемые зна4ения.т.е. определяет множество возможных решений икс. Эти условия называют ограни4ение зада4и. Еще одной обязательной составной 4астью описания явл. Склярная мера ка4ества, именуемая целевой функцией и зависящая какимто образом от переменой.Решения оптимизационой зада4и заклю4аеться в определении такого зна4. Переменых из множества х, которому отве4ает эестримальное зна4. Целевой функции. Таким образом для достижения экстремума необходимо изменять в пределах х хна4ения независимых переменых. По этому они называються управляемыми перемеными.Под экстримальнгостью обы4но понимают максимальность или минимальность. 3. То4кой глобального минимума функции F на множестве х , или глобальным решением зада4и если F от х в степени 0 меньше или равно F от х при всех х принадлежит Х. ТО4кой локального минимума F на Х или локальным решением зада4и если существует 4исло Эпсилон больше 0 такое 4то F от Х в степени 0 = Меньше или равно F от х при всех х принадлежит [X пересе4ение U (X в степени 0)] Если неравенство выполняеться как строгое при Х не = Х в степени 0, то говорят 4то х в степени 0 , то4ка строгого минимума в глобальном или локальном смысле. 4.Все оптимизационые зада4и деляться на два больших подкласс Безусловный и условной оптимизации. В первом слу4ае множество решений х совпадает с областью существования с целевой функцией F(x) тоесть х принадлежит R в степени n . и неограни4ено ни какими доп. Условиями. Именно это определила название класса – безусловная оптимизация.Зада4а безусловной оптимизации имеет вид f от х стремится к минимуму., х принадлежит R в степени n. ВО втором слу4аее условной оптимизации – область решений х явл. Подмножеством области существования и задано ограни4ено дополнительными условиями на допустимые зна4ения управляемых переменх. В дальнейшем мы 4асто будем прибегать к гиометри4еской интерпретации зада4 оптимизации, основаной на понятии линии равного уровня функции F тоесть множеств вида. 6. Важной составляющей современного аппарата теории оптимизации является выпуклый анализ – раздел математики, в котором изучают свойства выпуклых множеств и выпуклых функций.  Множество  называется выпуклым, если  при всех . Иными словами множество X выпукло, если оно вместе с любым своими двумя точками   содержит соединяющий отрезок.7. *************************************************  8. Задача называется выпуклой, если X – выпуклое множество, f – выпуклая функция на X. Если задача выпукла, то любое её локальное решение является также глобальным. Таким образом, для выпуклых задач понятия локального и глобального решений не различаются и можно говорить просто об их решении. Второе свойство выпуклых задач можно высказать в виде следующего принципа: необходимые условия оптимальности в том или ином классе задач оптимизации при соответствующих предположениях выпуклости оказываются и достаточными. 9. Численные методы поиска экстремума делятся на 2 класса: - пассивные - активные Центральная идея пассивных методов заключается в выборе некоторого количества точек, которые регулярно или случайно размещаются на множестве свободных решений. Это означает, что для каждой точки задаются её координаты, т.е. значения многомерной независимой переменной. Затем в каждой точке вычисляется значение целевой функции и точка с минимальным значением принимается в качестве значения функции. Принципиальное отличие активных методов от пассивных заключается в построении последовательности точек целенаправленно приводящих в окрестности экстремума функции. Такая последовательность значений независимой переменной называется траекторией движения к экстремуму. По порядку метода: - нулевого порядка(прямые методы) - первого порядка(градиентные методы) - второго порядка(методы Ньютона) По формированию шага спуска: - с постоянным шагом - с дроблением шага - с оптимизацией длин шага 10.Во всех численных методах оптимизации необходимо найти экстремумы функции, а после производить над ними какие-либо действия для непосредственной оптимизации. 11. Что называется сходимостью численных методов оптимизации? Будем считать, что метод  сходится, если последовательность приближений  непременно приближается к точному решению  задачи  , т.е  при  . Такой вид сходимости еще называют сходимостью по аргументу. В отличие от него, сходимостью по функции называется такой вид сходимости, когда последовательность значений функции цели, вычисленной в точках , приближается к значению функции цели в точке х0, т.е  при 12. Какие условия остановки работы метода оптимизации? Условия остановки может определятся присутствующими вычислительными ресурсами. Поводом для остановки может быть зацикливание, когда последовательные приросты функции цели меняют знак на противоположный. В последовательности, которая минимизирует функцию цели, начинает повторятся определенный набор точек. Зацикливание свидетельствует о том, что поточное приближение находится в округе точки экстремума. В таком случае следует или уменьшить величину шага, или остановить работу алгоритма. В практике часто используют такие условия остановки:  ;  ,Вместо данных условий основанных на понятии абсолютной погрешности, можно также использовать аналогичные основанные на понятии относительной погрешности  ;  13. Приведите и объясните постановку задачи оптимизации функций одной переменной Задача оптимизации, функция цели которой зависит от одной переменной, относится к самому простому типу оптимизационных задач и имеет вид  Анализ задач такого типа занимает центральное место в оптимизационных исследованиях, как теоретической, так и практической направленности. Прежде всего это связано с тем, что методы оптимизации функций одной переменной используются для решения промежуточных подзадач во время поиска экстремума функций многих переменных. Важность оптимизационных задач с одной управляемой переменной обусловила разработку большого количества алгоритмов их решения. 14. Какая функция называется унимодальной?   15. Сформулируйте правило исключения интервалов (метод исключения интервалов) Методы поиска, которые позволяют определить оптимум функции одной переменной путем уменьшения интервала поиска, носят название методов исключения интервалов. Все методы одномерной оптимизации основаны на предположении, что исследуемая целевая функция в допустимой области по крайней мере обладает свойством унимодальности, так как для унимодальной функции W(x) сравнение значений W(t) в двух различных точках интервала поиска позволяет определить, в каком из заданных двумя указанными точками подынтервалов точки оптимума отсутствуют. Правило исключения интервалов. Пусть W(x) унимодальна на отрезке [a,b], а ее минимум достигается в точке x*. Рассмотрим x1 и x2, расположенные a Если W(x1)>W(x2), то точка минимума W(x) не лежит в интервале (a,x1), т.е. x*Є (x1,b). Если W(x1) Это правило позволяет реализовать процедуру поиска путем последовательного исключения частей исходного ограниченного интервала. Поиск завершается тогда, когда оставшийся подынтервал уменьшается до достаточно малых размеров. Главное достоинство поисковых методов - основаны на вычислении только значений функции и, следовательно, не требуют выполнения условия дифференцируемости и записи в аналитическом виде. Последнее свойство особенно ценно при имитационном моделировании. Процесс применения методов поиска на основе исключения интервалов включает два этапа: этап установления границ интервала; этап уменьшения интервала. Этап установления границ интервала Выбирается исходная точка, а затем на основе правила исключения строится относительно широкий интервал, содержащий точку оптимума. Обычно используется эвристический метод, например, Свенна, в котором (k+1) пробная точка определяется по рекуррентной формуле xk+1 = xk + 2kD , k=0,1,2... (3.1) где xo - произвольно выбранная начальная точка; D - подбираемая величина шага. Знак D определяется путем сравнения значений W(x), W(xo + |D | ), W(xo -|D | ): если W(xo -|D| ) W(x) W(xo + |D| ), то D имеет положительное значение; если W(xo -|D| ) W(x) W(xo + |D| ), то D имеет отрицательное значение; если W(xo -|D| ) W(x) W(xo + |D| ), то точка минимума лежит между xo - |D| и xo + |D| и поиск граничных точек завершен; если W(xo -|D| ) W(x) W(xo + |D| ), то имеем противоречие предположению об унимодальности. Пример 3. W(x)=(100-x)2, xo=30, |D| =5. Определим знак D : W(30)=4900; W(30+5)=4225; W(30-5)=5625. Выполняется условие W(xo -|D| ) W(x) W(xo + |D| ), следовательно, D имеет положительное значение; x*=30. x1=xo+20D = 35; x2=x1+21D = 45, W(45)=3025 < W(x1) ® x*>35; x3=x2+22D = 65, W(65)=1225 < W(x2) ® x*>45; x4=x3+23D = 105, W(105)=25 < W(x3) ® x*>65; x5=x4+24D = 185, W(185)=7225 > W(x4) ® x*<185. Искомый интервал 65 16. Что такое интервал неопределенности? 17. В чем состoит minmax стратегия поиска минимума на интервале неопределенности? 18. Какие преимущества и недостатки пассивных методов? В отличие от аналитических, численные методы предусматривают многократное вычисление значений целевой функции и, в случае необходимости, других ее характеристик, например, производных, в разных точках допустимого множества решений, т.е. при разных значениях независимых переменных. Согласно этой информации с большей или меньшей точностью определяется экстремум функции. Такой подход является более трудоемким в сравнении с аналитическим и предполагает, что пользователь имеет в своем распоряжении достаточно большие вычислительные ресурсы. Численные методы поиски экстремумов делят на 2 класса: пассивные и активные Основная идея пассивных методов заключается в выборе некоторого количества точек, которые регулярно или случайно располагаются на множестве возможных решений. Это означает, что для каждой точки задаются координаты, т.е. значение многомерной независимой переменной. Потом в каждой точке вычисляется значение целевой функции и точка с минимальным значением является экстремумом функции. Очевидными являются такие особенности пассивных методов : они в общем случае не гарантируют определения точного значения экстремума функции, точность определения которого зависит от количества точек и их размещения; методы имеют большую трудоемкость. Альтернативными являются активные методы. Их принципиальное отличие от пассивных заключается в построение последовательности точек, которая целенаправленно приводит в окружение экстремума функции. Такая последовательность значений независимой переменной  называется траекторией движения к экстремуму.При активном методе координаты каждой следующей точки траектории движения к экстремуму определяются на основании анализа значения целевой функции и зависимо от метода, значений тех или иных характеристик в одной или группе предыдущих точек. Каждая последующая точка траектории выбирается таким образом, чтобы обязательно выполнялось условие  Такие последовательности называются релаксационными, а методы их построения – методами спуска. Релаксационная последовательность гарантирует приближение к экстремуму. Активные и пассивные численные методы поиска экстремума не гарантируют в общем случае точного значения оптимума, а только помогают найти приближенное значение в близких окрестностях экстремума, причем эти окрестности могут быть как угодно малы. 19. Опишите схему метода разделения интервала пополам   20. Сформулируйте метод золотого сечения. В чем его отличие от метода разделения интервала пополам?        
Методы исключения интервалов сравниваются по размерам относительного уменьшения интервалов, и по количеству вычислений значений функции. В качестве показателя эффективности примем относительное уменьшение выходного интервала  .
В случае безусловной оптимизации, множество решений Х совпадает с областью существования целевой функции f(x), то есть x Rn и не ограничена никакими дополнительными условиями. Задача безусловной оптимизации принимает вид: 
Для реализации методов прямого поиска нужны только значение целевой функции. Пусть целевая функция f(x) может быть вычислена в любой точкеx Є Rᶰ и есть унимодальной в рассматриваемой области. Методы прямого поиска: - метод сеток; - метод покоординатного спуска; - модификации метода покоординатного спуска; - метод поиска по симплексу (метод многогранника); - метод деформированного многогранника; - метод случайного поиска. Общие особенности указанных методов заключаются в простоте соответствующих вычислительных процедур, которые легко реализуются и эффективно функционируют
Основная особенность пассивных методов заключается в том, что на этапе подготовки задачи к решению определяется необходимое число экспериментов n и стратегия их проведения. Далее все Опыты выполняются одновременно. Согласно полученным результатам по формуле:  =( ,… )= определяется зона неопределенности, внутри которой находится оптимум  .Простейшая пассивная стратегия проведения n экспериментов (метод равномерного поиска) состоит в разбивании исходного интервала неопределенности на равные отрезки Δ, число которых в этом случае равна (n+1), а Δ=  . Тогда зона неопределенности согласно той же формуле будет равна  . Если задана нужна точность определения экстремума , нетрудно решить обратную задачу и задать для ее обеспечения количество экспериментов:  .Для реализации пассивных стратегий потребуется гораздо больше вычислительных ресурсов, чем для активных. Несмотря на это, они используются на практике, когда наряду с определением экстремум функции требуется визуализация ее графика на выделенном интервале; исследованию подлежат функции, отличные от унимодальных, в том числе многоэкстремального, в этом случае находятся все локальные экстремумы. Альтернативойпсивним методам являются активные стратегии поиска экстремума. их особенность заключается в том что, каждый следующий эксперимент планируется с учетом информации, полученной на предыдущих шагах поиска. Это предопределяет существенное повышение эффективности процедур поиска экстремума. 25. В чем состоит стратегия поиска по образцу? В каких методах она реализована? На першому етапі метода по координатного спуску має назву дослідницького пошуку, формується так звана базова точка. На другому етапі (спуск за зразком) полягає у формуванні траєкторії руху до екстремуму. Пряма, що з’єднує стартову і базову точки, визначає напрямок руху. У цьому напрямку виконують крок. Нову (k+1)точку визначають за формулою  Потім провести дослідницький пошук, використовуючи  як нову початкову точку.26. Какие преимущества симплекса? Симплексний пошук має кілька переваг:
27. Опишите схему методов многогранника и деформированного многогранника. Одна з найцікавіших стратегій пошуку покладена в основу методу пошуку по симплексу. Поняття симплекс означає опуклий багатогранник з n+1 вершиною в просторі nзмінних. Процедурасимплексного пошуку базується на тому, що експериментальним зразком, який має найменшу кількість точок, є регулярний симплекс. В алгоритмі симплексного пошуку використовується важлива властивість симплексів, відповідно до якої новий симплекс можна побудувати на будь-якій грані початкового шляхом перенесення обраної вершини на належну відстань уздовж прямої, проведеної через центр ваги інших вершин початкового симплекса. Отримана в такий спосіб точка є вершиною нового симплекса, а вихідна вершина початкового симплекса вилучається. При цьому визначається вершина, якій відповідає найбільше значення цільової функції. Потім знайдена вершина проектується через центр ваги інших вершин симплекса в нову точку, яка приймається за вершину нового симплекса. Ітерації продовжуються доти, поки не буде накрита точка мінімуму, або не почнеться циклічний рух по двох чи більше симплексах. Побудова симплекса є досить простою процедурою, оскільки з елементарної геометрії відомо, що при заданих початковій точці  і масштабному множнику  координати інших nвершин симплекса в n-вимірному просторі обчислюються за формолую для i,  Метод деформованого багатогранника Модифікована процедура пошуку по симплексу, яку називають методом деформованого багатогранника, частково усуває деякі з перерахованих недоліків. Неважко помітити, що хоча формула для визначення вершин регулярного симплекса виявляється дуже зручною при побудові вихідного зразка, однак вагомих основ для зберігання властивості регулярності симплекса в процесі пошуку немає. 28. В чем особенность метода случайного поиска? Метод випадкового пошуку характеризуються навмисним уведенням елемента випадку в алгоритм пошуку. Багато варіантів методу випадкового пошуку зводяться до побудови послідовності {xk}за правилом: Xk+1=xk+αkξ, k=0,1… Де αk–деяка додатна величина; ξ=(ξ1,…, ξn)- реалізація n-вимірної випадкової величини ξ з відомим законом розподілу. Наприклад, координатами ξiвипадкового вектора ξ можуть бути незалежні випадкові величини, розподілені рівномірно на відрізку [-1,1]. Отже, метод випадкового пошуку мінімуму функції nзмінних передбачає наявність датчика(генератора) псевдовипадкових чисел, звертаючись до якого можна одержати реалізацію n-вимірного випадкового вектора ξ з заданим законом розподілу. Наведемо кілька варіантів методу випадкового пошуку мінімуму функції f(x) на множині Xϲ_Rn, припускаючи, що k-те наближення xkєХ (k≥0) уже відоме. В окремому випадку xk- стартова точка xs 29. Какая основная особенность градиента используется в методах оптымизации?  30. Опишите общую схему градиентных методов.   31. В чем состоят особенности методов второго порядка (Метод Ньютона и его модификации)? 32. Опишите схему метода Ньютона. Для того чтобы построить более эффективную по скорости сходимости стратегию поиска, следует дополнительно привлечь информацию о вторых производных целевой функции, что позволяет реализовать нелинейную (квадратичную) аппроксимацию целевой функции. С этой целью разложим целевую функцию в ряд Тейлора  Отбрасывая все члены разложения третьего порядка и выше, получим квадратичную аппроксимацию f(x):   На основе квадратичной аппроксимации функции f(x) сформируем последовательность итераций таким образом, чтобы во вновь получаемой точке x(k+1) градиент аппроксимирующей функции обращался в нуль. С этой целью продифференцируем (7.25) по Δx с учетом того, что все остальные компоненты являются константами. В результате получим  33. Какие недостатки метода Ньютона? Дайте их характеристику – предполагает вычисление вторых производных, что может быть связано с существенными трудностями; – очень чувствителен к выбору стартовой точки, т.е. может расходиться, если целевая функция не является выпуклой, а начальное приближение находится достаточно далеко от точки минимума. 35. Структурная идентификация В общем случае критерии ki(x) имеют различный смысл, размерность, интервал и шкалы измерения, т.е. не сравнимы между собой. Поэтому сначала их необходимо привести к некоторому общему базису (изоморфному виду). При этом процедура приведения должна быть однотипной для всех критериев, не зависеть от их смысла и отражать представление ЛПР о предпочтительности различных значений оценки. Такая базовая оценка может быть интерпретирована как функция полезности частных критериев  37. Принцип последовательной (лексикографической) оптимизации. Наибольшая трудность анализа любого крупного технического и народнохозяйственного проекта заключается внеобходимости решения задачи многокритериальной оптими за ции для управления его характеристиками. При этом многокритериальную задачу желательно свести к однокритериальной задаче, сформулировав единую цель при множестве критериев:  .Однако математика не может на это дать однозначного ответа (добиться оптимизации всех критериев одновременно невозможно в принципе), но может помочь принять решение и сделать правильный выбор. Реально возмож но достичь только некоторого компромисса (сочетания требуемых ка честв). В некоторых случаях эффективным методом сведения многокритериальной задачи к однокритериальной является расстановка приоритетов. В этом случае в многокритериальной задаче оптимизации на множестве допустимых решений задаются лексикографические отношения предпочтения: все критерии можно ранжировать (строго упорядочить) по важности так, что при последовательном рассмотрении критериев вначале используется первый критерий, затем второй и т.д. Задание набора ранжированных критериев  ,  ,…,  при синтезе сложной системы позволяет выделить некоторые стратегии в качестве оптимальных, упорядочить все стратегии по степени их предпочтительности (так располагают слова в словаре) и свести многокритериальную задачу к лексикографической [1].При отсутствии случайных и неопределенных факторов (детерминированной) в лексикографической задаче каждой стратегии соответствуют определенные числовые значения частных критериев. Оптимизация структуры и свойств сложной системы, состоящей из взаимосвязанных подсистем, находящихся на разных иерархических уровнях, легко представляется в лексикографической форме. Как уже отмечалось, при сравнении двух стратегий в первую очередь используется первый критерий: лучшей считается та стратегия, для которой значение этого критерия больше. Если значения первого критерия для обеих стратегий равны, то применяется второй критерий и предпочтение отдается той стратегии, для которой его значение больше. Если и второй критерий не позволяет выделить лучшую стратегию, привлекается третий и т.д. Лексикографическое отношение предпочтения задается в виде: - стратегия  предпочтительнее стратегии v (обозначается  ), если выполняется одно из  условий:1.  ;2.  ,  ;… r. ,  ,…, ,  ;… m. , ,…, ,  .- стратегии иv эквивалентны (  .38. Что положено в основу типизации ситуаций принятия решений? Приведите основные типы ситуаций выбора компромиссного решения. Введение понятия функции полезности частных критериев, как способа приведения разнородных факторов к изоморфному количественному виду и синтез соответствующей математической модели позволяет представить исходную задачу формирования многофакторной оценки альтернативы xєX в виде  Здесь все частные критерии представлены в изоморфной нормализованной форме, поэтому возможные ситуации принятия решений будут отличаться только степенью информированности ЛПР об относительной важности частных критериев и формой представления этой информации J(ai). Это обстоятельство положено в основу типизации ситуаций принятия решения.    39. Поясните задачу нормализации частных критериев При решении задачи нормализации частных критериев предполагается по умолчанию, что зависимость полезности от абсолютного значения частного критерия всегда линейна и выбор функций полезности осуществляется из класса линейных функций. Чаще всего используются количественная интервальная шкала, которой соответствует преобразование вида:  нить тем, что задача нормализации частных критериев рассматривается формально как задача вторичного шкалирования, а не как задача формализации информации о степени доминирования альтернатив или предпочтений ЛПР. |
.
), если выполнено одно из приведенных выше (
) условий.
; 
;