Методы многокритериальной целочисленной оптимизации, основанные на аппроксимации границы Парето тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Поспелов, Алексей Игоревич

• Поспелов, Алексей Игоревич
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Поспелов, Алексей Игоревич

Введение

Глава 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. программный комплекс применен в рамках двух проектов улучшения качества воды в больших и малых реках.

Список литературы диссертационного исследования кандидат физико-математических наук Поспелов, Алексей Игоревич, 2010 год

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.