Содержание к диссертации
Введение
Глава 1. Монотонные многокритериальные задачи целочисленной оптимизации 23
1.1. Задача о наименьшем покрытии множествами 23
1.2. Многокритериальная задача о рюкзаке 25
1.3. Задача локального уменьшения загрязнения в реке 26
Глава 2. Методы решения задач многокритериальной целочисленной оптимизации с монотонными критериями 31
2.1. Метод квазиразумных целей 32
2.2. Модификация метода уточнения оценок для полиэдральной аппроксимации выпуклых многогранников 39
2.3. Метод разумных целей, основанный на аппроксимации выпуклой оболочки Эджворта-Парето 50
Глава 3. Теоретический анализ скорости сходимости метода аппроксимации ВОЭП 77
3.1. Общие хаусдорфовы схемы, адаптивные методы и последовательности наполнения 77
3.2. Скорость сходимости метода аппроксимации ВОЭП 93
Глава 4. Решения прикладных задач с помощью метода разумных целей 108
4.1. Программный комплекс МРЦ для монотонных целочисленных задач многокритериальной оптимизации 108
4.2. Использование программного комплекса в системе поиска эффективных технологий очистки воды в бассейнах крупных рек 118
4.3. Использование комплекса для поиска эффективных технологий очистки воды в малых реках 132
Заключение 139
Литература 140
- Задача локального уменьшения загрязнения в реке
- Модификация метода уточнения оценок для полиэдральной аппроксимации выпуклых многогранников
- Скорость сходимости метода аппроксимации ВОЭП
- Использование программного комплекса в системе поиска эффективных технологий очистки воды в бассейнах крупных рек
Введение к работе
Актуальность работы. При моделирования сложных систем важным моментом является оценка стратегий с точки зрения различных критериев. При большом числе решений сравнение их критериальных оценок и выбор подходящего решения становится крайне трудной задачей для лица, принимающего решение (ЛПР). Важную роль в таких случаях играют методы поддержки принятия решений, основанные на многокритериальной оптимизации.
Одним из основных подходов, используемых в многокритериальной оптимизации, является аппроксимация границы Парето множества достижимых критериальных точек (т.е. множества всех недоминируемых по Парето критериальных точек) и представление этой информации ЛПР (работы академика П. С. Краснощёкова и его учеников В. В. Морозова, Н. М. Попова, В. В. Федорова и других, а также иностранных специалистов М. Зелены, Р. Штойера, По-лунг Ю). Как показывает практика, наиболее удобным способом представления информации о границе Парето является ее визуализация. Такой подход развивается исследованиях многокритериальных задач школы академика А. А. Петрова, проводимых под руководством А. В. Лотова и Г. К. Каменева. Для реализации подобного подхода при более чем двух критериях необходимо предварительно решать задачу аппроксимации многомерной границы Парето в форме, удобной для последующей визуализации. В зависимости от структуры задачи для этого применяются разные методы. Так, для непрерывных задач были разработаны методы, основанные на аппроксимации множества достижимых критериальных точек с помощью относительно простых фигур (многогранников, объединения конечного числа конусов и т.д.).
В прикладных задачах множество допустимых решений часто является дискретным. Такая ситуация встречается, например, в транспортных задачах, задачах составления расписаний, телекоммуникационной маршрутизации, зада-
чах планирования инвестиций и производства и многих других задачах. В настоящей диссертационной работе рассматривается случай, когда множество решений является подмножеством целочисленного куба. К такому случаю могут быть сведены многие прикладные задачи дискретные оптимизации.
Проблема поиска или аппроксимации множества решений, эффективных по Паретои, и соответствующей совокупности критериальных точек в многокритериальных дискретных задачах изучалась ранее в работах И. X. Сигала, И. И. Меламеда, М. Эрготта. Был предложен широкий спектр методов, использующих комбинаторную специфику рассматриваемых задач или сведение их к решению серии однокритериальных задач оптимизации, для каждой из которых можно найти решение.
В ряде прикладных задач дискретной оптимизации (в том числе многокритериальных) возникает необходимость решать комбинаторные задачи, которые не относятся к изученным классам. К таким задачам, в частности, относятся проблемы, в которых модель задана вычислительным модулем с закрытым кодом (черным ящиком), предоставляющим возможность только для расчета значений критериев по заданным решениям. В подобных случаях можно применять, например, методы случайного поиска и методы, основанные на термодинамических и биологических аналогиях. Для многокритериальных дискретных задач эти методы получили развитие в работах К. Деба, Е. Цитцлера и его коллег. В указанных методах число критериев не превосходит двух или трех, а оценки точности аппроксимации границы Парето отсутствуют (обычно качество алгоритма оценивается на основе сравнения аппроксимации с заранее известной точной границей Парето, которую удается построить лишь в простейших случаях), так что эти методы, по существу, являются эвристическими.
Эффективным подходом к решению задач многокритериального выбора из конечного числа вариантов (альтернатив) является метод разумных целей
(МРЦ), разработанный А. В. Лотовым и Д. В. Гусевым. МРЦ основан на сведении многокритериальной задачи выбора к анализу границы Парето выпуклой оболочки критериальных точек — образов рассматриваемых альтернатив. В рамках МРЦ происходит визуализация границы Парето этой выпуклой оболочки (или более простого множества — оболочки Эджворта-Парето выпуклой оболочки), на которой ЛПР выбирает цель, отвечающую его интересам; далее компьютер находит оптимальные по Парето альтернативы, результаты выполнения которых близки к цели, выбранной ЛПР. Практическое использование МРЦ продемонстрировало его удобство при поддержке многокритериального выбора из конечного, но относительно небольшого числа альтернатив при числе критериев от трех до восьми. Ограничение на применение МРЦ по числу альтернатив обусловлено необходимостью их явного представления в критериальном пространстве, что оказывается затруднительным для большого числа альтернатив.
Сказанное выше обосновывает актуальность разработки новых методов, которые применимы к широкому спектру задач дискретной многокритериальной оптимизации, характеризующихся более чем двумя критериями и большим числом альтернатив, причем позволяют оценивать точность аппроксимации границы Парето.
Цель диссертационной работы. Целью данной диссертации является построение и изучение методов, обобщающих МРЦ на задачи многокритериальной целочисленной оптимизации, характеризующиеся большим числом альтернатив, в том числе заданных вычислительным модулем типа черного ящика.
Методы исследований. В работе используется математический аппарат теории дискретной оптимизации, теории многокритериальной оптимизации и теории адаптивных методов полиэдральной аппроксимации выпуклых тел.
Достоверность полученных результатов подтверждена доказательствами теорем, экспериментальной проверкой алгоритмов и программ на модельных и реальных данных.
Научная новизна. Предложены два метода решения целочисленных задач многокритериальной оптимизации с монотонными критериями и ограничениями, являющиеся обобщениями МРЦ. Предложенные методы позволяют работать с задачами, в которых исходный МРЦ уже неприменим из-за слишком большого числа альтернатив. Первый из предложенных методов — метод квазиразумных целей, основанный на аппроксимации оболочки Эджворта-Парето релаксированной задачи. Метод может быть использован в том случае, когда критерии и ограничения заданы явно. Второй — метод разумных целей, основанный на непосредственной полиэдральной аппроксимации оболочки Эджворта-Парето выпуклой оболочки множества достижимых критериальных векторов. Метод применим в том случае, когда модель задана в виде черного ящика.
Предложена и изучена схема наполнения, являющаяся обобщением известных адаптивных методов полиэдральной аппроксимации выпуклых компактных тел; полученные результаты использованы для теоретической оценки скорости сходимости метода полиэдральной аппроксимации оболочки Эджворта-Парето выпуклой оболочки критериальных векторов целочисленной задачи оптимизации.
Практическая ценность работы. Результаты, полученные в работе, могут быть использованы для поддержки принятия решений в проблемах, моделируемых целочисленными многокритериальными задачами с монотонными критериями и ограничениям. В диссертации разработанные методы применены в рамках двух проектов улучшения качества воды в больших и малых реках с
числом допустимых альтернатив до 10 и числом критериев до пяти.
Апробация работы прошла на следующих научных конференциях: на Международной конференции студентов и аспирантов по фундаментальным наукам "Ломоносов-2004", секция "Вычислительной математики и кибернетики" (Россия, Москва, 12-15 апреля 2004), на 4-й Московской международной конференции по исследованию операций (Россия, Москва, 21-24 сентября 2004), на XIII Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (Россия, Северобайкальск, 2-8 июля 2005), на 7-й Международной конференции, посвященной многокритериальной оптимизации и целевому программированию (Франция, Тур, 12-14 июня 2006), на V Московской международной конференции по исследованию операций (Россия, Москва, 10-14 апреля 2007), на Всероссийской конференции ЭКОМОД (Россия, Киров, 6-12 июля 2009).
Публикации. По теме диссертации опубликовано 9 работ, в том числе 3 статьи в журналах из списка ВАК.
Структура и объем диссертации. Диссертационная работа объемом 150 страниц состоит из введения, четырех глав, заключения, библиографического списка. Библиографический список содержит 89 источников, из них 37 на иностранных языках.
Задача локального уменьшения загрязнения в реке
Важной областью применения методов поддержки принятия решения является поиск эффективных решений в экологических проблемах. Часто возникает необходимость формулировать экологические задачи в виде задач дискретного программирования, как, например, в рассмотренной выше модели [69].
Однако не всегда удается сформулировать подобные задачи в виде хорошо изученных классов дискретных задач.
Характерным свойством экологических задач ялятся монотонность критериев и ограничений. Это связано с тем, что применение технологий, оказывающих большее положительное влияние на экологические показатели (например, использование более мощных технологий очистки), является более затратным. Упорядочивание технологий по возрастанию мощности приводит к монотонности задачи по критериям.
Примером экологических проблем, приводящих к монотонным задачам целочисленной оптимизации служат интегрированные модели распространения загрязнения в бассейнах крупных рек (см., например, [25, 71] ). Ниже подробно описана задача улучшения качества воды в реке Ока в районе города Коломна.
В рамках задачи ставится вопрос о поиске эффективных мер по улучшению качества воды. Для этих целей была построена водохозяйственная модель на основе данных Института водных проблем РАН и АО Союзводпроект. Так как целью является изучение влияния локальных мероприятий, загрязнение, поступающее из Верхней Оки и реки Москва выше города Коломна, считается заданным РІ не превышающим нормы. В модели используются данные о выбросах по основным (с точки зрения вклада в загрязнение) предприятиям города Коломна. При этом предполагается, что остальные предприятия выбросов загрязнения не осуществляют. Измерения качества воды проводится ниже точек сборса. Таким образом, пункты измерения разбивают всю реку на R участков (створов). Математическая модель состоит из двух частей: модели переноса загрязнителей, дающей возможность вычислять концентрации загрязнителей в гидрологических пунктах при заданных выбросах загрязнителей по створам, модели очистки стоков, связывающей уменьшение выбросов загрязнителей с масштабами использования имеющихся технологий очистки сточных вод и объемом капиталовложений в очистное оборудование.
Всего рассматривается три типа загрязнителей: азот, фосфор и биологическая потребность в кислороде(БПК). Объемы сточных вод и их состав известны и постоянны во времени. Для каждого из предприятий возможен выбор одного из (К + 1)-го технологического решения по очистке выбросов. Для каждой из технологий известны стоимость очистки единичного объема сточных вод и эффект от ее применения, что позволяет связать используемую технологию и качество воды стока. Используя это, получаем модель описания потоков загрязнителей в составе сточных вод, величины mrs: соотношениями где ms — поток s-ro загрязнителя в составе сточных вод, выбрасываемых в г-м створе до строительства очистных сооружений, 5s{n) — коэффициент очистки 5-го загрязнителя при обработке сточных вод по п-й технологии очистки (п = 0,1,... К), хг принимает значения от нуля до К и характеризует используемую технологию для очистки сточных вод в г-ом створе. Всего в рассматриваемой задаче было 5 технологий очистки и 8 возможных мест установки технолгий. Таким образом всего было порядка 400000 различных решений.
Модель переноса загрязнения задается матрицей влияния, позволяющей вычислять концентрации загрязнителей в любом гидрологическом пункте при заданных выбросах загрязнителей на предприятиях. Такая модель не учитывает, например, наличие химических и биологических процессов в воде, нелинейность и запаздывания при распространении загрязнителей и описывает некоторую установившуюся ситуацию в среднем за длительный период времени. В рамках этой модели уравнение баланса 5-го загрязнителя для r-го створа имеет вид где Prs — поток 5-го загрязнителя в реке через г-й гидрологический пункт, 7rs — коэффициент распада s-ro загрязнителя, поступившего из предыдущего створа, 5rs — коэффициент распада s-ro загрязнителя, поступившего из предприятий, расположенных в г-м створе, mrs — сброс s-ro загрязнителя в единицу времени в составе сточных вод в г-м створе.
В модели рассматривается четыре критерия: стоимость проекта, измеряемая в миллионах рублей, и максимальные по району концентрации соединений азота, фосфора и ВПК, измеряемые в предельно допустимых концентрация (ПДК).
Критерии загрязненности речной воды вычисляются как максимальные значения относительных концентраций по всем створам бассейнов рек , т. е. величины
Модификация метода уточнения оценок для полиэдральной аппроксимации выпуклых многогранников
Одной из важных областей применения МКРЦ является решение линейных задач многокритериальной целочисленной оптимизации. В таких задачах релаксированная задача 2.1 представляет собой задачу линейного программирования. Аппроксимация ВОЭП может быть осуществлена с помощью метода уточнения оценок (УО) [19, 21]. Метод УО предполагает решение значительного числа задач выпуклой скалярной оптимизащга на каждой итерации для нахождения значений опорной функции аппроксимируемого тела. В частности, как показывает опыт, для пространства размерности порядка пяти на каждой итерации может потребоваться решить до нескольких сотен таких задач [52]. В том случае, когда решение каждой задачи оптимизации требует существенных вычислительных затрат, для построения достаточно точной аппроксимации выпуклого тела может потребоваться значительный объем вычислений. Поэтому для уменьшения трудоемкости построения аппроксимации ВОЭП в линейных задачах многокритериальной оптимизации и, в частности, в рамках работы МКРЦ, была разработана модификация метода УО, описанная в данном разделе. Заметим, что предлагаемая модификация может быть использована и для аппроксимации выпуклых многомерных многогранников, заданных явно или неявно и имеющих большое число вершин, многогранниками с малым числом вершин и т. д. [73].
Описываемый подход к снижению трудоемкости построения аппроксимации основан на совершенствовании метода УО. При этом можно по-прежнему использовать программное обеспечение метода УО, несколько модифицировав его. В предлагаемой модификации вычислительные затраты уменьшаются за счет снижения трудоемкости решения совокупности задач расчета опорной функции. Модификация описывается для задачи аппроксимации многогранника; ее несложно перенести па случай аппроксимации ВОЭП в линейных многокритериальных задачах [74].
Рассматривается задача аппроксимации множества достижимых критериальных векторов евклидовом пространстве Rm , задаваемого как где х Є Rn , Gx д — компактное множество допустимых решений, G и д — заданные матрица и вектор, F : Rn — Rm — заданное линейное отображение, связывающее значения критериев с решениями.
Как известно, работа симплекс-метода обычно разбивается на два этапа (см. [75]). Первый состоит в поиске допустимой вершины и соответствующего базисного разложения. Второй — в последовательном переходе от одной вершины к другой до тех пор, пока не будет достигнуто оптимальное решение задачи. Отметим, что в задаче (2.4) симплекс-метод работает с вершинами многогранника Gx д . Поскольку метод УО требует многократного решения задач ЛП на одном и том же многограннике, допустимые вершины, найденные при решении предыдущих задач, можно использовать в качестве начальных при решении следующих задач.
Время поиска оптимального решения задачи ЛП отличается при использовании различных начальных вершин, поскольку зависит от числа итераций симплекс-метода, т.е. числа промежуточных вершин. При построении модификации метода УО используется грубое предположение о том, что число промежуточных вершин в среднем растет с увеличением углового расстояния между начальной и оптимальной вершинами. Можно надеяться, что время поиска оптимального решения очередной задачи ЛП удастся уменьшить, если начинать процесс решения с вершины, относительно близкой по угловому расстоянию к оптимальной.
Идея использования результатов предыдущих вычислений широко применяется при решении задач линейной оптимизации, в том числе и многокритериальных. Так, в работах Р. Штойера и М. М. Смирнова эта идея использовалась в неадаптивных методах поиска недоминируемых вершин. Идея модификации заключается в том, чтобы на основе вершин, полученных при решении задач ЛП, формировать базу, каждым элементом которой является пара (направление, вершина), и при решении новой задачи ЛП на аппроксимируемом многограннике в качестве начальной вершины использовать вершину из базы, ближайшую по направлению.
Заметим, что с увеличением числа направлений, для которых уже известны решения задач ЛП, удается начинать оптимизацию с вершин, все более близких к оптимальным. За счет этого могут быть снижены вычислительные затраты, связанные с решением каждой из задач ЛП. В то же время, дополнительная работа, связанная с хранением совокупности оптимальных вершин и выделением из них тех, которые соответствуют описанному выше правилу, требует дополнительных затрат времени. В связи с этим заранее не ясно, в какой мере предложенная модификация способствует ускорению процесса аппроксимации. Этот вопрос изучается экспериментально в данном разделе.
Перейдем к описанию модификации метода уточнения оценок (МУО). Пусть задана требуемая точность є 0. Пусть, как и в методе УО на к-й итерации построен многогранник Pk , вписанный в аппроксимируемый многогранник С. Многогранник Р задан и в виде списка вершин, и как множество решений конечной системы линейных неравенств. Пусть на всех предыдущих итерациях для построения многогранника Pk было решено М& задач ЛП для совокупностей единичных направлений MF(Pk) многогранников Pk
Скорость сходимости метода аппроксимации ВОЭП
Для начала опишем алгоритм, позволяющий находить допустимое решение, образ которого достаточно удален от построенной внутренней аппроксимации в задаче (2)-(4). Пусть задано некоторое 0 г 1, а є = р(Р, У), пусть так же имеется некоторое разбиение Е множества XQ на подмножества Х такое, что для всех Х% Є Е вектор d(X ) $. Р, причем Выполнение свойства (3.6) означает, что имеется вся необходимая информация для построения YQ. При этом она находится либо в множестве Р, либо в подмножества, на которые произведено разбиение. Идея вспомогательного метода заключается в разбиении множеств из Е на подмножества и в поиске в них допустимых решений до тех пор, пока не будет найдено решение, лежащее на расстоянии больше чем js от многогранного множества Р. Опишем сам алгоритм. На нулевой итерации полагаем набор активных подмножеств Но = Е. Рассмотрим произвольную 1-ю итерацию. Перед ее началом должен быть задан набор Ei-i подмножеств XQ вида Х, порожденных алгоритмом на предыдущих итерациях. аг 1. Из набора E;_i выбираем множество X", для которого оценка d (Xf) наиболее удалена от построенной аппроксимации P/_i, т. е. Способ формирования Hf_x позволяет гарантировать, что у всех А Є Ef_x расстояние до Pi-i будет больше нуля. аг 2.
Для каждого Х находим множество Л (Х ] и вычисляем оценку Шаг 3. Среди множества всех рассчитанных альтернатив находим ж/, наиболее удаленную от Р, т.е. Шаг 4. Строим набор ;. Для этого берем объединение S/_i\ Xj/ и совокупности множеств Х !І\ для которых Л (Х ) не пусто; из полученного множества исключаем множества, для которых нижняя оценка d (- +1 ) попадает внутрь многогранного множества Р. Если S; оказывается пусто, то это означает, что Р = YQ. В этом случае алгоритм заканчивает работу. Шаг 5. Уточняем оценку точности є і: Шаг 6. если p(f(xi),P) тєі переходим к шагу 1(/ + 1)-й итерации, иначе полагаем ж — хі, Е = j, в этом случае алгоритм заканчивает работу, так как искомая точка найдена. Теорема 3.5. Вспомогательный алгоритм за конечное число итераций находит в задаче (2)-(4) допустимую точку х , образ которой лежит на расстоянии более чем тр(Р: Y) от некоторого заданного внутреннего многогранного тела Р С YQ или определяет, что Р совпадает с YQ . Доказательство. Алгоритм направленно перебирает все точки из Цх єг- т? поэтому, в конечном счете, либо искомая точка будет найдена, либо все множества из Е будут разбиты на одноточечные множества вида Х%, для каждого из которых будут рассчитаны оценки. В этом случае оценка точности будет равна Р = YQ. Если є О, то в силу того, что на шаге 2 выбирается наиболее удаленное подмножество, метод найдет точку, образ которой удален от Р на є те. Таким образом, утверждение теоремы доказано.
Помимо поиска точки, алгоритм формирует некоторое новое разбиение Н , причем если многогранное множество Р строго лежит внутри Y, то на выходе вспомогательный алгоритм выдает точку х , такую что p{f{x )1Y !) rp(P,Yc), некоторое новое разбиение Е , удовлетворяющее свойству (3.6), а если Р = У , то S будет пустым. Так как Єї является оценкой сверху для точности аппроксимации, найденная вспомогательным алгоритмом точка будут гарантированно находиться на расстоянии не менее чем тр{Р, YQ). Замечание 1. Параметр г существенно влияет на ход работы алгоритма. При значениях параметра близких к единице алгоритм будет находить практически максимально удаленную точку, но при этом будет перебирать почти все XQ и может проработать очень долго. При значениях параметра близких к нулю алгоритм будет останавливаться очень быстро, но и оценка для дальности точки от построенного многогранника в этом случае тоже будет низкой. Замечание 2. Вычисление на каждой итерации заново допустимых вершин всех рассматриваемых подмножеств S/, необходимое для выполнения пункта 3 алгоритма, может оказаться очень затратным. При реализации метода вычисление может быть заменено однократным вычислением и последующим хранением вычисленных вершин. При этом достаточно хранить не все вычисленные вершины, а только оптимальные по Парето среди них.
Использование программного комплекса в системе поиска эффективных технологий очистки воды в бассейнах крупных рек
В задачах эффективного природопользования вовлекаются интересы различных агентов с разными целями, использующих различные технологические и экономические критерии для оценки принимаемых решений. Наличие таких факторов делает невозможным применение скалярного оптимизационного подхода, поэтому в таких задачах общепринятым является использование систем поддержки принятия решения (СППР) на основе методов многокритериальной оптимизации. Одна из таких систем была разработана в рамках федеральной целевой программы "Возрождение Волги" [71]. Эта система была ориентирована на помощь в поиске эффективных вариантов капиталовложений с целью снижения уровня загрязнения в реках, учитывая необходимость компромисса между затратами бюджетов разных регионов. СППР основана на использование метода достижимых целей. Система позволяет графически изучить возможные значения критериев (стоимости проектов улучшения качества воды и показателей качества воды) и кривые эффективного замещения между критериями на основе предварительногй аппроксимации ОЭП. Это способствует лучшему пониманию проблемы и помогает пользователям находить предпочтительные достижимые сочетания значений критериев (достижимые цели). На основе выбранных целей компьютером строятся стратегии распределения капиталовложений по регионам и створам реки, реализация которых приводит к достижению выбранных целей. При подготовке переговоров система позволяет найти стратегии, которые будут выгодны для выдвинувшей их стороны и приемлемы для остальных сторон.
Работа системы основана па методике целостного рассмотрения экологических проблем. Методика целостного рассмотрения экологических проблем, предназначена для решения задачи скрининга (просеивания) совокупности возможных стратегий, т.е. поиска тех из них, которые в наибольшей степени соответствуют интересам пользователя [20]. Задача скрининга принципиально отличается от задачи выбора окончательного проекта тем, что в процессе скрининга рассматривается огромное число конкурирующих вариантов и требуется всесторонний анализ (целостное рассмотрение) изучаемой проблемы. Поэтому при целостном рассмотрении используют единую интегрированную модель ситуации, построенную на основе объединения упрощенных описаний отдельных подсистем и включающую в себя несколько критериев выбора. В описываемой СППР используется линейная целостная модель реки, построенная на основе упрощения нелинейной модели очистки и распространения загрязнений.
Описываемая система поддержки поиска эффективных решений и переговоров состоит из следующих подсистем: подсистемы визуализации текущего состояния реки, подсистемы выбора критериев из списка и назначения ограничений на другие показатели, подсистемы аппроксимации ОЭП, подсистемы визуализации эффективных границ и выбора достижимой цели, подсистемы расчета стратегии, подсистемы визуализации полученной стратегии с помощью географической информационной системы.
В подсистеме визуализации текущего состояния реки на географической карте бассейна реки изображаются данные концентрации загрязнителей и объемах сбросов загрязнителей в регионе. В подсистеме, предназначенной для выбора критериев и назначения ограничений, ЛПР имеет возможность выбрать интересующие его критерии и назначить ограничения на остальные показатели. В подсистеме аппроксимации происходит аппроксимация ОЭП множества достижимых значений критериев, которая потом отображается в подсистеме визуализации. Используя подсистему визуализации (диалоговые карты решений), пользователь осуществляет исследование границы Парето и назначает достижимую цель, которая используется в дальнейшем для построения стратегии улучшения качества воды. Стратегия отображается с помощью географической информационной системы.
Отсутствие методов многокритериальной оптимизации, применимых к задачам с большим числом вариантов, повлекло за собой использование в рамках СППР непрерывной модели капиталовложений. При этом проекты очистки, рассматриваемые в проблеме, представляют собой набор технологий, т.е. исходное множество стратегий было дискретно. В непрерывной модели предполагалось, что на каждом участке возможно использование выпуклой комбинации исходных технологий. Таким образом, стратегии, получаемые в результате применения метода достижимых целей, могли оказаться технически нереали-зуемы.
Программный комплекс, разработанный в рамках настоящей диссертационной работы, может быть использован в СППР в подсистемах аппроксимации и расчета стратегий с целью учета дискретности задачи.
Адекватная математическая модель, которая могла бы полностью описать изучаемую проблему, должна была бы включать подробное описание технологий очистки стоков предприятий различных типов расположенных в различных точках бассейна реки, а также детальное описание переноса различных типов загрязнения вдоль реки с учетом особенностей рельефа русла реки, различных режимов стока и т.д. Такие модели пригодны лишь для вариантных расчетов, когда при различных режимах стока изучаются последствия некоторого заданного варианта размещения капиталовложений и выбора технологий очистки. Более того, данные, необходимые для таких моделей, не надежны или их вообще не удается собрать. Для целостного рассмотрения проблемы, в том числе для поддержки переговоров о выделении капиталовложений и о выборе разумных вариантов проекта из огромного числа возможных, требуется использовать упрощенные интегрированные модели, которые описывают ситуацию в целом. Такая интегрированная модель описана в работах [21, 71]. Река разбивается на конечное число участков (створов). В нижней части каждого створа находится гидрологический пункт (станция мониторинга), в котором измеряются, в частности, концентрации загрязняющих веществ. Математическая модель состоит из двух составляющих
