О сложности некоторых многокритериальных дискретных задач

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

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

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

Может показаться, что в силу конечности множества допустимых вариантов, решение подобных задач не потребует больших усилий. Но количество анализируемых маршрутов растет очень быстро с увеличением размерности задачи, роль которой в данном случае играет количество городов п (заметим, что для задачи коммивояжера эта величина составляет (п — 1)!/2, а для задачи о минимальном остов-ном дереве — лп~2). II если для второй задачи известен эффективный «жадный» алгоритм, дающий точное решение и позволяющий с помощью современных ЭВМ строить сети для тысяч городов, то для задачи коммивояжера алгоритма с подобными качествами до сих пор не найдено, несмотря на значительные усилия, приложенные в этом направлении. Более того, существуют достаточно веские причины, лишающие надежды отыскать такой алгоритм в ближайшем будущем.

Перейдем к общей постановке задачи дискретной оптимизации в обычной, однокрнтериальной постановке. Пусть задано конечное множество А" и функция /, определенная на этом множестве и принимающая действительные значения. Требуется найти такой элемент .г* 6 А", для которого /(х*) < /(х) для любого элемента х? X.

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

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

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

• описанные выше трудности.

Специфика многокритериальных задач определяется прежде всего тем, что при к > 2 (к— количество критериев) формулировка задачи связана с предварительным выбором типа упорядоченности в Як. Для уточнения термина «оптимизация» остановимся на двух типах упорядоченности, которые рассматриваются далее — обычное, покоординатное сравнение векторов и лексикографическое.

Будем писать и < V, где и = [щ,., щ), V = (г>1,., г*) если г = Такое отношение определяет в Як полуупорядоченность.

Лексикографическое неравенство между элементами из Як будем обозначать и <1ех Vоно означает, что для некоторого г, 0 < г < к,.

ВЫПОЛНЯЮТСЯ УСЛОВИЯ Щ = VI,. = щ+1 <

Замечание 0.1. Очевидно, что минимальных элементов, в конечном множестве может быть несколько, а лексикографически минимальный — ровно один.

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

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

Теория многокритериальных задач развита в работах Дубова Ю. А., Травкина С.II. [1], Подиновского В. В., Ногина В. Д., Гаврилова В. М. [2], [3], Березовского Б. А. [4], большое количество результатов приведено в обзорной статье Емеличева В. А. и Перепелицы В. А. [5].

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

• Получение множества решений по Парето с помощью детального учета конструкции множества допустимых решений Лг. В качестве примера можно привести следующие публикации:

1) в работе Guerriero F., Musmanno R. [G] предложен псевдопо-лнномнальный алгоритм отыскания множества Парето минимальных элементов для многокритериальной задачи о кратчайшем пути;

2) в работе Djordje D. [7] рассматривается псевдополиномиальный алгоритм для многокритериальной задачи о рюкзаке.

• Исследование возможности получения оптимального решения путем перехода от многокритериальной задачи к однокритериаль-ной с аддитивным целевым критерием. Установлено, что, используя линейную свертку критериев, можно находить все оптимумы Парето (эффективные решения) в многокритериальной задаче линейного программирования. Упомянем также работы Кравцова М. К. и Янушкевича O.A. [8], Емеличева В. А. и Янушкевича.

O.A. [9], где указана общая формула для оптимумов Парето, находимых сверткой критериев в случае, когда множество векторных (достижимых) оценок конечно. В работе Кравцова М. К. [10] показано, что существуют задачи, которые нельзя разрешить в классе алгоритмов линейной свертки критериев. Кроме того, следует упомянуть публикации: Меламеда II.II. и Сигала И. Х. [11−13], Емелнчева В. А., Кравцова М. К. [14], Емеличева В. А., Кравцова М. К., Янушкевича O.A. [15,16], Смирнова М. М. [17].

• Получение решения для лексикографической многокритериальной задачи. Это направление исследований представлено работами Емеличева В. А., Кравцова М. К., Янушкевича O.A., Гирлиха.

Э., Червака Ю. Ю., Червака О. Ю. [18−20].

