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

На правах рукописи

Поспелов Алексей Игоревич

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

05.13.18 — Математическое моделирование, численные методы и комплексы

программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2010

003492485

Работа выполнена в Учреждении Российской академии наук Вычислительный центр им. A.A. Дородницына РАН

Научный руководитель: доктор физико-математических наук,

профессор

Лотов Александр Владимирович

Официальные оппоненты: доктор технических наук, профессор

Сигал Израиль Хаимович

кандидат физико-математических наук, доцент

Морозов Владимир Викторович

Ведущая организация: Учреждение Российской академии наук

Центральный экономико-математический институт РАН

Защита состоится 2010 года в /¿Г часов на заседании диссер-

тационного совета Д 002.017.04 Учреждения Российской академии наук Вычис лительный центр им. A.A. Дородницына РАН по адресу: 119333 Москва, улиц Вавилова, дом 40, конференц-зал.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан tfO ¿bp'-bCL20 /года.

Ученый секретарь диссертационного совета доктор физико-математических наук, у

профессор /V^N Новикова Н. М.

Общая характеристика работы

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

Одним из основных подходов, используемых в многокритериальной оптимизации, является аппроксимация границы Парето множества достижимых критериальных точек (т.е. множества всех недоминируемых по Парето критериальных точек) и представление этой информации ЛПР (работы академика П. С. Краснощёкова и его учеников В. В. Морозова, Н. М. Попова, В. В. Федорова и других, а также иностранных специалистов М. Зелены, Р. Штойера, По-лунг Ю). Как показывает практика, наиболее удобным способом представления информации о границе Парето является ее визуализация. Такой подход развивается исследованиях многокритериальных задач школы академика А. А. Петрова, проводимых под руководством А. В. Лотова и Г. К. Каменева. Для реализации подобного подхода при более чем двух критериях необходимо предварительно решать задачу аппроксимации многомерной границы Парето в форме, удобной для последующей визуализации. В зависимости от структуры задачи для этого применяются разные методы. Так, для непрерывных задач были разработаны методы, основанные на аппроксимации множества достижимых критериальных точек с помощью относительно простых фигур (многогранников, объединения конечного числа конусов и т.д.).

В прикладных задачах множество допустимых решений часто является дискретным. Такая ситуация встречается, например, в транспортных задачах, задачах составления расписаний, телекоммуникационной маршрутизации, зада-

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

Проблема поиска или аппроксимации множества решений, эффективны по Паретои, и соответствующей совокупности критериальных точек в многс критериальных дискретных задачах изучалась ранее в работах Й. X. Сигале И. И. Меламеда, М. Эрготта. Был предложен широкий спектр методов, ис пользующих комбинаторную специфику рассматриваемых задач или сведени их к решению серии однокритериальных задач оптимизации, для каждой и которых можно найти решение.

В ряде прикладных задач дискретной оптимизации (в том числе многокр* териальных) возникает необходимость решать комбинаторные задачи, которы не относятся к изученным классам. К таким задачам, в частности, относятс проблемы, в которых модель задана вычислительным модулем с закрыты: кодом (черным ящиком), предоставляющим возможность только для расчеа значений критериев по заданным решениям. В подобных случаях можно пр! менять, например, методы случайного поиска и методы, основанные на терм< динамических и биологических аналогиях. Для многокритериальных дискре' ных задач эти методы получили развитие в работах К. Деба, Е. Цитцлера и е! коллег. В указанных методах число критериев не превосходит двух или тре: а оценки точности аппроксимации границы Парето отсутствуют (обычно к чество алгоритма оценивается на основе сравнения аппроксимации с заран известной точной границей Парето, которую удается построить лишь в просте: ших случаях), так что эти методы, по существу, являются эвристическими.

Эффективным подходом к решению задач многокритериального выбо] из конечного числа вариантов (альтернатив) является метод разумных цел<

(МРЦ), разработанный А. В. Лотовым и Д. В. Гусевым. МРЦ основан на сведении многокритериальной задачи выбора к анализу границы Парето выпуклой оболочки критериальных точек — образов рассматриваемых альтернатив. В рамках МРЦ происходит визуализация границы Парето этой выпуклой оболочки (или более простого множества — оболочки Эджворта-Парето выпуклой оболочки), на которой ЛПР выбирает цель, отвечающую его интересам; далее компьютер находит оптимальные по Парето альтернативы, результаты выполнения которых близки к цели, выбранной ЛПР. Практическое использование МРЦ продемонстрировало его удобство при поддержке многокритериального выбора из конечного,, но относительно небольшого числа альтернатив при числе критериев от трех до восьми. Ограничение на применение МРЦ по числу альтернатив обусловлено необходимостью их явного представления в критериальном пространстве, что оказывается затруднительным для большого числа альтернатив.

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

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

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

Достоверность полученных результатов подтверждена доказательствам] теорем, экспериментальной проверкой алгоритмов и программ на модельных ] реальных данных.

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

Предложена и изучена схема наполнения, являющаяся обобщением извест ных адаптивных методов полиэдральной аппроксимации выпуклых компакт ных тел; полученные результаты использованы для теоретической оценки сю рости сходимости метода полиэдральной аппроксимации оболочки Эджвортг Парето выпуклой оболочки критериальных векторов целочисленной задачи 01 тимизации.

Практическая ценность работы. Результаты, полученные в работе, мог} быть использованы для поддержки принятия решений в проблемах, моделир; емых целочисленными многокритериальными задачами с монотонными кр] териями и ограничениям. В диссертации разработанные методы применены рамках двух проектов улучшения качества воды в больших и малых реках

числом допустимых альтернатив до 1032 и числом критериев до пяти.

Апробация работы прошла на следующих научных конференциях: на Международной конференции студентов и аспирантов по фундаментальным наукам "Ломоносов-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 на иностранных языках.

Содержание работы

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

нейшие результаты теории и методы полиэдральной аппроксимации выпуклых компактных тел, дано краткое описание диссертации по главам.

Математическая задача целочисленной многокритериальной оптимизации, рассматриваемая в диссертационной работе, формулируется следующим образом:

