Введение к работе
Актуальность темы диссертации. Математическое моделирование яв-іется общепринятым средством поиска эффективных решений сложных юблем. В процессе поиска эффективных решений все более важную роль рают методы многокритериальной оптимизации, позволяющие учесть про-:воречивые требования, предъявляемые к рассматриваемым решениям. Од-[м из таких методов является метод достижимых целей (МДЦ) (А. В. Ло-в, 1973), в рамках которого осуществляется аппроксимация и визуализация югомерных множеств достижимых значений критериев оценки качества шений (так называемых множеств достижимых целей). МДЦ помогает ис-едовать взаимозависимости между эффективными сочетаниями достижи->гх значений критериев, что способствует поиску и изучению разумных ком-юмиссных решений. МДЦ применяется для поиска эффективных решений ономических проблем, при изучении возможных вариантов технических стем на предпроектной стадии проектирования, а также в задачах поиска )фекгивных стратегий улучшения состояния окружающей среды. Для построения множеств достижимых значений критериев для выпук-IX, в том числе и линейных моделей, которые применяются для описания учаемых проблем во многих прикладных задачах, в рамках МДЦ исполь-ются итеративные методы аппроксимации выпуклых множеств многогран-ками, которые строятся с помощью расчета значений опорной функции проксимируемого множества. Данная диссертационная работа посвящена зработке и применению новых итеративных методов, предназначенных для проксимации выпуклых множеств, расчет значения опорной функции ко-рых требует значительного времени.
Построение аппроксимации выпуклых множеств многогранниками явля-гя классической проблемой. Стандартный подход к построению аппрокси-ірующих многогранников основан на расчете значений опорной функции проксимируемого множества на заданной сетке направлений. Показано, о использование заранее заданных (так называемых неадаптивных) сеток правлений не позволяет эффективно аппроксимировать многомерные мно-ютва (Д. Зонневенд, 1983). Для эффективной аппроксимации многомерных :ожеств в 80-х годах была выдвинута концепция адаптивной итеративной проксимации выпуклых множеств многогранниками и предложен первый тод такого типа — метод уточнения оценок (метод УО) (В. А. Бушенков и В. Лотов, 1982). В этом методе направления, для которых осуществляется счет опорной функции аппроксимируемого множества, формируются с пользованием описания уже построенного аппроксимирующего многогранни-. Разработка устойчивой численной схемы метода УО (О. Л. Черных, 1987)
позволила реализовать математическое обеспечение, предназначенное д, аппроксимации выпуклых множеств с использованием метода УО. До п следнего времени метод УО являлся единственным методом аппроксимаді выпуклых множеств многогранниками, используемым в рамках МДЦ.
С середины 80-х годов ведется теоретический анализ адаптивных итер тивных методов аппроксимации выпуклых множеств многогранниками. ДJ анализа адаптивных методов выдвинута концепция хаусдофовых методов а проксимации выпуклых компактных тел многогранниками и показано, ч-методы, являющиеся хаусдофовыми, оптимальны по порядку скорости сх димости для гладких тел (Г. К. Каменев, 1992). В 1994 г. Г. К. Каменев док зал, что метод УО является хаусдорфовым и потому оптимален по поряді скорости сходимости. Анализ практического использования метода УО пок зал, что его недостатком является то, что на каждой итерации используют* многократные расчеты значений опорной функции аппроксимируемого тел Каждый расчет значения опорной функции в практических задачах сложен требует значительного времени, что приводит к существенным затратам вр мени на построение и аппроксимацию множества достижимых значений кр: териев с помощью метода УО. Эта проблема особенно остро стоит при мн гократпой аппроксимации, которая необходима при исследовании практич ских задач поиска эффективных решений многокритериальных проблем.
Диссертация посвящена разработке, анализу и использованию новых хау дорфовых адаптивных методов аппроксимации выпуклых компактных т< многогранниками, которые являются оптимальными по скорости сходим сти при аппроксимации как гладких, так и негладких тел, и при этом і каждой итерации используют малое число расчетов опорной функции а; проксимируемого тела. Тема диссертации является актуальной, посколы до сих пор не существовало методов, обладающих такими свойствами, а і разработка позволила создать математическое обеспечение, предназначение для поддержки поиска эффективных решений в прикладных задачах с с щественным временем расчета опорной функции.
Цели диссертационной работы. Разработка нового хаусдорфового ад тивного метода аппроксимации выпуклых компактных тел многогранник; ми, оптимального по порядку скорости сходимости как для гладких, так негладких тел, и при этом не требующего большого числа расчетов значені: опорной функции аппроксимируемого тела на каждой итерации. Обоснов; ние оптимальности разработанного метода. Проведение сравнительного ан; лиза свойств разработанного и существующих методов на основе результате их теоретического и экспериментального исследования, в том числе экспер] ментального применения в практических задачах. Выработка рекомендацк
) использованию разработанного метода в прикладных исследованиях и его жменение в практических задачах поиска эффективных решений много-)итериальных проблем. Результаты, выносимые на защиту, состоят в следующем.
-
Разработан новый хаудорфов адаптивный метод аппроксимации выпук-»ix компактных тел многогранниками — модифицированный метод сближа-щихся многогранников.
-
Доказана оптимальность порядка числа вершин аппроксимирующих югогранников, порождаемых модифицированным методом сближающихся іогогранников, и оптимальность порядка числа расчетов опорной функции, шолняемых методом при аппроксимации гладких тел. Для выпуклых тел іщего вида получены теоретически оценки скорости сходимости модифици-іванного метода сближающихся многогранников, совпадающие по порядку теоретически оптимальными оценками, а также получены оценки числа .счетов опорной функции, выполняемых методом.
3. Проведено экспериментальное изучение разработанного метода на осно-
данных аппроксимации многомерных эллипсоидов, получены оценки его
имптотических характеристик и выработаны рекомендации по применению ітода для аппроксимации гладких тел.
4. Разработана и реализована (совместно с А. В. Лотовым, В. А. Бушен-
вым и Р. В. Ефремовым) система поддержки поиска эффективных страте-
й улучшения качества воды в бассейнах крупных рек. В систему включена
намическая библиотека, реализующая построение аппроксимации множе-
ва достижимых значений критериев или его оболочки Эджворта-Парето
разработанному методу. Система создана в рамках Федеральной целевой ограммы "Возрождение Волги". Проведен сравнительный анализ исполь-вания предложенного метода и метода уточнения оценок в задачах, изуча-ых при помощи системы, и выработаны рекомендации по их применению. Методы исследования, применяемые в диссертации, используют ма-матический аппарат теории выпуклых множеств, элементы теории выпук-[х многогранников, элементы дифференциальной геометрии и теории укла-к и покрытий, а также теорию численных методов, методы математической ітистики и методы создания комплексов программ.
Обоснованность научных положений. Теоретические результаты, по-ченные в диссертации, сформулированы в виде лемм и теорем и строго казаны. Экспериментальные исследования проведены по предварительно зработанным и теоретически обоснованным методикам. Научная новизна результатов. В диссертации предложен новый адап-зный итеративный метод аппроксимации выпуклых компактных тел мно-
гогранниками. Для предложенного метода теоретически показана оптималі ность порядка скорости сходимости, оптимальность метода по порядку чист вершин и по порядку числа расчетов опорной функции, выполняемых меті дом при аппроксимации гладких тел, а также получены оценки скорост сходимости метода при аппроксимации выпуклых тел общего вида, совпаді ющие по порядку с оптимальными теоретическими оценками, и оценки чиї ла расчетов опорной функции. Разработанный метод является единственны адаптивным итеративным методом, обладающим подобными свойствами.
Практическая ценность работы заключается в том, что предложеі ный в ней метод, возможность использования которого для аппроксимаци любых выпуклых тел обоснована теоретически, реализован в виде динамі ческой библиотеки Windows. Выработаны рекомендации по выбору значі ний параметра метода, влияющего на процесс аппроксимации. Это позы лило эффективно использовать метод в практических задачах исследоваїге многокритериальных проблем принятия решений. Динамическая библиоті ка является частью математического обеспечения системы поддержки поии эффективных стратегий улучшения качества воды в крупных реках, разр; ботанной в рамках Федеральной целевой программы "Возрождение Волги" применяемой специалистами проектной организации "Союзводпроект". Ря результатов диссертации использован в работе по проектам РФФИ N 95-0 00968 и N 98-01-00323.
Апробация работы. Основные результаты диссертации докладывалж на 2-й Московской международной конференции по исследованию операцг (Россия, Москва, 17-20 ноября 1998 г.), на семинарах Международной летне математической школы (Италия, Перуджиа, 25 июля-31 августа 1999 г.), і заседаниях XXVII школы-семинара "Математическое моделирование в прі блемах рационального природопользования" (Россия, Ростов-на-Дону, 13-1 сентября 1999 г.), на XV международной конференции "Принятие решею при многих критериях" (Турция, Анкара, 10-14 июля 2000 г.), на научнь семинарах Вычислительного центра РАН и факультета Вычислительной м, тематики и кибернетики МГУ им. М. В. Ломоносова.
Разработанная система поддержки поиска эффективных стратегий улу1 шения качества воды в крупных реках представлена в павильоне "Водні хозяйство" Всероссийского выставочного центра (Москва).
Публикации. По материалам диссертации опубликовано пять печатнь работ, одна работа опубликована в сети Интернет.
Структура и объем работы. Диссертация состоит из введения, трі глав, заключения, трех приложений и списка литературы. Содержит у| 9 страниц, включая список литературы из 75 наименований, ті иллюстращ и шесть таблиц.