• Анализ сложности многокритериальных задач (см. Емеличев В. А., Перепелица В. А., Сергиенко II.B. [21]- [23]).

• Приближенные методы отыскания элементов, входящих в Паре-товское множество. В качестве примера можно привести следующие публикации: Емеличева В. А. и Перепелицы В. А. [24], Gengui Z. и Mutsio G. [25].

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

Содержательная часть работы разделена на несколько глав.

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

Во второй главе изучается вопрос о мощности множества минимальных элементов в f (X).

Предположим, что рассматривается произвольное конечное множество Е, на котором определена функция с: Е —" R2. Обозначим через, А множество всех непустых его подмножеств, |А" | = 2¹ — 1, и положим.

Д*) = 2>(е), е? х.

Для сформулированной модели устанавливаются следующие утверждения:

• Теорема. Для любого конечного множества Е существует такая функция с: Е —> Л2, для которой множество {/(я): ж 6 А'} состоит из попарно несравнимых элементов, или, иначе, Аг° = А" .

• Теорема. Пусть Хт — множество всех подмножеств Е, содержащих по т элементов, 1 < т < п = Е. Тогда существует такая положительная функция с: Е —>• Я2, для которой множество {/(х): х € А" т} состоит из попарно несравнимых элементов.

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

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

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

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

1. Дубов Ю. А., Травкин СЛ., Янимец В. Н. Многокритериальные модели формирования и выбора вариантов систем. М.: Наука, 198G.

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

3. Подиновский В. В., Гаврилов В. М. Оптимизация по последовательно применяемым критериям. М.: Сов. радио, 1975.

4. Березовский Б. А., Борзенко В. И., Кемпнер JI.M. Бинарные отношения в многокритериальной оптимизации М.:Наука. 1981. С. 150.

5. Djordje D. Многокритериальная задача о ранце. //9 Kongr. mat. Jugosl., Petrovac, May 22−27, 1995: Rez.: YUMC'95. Podgorica, 1995. C. 135.

6. Кравцов M.K., Янушкевич O.A. О разрешимости векторной задачи с помощью алгоритма линейной свертки критериев.// Математические заметки. 1997. Т. 62. № 4. С. 502−509.

7. Емеличев В. А., Янушкевич O.A. Условия Парето-оптимальности в дискретных векторных задачах оптимизации. // Дискретная математика. 1997. Т. 9. Вып. 3. С. 153−1G0.

8. Кравцов М. К. Неразрешимость задач векторной дискретной оптимизации в классе алгоритмов линейной свертки критериев. // Дискретная математика. 1996. Т. 8 Вып. 2. С. 89−96.

9. Меламед II-II., Сигал И. Х. Вычислительное исследование линейной свертки критериев в многокритериальном дискретном программировании. //Докл. РАН 1995. Т. 345. Ш С.463−466.

10. Меламед II.II. Теория линейной параметризации критериев в многокритериальной оптимизации.// Докл. РАН 199G. Т. 348 № 4. С. 446−448.

11. Меламед II. IL, Сигал И. Х. Бикритериальные задачи дискретного программирования с MINSUM-MINSUM критериями // М.: Из-во ВЦ РАН (Сер. сообщ. по прикл. мат.) 2000. 29 с.

12. Емеличев В. А., Кравцов М. К. О комбинаторных задачах векторной оптимизации. // Дискретная математика. 1995. Т. 7 Вып. 1. С. 3−18.

13. Емеличев В. А., Кравцов М. К., Янушкевич O.A. Условия Парето-оптимальности в одной дискретной векторной задаче на системе подмножеств. // Журнал вычислительной математики и математической физики. 1995. Т. 35 № 11. С. 1641−1652.

14. Емеличев В. А., Кравцов М. К., Янушкувич O.A. Разрешимость векторной траекторной задачи на «узкие места» с помощью алгоритма линейной свертки критериев. // Докл. АН Беларуси. 1996. Т. 40 т. С. 29−33.

15. Смирнов М. М. О логической свертке вектора критериев в задаче аппроксимации множества Парето. // Журнал вычислительной математики и математической физики. 1996. Т. 36 № 5. С. 62−74.

16. Емеличев В. А., Кравцов М. К., Янушкевич O.A. Лексикографические оптимумы многокритериальной задачи дискретной оптимизации.// Математические заметки. 1995. Т. 58. № 3. С. 365−372.

17. Емеличев В. А., Гирлих Э., Янушкевич O.A. Лексикографические оптимумы многокритериальной задачи.// Дискретный анализ и исследование операций. 1997. Т. 4. № 3. С. 365−372.

18. Червак Ю. Ю., х1ервак О. Ю. Один из способов формулирования Парето-лексикографических задач оптимизации. // Кибернетика п системный анализ. 199G. № 3. С. 108−111.

19. Емеличев В. А., Перепелица В. А. О мощности множества альтернатив в дискретных многокритериальных задачах. // Дискретная математика. 1991. Т. 3. Вып. 3. С. 3−13.

20. Емеличев В. А., Перепелица В. А. К вычислительной сложности многокритериальных задач // Пзв. АН СССР. Техн. кибернетика. 1988. № 1. С. 78−85.

21. Сергненко И. В., Перепелица В. А. К проблеме нахождения множеств альтернатив в дискретных многокритериальных задачах. // Кибернетика 1987. № 5. С. 85−93.

22. Емеличев В. А., Перепелица В. А. О некоторых алгоритмических проблемах многокритериальной оптимизации на графах. // Журнал вычислительной математики и математической физики. 1989. Т. 29 № 2. С. 171−183.

23. Гэри М., Джонсон Д. Вычислительные машины и труднорешае-мые задачи. М.: Мир. 1982.

24. Dijkstra E.W. A Note on Two Problems in Connexion with Graphs, Nuinerislie Mathematik, 1 (1959), 289−271.

25. Краснов M.B. Многокритериальная задача о кратчайших путях для всех пар узлов графа. //В сб. научн. тр. «Современные проблемы математики и информатики», вып. З, Ярославль, ЯрГУ, 2000, С. G2-GG.

26. Краснов М. В. О многокритериальной оптимизации. //В сб. тезисы докладов Международной научной конференции студентов, аспирантов и молодых ученых «Молодая наука 21 веку» Иваново, ИвГУ, 2001, С. 62−63.

27. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир. 1978. 432 с.

28. Емеличев В. А., Пашкевич A.B., Янушкевич O.A. Условия эффективности решения векторной задачи дискретной оптимизации. // Дискретная математика. 1999i Т. 11. Вып. 1. С. 141−145.I.

29. Бондаренко В. А., Клоеден П. Е., Краснов М. В. О лексикографической оптимизации в многокритериальных дискретных задачах. // Автоматика и телемеханика. 2000. № 2. С. 29−35.

30. Груздев О. И., Краснов М. В. О сложности одной многокритериальной задачи. // Модел. и анализ информ. систем. 2002. Т. 9 JY"1. С. 15−18.

31. Меламед II. IL, Сигал И. Х. Вычислительное исследование линейной параметризации критериев в многокритериальном дискретном программировании. // Журнал вычислительной математики п математической физики. 1996. Т. 36 Л'210. С. 23−25.

32. Меламед И. IL, Сигал И. Х. Исследование линейной свертки критериев в многокритериальном дискретном программировании. // Журнал вычислительной математики и математической физики. 1995. Т. 35 т. С. 1260−1270.

33. Емеличев В. А., Перепелица В. А. Полные задачи многокритериальной дискретной оптимизации Сообщения АН ГССР 1988. Т. 131 № 3. С. 501−504.

34. Бондаренко В. А., Калацей A.A. Задача о коалиции //В сб. науч. тр.: Современные проблемы математики и информатики. Ярославль. 2001. С. 146−147.

35. Gavril F. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a cliordal graph. SIAMJ. Comput. JV"1. P. 180−187.

36. Краснов M.B. К вопросу о многокритериальной оптимизации //В сб. тезисов Второй областной научно-практической конференции студентов, аспирантов и молодых ученых вузов «Ярославский край. Наше общество в третьим тысячелетии». Ярославль. 2001. С. 7−9.