/ (х) —► min, хеХ = {хе (х) < 0, i = 1,2,..., к}, где Х0 — {0,1 ...К}п — целочисленный куб, /(•) : R" —► Rm — векторнозначная функция, задающая критерии оценки альтернатив, ги(-) : Мп —► Rfc — набор функций, используемых для описания ограничений. Рассматривается случа! монотонных критериев, часто встречающийся в прикладных исследованиях -предполагается, что

/(■) = («(•).«(■)).

где и(-) и v(-) — такие векторнозначные функции, что и(-) : Еп —> Ж' и v(-) R" —► Rm-i для некоторого целого t, 0 ^ t < т, и при этом и и v монотонны следующем смысле:

для х'а ^ x"s, з = 1,2,..., 7i, имеем гц(х') г = l,2,...,i, и Vj(x') j = 1,2 ,...,m-i.

Кроме того, предполагается, что ограничения также монотонны, т.е.

для x's ^ г", s = 1,2,..., п, имеем ^

wi(x') ^wt(x"), 1 = l,2,...,k.

В (1) под записью / (х) —> min понимается, что желательным являете уменьшение каждого частного критерия /¿, г = 1,2,...т, при прочих ра: ных условиях (задача многокритериальной минимизации). В этом случае г ворят, что решение х' доминирует х" по Парето, если /¿(ж') < fi(x"), i

1,2,..., m, и f(x') ф fix"). Критериальная точка f(x') называется оптимальной по Парето, а соответствующее ей решение х' G X — эффективным по Парето, если не существует решения х" £ X, доминирующего х' по Парето. Множество всех оптимальных по Парето критериальных точек называется границей Парето. Для удобства визуализации границы Парето в работе рассматривается аппроксимация двух объектов: оболочки Эджворта-Парето (ОЭП), которая может быть определена как Y* = f(X) + и оболочки Эджворта-Парето выпуклой оболочки (ВОЭП) критериальных точек, которая может быть определена как = conv(/psT))+R™, где К™ — неотрицательный конус пространства Rm.

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

Во второй главе предложены методы решения задач типа (1)-(3).

В разделе 2.1 описан метод квазиразумных целей (МКРЦ). Метод предполагает, что имеется возможность вычислять значения критериев и ограничений задачи не только на множестве Х0) но и на более широком множестве Хо = [0, К]п. В МКРЦ используется вспомогательная релаксированная задача

fix) -> min, х е X С Rn,

■ (4)

X = {х € Rn I w (Xi) < 0, 0 < Хг < К, г = 1,... ,п} , получаемая из (1)-(3) заменой дискретного множества X на непрерывное X и

продолжением на X критериев и ограничений.

В МКРЦ предлагается аппроксимировать ОЭП релаксированной задачи Так как релаксированная задача (4) непрерывна, для аппроксимации ее ОЭГ могут быть использованы методы, разработанные для непрерывных задач: ме тод уточнения оценок (УО) в выпуклом случае и гибридные методы — в невы пуклом. Построенная аппроксимация визуализируется с помощью диалогового изображения карт решений — совокупностей двумерных сечений аппроксима ции ОЭП. ЛПР предлагается указать желаемую цель у (называемую квазира зумной) на границе Парето подходящего сечения аппроксимации ОЭП. Далее аналогично исходному МРЦ, по цели находится множество X альтернатив та ких, что множество Y = f(X) близко к у. Для этого требуется разработат метод поиска X, применимый в случае большого числа альтернатив.

Задача поиска X сводится в диссертации к нахождению всех оптимальны по Парето решений многокритериальной задачи

/(я)-» min,

(>-

хех,

где fi(x) = max{fi(x),i/i} для х Е Xq. В случае когда мощность Xq велию задача (5) не может быть решена прямым перебором, поэтому для ее решени в диссертации предлагается использовать метод, основанный на приложени концепции ветвей и границ к многокритериальным задачам с монотонным критериями. При этом предлагается разбивать множество .Хо на подмножеси вида

X? — {х £ XQ\xj = aj, j = 1,2... ,s} , (I

где s € {1,2,..., n}, a a = (ai,..., a3) — некоторый элемент целочисленно) куба {0,1,..., K}s. В качестве вектора нижних оценок подмножеств X" пре,

латается использовать

<1(х?) = (й(х°(Х!')),а(хХ1х?)))1 (?)

а в качестве верхних оценок — векторы из множества

Л(X?) = {х1 (Х%), г — 0,1,... ,К\ю (а4) ^ 0} , (8)

где х{ (X£) = (ах, а2, ■.., аа, г,... ,г), г = 0,1 ,...,К.

Предлагаемый метод основан на последовательно разбиение множества Хо на подмножества вида Х£, построении оценок для этих подмножеств, выделении альтернатив, являющихся кандидатами на вхождение в X, сравнении найденных альтернатив и оценок и исключении подмножеств, заведомо не содержащих альтернатив из X.

В конце раздела 2.1 приводятся результаты применения МКРЦ для прикладной задачи с числом альтернатив порядка 1013 и числом критериев от двух до пяти.

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

рамках работы МКРЦ, и основанная на следующих соображениях.

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

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

латаемого метода основана на последовательном разбиении множества Хо на подмножества Х° вида (6), вычислении векторов ¿(X") (см. (7)) и множеств Л(Х^) (см. (8)), построении на их основе очередных внешних и внутренних полиэдральных аппроксимаций У<? и отсеивании таких подмножеств вида вектор оценок которых <1 (Х£) принадлежит построенной внутренней аппроксимации Уд. Перейдем непосредственно к строгому описанию алгоритма.

На нулевой итерации строим начальные аппроксимирующие внешнее и внутреннее многогранные множества Рд и фо! полагаем начальный набор активных подмножеств Но = {Хо}- В общем случае начальные аппроксимации могут быть построены, например, в виде

Р0 = сопу(/ (Л (*„))) +К™,

Яо = + (9)

Построение сопу (/ (Л (Хо))) не вызывает трудностей, поскольку число точек Л (Хо) невелико.

Рассмотрим произвольную 1-ю итерацию. Перед ее началом должны быть заданы внутренняя аппроксимация и набор Нг—1 активных подмножеств Х0 вида X", порожденный на предыдущих итерациях.

1. Из набора Н;_1 выбираем множество для которого оценка ¿(Х£{) наиболее удалена от построенной аппроксимации Р1-1, т.е.

е Агётах/9(Й(А),Р,_1).

Ае

Способ формирования 1 позволяет гарантировать, что у всех А 6 Н;_1 расстояние до будет больше нуля.

2. Разбиваем Х^ па. К + 1 подмножество Х^'^, г = О,1,..., К.

3. Для каждого находим множество Л и вычисляем оценку

4. Строим Р/ на основе имеющегося многогранного множества Р\-\ и вычисленных оценок:

Р, = сопг ^и {/ (Л (*£?)) + ну} иЦ .

5. Строим набор Н¡. Для этого берем объединение 5(_Д и совокупности множеств для которых Л (х^1^ непусто; из этого объединения исключаем множества, для которых нижняя оценка <1 попадает внутрь построенного многогранного множества Р\. Заметим, что для множеств Xкоторые содержат единственный вектор, вектор й (Х%) принадлежит А(Х"), поэтому для таких множеств <1(Х%) всегда будет оказываться внутри Р;, и они будут исключаться из дальнейшего рассмотрения.

6. На основе построенного многогранного множества Р; строим <3/:

- СОПУ ^ у {¿{А) + К™} и Р^ . (10)

7. Если Н; не пусто, переходим к шагу 1 итерации (1 + 1). Если Е; пусто, завершаем работу алгоритма.

В данном методе на каждой итерации может быть получена оценка достигнутой точности:

леч

где 5Н(-, •) — метрика Хаусдорфа. Для метода аппроксимации ВОЭП показана корректность и монотонность (Р;_х С С С (¿1 С ¡-г), проведено экспериментальное изучение работы метода на модельных и прикладных задачах,

показывающее возможность использовать метод для задач с числом вариантов порядка 109 — 1013 и числом критериев от двух до пяти.

После построения аппроксимации ВОЭП, дальнейшая работа метода аналогична исходному МРЦ, т.е. построенная аппроксимация ВОЭП визуализируется с помощью карт решений и ЛПР предлагается указать желаемую разумную цель на границе Парето подходящего сечения аппроксимации ВОЭП. Далее, с помощью метода, предложенного в разделе 2.1, находится множество таких альтернатив X, что множество У" = /(X) близко выбранной цели.

В третьей главе рассматриваются теоретические вопросы скорости сходимости. Раздел 3.1 посвящен разработке методики, предназначенной для теоретического анализа скорости сходимости метода полиэдральной аппроксимации ВОЭП, предложенного в разделе 2.3. Как обычно, методика разрабатывается для задачи аппроксимации выпуклых компактных тел; далее она переносится на методы аппроксимации ВОЭП. В разделе 3.1 предложена схема наполнения — итерационная схема аппроксимации, порождающая для тела С из множества всех выпуклых компактных тел ^ в пространстве Ят последовательность многогранников {Рг}, удовлетворяющих свойству

Рг_гСР;С(7, 1 = 1,2,....

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

На основе схем наполнения по аналогии с хаудорфовыми последовательностями восполнения введено понятие хаусдорфовых последовательностей на-

полнения.

Определение 3.6 Последовательность многогранников порождае-

мая для С Е некоторой реализацией схемы наполнения, называется ха-■усдорфовой последовательностью наполнения (или (3#(7, С) -последовательностью), если существует константа 7 > О такая, что для любого I = 0,1,... справедливо

В диссертации для хаусдорфовых последовательностей наполнения доказана сходимость.

Теорема 3.1 Пусть есть хаусдорфова последовательность наполне-

ния для С ё . Тогда

Основными результатами раздела 3.1 являются оценки скорости сходимости хаусдорфовых последовательностей наполнения.

Теорема 3.2 Пусть есть GHfa, С)-последовательность для С £ "г? и

О < 7 < 1. Тогда для любого s > 0 существует N{e) такое, что при 1 ^ N(e) справедливо

где 7гт_1 — объем (т — 1)-мерного единичного шара, ш(С) — асферичность тела С, а а [С) — его поверхностный объем.

SH(Pl,Pl+1)^15H(Pl,C).

lim 5H{Pi,C) = 0.

8H(Pl,C)^(l + e)\2b,0)l1/{1-m).

Здесь

Теорема 3.3 Пусть {Р/}^0 есть С?#(7, С)-последовательность для С е "г?, О < 7 < 1 и пусть г, В. и г таковы, что Вг(г) С Ро С С С Вц(г). Тогда для любого I ^ 1 справедливо

симметрической разности.

В разделе 3.2 результаты, полученные для схем наполнения, применены для анализа метода полиэдральной аппроксимации ВОЭП в монотонных многокритериальных задачах. Введена экономичная модификация, особенностью которой является то, что шаг 4 метода полиэдральной аппроксимации ВОЭП разбивается на подшаги, на каждом из которых выбирается очередная точка р из множества верхних оценок всех имеющихся на итерации подмножеств, на которые разбито Хо. Для этой точки р проверяется условие

где 0 < т ^ 1 — заданный параметр, Р{ — многогранное множество, полученное из Р; на предыдущих подшагах. Если условие выполнено, то точка р присоединяется к Р(, тем самым улучшая аппроксимацию.

Доказано, что для экономичной модификации метода полиэдральной аппроксимации выпуклой оболочки Эджворта-Парето с параметром 0 < г ^ 1 справедливы оценки аналогичные оценкам теорем 3.2 и 3.3 не только по числу итераций, но и по числу вершин аппроксимирующих многогранников. При этом константы, входящие в соответствующие оценки, могут быть выражены через т, размерность т и диапазон изменения критериев на множестве X.

где

р(р,Р/)^гтахр(Р/,ад),

Четвертая глава посвящена использованию методов, предложенных в диссертации, при решении прикладных задач.

В разделе 4,1 описаны принципы функционирования программного комплекса, разработанного диссертантом для реализации МРЦ в задачах многокритериальной целочисленной оптимизации. Программный комплекс реализован на основе предложенных методов и состоит из трех компонентов: компонента аппроксимации ВОЭП, компонента визуализации ВОЭП в виде карт решений, компонента выделения малого числа альтернатив по выбранной цели. Комплекс рассчитан на работу под управлением ОС семейства Windows.

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

В разделе 4.2 приводится использование предложенных в диссертации мете дов для решения задачи поиска стратегии улучшения качества воды в бассейн крупной реки. В конкретной рассматриваемой задаче изучается бассейн рек Ока. Бассейн разбит на 14 участков, в каждом из которых возможно усте новить одну из 9 технологий очистки различной интенсивности и стоимости. Таким образом, в задаче около 1013 различных вариантов. В задаче изучает ся взаимосвязь между затратами и экологической обстановкой для различны решений, задаваемых набором технологий, установленных на участках. М<

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

В разделе 4.3 описано использование МРЦ в задаче поиска стратегии улучшения качества воды на основе детального описания бассейна небольшой реки. Изучается бассейн реки Муга (Каталония, Испания). Основным возможным мероприятием по улучшению качества воды является установка очистных сооружений в некоторых из 42-х пунктов выброса загрязнений. Всего рассматривалось 7 различных типов очистных сооружений. С учетом ограничений, общее число вариантов в задаче было порядка 1032. Так как модель была задана в виде вычислительного модуля, способного вычислять значения критериев только в целых точках, применить МКРЦ оказалось невозможно. Поэтому применялся только МРЦ. Была построена аппроксимация ВОЭП для пяти критериев с относительной точностью 0.2 за 200 итераций (50 часов). В работе приведены матрицы карт решений и результаты, получаемые при выборе разумной цели на границе Парето аппроксимации ВОЭП.

Заключение

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

программное обеспечение и решены прикладные задачи. В частности:

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

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

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

4. предложена и изучена схема наполнения, являющаяся обобщением известных адаптивных схем полиэдральной аппроксимации выпуклых компактных тел; полученные результаты использованы для теоретическо] оценки скорости сходимости по числу вершин метода полиэдральной аппроксимации оболочки Эджворта-Парето выпуклой оболочки критери альных точек;

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

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

Основные результаты опубликованы в работах

[1] А. В. Лотов, А. И. Поспелов. Метод квазиразумных целей для целочисленных задач многокритериальной оптимизации // Доклады Акад. наук. — 2007. - Т. 414, № 3. - С. 317-319.

[2] А. В. Лотов, А. И. Поспелов. Модифицированный метод уточнения оценок для полиэдральной аппроксимации выпуклых многогранников // Журн. вычисл. матем. и матем. физ,— 2008.— Т. 48, № 6.— С. 990998.

[3] А. И. Поспелов. Аппроксимация выпуклой оболочки Эджворта-Парето в многокритериальных задачах с монотонными критериями // Журн. вычисл. матем. и матем. физ. — 2009. — Т. 49, № 10. — С. 1765-1778.

[4] А. И. Поспелов. Аппроксимация выпуклой оболочки Эджворта-Парето в целочисленных задачах многокритериальной оптимизации // Материалы Международной конференции студентов и аспирантов по фундаментальным наукам "Ломоносов-2004", секция "Вычислительной математики и кибернетики". — М.: Издательский отдел ВМиК МГУ, 2004. — С. 25.

[5] A. I. Pospelov. About Polyhedral Approximation of Edgeworth-Pareto Convex Hull for the Special Class of Integer Multicriteria Optimization Problems // Труды 4-й Московской международной конференции по исследованию операций. - М.: МАКС Пресс, 2004. - С. 185-188.

[6] А. И. Поспелов. Алгоритм аппроксимации выпуклой оболочки Эджворта-Парето в некоторых задачах целочисленной многокритериальной оптимизации // Труды XIII Байкальской международной школы-семинара "Методы оптимизации и их приложения". — Т. 1. — Иркутск: ИСЭМ СО РАН, 2005. - С. 359-363.

[7] A. I. Pospelov, A. V. Lotov. Application of Convex Pareto Prontiei Approximation and Visualization in Integer Multicriteria Optimizatior Problems. — Loire Valley (old city hall of Tours), France: 2006.

[8] А. В. Лотов, А. И. Поспелов. Метод разумных целей для целочисленные задач многокритериальной оптимизации // Труды V Московской между народной конференции по Исследованию операций. — М.: МАКС Пресс 2007. - С. 149-151.

[9] А. И. Поспелов. Аппроксимация границы Парето выпуклой оболочга критериальных векторов в целочисленных задачах с монотонными кри териями // Сборник тезисов IV Всероссийской научной конференцш "Математическое моделирование развивающейся экономики и экологии

ЭКОМОД-2009 (Киров, 6-12 июля). - Киров: ГОУ ВПО "ВятГУ", 2009. -

С. 56.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 25.01.2010 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 028. Тел. 939-3890. Тел./факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Введение

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

1.1. Задача о наименьшем покрытии множествами

1.2. Многокритериальная задача о рюкзаке

1.3. Задача локального уменьшения загрязнения в реке.

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

2.1. Метод квазиразумных целей.

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

2.3. Метод разумных целей, основанный на аппроксимации выпуклой оболочки Эджворта-Парето.

Глава 3. Теоретический анализ скорости сходимости метода аппроксимации ВОЭП.

3.1. Общие хаусдорфовы схемы, адаптивные методы и последовательности наполнения

3.2. Скорость сходимости метода аппроксимации ВОЭП

Глава 4. Решения прикладных задач с помощью метода разумных целей

4.1. Программный комплекс МРЦ для монотонных целочисленных задач многокритериальной оптимизации.

4.2. Использование программного комплекса в системе поиска эффективных технологий очистки воды в бассейнах крупных рек

4.3. Использование комплекса для поиска эффективных технологий очистки воды в малых реках

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

Одним из подходов, использующих аппроксимацию границы Парето, является ее визуализация. Этот подход развивают исследования, проводимые школами академиков П. С. Краснощёкова и А. А. Петрова в области поддержки выбора наиболее перспективных вариантов в задачах проектирования сложных систем и анализа сложных моделей. Компьютерная визуализация границы Парето должна помочь конструкторам и исследователям оценить возможности объекта проектирования или исследования, выявить связь различных характеристик объекта и найти его перспективные варианты ([11-21]). При этом в случае более чем двух критериев используется интерактивная визуализация и анимация границы Парето. Такая визуализация оказывается возможной на основе предварительной аппроксимации многомерного множества достижимых критериальных векторов (или другого, более широкого множества — оболочки Эджворта-Парето (ОЭП) множества достижимых критериальных векторов, являющейся максимальным множеством, имеющим ту же границу Парето) с помощью относительно простых фигур (многогранников, объединения коиечного числа конусов и т.д.). Интерактивная визуализация и анимация границы Парето осуществляется путем расчета и изображения двумерных сечений аппроксимации. ЛПР на основе визуального изучения границы Парето осознанно выбирает предпочтительное достижимое сочетание значений критериев (достижимую цель), а последующий расчет соответствующего эффективного по Парето решения осуществляется компьютером автоматически.

Разработка таких методов для поиска эффективных по Парето решений экономических задач началась еще в семидесятых годах прошлого века [11]. С середины восьмидесятых годов методы используются для поиска эффективных по Парето стратегий улучшения состояния окружающей среды (см., например, [16-19]). Дальнейшее развитие методов может быть связано с их применением в компьютерных сетях, где методы могут быть использованы как в системах электронной торговли, так и для поддержки индивидуального или коллективного выбора экологических и других важных решений.

Отметим, что результаты, полученные в 1980-1990-х годах, были основаны преимущественно на анализе выпуклых, в том числе и линейных моделей; были разработаны адаптивные итеративные методы полиэдральной аппроксимации выпуклых многомерных множеств, асимптотически оптимальные по скорости сходимости и сложности описания аппроксимации, в которых аппроксимирующие многогранные множества строятся с помощью расчета значений опорной функции аппроксимируемого множества ([19-22]).

Для обобщения этих результатов на дискретные задачи в начале 1990-х годов была разработана концепция метода разумных целей [23, 24], основанного на сведении многокритериальной задачи выбора из конечного числа вариантов (альтернатив) к анализу границы Парето выпуклой оболочки критериальных точек — образов рассматриваемых альтернатив. Метод разумных целей (МРЦ) оказался эффективным средством поддержки многокритериального выбора из конечного числа решений с количественными критериями (см. [21, 25-29]). Ограничением на использование МРЦ является то, что в нем требуется явное описание всех возможных решений (альтернатив) в виде точек в критериальном пространстве. Это вызывает затруднения при решении задач, в которых число вариантов велико (более 106). Рекордом стала задача улучшения качества воды, описанная в [25], в которой для применения МРЦ пришлось разработать специальный быстрый метод расчета критериальных точек для 400 тысяч альтернатив. Выше сказанное обосновывает необходимость разработки новых методов, которые могут быть использованы в задачах многокритериального выбора из большего конечного числа альтернатив.

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

В общем случае в задачах многокритериальной оптимизации предполагается, что заданы некоторое множестве решений X С Шп и векторнозначная функция /(•) : Ш.п —> Кт; при этом компоненты функции /(•), т.е. числовые функции fi (•),., fm(-), так называемые частные критерии, характеризуют эффективность решений х 6 X с разных точек зрения. Далее для определенности, если не оговорено обратное, будем предполагать, что желательным является уменьшение значения каждого из частных критериев /¿(-),г — 1,2,. ,т, при прочих равных условиях. Такие задачи называются задачами многокритериальной минимизации и формально записываются в виде х) —> min,

1) х G X.

Как и в классической оптимизации, в многокритериальной оптимизации важную роль играет понятие оптимальности. В многокритериальной оптимизации, вообще говоря, существуют различные определения оптимальности (см., например, [6, 8]). В настоящей диссертационной работе используется оптимальность по Парето.

Приведем математическую формулировку оптимальности по Парето.

Определение 1. Пусть х' и х" — некоторые решения из Rn. Говорят, что решение х' доминирует х" по Парето с точки зрения набора частных критериев /(■) = (/i(-), /2(-), • ■ •, 1т{-)), если fi{x') ^ fi(x"), г = 1,2 и

М ^ /М

Определение 2. Критериальная точка fix') называется оптимальной по Парето в задаче (1), а соответствующее ей решение х' Е X — эффективным по Парето, если не суш,ествует решения х" 6 X, доминирующего х' по Парето.

Множество всех оптимальных по Парето критериальных точек называется границей Парето.

В прикладных задачах принятия решения часто приходится сталкиваться с ситуацией, когда множество допустимых решений X является дискретным. Такая ситуация встречается, например, в транспортных задачах, задачах составления расписаний, телекоммуникационной маршрутизации, задачах планирования инвестиций и производства и в других задачах (см., например, [30,31]).

Математическая задача целочисленной многокритериальной оптимизации, рассматриваемая в диссертационной работе, формулируется следующим образом. (х) —> min,

2) х € X = {х G Хо\Wi (х) ^ 0, г = 1, 2,., к} , где Х0 — {0,1 .К}п — целочисленный куб Rn, /(•) : Xq —> Rm — векторнознач-ная функция, задающая критерии, w(-) : Хо —> Шк — набор функций, используемых для описания ограничений. Рассматривается случай монотонных критериев, часто встречающийся в прикладных исследованиях — предполагается, что {х) = (и (х) ,у (ж)), х € Х0: где и(-) и у(-) — такие векторнозначные функции, что и(-) : Хо —> М* и у(-) : Хо —> ит~1 для некоторого целого 0 ^ £ ^ га, и при этом и(-) и у(') монотонны в следующем смысле:

Ух', х" еХ0:х'3^х^ 5 = 1,2,. щ(х') ^ щ(х"), г = 1, 2,., и у^х') ^ у^(х"), у = 1, 2,., т — ¿. Кроме того, предполагается, что ограничения также монотонны, т.е.

V®', х" £Х0:х'^х^ 5 = 1, 2, .,71,

4)

1щ{х') ^ш^х"), / = 1,2,.,*;.

К виду (2)-(4) могут быть сведены многие дискретные многокритериальные прикладные задачи.

Проблема поиска или аппроксимации множества эффективных решений и соответствующей совокупности оптимальных по Парето критериальных точек в многокритериальных дискретных задачах оптимизации изучалась ранее (см. [32-35]). Был предложен широкий спектр методов, использующих комбинаторную специфику рассматриваемых задач или сведение их к решению серии од-нокритериальных задач оптимизации, для каждой из которых можно найти решение (см., например, [36-39]).

В различных прикладных задачах дискретной оптимизации (в том числе многокритериальных) часто возникает необходимость решать комбинаторные задачи, которые не относятся к изученным классам. К таким задачам, в частности, относятся проблемы, в которых модель задана вычислительным модулем с закрытым кодом (черным ящиком), предоставляющим возможность только для расчета значений критериев по заданным решениям. В таких случая можно применять, например, методы случайного поиска и методы, основанные на термодинамических и биологических аналогиях (см. [10, 40-44]). В этих методах оценки точности аппроксимации границы Парето отсутствуют (обычно качество алгоритма оценивается на основе сравнения аппроксимации с заранее известной точной границей Парето, которую удается построить лишь в простейших случаях), так что эти методы, по существу, являются эвристическими.

Для нахождения всех оптимальных решений в задачах типа (2)-(4) может быть использована схема ветвей и границ (см. например, [45]). Но, как показывает опыт, такой подход обладает очень высокой трудоемкостью в связи с тем, что число решений может оказаться очень велико даже для задач сравнительно малой размерности.

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

Диссертация состоит из введения, четырех глав и заключения.

4.3.2. Результаты работы с комплексом при анализе бассейна реки Муга

Одной из рек для, которых была адаптирована модели, является река Муга. На рисунке 4.10 изображен общий вид бассейна реки с разбиением на участки, в которых проводились замеры. Максимальная протяженность реки около 60 км, площадь бассейна — 760 км2.

Солса сЗе 1а Мида А \ г и*п$«

Сдтди.11»

ШаДОа Г

МтЬд»1

Ба!е» 4» Шегс«

СЫсШ

• Ез1ааопз чиаиа11 яиагШ1аг

• ЕОАВ

Сар1асЬп5 13'аЬаз1атагЛ игЬа

• Са^асюпв а о гедайш [ , Тегтез тигке!ра1в

I 1 Сопса da 1а Мида СП Ми<Й8 иЬапа г X """V

1Цлп«п1 { ' - ,

-¿«А , У|и|«п|м" 1 л V

1 V

V р,и

ЛОМ^тгап"^ * >> л Л / Ч

КО«!

Ч^ / 5«пи иеааа

AUmalli /• "

ГЕтрвпЦ ^ } V

О 2500 5 000

10 ООО Элл» Рйг© Ревсэс| а^^^^От^ог 8»гЬуА ЕаровсШ

ТАттвМег*

Рис. 4.10. Схема бассейна реки Муга

Всего в бассейне 42 места возможного использования мероприятий по очистки воды. Таким образом, число возможных проектов очистки составляло порядка Ю40; однако, в задаче присутствовали дополнительные ограничения на возможность установки технологий, поэтому общее число доступных альтернатив было порядка 1032.

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

В качестве критериев выбраны пять наиболее важных в данной задаче критериев: стоимость, содержание аммония, нитратов, фосфатов и углерода в органических соединениях. Общее время аппроксимации ВОЭП занимало около двух суток, при этом более 99% времени ушло на расчет значений критериев, число итераций метода полиэдральной аппроксимации было около 200. Оценка погрешности построенной аппроксимации составлял 0.2. На рис. 4.11 изображены карты решений для пятимерной ВОЭП этой задачи.

В данной задаче была сделана попытка выбрать некоторое сбалансированное решение. Таким образом, на матрице карт решений была выбрана карта, для которой критерии Fosfatos и ТОО равны 0.89 и 0.87 соответственно. На рис. 4.12 изображена карта решений при зафиксированных Fosfatos и ТОС. На карте решений была выбрана цель (3.565524, 0.657521, 0.873195, 0.883993, 0.877295). По этой цели компонент поиска решений нашел единственное оптимальное по Парето решение, имеющее критериальную оценку (3.594556, 0.676394, 0.874914 0.897402, 0.884669); при этом для этого потребовалось порядка 2 часов. Как и в случае с задачей очистки стоков в бассейне реки Ока (см. раздел 4.2.1), использовалось дополнительное правило отсева (2.3) с к = 1.5.

Рис. 4.11. Матрицы карт решений для пяти критериев: стоимости (costetotal), содержания аммония (Amonio), нитратов (Nitratos), фосфатов (Fosfatos) и углерода в органических соединениях (ТОС)

Jivi App!«t Window jPriif Diielzv iftirnitivt5 button to show th< list of illtrnitivts rtilliv« to thi sffactid qoal

Рис. 4.12. Карта решений для трех критериев: стоимости (costetotal), содержания аммония (Amonio), нитратов (Nitratos) при фиксированных значениях фосфатов (Fosfatos) и углерода в органических соединениях (ТОС)

Заключение

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

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

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

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

4. предложена и изучена схема наполнения, являющаяся обобщением известных адаптивных схем полиэдральной аппроксимации выпуклых компактных тел; полученные результаты использованы для теоретической оценки скорости сходимости по числу вершин метода полиэдральной аппроксимации оболочки Эджворта-Парето выпуклой оболочки критериальных точек;

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

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

1. П. С. Краснощёкое, А. А. Петров. Принципы построения моделей. — М.: МГУ, 1983.

2. П. С. Краснощёкое, А. А. Петров, В. В. Фёдоров. Информатика и проектирование. — М.: Знание, 1986.

3. Ю. Г. Евтушенко, М. А. Потапов. Численные методы решения многокритериальных задач // Кибернетика и вычислит, техника. Вып. 3. — М.: Наука, 1987. С. 209-218.

4. В. В. Подиновский, В. Д. Ногин. Парето-оптимальные решения многокритериальных задач. — М.: Физматлит, 2007.

5. И. М. Соболь, Р. Б. Статников. Выбор оптимальных параметров в задачах со многими критериями. — М.: Наука, 1981.

6. Р. Штойер. Многокритериальная оптимизация. — М.: Радио и связь, 1992.

7. R. В. Statnikov, J. Matusov. Multicriteria Optimization and Engineering. —■ New Jersey: Chapman and Hall, 1995.

8. K. . Deb. Multi-objective optimization using evolutionary algorithms. — ' Chichester: Wiley, 2001.

9. A.B. Лотов. Исследование экономических систем с помощью множеств достижимости // Труды международной конференции "Моделированиеэкономических процессов" (Ереван, апрель 1974).— М.: ВЦ АН СССР, 1975.

10. А.В. Лотов. О понятии обобщенных множеств достижимости и их построении для линейных управляемых систем // Доклады АН СССР. — 1980. — Т. 250, № 5.

11. А.В. Лотов. Анализ потенциальных возможностей экономических систем // экономика и матем. методы. — 1983. — Т. 17, № 2.

12. А.В. Лотов. Согласование математических моделей с использованием множеств достижимости // Математические методы анализа взаимодействия отраслевых и региональных систем. — Новосибирск: Наука, 1983.

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

14. А.В. Лотов. Методы анализа математических моделей управляемых систем на основе построения множества достижимых значений показателей качества управления: Дис. на соискан. учен. степ. докт. физ.-мат. наук. / М.: ВЦ АН СССР. 1986.

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

16. A. Lotov, V. Bushenkov, 0. Chernykh. Multi-criteria DSS for River Water Quality Planning // Microcomputers in Civil Engineering. — 1997. — no. 1. — Pp. 57-67.

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

18. А. В. Лотов, В. А. Бушеиков, Г. К. Каменев. Метод достижимых целей. Математические основы и экологические приложения. — Эдвин Меллен Пресс, Нью-Йорк, США, 1999.

19. А. V. Lotov, V. A. Bushenkov, G. К. Kamenev. Interactive Decision Maps. Approximation and Visualization of Pareto frontier. — Boston: Kluwer Academic Publishers, 2004.

20. Г. К. Каменев. Оптимальные адаптивные методы полиэдральной аппроксимации выпуклых тел. — ВЦ РАН, 2007.

21. Д. В. Гусев, А. В. Лотов. Модели, системы, решения // Исследование операций / Под ред. Ю. П. Иванилова. — М.: ВЦ РАН, 1994. — С. 15-43.

22. В. А. Бушенков, Д. И. Гусев, Г. К. Каменев и др. Визуализация множества Парето в многомерной задаче выбора // Доклады Академии наук. — 1994. Т. 335, № 5. - С. 567-569.

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

24. D. Soloveichik, N. Ben-Aderet, M. Grinman, A. Lotov. Multi-objective optimization and marginal abatement cost in the electricity sector — an Israeli case study // European Journal on Operational Research. — 2002. — no. 140(3).-Pp. 571-583.

25. А. V. Lotov, V. A. Bushenkov, G. К. Kamenev. Feasible goals method — Search for smart decisions. — M.: Comput. Centre RAS, 2001.

26. И. X. Сигал, А. П. Иванова. Введение в прикладное дискретное программирование. — М.: Физматлит, 2007.

27. G. Yu. Industrial applications of combinatorial optimization. — Boston: Kluwer Acad. Pubis., 1998.

28. И. X. Сигал, И. И. Меламед. Исследование линейной свертки критериев в многокритериальном дискретном программирование // Ж. вычисл. матем. и матем. физ. — 1995. — Т. 35, № 8. С. 1260-1270.

29. И. X. Сигал, И. И. Меламед. Теория и алгоритмы решения многокритериальных задач комбинаторной оптимизации. — М.: ВЦ РАН, 1996.

30. И. X. Сигал. Алгоритмы для решения бикритериальной задачи коммивояжера большой размерности // Ж. вычисл. матем. и матем. физ.— 1994. Т. 34, № 1. - С. 44-57.

31. М. Ehrgott, X. Gandibleux. An annotated bibliography of multiobjective combinatorial optimization: Tech. Rep. 62: Wirtschaftsmathematik, 2000.

32. И. И. Меламед, И. И. Сигал, Н. Ю. Владимирова. Исследование линейной свертки критериев в бикритериальной задаче о ранце // Ж. вычисл. матем. и матем. физ. — 1999. — Т. 39, № 5.

33. X. Gandibleux, K. Klamroth. Cardinality bounds for multiobjective knapsack problems: Tech. rep.: Inst, of Appl. Math., Univ. of Erlangen-Nuremberg, Germany, 2006.

34. H. W. Hamacher, C. R. Pedersen, S. Ruzika. Finding representative systems for discrete bicriteria optimization problems by box algorithms // Operat. Res. Lett. 2007. - Vol. 35. - Pp. 336 - 344.

35. D. Schweigert. Vector-weighted matchings // Combinatorics Advances / Ed. by C. Colbourn, E. Mahmoodián. — Dordrecht: Kluwer Academic, 1995.— Pp. 267-276.

36. F. Glover, M. Laguna. Tabu Search. — Dordrecht: Kluwer Acad. Pubis., 1997.

37. A. J. Chipperfield, J. F. Whideborn, P. J. Fleming. Evolutionary algorithms and Simulated Annealing for MCDM // Multicriteria Decision Making: Advances in MCDM Models, Algorithms, Theory, and Applications. — Boston: Kluwer Academic Publishers, 1999.

38. A. Suppaptnarm, K .A. Steffen, G. T. Parks, P. J. Clarkson. Simulated Annealing: An alternative approach to true multiobjective optimization // Engineering Optimization. — 2000. — Vol. 33, no. 1. — Pp. 59-85.

39. M. В. Евдокимов, В. Г. Медницкий, И. X. Сигал. Бикритериальная задача переоборудования производства // Изв. РАН. Теория и системы управления. 2001. - № 5. - С. 90-96.

40. А. V. Lotov, К. Miettinen. Visualizing the Pareto frontier // Multiobjective optimizat. Interact, and Evolutionary Approach., Led. Notes in Comput. Sci. Berlin-Heidelberg: Springer. — 2008. — Vol. 5252. — Pp. 213-244.

41. В. А. Вушенков, А. В. Лотов. Методы построения и использования обобщенных множеств достижимости. — М.: ВЦ АН СССР, 1982.

42. M. Karwan, V. Lotfi, J. Telgen, S. Zionts. Redundancy in mathematical programming. — Berlin: Springer-Verlag, 1983. — Vol. 206 of Lecture Notes in Economics and Mathematical Systems.

43. B. Roy. Classement et choix en presence de points de vue multiples (la methode ELECTRE) // Revue Française d'Informatique et de Recherche Op 'rationnelle. 1968. — Vol. 2, no. 8. — Pp. 57-75. 1

44. P. Slovic, B. FischhoffS. Lichtenstein. Behavioural Decision Theory // Annual Review of Psychology. — 1977. — Vol. 28. — P. 1-39.

45. О. Л. Черных. Построение выпуклой оболочки конечного множества точек на основе триангуляции // Журн. вычисл. матем. и матем. физ. — 1991. Т. 31, № 8. - С. 1231-1242.

46. Л.В. Вурмистрова. Экспериментальный анализ нового адаптивного метода полиэдральной аппроксимации многомерных в ыпуклых тел: методика, программное обеспечение и некоторые результаты // Ж. вычисл. матем. и матем. физ. 2003. — Т. 43, № 3. — С. 328-346.

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

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

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

50. А. В. Лотов, А. И. Поспелов. Метод разумных целей для целочисленных задач многокритериальной оптимизации // Труды V Труды V Московской международной конференции по Исследованию операций (ORM2007).— М.: МАКС Пресс, 2007. С. 149-151.

51. A. I. Pospelov, А. V. Lotov // Application of Convex Pareto Frontier

52. Approximation and Visualization in Integer Multicriteria Optimization Problems. — Loire Valley (old city hall of Tours), France: 2006.

53. А. В. Лотов, А. И. Поспелов. Метод квазиразумных целей для целочисленных задач многокритериальной оптимизации // Доклады Акад. наук. 2007. - Т. 414, № 3. - С. 317-319.

54. А. В. Лотов, А. И. Поспелов. Модифицированный метод уточнения оценок для полиэдральной аппроксимации выпуклых многогранников // Журн. вычисл. матем. и матем. физ.— 2008. —Июнь. — Т. 48, № 6.— С. 990-998.

55. А. И. Поспелов. Аппроксимация выпуклой оболочки Эджворта-Парето в многокритериальных задачах с монотонными критериями // Журн. вычисл. матем. и матем. физ.— 2009. — Октябрь. — Т. 49, № 10.— С. 1765-1778.

56. R. М. Karp. Reducibility Among Combinatorial Problems // Complexity of Computer Computations / Ed. by R. E. Miller, J. W. Thatcher. — New York: Plenum, 1972. Pp. 85-103.

57. M. A. Badri, A. K. Mortagy, C. A. Alsayed. A multi-objective model for locating fire stations // European journal of operational research. — 1998.— Vol. 110, no. 2.- Pp. 243-260.

58. A. Jaszkiewicz. A comparative study of multiple-objective metaheuristics on the bi-objective set covering problem and the Pareto memetic algorithm: Tech.

59. Rep. RA-003/01, 2001.— Poznan, Poland: Institute of Computing Science, Poznan University of Technology, 2001.

60. В. M. Smith, A. Wren. A Bus Crew Scheduling System Using a Set Covering Formulation // Transportation Research. — 1988. — no. 22A. — Pp. 97-108.

61. H. W. Hamacher, S. Ruzika, A. Tanatmis. Acquisition Prioritization: A Multicriteria Approach Based on a Case Study: Tech. Rep. 100/2006: University of Kaiserslautern, Department of Mathematics, 2006.

62. А. В. Лотов, Г. К. Каменев, В. Е. Вёрезкин. Аппроксимация и визуализация паретовой границы для невыпуклых многокритериальных задач // ДАН. 2002. - Т. 386, № 6. - С. 738-741.

63. С. Н. Черников. Линейные неравенства. — М.: Наука, 1968.

64. О. JI. Черных. Аппроксимация Парето-оболочки выпуклого множества многогранными множествами // Ж. вычисл. матем. и матем. физ. — 1995. Т. 35, № 8. - С. 1033-1039.

65. Ф. П. Васильев, А. Ю. Ивапицкий. Линейное программирование. — М.: Изд-во "Факториал Пресс", 2003.

66. Н. К. Бурова, Л. И. Стапевичене, А.-И. А. Станевичус, П. Э. Шкляр. Система линейного программирования. — М.: ВЦ АН СССР, 1981.

67. У. X. Малков. Обзор путей повышения эффективности мультипликативного алгоритма симплекс-метода // Математические методы решения экономических задач. — М.: Наука, 1977.

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

69. О. Л. Черных. Построение выпуклой оболочки конечного множества точек в виде системы линейных неравенств // Ж. вычисл. матем. и матем. физ. 1992. — Т. 32, № 8. - С. 1213-1228.

70. E. Zitzler, M. Laumanns. ETH SOP - Downloads/Material

71. Supplementary Material Test Problem Suite.http: / / www.tik.ee.ethz.ch/sop/download/supplementary/testProblemSuite/.

72. E. M. Бронштейн. Аппроксимация выпуклых множеств многогранниками // Геометрия. М.: РУДН, 2007. - Т. 22 из СМФН. - С. 5-37.

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

74. P. М. Gruber. Approximation of Convex Bodies // Convexity and Its Applications / Ed. by P. M. Gruber.— Basel etc.: Birkhauser, 1983.— Pp. 131-162.

75. P. M. Gruber. Aspects of Approximation of Convex Bodies // Handbook of Convex Geometry / Ed. by P. M. Gruber, J. M. Wills.— Elsevier Sci. Publishers B.V., 1993. Pp. 321-345.

76. Г. К. Каменев. Об одном классе адаптивных схем аппроксимации выпуклых тел многогранниками // Матем. моделирование и дискретная оптимизация. М.: ВЦ АН СССР, 1988. - Pp. 3-9.

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

78. Е. М. Бронштейн, JI. Д. Иванов. О приближении выпуклых множеств многогранниками // Сибирский матем. ж.— 1975.— Т. 26, № 5.— С. 1110-1112.

79. А. Ф. Измаилов, М. В. Солодов. Численный методы оптимизации. — М.: Физматлит, 2003.