автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Анализ методов полиэдральной аппроксимации выпуклых тел и их применение в задачах многокритериальной оптимизации

Содержание.

Введение.

Глава 1. Теоретический анализ асимптотической эффективности хаусдорфовых методов полиэдральной аппроксимации.

1.1. Некоторые понятия теории методов полиэдральной аппроксимации ВКТ многогранниками.

1.2. Формулировка основных результатов главы.

1.3. Доказательство основных результатов.

1.3.1. Метрика второй основной квадратичной формы на поверхности ВКТ.

1.3.2. Вспомогательные утверждения.

1.3.3. Доказательство основных теорем.

1.4. Анализ метода Уточнения Оценок.

1.5. Достижимость полученных оценок асимптотической эффективности.

Глава 2. Экспериментальный анализ эффективности методов полиэдральной аппроксимации ВКТ.

2.1. Некоторые определения и результаты теории двойственности методов полиэдральной аппроксимации.

2.2. Метод внешней полиэдральной аппроксимации, двойственный к методу У 0.

2.2.1. Схема отсечения, реализуемая методом УО*.

2.2.2. Реализация метода УО*.

2.2.3. Оценка асимптотической эффективности метода УО*

2.3. Методика проведения эксперимента.

2.3.1. План эксперимента.

2.3.2. Формирование совокупности эллипсоидов, участвующих в эксперименте.

2.3.3. Расчет аппроксимирующих последовательностей.

2.3.4. Расчет выборочной эффективности.

2.3.5. Методика оценки номера многогранника, с которого можно изучать асимптотические свойства в аппроксимирующей последовательности.

2.3.6. Методика оценки нижней ассимптотической эффективности.

2.4. Анализ экспериментальных данных.

2.4.1. Анализ асимптотической эффективности.

2.4.2. Дополнительные результаты.

2.5. Выводы из экспериментального исследования.

Глава 3. Использование методов аппроксимации в системе поддержки поиска эффективных стратегий улучшения качества воды.

3.1. Проблема поддержки поиска эффективных стратегий улучшения качества воды.

3.1.1. Постановка задачи.

3.1.2. Математическая модель планирования качества воды

3.1.3. Использование Метода Разумных Целей.

3.2. Метод Экономного Описания Аппроксимации.

3.2.1. Описание метода.

3.2.2. Экспериментальное исследование метода.

3.3. Система поддержки поиска стратегий улучшения качества воды.

3.3.1. Описание системы.

3.3.2. Пример использования системы.

3.3.3. Результаты экспериментального использования метода ЭОА в системе.

Математическое моделирование является общепринятым средством поиска эффективных решений сложных проблем. В процессе поиска эффективных решений все более важную роль играют методы многокритериальной оптимизации, позволяющие учесть противоречивые требования, предъявляемые к рассматриваемым решениям. Одним из таких методов является метод достижимых целей (МДЦ) ([1], [2]), в рамках которого осуществляется аппроксимация и визуализация многомерных множеств достижимых векторных критериев оценки качества решений (так называемых множеств достижимых целей). МДЦ дает возможность визуального изучения взаимозависимостей между недоминируемыми сочетаниями достижимых значений критериев (Паретову границу множества достижимых целей), что способствует поиску разумных компромиссных решений.

Применение МДЦ для поиска Парето-эффективных решений экономических задач началось еще в семидесятых годах ([3], [4]). С середины восьмидесятых годов МДЦ используется для поиска Парето-эффективных стратегий улучшения состояния окружающей среды (см., например, [2], [5] - [8]). Другой важной областью применения МДЦ является изучение возможных вариантов технических систем на предпроектной стадии процесса проектирования [2]. Дальнейшее развитие МДЦ связано с его применением в сети Интернет, где метод может быть использован в системах электронной торговли, выбора экологических решений и т.д.

Для построения множеств достижимых значений критериев в случае выпуклых, в том числе и линейных моделей, в рамках МДЦ используются итеративные методы аппроксимации выпуклых множеств многогранниками, которые строятся с помощью расчета значений опорной функции аппроксимируемого множества. Данная диссертационная работа посвящена изучению методов полиэдральной аппроксимации выпуклых компактных множеств, в частности методов, основанных на понятии двойственности выпуклых множеств.

Математическая задача многокритериальной оптимизации выглядит следующим образом. Пусть задано линейное пространство решений }¥ и пусть критериальное пространство является ¿/-мерным линейным пространством Пусть связь между решениями (стратегиями) и значениями критериев выбора решения устанавливается отображением Ж —> Е^. Пусть X с Ж - множество возможных (допустимых) решений. Будем считать, что лицо, принимающее решение (ЛПР) заинтересовано в уменьшении значений каждого из с! критериев. В этом случае, критериальная точка У е доминирует другую критериальную точку у е если у' <у, т.е. у\ <у„

1, ., с1, и У Фу. Не доминируемая по Парето (в дальнейшем, просто недоминируемая) граница множества У =ДХ), определяемая как множество недоминируемых точек у е У, в этом случае имеет вид Р(У)={у е 7: (У е 7:у йу,у Фу} = 0}.

Множество Р(У) характеризует совокупность компромиссов, разумных с точки зрения рассматриваемых критериев и представляет наибольший интерес для ЛПР, заинтересованных в поиске эффективных решений проблемы. Все методы поддержки принятия решения, основанные на многокритериальной оптимизации, так или иначе решают задачу представления информации о множестве Р(У) и дают возможность отбора наиболее интересных вариантов.

Особенностью МДЦ является предварительное построение аппроксимации множества У и дальнейшая визуализация множества

Р{Т) с использованием двумерных сечений аппроксимации. В том случае, если множество достижимых целей выпуклое, осуществляется его полиэдральная аппроксимация. В смысле вычислительных затрат этап аппроксимации - самый трудоемкий в МДЦ, поэтому он требует использования эффективных методов. В дальнейшем рассматриваются методы аппроксимации множества У, которое предполагается выпуклым, компактным и телесным.

Построение аппроксимации выпуклых компактных множеств многогранниками является классической проблемой, разработка способов решения которой представляет большой теоретический и практический интерес, поскольку задача аппроксимации выпуклых множеств возникает и во многих других приложениях: при аппроксимации множеств достижимости динамических систем, в математическом программировании, в компьютерной графике и других областях.

Задача аппроксимации выпуклых компактных множеств многогранниками ставится следующим образом: в евклидовом пространстве для заданного выпуклого компактного тела (ВКТ) нужно построить последовательность выпуклых телесных многогранников, аппроксимирующих его с любой степенью точности. Среди методов полиэдральной аппроксимации ВКТ имеется большая группа методов, в которых построение аппроксимирующих многогранников основано на построении асимптотически оптимальных покрытий поверхности аппроксимируемого тела (см., например, [9] - [13]). Для с1> 2 эти методы являются теоретическими конструкциями, посредством которых можно получить свойства задач полиэдральной аппроксимации ВКТ. На практике используются итеративные методы аппроксимации ([14] - [21]).

Под итеративным методом полиэдральной аппроксимации тела С понимают метод, в котором строятся последовательности телесных многогранников Р°, Р1Рп,., сходящиеся к С, причем на каждой итерации п последующий многогранник Рп строится на основе предыдущего за счет добавления к совокупности его вершин (либо к совокупности его гиперграней) единственной новой вершины (гиперграни).

Итеративные методы различаются способом построения последующего многогранника по предыдущему. В данной работе рассматриваются методы, использующие две схемы построения последующего многогранника по предыдущему: схему восполнения и схему отсечения. В схеме восполнения, предположив построенным вписанный в тело С многогранник Рп, («+1)-ю итерацию реализуют в виде двух шагов: выбора точки рпедС и построения нового вписанного в С многогранника Р"+] := сопу^иР}. Конкретные методы, основанные на схеме восполнения, можно характеризовать способами решения двух задач: способом выборарпедС и способом построения сопу{р„иР} в требуемом виде. В схеме отсечения предполагается построенным описанный вокруг тела С многогранник Р". Тогда («+1)-я итерация состоит из двух шагов: выбора направления ип&5?~1 и построения нового описанного вокруг С многогранника рп+1 Где Ци^ С) - опорное к С гиперпространство, с нормалью ип. Конкретные методы, основанные на схеме отсечения, можно характеризовать способами решения задач выбора направления ип и построения РпглЬ{ит С) в требуемом виде.

Эти две схемы могут быть реализованы на основе вычисления опорной функции аппроксимируемого тела С, определяемой как

С) = шах {<и, х>\хеС), (1) где и е^"1 , где = {меМ"': ||и|| = 1}. Схема восполнения реализуется следующим образом. Пусть дан многогранник Рп, вписанный в С. Тогда для некоторого направления ип находится такая граничная точка р„ , что <ип,рп>= g{um С). Эта точка используется в качестве вершины нового вписанного в С многогранника сот/{рпиРп}. В случае схемы отсечения считается, что задан многогранник Р" , описанный вокруг С. Тогда для некоторого направления рассчитывается значение опорной функции g{un, С), вместе с и„ определяющее полупространство Ь = [у е <иту> < g(и„, С)}, которое затем используется для построения нового описанного вокруг С многогранника Рп глЬ. Отметим, что в МДЦ для расчета значения опорной функции (1) множества/(X) требуется решить задачу оптимизации тах {<и, у>'у=/(х), х^Х}.

Наиболее эффективными являются адаптивные методы выбора направлений направление выбирается на основе информации об аппроксимируемом теле, полученной на предыдущих итерациях. Впервые идеи адаптивной аппроксимации тел были предложены в [14] и [15]. В [14] для аппроксимации части границы двумерного выпуклого тела было предложено уточнение вписанного в тело аппроксимирующего многогранника в направлении нормали того ребра, на котором достигается наибольшее отклонение многогранника от аппроксимируемого тела. В [15] предложено аппроксимировать проекцию выпуклого компактного множества последовательностью многогранников. Синтез этих двух идей осуществлен в методе Уточнения Оценок (У О) [18]. Метод У О, использующий схему восполнения, до недавнего времени являлся единственным адаптивным методом аппроксимации ВКТ многогранниками, используемым на практике.

Метод УО состоит в следующем. Пусть требуется аппроксимировать тело С. Пусть задана желаемая точность аппроксимации е. На п-й итерации должен быть построен вписанный в тело С многогранник Рп в виде как множества решений системы линейных неравенств, так и списка вершин, для которых указана принадлежность к гиперграням многогранника (так называемое двойное описание). Пусть 1]{Рп) - множество единичных внешних нормалей гиперграней многогранника Рп, которое можно считать заданным системой линейных неравенств, описывающей многогранник Рп. Тогда п+ 1-я итерация метода УО состоит в следующем.

На первом шаге для каждого из неравенств описания многогранника Рп (т.е. направлений из и{Рп)) рассчитываем опорную функцию тела С на основе решения соответствующей задачи оптимизации (1). Выбираем такое направление иеЩР"), для которого величина g(u, С) - g( и, Рп) максимальна. Отметим, что в процессе расчета опорной функции для направлений ие11(Рп) находятся и точки р границы тела С, что <и, р> = g(u, С). Если величина та х {g( и, С) - g(li, Рп): иеЩР")} меньше желаемой точности аппроксимации £, то процесс завершается. В противном случае, строится выпуклая оболочка многогранника Рп и точки рп, соответствующей направлению ип, на котором достигается тах {g{u, С) - g{u, Рп)\ и<=и(Рп)}. Сложная операция построения сопу{р„ и Рп} в виде множества решений системы линейных неравенств осуществляется на основе специально разработанного алгоритма, использующего двойное описание многогранника Рп [22]. Множество сопу{р„ и Р"} используется в качестве новой аппроксимации Рп+Х множества С.

Для целей анализа качества аппроксимации множества С последовательностью многогранников {Р"}„=0.1.2. . удобно использовать описание метода У О в виде схемы восполнения [19], в которой отсутствуют черты метода, важные для его реализации, но имеющие значение для анализа сходимости.

Шаг 1: а) на основе измерения значений опорной функции находим направление ип е U(Pn) такое, что щ = argmax {g( u,Q-g( и, Рп): ие U{Pn)}. Если |g(un, С) - g{un, Рп)| < s, то останавливаем работу метода, иначе переходим к п. б). б) Берем такую точку рп границы тела С, что для направления ип, найденного в п. а) шага 1, выполняется <ип,рп> = g(un, С).

Шаг 2: в качестве очередного многогранника РпЛ 1 берем conv{pnu Рп].

Разработка численной схемы метода УО [22], устойчивой к ошибкам округления, позволила реализовать программное обеспечение, выполняющее аппроксимацию ВКТ, заданного алгоритмически своей опорной функцией, в автоматическом режиме без участия пользователя.

Теоретические исследования в области полиэдральной аппроксимации ВКТ привели к понятию многогранников наилучшей аппроксимации (МНА) [23], которые доставляют минимум отклонения от аппроксимируемого множества при заданной сложности многогранника, под которой в данной работе понимается число вершин для МНА внутренней полиэдральной аппроксимации или гиперграней для МНА внешней полиэдральной аппроксимации. В [23] исследованы асимптотические свойства МНА и показано, что для тел с дважды непрерывно дифференцируемой границей и положительными главными кривизнами (для класса таких тел принято 2 обозначение %' ) выполняется lim ö(C,Pm(C))m2l{d~X) =А(С), m— где через Рт(С) обозначен МНА тела С сложности т, а через А(С) обозначается аппроксимируемость тела С, которая является теоретической характеристикой возможностей приближения тела многогранниками. Способы построения МНА существуют только для некоторых двумерных тел; в общем случае такие методы не известны. Эффективные методы полиэдральной аппроксимации ВКТ должны приводить к построению многогранников, близких, в каком-то смысле, по своим аппроксимирующим свойствам к МНА. Отметим, что в силу определения МНА, ни одна последовательность вписанных (или описанных) многогранников с последовательно возрастающим числом вершин (гиперграней), не может обеспечить лучшую точность аппроксимации, чем последовательность МНА для данного тела. Как оказалось, существуют итеративные методы ([15], л

19], [20], [21]), строящие для тел из св последовательности многогранников {Р"}п=0,1,2,., Для которых при п —» со имеет место

8{С,Рп)~ 0{[1{т{Рп))21(с1'])), (2) где т{Р п) - сложность описания Р п. Поэтому 2l{d-\) является асимптотически оптимальным порядком сложности для итеративных методов аппроксимации для тел из . Итеративный метод называют оптимальным по порядку сложности для тела из V , если он строит аппроксимирующую последовательность, для которой выполняется (2).

Теоретические исследования адаптивных итеративных методов привели к выделению классов методов аппроксимации, для которых доказана оптимальность по порядку сложности аппроксимирующих многогранников для тел из %" ([25]). Это, например, хаус-дорфовы методы, введенные в [25]. В частности доказано ([26]) что метод УО является хаусдорфовым и потому асимптотически оптимален по порядку числа вершин для тел из %' . В связи с этим представляют интерес оценки констант сходимости хаусдорфовых методов.

В процессе исследования констант сходимости методов, асимптотически оптимальных по порядку сложности, в [24] введено понятие эффективности аппроксимации ВКТ С последовательностью многогранников F. Пусть F={Pn}„^- сходящаяся к С последовательность вписанных или описанных многогранников. Через rj(P) обозначим отношение расстояния (по Хаусдорфу) от тела С до МНА с той же сложностью, что и многогранник Р, к расстоянию от С до Р:

S(C,Pm{P)(C)) //(г) =---------------------.

6(С,Р)

Величину r](F) = liminf rj(Pn) (3)

П—>00 называют (нижней асимптотической) эффективностью аппроксимации тела С последовательностью F. Под эффективностью метода полиэдральной аппроксимации тела С понимают эффективность порождаемой им последовательности многогранников. Очевидно, что 0 < j](F) < 1, причем эффективность аппроксимации тела С последовательностью МНА равна 1. Метод полиэдральной аппроксимации, порождающий для тела С последовательность с нижней асимптотической эффективностью, большей нуля, называют асимптотически эффективным для тела С. Согласно [25], хаусдорфовы методы для тел из класса W являются асимптотически эффективными.

В [24] получена оценка эффективности хаусдорфовых методов, которая, однако, значительно уступает результатам, полученным в экспериментах по аппроксимации эллипсоидов, описанным в [19], [27] - [29], и, в частности, зависит от асферичности аппроксимируемого тела. Представляет практический интерес задача построения более точных оценок эффективности хаусдорфовых методов. Эта задача рассматривается в первой главе диссертации.

Все изложенные выше факты, касающиеся хаусдорфовых методов в равной степени справедливы как для итеративных методов, реализующих схему восполнения, так и для методов, реализующих схему отсечения. Однако на практике распространение получили методы, реализующие схему восполнения, и их свойства хорошо изучены экспериментально ([19], [20], [27] - [30]). В частности, отсутствует информация о практической реализации эффективных хаусдорфовых методов внешней полиэдральной аппроксимации, реализующих схему отсечения, и о работах, посвященных их экспериментальному исследованию. В то же время, такие методы могут быть востребованы на практике, например в случае, когда необходимо получить аппроксимацию выпуклого тела многогранником с возможно меньшим числом гиперграней. Методы, реализующие схему восполнения, не решают указанной задачи. В то же время ха-усдорфовы методы полиэдральной аппроксимации, реализующие схему отсечения, асимптотически оптимальны по порядку числа ги-пергранеи для тел из СС' . Актуальность задачи построения аппроксимирующих многогранников с малым числом гиперграней объясняется в рамках МДЦ тем, что сложность этапа визуализации множества достижимых целей определяется числом гиперграней в аппроксимирующем многограннике.

Некоторые адаптивные итеративные методы внешней полиэдральной аппроксимации предложены в [16], [19], [20], [21]. В методе из [16] очередное направление и е выбирается адаптивно из узлов априорно заданной регулярной сетки на б^"1 с учетом теоретической оценки локального отклонения уточняемого многогранника от аппроксимируемого тела. В [16] показано, что для С е %' из М6' при

7 Л

3=2,ЗяСе(£ из К. при > 3 этот метод обеспечивает сходимость в метрике Хаусдорфа со скоростью 0(п2/(сМ) ^ п), где п - номер итерации метода, отличающийся на постоянную величину от числа гиперграней описанного аппроксимирующего многогранника. Появление множителя ^ п в оценке скорости сходимости метода из [16] может быть обусловлено априорным выбором сетки направлений на З^"1. В [19] было предложено два адаптивных метода, в которых строятся последовательности описанных многогранников. Первый метод (Базовый Метод Отсечения) является чисто теоретической конструкцией, поскольку требует вычисления расстояния по Хаус-дорфу между двумя компактными множествами. Второй метод из [19], известный как метод Сближающихся Многогранников (СМ), а также его модификация, предложенная в [20], являются, по сути, методами внутренней полиэдральной аппроксимации, а последовательности описанных многогранников являются в них вспомогательным построением и строятся для того, чтобы уменьшить число вычислений опорной функции на аппроксимируемом теле. В результате построенные внешние многогранники не обладают удовлетворительными оценками асимптотической эффективности.

Один из способов построения методов внешней полиэдральной аппроксимации дается развитой в [21] теорией двойственности методов внутренней и внешней полиэдральной аппроксимации. Она основывается на понятии множества, сопряженного к выпуклому множеству ([40]), и на том факте, что если Т7 = {Рп}п=олд,. является последовательностью многогранников, вписанных в ВКТ С, то сопряженная последовательность многогранников Т7* = {(Р")*}я=о,1,2,. является последовательностью описанных вокруг сопряженного тела С*. Если прямой метод строит для тела С последовательность ^ то двойственный ему метод строит для тела С* последовательность Г*. В [21] показано, что методы двойственные к хаусдорфовым методам внутренней полиэдральной аппроксимации будут также хаусдорфо-выми, и, значит, оптимальными по порядку числа гиперграней для тел из %' . Это позволяет строить двойственные методы с априорно известными свойствами сходимости. Поэтому такая методика заслуживает тщательного исследования.

В то же время, теоретические оценки эффективности двойственных методов, полученные в [21], существенно зависят от асферичности аппроксимируемых тел. В связи с этим возникает важный для практики вопрос о том, является ли свойство зависимости оценок двойственных методов от асферичности следствием методики, использованной для их получения, или имеет место в действительности. Ответить на этот вопрос может экспериментальное исследование, направленное на изучение асимптотических свойств двойственных методов. Экспериментальные исследования асимптотических свойств адаптивных методов проводились в [19], [20], [27] -[30]. В качестве объектов эксперимента в этих работах брались многомерные эллипсоиды. Использование эллипсоидов в этих экспериментах основано на том, что для любого эллипсоида Е размерности не больше четырех может быть вычислена его аппроксимируемость А(Е) ([19]). Во второй главе диссертационной работы описаны результаты проведения экспериментов по аппроксимации многомерных эллипсоидов с использованием метода, двойственного методу УО. Эти эксперименты показали практическую применимость такого метода.

В третьей главе описывается использование методов полиэдральной аппроксимации в проблемах улучшения качества воды. Задача улучшения качества воды состоит в выработке рекомендаций по размещению оборудования, предназначенного для очистки стоков промышленности и жилищно-коммунального хозяйства, и по выбору технологии очистки. Для поддержки выбора эффективных стратегий улучшения качества воды в Вычислительном центре РАН была разработана методика целостного рассмотрения водохозяйственных проблем [7], заключающаяся в использовании интегрированных моделей для описания проблем и применении МДЦ для поддержки их исследования. С середины восьмидесятых годов МДЦ успешно используется для поиска эффективных стратегий улучшения качества воды в бассейнах крупных рек ([2], [6] - [8]). На базе МДЦ создаются системы поддержки поиска эффективных стратегий улучшения качества воды, предназначенные для установки в бассейновых управлениях.

В зависимости от масштаба решаемой проблемы, такие системы адаптируются для бассейна крупной реки в целом или для любого его участка. При этом используется разная детализация в математической модели изучаемой проблемы. Для анализа бассейна в целом используется линейная модель очистки стоков, в рамках которой предприятия группируются в отрасли по принципу схожести состава загрязнения, и к стоку от каждой из отраслей может быть применено несколько технологий в разных пропорциях ([2]). В локальной проблеме задача улучшения качества воды сводится к проблеме с большим конечным числом вариантов решения. При этом метод МДЦ модифицируется в Метод Разумных Целей (МРЦ)

38]), в котором осуществляется аппроксимация выпуклой оболочки критериальных векторов, соответствующих вариантам решения.

Число возможных вариантов стратегий очистки в задаче улучшения качества воды может оказаться очень большим - порядка нескольких миллионов. При аппроксимации выпуклой оболочки такого большого числа точек методами, реализующими схему восполнения, может быть построен аппроксимирующий многогранник с очень большим числом гиперграней. Надо отметить, что от числа гиперграней аппроксимирующего многогранника зависит скорость визуализации его сечений. Технология Диалоговых Карт Решений (ДКР) с помощью интерактивной анимации цветных карт решений (наборов сечений, в которых от сечения к сечению меняется только один некоординатный критерий) позволяет изобразить Паретову границу для нескольких (до семи) критериев в наглядной форме. Такая наглядность, однако, может быть достигнута только в случае быстрой и стабильной работы программного обеспечения ДКР. Поскольку системы поддержки поиска эффективных стратегий улучшения качества воды планируется устанавливать в бассейновых управлениях, т.е. в учреждениях с, возможно, слабой компьютерной базой, то для надежной работы программного обеспечения МДЦ необходимо разрабатывать методы полиэдральной аппроксимации ВКТ, строящие аппроксимирующие многогранники с небольшим числом гиперграней. Таким образом, возникает задача практического использования эффективных адаптивных методов полиэдральной аппроксимации с малым числом гиперграней, которая решается в главе 3.

Итак, диссертационная работа направлена на дальнейшее развитие методов полиэдральной аппроксимации ВКТ, их исследование и применение к решению практических задач.

Цели диссертационной работы

• Построение априорных оценок нижней асимптотической эффективности аппроксимации многомерных тел хаусдорфовыми методами внутренней и внешней полиэдральной аппроксимации.

• Уточнение теоретических оценок асимптотической эффективности метода внешней полиэдральной аппроксимации, двойственного к методу УО, на основе данных его экспериментального исследования.

• Использование методов аппроксимации ВКТ в системе поддержки принятия решений об улучшении качества воды в сегментах бассейнов крупных рек и исследование с ее помощью конкретной природоохранной задачи.

В первой главе проведено исследование нижней асимптотической эффективности хаусдорфовых методов аппроксимации в классе тел с€ . В разделе 1.1 изложены основные понятия и результаты теории методов аппроксимации выпуклых компактных тел многогранниками, использующиеся в дальнейшем. В разделах 1.2 и 1.3 получены априорные оценки нижней асимптотической эффективности аппроксимации многомерных тел из 'б2 последовательностями многогранников, которые строятся хаусдорфовыми методами как внутренней так и внешней полиэдральной аппроксимации. Полученные оценки оказались не зависящими от аппроксимируемого тела. В качестве примера, иллюстрирующего полученные результаты, эти оценки применены к методу УО. В разделе 1.4 показано, что для многомерных тел из с6 метод УО позволяет строить вписанные многогранники, асимптотически отличающиеся по точности от многогранников наилучшей аппроксимации не более чем в четыре раза. Непосредственные вычисления, проведенные в разделе 1.5 для метода УО при аппроксимации круга, показывают, что полученные оценки достижимы.

Во второй главе диссертационной работы проведено экспериментальное исследование метода внешней аппроксимации УО*, двойственного к методу УО. В разделе 2.1 даны необходимые для дальнейшего изложения сведения из теории двойственности методов полиэдральной аппроксимации ВКТ. В разделе 2.2 на основе использования теории двойственности получено описание метода УО* и теоретически показана его оптимальность по порядку числа гиперграней. В разделе 2.3 описана методика проведения эксперимента, направленного на оценку асимптотической эффективности метода УО*. В разделе 2.4 проведен анализ экспериментальных данных. Анализ показал, что асимптотическая эффективность метода УО* зависит от асферичности аппроксимируемого тела. В то же время показано, что теоретические оценки оказались очень грубыми. В ходе экспериментального исследования метода УО* разработана методика, направленная на выявление асимптотического поведения аппроксимирующих последовательностей. Результаты эксперимента обсуждены в разделе 2.5, где даны рекомендации по поводу применения метода на практике.

В главе 3 методы полиэдральной аппроксимации ВКТ применяются в системе поддержки поиска стратегий улучшения качества воды в бассейне реки. Раздел 3.1. содержит постановку и методику решения задачи. В разделе 3.1.1. описана интегрированная математическая модель целостного рассмотрения проблемы; модель используется для расчета конечной совокупности возможных стратегий улучшения качества воды. В разделе 3.1.2 дана математическая формулировка Метода Разумных Целей (МРЦ), который позволяет осуществлять отбор природоохранных стратегий с использованием графического представления информации о множестве Парето.

В разделе 3.2. разрабатывается метод Экономного Описания Аппроксимации (ЭОА), предназначенный для аппроксимации многомерной выпуклой оболочки большого числа точек многогранником с небольшим числом гиперграней. Такая задача возникает в связи с тем, что в задачах улучшения качества воды число возможных природоохранных мероприятий может быть очень велико - до нескольких миллионов, а программное обеспечение предназначено для использования в организациях со слабой компьютерной базой.

Метод ЭОА основан на идеях теории двойственности методов полиэдральной аппроксимации. В разделе 3.2.1. дается описание метода. В разделе 3.2.2 свойства метода исследуются экспериментально на основе аппроксимации выпуклых оболочек специально сгенерированных совокупностей точек. В качестве таких точек взяты множества вершин т.н. циклических многогранников ([39]).

Раздел 3.3. содержит описание системы поддержки отбора среди совокупности возможных стратегий улучшения качества воды на базе МРЦ. Эта система адаптирована к бассейну реки Оки в районе города Коломны. Она реализована диссертантом совместно с А. В. Лотовым, Л. В. Бурмистровой и В. А. Бушенковым. В 3.3.1 описаны подсистемы СППР. При аппроксимации выпуклой оболочки точек в СППР экспериментально использовался исполняемый модуль, реализующий метод ЭОА. Пример использования системы рассмотрен в разделе 3.3.2. Особенность задачи состоит в относительно большом числе стратегий улучшения качества воды : примерно 400 тысяч исходных стратегий. В разделе 3.3.3 проведен сравнительный анализ методов ЭОА и УО в этой задаче.

В Заключении сформулированы результаты диссертационной работы, выносимые на защиту.

Приложения содержат графические материалы экспериментального исследования метода УО*, иллюстрации работы в СППР об улучшении качества воды в бассейне реки Коломна, графические материалы экспериментального исследования методЯЭО&ме диссертации опубликовано 10 печатных работ [46] - [55].

Основные результаты диссертации докладывались на заседаниях XXVII школы-семинара "Математическое моделирование в проблемах рационального природопользования" (Россия, Ростов-на-Дону, 13—18 сентября 1999 г.), на XV международной конференции "Принятие решений при многих критериях" (Турция, Анкара, 10-14 июля 2000 г.), на научной сессии "Проблемы прикладной математики и информатики - 2000", посвященной 90-летию академика А.А.Дородницына (Россия, Москва, 6-7 декабря 2000 г.), на национальном конгрессе Мексиканского математического общества (Mexico, Guadalajara, 1999, October 10 -16), на 3-й Московской международной конференции по исследованию операций (Россия, Москва, 4-6 апреля 2001 г.), на научной конференции "Математические модели сложных систем и междисциплинарные исследования", посвященной 85-летию академика H.H. Моисеева (23-24 октября 2002), на научных семинарах Вычислительного центра РАН и Механико-математического факультета МГУ.

Автор искренне благодарен научному руководителю A.B. Лотову за постановки задач и внимание к работе, Г.К. Каменеву за помощь в работе и обсуждение результатов, а также JI.B. Бурмистровой за предоставление материалов, использованных при постановке эксперимента по аппроксимации эллипсоидов и ценные замечания.

2.5. Выводы из экспериментального исследования

Эффективность аппроксимации методом УО* зависит от двух связанных между собой характеристик аппроксимируемого эллипсоида - его аппроксимируемости и асферичности. Это невыгодно отличает метод УО* от метода УО. Напомним, что мы получили метод УО*, прямо описав для любого тела Се ^применение метода У О к двойственному телу С* и переход от полученной последовательности многогранников к двойственной. По такому принципу, в силу утверждения 1, можно для любого метода внутренней полиэдральной аппроксимации построить некоторый метод внешней полиэдральной аппроксимации. Согласно теоретической оценки (82), эффективность таких методов зависит от асферичности эллипсоида, что и подтвердилось на практике. В работе показано, что такой подход действительно приводит к методу с меньшей эффективностью, чем базовый. Однако оценка (82), полученная из теории, оказалась сильно заниженной в сравнении с экспериментальными данными. Кроме того оценка (82) не зависит от размерности пространства. Вместе с тем, полученные результаты позволяют предположить, что эффективность метода У О* растет с увеличением размерности. Итак, исследование показало, что эффективность метода УО* зависит от асферичности аппроксимируемого тела; в то же время удалось значительно улучшить теоретические оценки зависимости эффективности метода от асферичности.

Выборка экспериментальных эллипсоидов имеет характерное расслоение на два вида; эллипсоиды каждого вида ведут себя по-разному при аппроксимации. Выборка эллипсоидов была взята та же самая, что и в исследованиях [30], однако там подобного эффекта не наблюдалось. Не наблюдалось его и в работах [28, 29]. Автор связывает эти эффекты с чувствительностью метода УО* к характеристикам тел, таким как асферичность и аппроксимируемость. Два эллипсоида принадлежат к двум разным видам, если при равной аппроксимируемости (асферичности) они имеют существенно разную асферичность (аппроксимируемость). Эллипсоид с меньшей асферичностью (аппроксимируемостью) имеет лучшие аппроксимацион-ные характеристики, чем эллипсоид с большей асферичностью (аппроксимируемостью), в том смысле, что эффективность аппроксимации первого изменяется более предсказуемо при росте числа гиперграней аппроксимирующего многогранника - не уходит далеко от своих средних значений. Кроме того, эффективность аппроксимации второго убывает с возрастанием числа гиперграней. Для с1 = 3 удалось установить, что эллипсоиды разных типов различаются на уровне строения.

На практике процесс аппроксимации останавливается либо по достижении некоторой точности аппроксимации, либо когда построено достаточное число гиперграней. Можно также, наблюдая за ходом аппроксимации, остановить процесс вручную. Можно сделать практический вывод, что для первого эллипсоида не имеет принципиального значения, какой способ остановки выбрать, а для второго предпочтительнее останавливать процесс вручную после резкого увеличения точности аппроксимации, либо, если может быть реализована только автоматическая остановка, то целесообразно выбрать остановку по достижении точности. Вообще, для практики целесообразно масштабировать переменные так, чтобы аппроксимируемые тела имели минимально возможную асферичность, ведь, как правило, при решении практических задач модуль аппроксимации тел входит в более сложную систему, и методы, на базе которых реализованы другие модули, бывают также чувствительны к асферичности.

Глава 3. Использование методов аппроксимации в системе поддержки поиска эффективных стратегий улучшения качества воды

3.1. Проблема поддержки поиска эффективных стратегий улучшения качества воды 3.1.1. ПОСТАНОВКА ЗАДАЧИ

Традиционным подходом к проблеме улучшения качества воды в бассейнах рек является оптимизационный подход. Он заключается в нахождении минимальной стоимости проекта при условии удовлетворения экологических требований. Такой подход обычно приводит к проектам, превышающим финансовые возможности. Зачастую решения, удовлетворяющего всем ограничениям, может просто не существовать. Для поддержки поиска приемлемых стратегий улучшения качества воды, приносящих заметный эффект даже при относительно небольших затратах, в Вычислительном центре РАН разработан многокритериальный подход к решению проблемы проектирования качества воды [2]. В рамках этого подхода, мероприятия, направленные на улучшение качества воды, разбиваются на два этапа: этап резкого уменьшения загрязнения за счет эффективного использования относительно небольших капиталовложений и этап окончательного решения проблемы улучшения качества воды в реке. Методика, разработанная в [2], направлена на поддержку поиска стратегий, решающих задачи первого этапа. Методика основывается на использовании интегрированных упрощенных математических моделей для описания проблем и применении МДЦ для поддержки поиска предпочтительных стратегий.

В математических моделях, используемых при анализе природоохранных стратегий, описываются процессы различной природы (физические, биологические, экономические, социальные, и т.д.). Это затрудняет поиск предпочтительных стратегий. Для преодоления такой трудности была предложена концепция целостного описания экологических проблем, в рамках которой используют интегрированные модели, описывающие изучаемую экологическую проблему всесторонне [2]. Интегрированные упрощенные модели строятся на основе объединения разнородных моделей частных процессов в единую модель. Процесс построения интегрированной модели базируется на построении упрощенного описания отдельных подсистем (так называемая параметризация подсистем). Такое описание можно сформулировать на основе аппроксимации зависимостей, связывающих выходы подсистем с их входами. Для этого могут быть использованы имитационные расчеты по исходным моделям. В том случае, когда модели подсистем отсутствуют, для построения упрощенных описаний могут быть использованы результаты натурных экспериментов или экспертные оценки.

Интегрированная модель составляется из построенных параметризаций моделей отдельных подсистем, описания областей их применимости (ограничений на диапазоны входных переменных), балансовых и других соотношений, связывающих подсистемы между собой, а также ограничений на возможные стратегии решения рассматриваемых экологических проблем.

В данной работе описанная методика применяется для решения задачи выбора стратегий уменьшения выброса загрязнителей из постоянно действующих источников в период наименьшего стока.

3.1.2. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ПЛАНИРОВАНИЯ КАЧЕСТВА ВОДЫ

Адекватная математическая модель, которая могла бы полностью описать проблему улучшения качества воды в бассейне реки, должна была бы включать подробное описание стоков предприятий различных типов, технологий их очистки, а также детальное описание переноса различных типов загрязнения вдоль реки с учетом особенностей рельефа русла реки, различных режимов стока и т.д. Такие модели, однако, пригодны лишь для расчетов по малому числу вариантов. Поэтому при выборе стратегий улучшения качества воды, требуется использовать интегрированные модели.

Рассмотрим интегрированную математическую модель, использованную в рассматриваемой задаче. Рассматривается часть бассейна реки. В модели предполагается, что задано некоторое число предприятий, осуществляющих выброс загрязненных сточных вод. Концентрации загрязняющих веществ измеряются в гидрологических пунктах, расположенных ниже точек выброса.

Математическая модель состоит из трех частей:

• модели выброса загрязнителей,

• модели переноса загрязнителей,

• модели очистки стоков.

В соответствии с рассматриваемой задачей считается, что объемы сточных вод и их состав известны и постоянны во времени. В модели очистки стоков задается совокупность возможных технологий очистки с указанием результатов их применения. Для каждой из технологий задается стоимость очистки единицы объема сточных вод. Эта модель позволяет связать уменьшение выбросов загрязнителей с объемом капиталовложений в очистное оборудование предприятий.

Перейдем к вопросу об упрощенной модели переноса загрязнения. Используемая упрощенная модель переноса загрязнения представляет собой матрицу влияния, которая задает линейную модель, позволяющую вычислять концентрации загрязнителей в любом гидрологическом пункте при заданных выбросах загрязнителей на предприятиях. В данной работе используются матрицы влияния для модели переноса, построенные сотрудниками АО Союзводпроект с помощью имитационных экспериментов, в которых перенос загрязнителей в период минимального стока рассчитывается на основе использования известной коммерческой системы моделирования водных объектов MIKE 11. Эта система, разработанная Датским гидрологическим институтом, использует нелинейные модели переноса. Важно что для этих моделей, однако, матрица влияния может быть построена точно. Методика оценки матрицы влияния подробно описана в [45].

В модели рассматривается К предприятий, расположенных на некотором участке бассейна реки. Гидрологические пункты, расположенные ниже точек выброса, разбивают реку на К участков (створов). Расход воды Qk в реке в районе к-то гидрологического пункта задан. Пусть / - число загрязнителей, рассматриваемых в модели. Уравнение баланса /-го загрязнителя для к-то створа имеет вид К

Mki = Y,Skimn+ökim?> * = 1,2,.К, / = 1,2,./, г=1 где Mki - поток /-го загрязнителя в реке через к-й гидрологический пункт, rki - коэффициент распада /-го загрязнителя, поступившего из г-го предприятия в к -ый створ (коэффициент матрицы влияния), mri - сброс /-го загрязнителя в единицу времени в составе сточных вод r-го предприятия.

Считается, что потоки каждого из I загрязнителей выше рассматриваемого участка бассейна реки (т0,) заданы заранее.

В технологической модели очистки стоков рассматривается совокупность из N возможных технологий очистки, заданных своими удельными приведенными затратами и коэффициентами очистки сбросов, различными для различных загрязнителей. Задача состоит в выборе некоторой технологии для каждого из К предприятий. Модель очистки стоков имеет следующий вид. Потоки загрязнителей в составе сточных вод, т.е. величины ты, заданы соотношениями

Щ = <(1-Ек = 1,2/ = 1,2,./ п=1 где т°к1 ~ поток /-го загрязнителя в составе сточных вод, выбрасываемых к-м предприятием до строительства очистных сооружений, 8Ш - коэффициент очистки /-го загрязнителя при обработке сточных вод по п-й технологии очистки,

4и ~ целочисленная переменная, равная единице, если технология применяется для очистки сточных вод к-то предприятия, и нулю в противном случае. Предполагается, что на каждом предприятии может быть использована только одна технология.

Концентрация /-го загрязнителя в речной воде в А;-ой станции мониторинга вычисляется по формуле к = \,2,.К, I -1,2,./ где ()к - расход воды в реке в районе к-го предприятия. Относительная концентрация /-го загрязнителя, измеряемая в единицах предельно допустимой концентрации (ПДК), в к-м створе вычисляется по формуле

Ры/(Р?ах, к = \,2,.К, / = 1,2,./ где (р"гах - ПДК для z-ro загрязнителя. В качестве критериев загрязненности речной воды используются максимальные по всем створам бассейнов рек значения относительных концентраций, т.е. величины

Z; = max Zkj, i = 1,2,./ представляющие собой максимальные загрязнения отдельными веществами по всей реке.

Модель расчета затрат на очистку сточных вод была построена следующим образом. Поскольку каждая технология очистки описывается стоимостью обработки кубического метра стоков, то капитальные затраты на водоохранные мероприятия на к-м предприятии рассчитываются по формуле N

Fk = = , п=\ где qk - объем стоков к-vo предприятия в единицу времени, а а„ -стоимость обработки кубического метра стоков по п-й технологии очистки. Здесь принимают значения 0, 1 и N п=1 что обеспечивает использование единственного варианта улучшения качества воды на предприятии.

В качестве стоимостного критерия в модели используется общая для всей реки стоимость проекта улучшения качества воды cost, равная сумме расходов по всем предприятиям.

Задача улучшения качества воды состоит в выборе технологии очистки для каждого источника загрязнения. Поскольку имеется конечный набор вариантов, то на основе описанной модели можно рассчитать последствия каждого из них и представить их в виде таблицы, каждая строка которой соответствует стратегии, а столбец -одной из характеристик (критериев выбора стратегии).

Поддержка выбора из конечных таблиц вариантов осуществляется на основе использования Метода Разумных Целей (МРЦ), являющегося развитием МДЦ для таких задач.

3.1.3. ИСПОЛЬЗОВАНИЕ МЕТОДА РАЗУМНЫХ ЦЕЛЕЙ

Заключение.

Результаты диссертационной работы, выносимые на защиту, состоят в следующем.

1) Построены априорные неулучшаемые оценки нижней асимптотической эффективности аппроксимации многомерных ВКТ с дважды непрерывно дифференцируемой границей и положительными главными кривизнами. Оценки получены для хаусдорфовых методов внутренней (совместно с Г.К. Каменевым) и внешней аппроксимации. Полученные оценки оказались независимыми от свойств аппроксимируемого тела. В частности показано, что метод УО позволяет строить вписанные многогранники, отличающиеся по точности от многогранников наилучшей аппроксимации не более чем в четыре раза.

2) Предложен метод внешней полиэдральной аппроксимации -метод УО*, двойственный методу УО. Проведено экспериментальное исследование эффективности метода УО* на основе данных аппроксимации многомерных эллипсоидов. Исследование показало, что эффективность метода УО* зависит от асферичности аппроксимируемого тела; в то же время удалось значительно улучшить теоретические оценки зависимости эффективности метода от асферичности.

3) Разработан метод аппроксимации выпуклой оболочки очень большого числа (порядка миллиона) точек многогранником с небольшим числом гиперграней - метод Экономного Описания Аппроксимации (ЭОА). Проведено экспериментальное исследование метода ЭОА на основе данных аппроксимации циклических многогранников. На основе результатов этого исследования проведен сравнительный анализ свойств метода ЭОА и метода УО.

4) Метод ЭОА использован в системе поддержки поиска эффективных стратегий улучшения качества воды, созданной в рамках Федеральной целевой программы "Возрождение Волги".

1. Лотов А.В. Один подход к перспективному планированию экономики в условиях отсутствия критерия // Тр. конф. "Системный анализ и перспективное планирование" (Москва, май 1972). М.: ВЦ АН СССР, 1973.

2. Лотов А.В., Бушенков В.А., Каменев Г.К. Комльютер и поиск компромисса. Метод достижимых целей. М.: Наука, 1997.

3. Лотов А.В. Введение в экономико-математическое моделирование. М.: Наука, 1984.

4. Lotov А. V., Chernykh О. L., Hellman О. Multiple objective analysis of long-term development strategies for a national economy// European Journal of Operational research. 1992. V.56. N.2.

5. Bushenkov V., Kaitala V., Lotov A., Pohjola M. Decision and negotiation support for transboundary air pollution control between Finland, Russia and Estonia// Finnish Economic Papers. V.7, N.l, Spring 1994. P.69-80.

6. Lotov A., Bushenkov V., Chernykh O. Multi-criteria DSS for River Water Quality Planning // Microcomputers in Civil Engineering. 1997, No 1, 57-67.

7. Лотов А.В. О целостном рассмотрении эколого-экономических проблем М.: изд. ВЦ РАН, 1994 г.

8. Toth L. F. Approximation by polygons and polyhedra //Bull. Amer. Math. Soc. 1948. V.54. N.4.

9. McClure D. E., Vitale R. A. Polygonal approximation of plane convex bodies // J. Math. Analys. and Appl. 1975.V.51. N.2. P. 326-358.

10. Schneider R. Zur optimalen Approximation konvexer Hyperflachen durch Polyeder//Math. Ann. 1983. Bd.256. N 3. P. 289-301.

11. Schneider R. Polyhedral approximation of smooth convex bodies// J.Math.Analys. and Applic. 1987. V.128. N2. P. 470-474.

12. Gruber P.M. Asymptotic estimates for best and stepwise approximation of convex bodies I // Forum Math. 5 (1993), 281-297.

13. Cohon J.L. Multiobjective programming and planning. N.Y.: Acad. Press, 1978.

14. Бушенков В.А. Численный алгоритм построения проекций многогранных множеств // Аэрофизика и прикл. математика. М.: МФТИ, 1981.

15. Sonnevend Gy. An optimal sequential algorithm for the uniform approximation of convex functions on 0,1. //Applied mathematics and optimization. 1983. V.10. P. 127-142.

16. Васильев H.C. К отысканию глобального минимума квазивогнутой функции//Ж. вычисл. матем. и матем. физ. 1983. Т.23. №.2. С.307-313.

17. Лотов А.В. Методы анализа математических моделей управляемых систем на основе построения множества достижимых значений показателей качества управления. Дис. . докт. физ.-матем. наук. М.: МФТИ, 1985.

18. Каменев Г. К. Методы аппроксимации выпуклых тел многогранниками и их применение для построения и анализа обобщенных множеств достижимости. Дис. . канд. физ.-матем. наук. М.: МФТИ, 1986.

19. Бурмистрова JI.B. Исследование нового метода аппроксимации выпуклых компактных тел многогранниками // Ж. вычисл. матем. и матем. физ. 2000. Т.40. №.10 С.1475-1491.

20. Каменев Г.К. Сопряженные адаптивные алгоритмы полиэдральной аппроксимации выпуклых тел // Ж. вычисл. матем. и матем. физ,. 42(9), 1351-1367, 2002.

21. Черных О. Л. Построение выпуклой оболочки конечного множества точек при приближенных вычислениях// Ж. вычисл. матем. и матем. физ. 1988. Т. 28. №.9. С. 1386-1396.

22. Gruber P.M. Approximation of convex bodies // Convexity and its Applies. Basel etc.: Birkhüser, 1983., P. 131-162.

23. Каменев Г.К. Об эффективности хаусдорфовых алгоритмов полиэдральной аппроксимации выпуклых тел// Ж. вычисл. матем. и ма~ тем. физ. 1993. Т.ЗЗ. № 5. С. 796-805.

24. Каменев Г.К Об одном классе адаптивных алгоритмов аппроксимации выпуклых тел многогранниками // Ж. вычисл. матем. и матем. физ. 1992. Т.32. № 1. С. 136-152.

25. Каменев Г.К. Исследование одного алгоритма аппроксимации выпуклых тел // Ж. вычисл. матем. и матем. физ. 1994. Т.34, № 4, С. 608-616.

26. Каменев Г.К. Исследование итерационных методов аппроксимации выпуклых множеств многогранниками. М.: ВЦ АН СССР, 1986.

27. Джолдыбаева С.М., Каменев Г.К. Экспериментальное исследование аппроксимации выпуклых тел многогранниками. М.: ВЦ АН СССР, 1991.

28. Джолдыбаева С.М., Каменев Г.К Численное исследование эффективности алгоритма аппроксимации выпуклых тел многогранниками // Ж. вычисл. матем. и матем. физ. 1992. Т.32. №6. С. 857 866.

29. Бурмистрова Л. В. Исследование одного алгоритма аппроксимации выпуклых компактных тел многогранниками. М.: ВЦ АН СССР, 1999.

30. Черных О.Л. Построение выпуклой оболочки конечного множества точек на основе триангуляции // Ж. вычисл. матем. и матем. физ. 1991. Т.31. N 8.

31. Препарата Ф., Шеймос М. Вычислительная геометрия. Введение. М.: Мир, 1989.

32. Minkowski Н. Volumen und Oberflache // Math.Ann. 1903. Bd.57. P. 447-495.

33. Gruber P. M., Kendrov P. Approximation of convex bodies by poly-topes // Rendiconti Circolo mat. Palermo. Ser.2. 1982. V.31. N2. P. 195-225.

34. Schneider R., Wieacker J. A. Approximation of convex bodies by polytopes//Bull. London Math. Soc, 1981. V.13. Pt.2. N41. P. 149-156.

35. Бронштейн E. M, Иванов Л. Д. О приближении выпуклых множеств многогранниками // Сибирский матем. ж. 1975. Т.26. N 5. С. 1110-1112.

36. Dudley R. Metric entropy of some classes of sets with differentiable boundaries // J. Approximation Theory. 1974. V.10. P. 227-236.

37. Гусев Д.В. и Лотов A.B. Методы поддержки принятия решений в задаче конечного выбора. Исследование операций. Модели, системы, решения (под ред. Ю.П.Иванилова). М.: ВЦ РАН, 1994.

38. Бренстед А. Введение в теорию выпуклых многогранников. М. Мир, 1988.

39. Лейхтвейс К. Выпуклые множества. М.: Наука, 1985.

40. Каменев Г. К. Эффективные алгоритмы аппроксимации негладких выпуклых тел// Ж. вычисл. матем. и матем. физ. 1999. Т. 39. № 3. С. 446-491.

41. Черных О. Л. Аппроксимация Парето-оболочки выпуклого множества многогранными множествами//Ж. вычисл. матем. и матем. физ. 1995. Т.35. N8.

42. Моисеев Н. Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. М.: Наука, 1978.

43. Тейл Г. Экономические прогнозы и принятие решений. М.: Статистика, 1971.

44. R.Efremov Strict estimate of efficiency of adaptive algorithm for polyhedral approximation of convex bodies in 2-dimensional case // Paper at Congreso Nacional de la sociedad matematica mexicana, Guadalajara, Mexico, 1999, October 10 -16, 77-78.

45. Ефремов P.B. Точная оценка асимптотической эффективности адаптивного алгоритма аппроксимации выпуклых гладких тел многогранниками в двумерном случае// Вестн. МГУ, Сер. 15. Вычисл. Матем. и кибернетика. 2000. № 2. стр. 29-32.

46. Ефремов P.В., Каменев Г.К. Класс алгоритмов полиэдральной аппроксимации выпуклых тел с априорной оценкой асимптотической эффективности // Ж. вычисл. матем. и матем. физ. 2001. Т. 42. №1. С.24 33.

47. Ефремов Р.В. Экспериментальный анализ методов внешней полиэдральной аппроксимации выпуклых тел. ВЦ РАН, Москва, 2002.

48. Бурмистрова Л.В., Ефремов Р.В., Лотов A.B. Методика визуальной поддержки принятия решений и ее применение в системах управления водными ресурсами// Известия АН. Сер. Теория и Системы Управления. 2002. № 5. С.89-100.

49. Ефремов Р.В. Априорная неулучшаемая оценка эффективности адаптивных алгоритмов внешней полиэдральной аппроксимации гладких выпуклых тел. // Ж. вычисл. матем. и матем. физ. 2003. Т43. №1. С.169-180.

50. РОССИЙСКАЯ ГОСУДА!"Т:даТ1ЛГ(

51. WBMMm¿j " . ^ХЪЪ^Н ~6> 0£>