Методы анализа динамических задач многокритериальной оптимизации

• Автор: Брусникина, Наталья Борисовна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Москва
• Количество страниц: 137 с.

Глава 1. Полиэдральная аппроксимация множеств достижимости линейных

управляемых систем

§1.1. Полиэдральная аппроксимация выпуклых тел с частично гладкой

границей

§1.2. Метод расчета опорной функции множества достижимости линейной

управляемой системы с гарантированной оценкой погрешности

§1.3. Аппроксимация терминального множества достижимости с априорной

и апостериорной оценками погрешности

§1.4. Гарантированно внутренняя и гарантированно внешняя

аппроксимации терминального множества достижимости

Глава 2. Методы многошаговой аппроксимации множеств достижимости с

гарантированной оценкой погрешности
§2.1. Метод крупных шагов для аппроксимации последовательности
множеств достижимости
§2.2. Построение гарантированно внутренней и гарантированно внешней
аппроксимаций последовательности множеств достижимости
§2.3. Использование метода крупных шагов для аппроксимации множеств
достижимости непрерывно-дискретных систем
§2.4. Метод движущейся паретовой границы в динамических задачах
многокритериальной оптимизации
Глава 3. Реализация методов и экспериментальные расчеты
§3.1. Реализация метода построения аппроксимации терминального
множества достижимости линейной системы
§3.2. Реализация метода построения многошаговой аппроксимации
последовательности множеств достижимости
§3.3. Реализация метода построения аппроксимации паретовой границы для
динамической задачи многокритериальной оптимизации
Заключение
Список литературы
Приложение. Иллюстрации к главе

Математические методы оптимизации являются часто используемым средством компьютерной поддержки поиска эффективных решений сложных проблем. Среди таких методов все более важную роль играют методы многокритериальной оптимизации, позволяющие учесть противоречивые требования, предъявляемые к рассматриваемым решениям ([22]-[24], [29], [30]). Решением задачи многокритериальной оптимизации является множество решений, эффективных по Парето, и соответствующая (паретова) граница множества достижимых критериальных векторов.
В последнее время все большее внимание привлекают динамические задачи многокритериальной оптимизации, в которых требуется найти эффективные решения задач проектирования динамических систем. Методы анализа таких задач могут быть основаны на использовании методов оптимизации динамических систем, основы которых были заложены Л.С. Понтрягиным и его школой. Близость методов оптимизации динамических систем и многокритериальной оптимизации особенно ясно проявляется при сопоставлении методов аппроксимации множеств достижимости динамических систем, развиваемых в нашей стране наряду со школой Л.С. Понтрягина школами А.Б. Куржанского и Ф.Л. Черноусько, и методов аппроксимации парстовой (недоминируемой) границы в задачах многокритериальной оптимизации, разрабатываемых школой П.С. Краснощекова. Оба упомянутых класса методов основаны на аппроксимации многомерных множеств, так что результаты работ в одной области могут быть применены в другой. Этот факт использован в исследованиях группы A.B. Лотова, проводящихся в ВЦ РАН и ВМиК МГУ и направленных на аппроксимацию и визуализацию выпуклых множеств. Методы аппроксимации множеств достижимости для линейных управляемых систем, разработанные в 70-е годы прошлого века, были затем использованы в многокритериальном методе достижимых целей (МДЦ), в рамках которого

аппроксимируется либо множество достижимых критериальных векторов, либо его оболочка Эджворта-Парето (ОЭП), т.е. максимальное множество, имеющее ту же паретову границу. В свою очередь, оптимальные методы полиэдральной аппроксимации ОЭП были в дальнейшем использованы для аппроксимации выпуклых множеств достижимости динамических систем.
Данная диссертационная работа посвящена развитию методов многокритериальной оптимизации, предназначенных для анализа и поиска эффективных решений в динамических системах на основе применения идей МДЦ. В рамках МДЦ человек изучает многокритериальную паретову границу с помощью ее интерактивной визуализации с использованием двумерных сечений аппроксимации ОЭП. Далее он указывает предпочтительную точку на паретовой границе и получает компромиссное Парето-эффективное решение. Такой подход показал свою полезность в задачах проектирования.
Применение МДЦ для поиска парето-эффективных решений экономических задач началось еще в семидесятых годах ([26]), а с середины восьмидесятых годов МДЦ используется для поиска парето-эффективных стратегий улучшения состояния окружающей среды ([29], [30]). Другой важной областью применения МДЦ является изучение возможных вариантов технических систем на предпроектной стадии процесса проектирования. Дальнейшее развитие МДЦ связано с его применением в сети Интернет, где метод может быть использован в системах электронной торговли, выбора экологических решений и т.д. ([58]).
Необходимо отметить, что ранее МДЦ, как правило, применялся для визуализации паретовой границы в статических задачах многокритериальной оптимизации, а при изучении динамических моделей рассматриваемые задачи сводились к задачам статического типа на основе аппроксимации множеств достижимости только в терминальный момент времени. В то же время, представляющие практический интерес динамические задачи многокритериальной оптимизации, в которых критерии могут зависеть от

Из (1.25) следует, что Х(Т) с Хе(Т) +е^В, с Х^, и Хы ^(Х.(Т))_С] сХ(Т). Кроме того, 5ХігЛ,Хех,)<єи+а(Хіл)єГі+є2е+є2і.
В дальнейшем нам понадобится следующий факт.
Замечание 1.3. Пусть известно, что для некоторого множества X' выполняется 5>'{Х' ,Х(Т))<є'. Построим Ры - вписанный в А'ДТ) многогранник, полученный с помощью метода УО, такой, что дІ,(Р-м,Хі(Т))<£2! и пусть г(Ры) >єи+с'. Пусть Хех, - описанный вокруг Хе(Т) + (£и + є')Ві многогранник, полученный с помощью метода УО такой, что 5Н(Ха„Хе(Т) + (£іе + £')В, )<є2е. Тогда
X* с С с Х'с Х(Т) + £’В{ с Хе(Т) + (єи+є,)Ві с Х^,
где Хы = {Ры , и, кроме того,
^Н(Хы,Хех1)<(1 + а>(ХЬ1У)£'+£и+С0(Хы)£и+£2е +є2і.
Таким образом, многогранники Хы и Хех1 будут гарантированно внутренней и гарантированно внешней оценкой множества X'.
Апостериорная оценка погрешности. Задав значения Ье, А,. - шагов разбиения временного отрезка [О,Г] при аппроксимации множеств Хе(Т) и УДГ) многогранниками Ха, и Рш соответственно и с2е, с2і - точности аппроксимации для метода У О, получим, что
*і(Хь,Х„)*±еІГ(ЛТ + ЗНІЩ(і,:+а>(Хн)І,ї)+е2'+е3/+ (1.32)
+ \Х01+Т\иікіО,е) + о)(Х.м)К1(кі)), где функция К] (Л) в случае метода Рунге-Кутты задается формулой (1.22). Априорная оценка погрешности. Пусть задана некоторая точность £ и требуется определить: