О сложности некоторых многокритериальных дискретных задач тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

КРАСНОВ МИХАИЛ ВЛАДИМИРОВИЧ

I

!

1 О СЛОЖНОСТИ НЕКОТОРЫХ

МНОГОКРИТЕРИАЛЬНЫХ ДИСКРЕТНЫХ

ЗАДАЧ

СПЕЦИАЛЬНОСТЬ 01.01.09 - ДИСКРЕТНАЯ МАТЕМАТИКА И МАТЕМАТИЧЕСКАЯ КИБЕРНЕТИКА

Автореферат

' ДИССЕРТАЦИИ НА СОИСКАНИЕ УЧЕНОЙ СТЕПЕНИ

КАНДИДАТА ФИЗИКО-МАТЕМАТИЧЕСКИХ НАУК

I

Ярославль - 2003

Работа выполнена в Ярославском государственном университете им. П.Г.Демидова

Научный руководитель

Официальные оппоненты:

доктор физико-математических наук, профессор Бондаренко Владимир Александрович

доктор физико-математических наук, профессор Дольников Владимир Леонидович,

кандидат физико-математических наук, доцент Корнилов Петр Анатольевич.

Ведущая организация

Институт проблем управления РАН

Защита состоится 2003 года в _^^часов на

заседании диссертационного совета_КР 212.002.18 при

Ярославском государственном университете им. П.Г.Демидова по адресу: 150000, г. Ярославль, ул. Советская, д.14.

С диссертацией можно ознакомиться в библиотеке Ярославского государственного университета им. П.Г.Демидова по адресу: г. Ярославль, ул. Полушкина роща, д. 1.

Автореферат разослан 2003 года.

Ученый секретарь _

диссертационного совета Яблокова С.И.

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

Актуальность проблемы.

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

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

« 1 1 ной сложности задач ' .

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

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

'A.A. Кук Сложность процедур вывода теорем.// Сб.: Кибернетический сборник, новая серия. М.: Мир. 1975. Вып. 12. С. 5-15.

2 P.M. Карп Сводимость комбинаторных проблем. // Сб.: Кибернетический

сборник, новая серия. М.: Мир. 1975. Вып. 12. С. 16-38,

(1)

X. Здесь, так же как и в случае однокритериалыюй задачи дискретной оптимизации, решение можно искать переборным способом, но это 1 таит в себе опасность " комбинаторного взрыва". )

Отметим, что разные критерии в многокритериальной задаче могут í

нести различную смысловую нагрузку. Например, в системах автоматизированного проектирования электронной техники возникают мно- 1 гокритериальные задачи на графах, в которых остовное дерево (связующая сеть) может оцениваться такими критериями, как вес, длина ' и т.п.. При этом по мере необходимости эти критерии входят в со- 1 став векторной функции в разнообразных комбинациях, порождая раз- ^ личные варианты задач об остовных деревьях. Общим у этих задач является лишь множество допустимых решений X, каждый элемент х которого является остовным деревом данного графа. ^

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

Напишем и < ь, где и = (щ,..., щ), V = («х,..., V/,), если щ < г,-, г = 1,..., п. Такое отношение определяет в Як полуупорядоченность.

Лексикографическое неравенство между элементами из Як обозначим и <1ех V] оно означает, что для некоторого г, 0 < г < к, выполняются условия и\ = VI,..., и,- = г>,-, и,+х < г),-+1.

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

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

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

Учитывая сказанное о типах упорядоченности в Як, уточним фор- I

мулировки задач, которые рассматриваются в диссертации.

Задача 1. Требуется найти подмножество X* С X всех таких элементов хдля каждого из которых значение /(х*) минимально в множестве

У = /(X) = {/(х) :х€Х}СЛк.

Задача 2. Для заданного у* 6 Як выяснить, существует ли х* £ X, для которого f{x*) < у*.

Задача 3. Требуется найти х* £ X, для которого значение f(x*) лексикографически минимально в Y.

Широкий класс частных случаев задач многокритериальной оптимизации образуют задачи на графах. При этом роль множества X выполняет совокупность подграфов определенного вида некоторого графа G = (V, Е), на множестве Е ребер которого задана векторная функция

с : Е —t Rk,

а значение целевой функции / определяется формулой

/(*) = J2 с(е) (2)

ее£х

или

/(*) = £ с(е) (з)

«6V*

(здесь через х обозначается подграф — элемент множества X, включение е £ Ех означает, что е £ ß является ребром этого подграфа; включение v £ Vx означает, что v £ V является вершиной этого подграфа).

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

• Получение множества решений по Парето с помощью детального учета конструкции множества допустимых решений X (Бонда-ренко В.А., Mustard J., Pokrovski A.V., Guerriero F., Musmanno R., Djordje D.)

• Возможность получения оптимального решения путем перехода от многокритериальной задачи к однокритериальной с'аддитив-ным целевым критерием, рассматриваемая в работах Кравцова М.К., Янушкевича O.A., Емеличева В.А., Меламеда И.И., Сигала И.Х..

• Получение решения для лексикографической многокритериальной задачи. Это направление исследований представлено работами

Емеличева В.А., Кравцова М.К., Янушкевича O.A., Гирлиха Э., Червака Ю.Ю., Червака О.Ю..

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

Цель работы.

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

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

Целью Главы 3 является исследование многокритериальных задач с равноценными критериями, а именно:

1. Анализ сложности в смысле теории Кука-Карпа классических задач комбинаторной оптимизации в многокритериальном случаях.

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

Глава 4 посвящена построению полиномиального алгоритма для многокритериальной лексикографической задачи, если в однокритериальном случае для нее существует полиномиальный алгоритм.

Методы исследования.

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

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

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

Научная новизна.

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

1 териального лексикографического случая.

2. Проведены исследования многокритериальных задач с равноцен-

I ными критериями. В частности, для двухкритериальной задачи

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

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

4. Исследован вопрос о том, что оказывается решающим в том факте, что многие известные полиномиально разрешимые однокритери-

' альные задачи дискретной оптимизации становятся NP-пoлными

уже при введении второго критерия.

»

Практическая ценность работы.

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

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

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

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

•3. Построен и обоснован алгоритм с псевдополиномиальной временной сложностью для модифицированной задачи о рюкзаке.

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

ными путями между всеми парами вершин графа О — (V, Е).

Апробация работы. Основные результаты работы докладывались и обсуждались на научных конференциях:

1) "Актуальные проблемы естественных и гуманитарных наук на пороге 21 века. Юбилейная научная конференция, посвященная 30-летию ЯрГУ", (Ярославль, 2000 год);

2) Международная научная конференция студентов, аспирантов и молодых ученых "Молодая наука - 21 веку", (Иваново, 2001 год);

3) Вторая областная научно-практическая конференция студентов, аспирантов и молодых ученых вузов "Ярославский край. Наше общество в третьем тысячелетии", (Ярославль, 2001 год).

1

Публикации. По результатам исследований было опубликовано 8 печатных работ: 5 статей и 3 тезиса докладов. Основные результаты вошли в отчеты по грантам РФФИ за 2001 и 2002 гг. '

Структура и объем работы. Диссертация состоит из введения, четырех глав и списка литературы, содержащего 54 наименования. Текст диссертации включает в себя 12 иллюстрирующих рисунков. Общий объем диссертации - 74 страницы.

Краткое содержание работы

Во Введении дается общая характеристика работы и обсуждается актуальность задач.

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

Назовем элемент х* 6 X, для которого /(ж*) мйнималей в /(X) па-ретовским минимумом, или минимумом по Парето, функции / на множестве X. Множество X*, состоящее из всех паретовских минимумов, будем называть паретовским множеством, или множеством минимальных по Парето элементов. Подмножество Х° С X* — полным множеством альтернатив, если его мощность минимальна и выполняется равенство: /(Х°) = /(X*).

Во второй главе изучается вопрос о мощности множества Парето-минимальных элементов, рассматривается Задача 1. Полное множество альтернатив является обобщением понятия классического оптимума (минимума): найти полное множество альтернатив в случае к = 1— значит найти какой-либо оптимум (минимум) рассматриваемой одно-критериальной задачи.

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

Предположим, что рассматривается произвольное конечное множество Е, на котором определена двумерная функция с : Е —> /?2. Обозначим через X множество всех непустых его подмножеств, = 2№ — 1, и положим

/(*) = £с(е),

ебг

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

1. Теорема 2.1. Для любого конечного множества Е существует такая функция с : Е В,2, для которой множество {/(х) : х € X} состоит из попарно несравнимых элементов, или, иначе, Х° = X.

2. Теорема 2.2. Пусть Хт — множество всех подмножеств Е, содержащих по т элементов, 1 < т < п = |2?|. Тогда существует

такая положительная функция с : Е Я,2, для которой множество {/(ж) : х 6 Хт} состоит из попарно несравнимых элементов.

Частными случаями сформулированной теоремы являются результаты, полученные Емеличевым и Перепелицей 4 относительно мощности полного множества альтернатив двухкритериальной задачи об остове графа. Действительно, для многокритериальной задачи об остове в графе положим т = |У| —1, а множество всех остовных деревьев является подмножеством множества Хт, следовательно, учитывая утверждение Теоремы 2.2., существует такая положительная функция с : Е —» Я2, что веса всех остовных деревьев будут попарно несравнимы. Отметим, что приведенные выше утверждения остаются верными и при к > 2.

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

Теорема 2.3. Пусть С? = (V, Е) — полный граф, на множестве Е ребер которого задана двумерная функция, удовлетворяющая условию с(е) > 0, е £ Е и пусть |1/| > 4. Тогда для любых двух вершин и, V £ V найдутся два простых пути х, у, соединяющих и и V, для которых значения f{x) и /(у), определяемые формулой (2), сравнимы.

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

Утверждение. Для любого пх > 2 существует такая неотрицательная функция с : Е Я2, определенная на ребрах полного неориентированного графа б = (V, Е), где |У| = п\, для которой существует не меньше чем («1 — 2)! попарно несравнимых путей между фиксированными вершинами.

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

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

4ЕмеличевВ.А., Перепелица В. А. Многокритериальные задачи об остовах графа.

// Докл. РАН (1998) №298 с. 544-547.

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

представления о труднорешаемости задач.

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

Двухкритпериальная задача о назначениях. Заданы пара чисел С\, С2 и полный двудольный граф в = (V, (У, Е) с п вершинами в каждой доле. На множестве Е = : 1 < г < п, 1 < ] < п} его ребер определена двухмерная функция (^(е^), С2(е,;)). Требуется выяснить, существует ли совершенное паросочстание £), для которого

£ С1(е,,) <Сг и £ с2{е,з) < С2.

Теорема 3.1. Двухкритериальная задача о назначениях является ИР-полной.

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

■МНОЖб*

ство.

Задача. Заданы натуральное число Б < 3, вектор С Е Як и полный граф С? = (V, Е), для каждого ребра е 6 Е определен вес с(е) = (с! (е),..., с^(е)) > 0. Существует ли в графе С = {У,Е) остов Т = (V, £{), в котором нет простого пути, с числом ребер, превосходящим Оу и выполняется условие:

£ с(е) < С.

еев,

Теорема 3.2. Задача Остов ограниченного диаметра является ИР— полной уже при к = 2.

Задача. Дан вектор С & Як и граф С = (V, Е), не имеющий вершин степени выше 2, и для каждого элемента множества £ V определен вес с(и;) = (сх (г>г),..., сЦи;)). Существует ли подмножество V' С V, такое, что V' является независимым множеством и для него выполняется условие

£ СхМ > С.

Теорема 3.3. Двухкритериальная задача о независимом множестве

для графа G — (V, Е), не имеющего вершин степени выше 2, является -/VP-ПОЛНОЙ.

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

Задача. Дан вектор С G Rk и двудольный граф G — (V, U, Е), каждому элементу множестваQ — V\JU присвоен вес c(q) = (ci{q),..., Ck(q)) Существует ли в графе G полный двудольный подграф S = (Vi, U\, Ei), для которого выполнено условие:

£ c(q) > С, яея 1

Теорема 3-4■ Задача о коалиции является NP—полной уже при к =

2.

Утверждения Теорем 3.1.— 3.4. дают основания говорить об отсутствии полиномиальных алгоритмов для сформулированных задач (при предположении, что Р ф NР). Поэтому особый интерес для NP-полных задач представляет построение алгоритмов, имеющих псевдополиномиальную временную трудоемкость. Время работы псевдополиномиальных алгоритмов ограничено полиномом от суммы абсолютных величин числовых параметров, определяющих индивидуальную задачу. (Здесь, как обычно в подобных вопросах, числовые параметры предполагаются целыми.) Как правило, псевдополиномиальные алгортмы оказываются достаточно эффективными в реальных ситуациях.

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

Для задачи Остов ограниченного диаметра в случае диаметра, не превосходящего трех, предложен алгоритм с псевдополиномиальной временной сложностью. Если же рассматривать задачу с диаметром, равным двум, то тогда задача решается за полиномиальное время.

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

6Bondarenko V.A., Mustard J., Pokrovski A.V. Combinatjrial problem connected with Stabilization of System with Quasichaotic Behaviour. // Deakin University. Geelong. AU. 1997. P. 1-23.

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

Задача А. Заданы множество Е = {ei,...e„}, на котором определена к—мерная функция с = с(е,) и вектор С £ Rk. Требуется выяснить, существует ли непустое подмножество Ai С Е, для которого

выполняется следующее условие:

£ с(е<) <

е.6 Ai

Задача В. Заданы множество Е = {ei,...e„}, на котором определена Аг—мерная функция с = с(е,), вектор С £ Rk и натуральное т. Требуется выяснить, существует ли подмножество АСЕ, для которого выполняются следующие условия:

|А| = т, с(е,) < С.

В случае Аг = 1 рассматриваемые задачи являются полиномиально разрешимыми с помощью тривиальных алгоритмов. Однако при переходе к случаю к > 2 множество допустимых решений остается по-прежнему простым.

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

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

Многокритериальные лексикографические задачи чаще всего решаются методом линейной свертки критериев в виде

к

Fa(*) = £A¿/{(*), гДе (Ab..,Afc) >0.

Если множество значений векторного критерия конечно, то существует функционал

F(*) = ¿ А,•/,(*),

1=1

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

к

Аг= П М,, г= 1,...,к- 1,.

¿=г+1

где М; натуральные числа, удовлетворяющие неравенствам:

М1 > тах{/1(х) : х £ X} - тг'п{/((а:) : х е X}, / = 1.....А:.

На практике выбор М; и далее Аг осуществляется на основе простых оценок.

Отметим, что редукция к однокритериальному варианту многокри- '

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

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

Широкий класс алгоритмов однокритериальной оптимизации образуют те из них, которые используют линейные сравнения для решения задачи. Такие алгоритмы принято называть линейными разделяющими алгоритмами. Заметим, что линейными разделяющими алгоритмами являются, в частности, алгоритм Мура-Дейкстры, решающий задачу о кратчайшем пути, жадный алгоритм для задачи о минимальном остов-ном дереве и т.д.. '

Опишем модификацию линейного разделяющего алгоритма для лексикографической Задачи 3. Структурно модифицированный алгоритм представляет бинарное дерево, совпадающее с тем, которое фигури- <

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

Пусть / = (с1,..., с^ набор т-мерных векторов, определяющих к-мерную целевую функцию

/ = /(*) = ((сьх),...,(ск,а;))

индивидуальной лексикографической задачи. Последовательно, начиная с корня, осуществляется применение функционалов, соответствующих вершинам линейного разделяющего алгоритма, к / и лексикографическое сравнение результата с нулевым вектором. В зависимости от этого происходит переход к очередной вершине. Работа алгоритма заканчивается после перехода в висячую вершину; соответствующий этой • вершине элемент гбХ объявляется решением индивидуальной лекси-

кографической задачи. Уточним характер вычислений на отдельном шаге алгоритма.

^ Пусть и/ - функционал, соответствующий 1-ой вершине линейно раз-

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

Теорема 4-2. Если линейный разделяющий алгоритм корректно решает Задачу 3 при к = 1, то описанная модификация корректно решает эту задачу при любом А > 1.

Список публикаций по теме диссертации.

1) Краснов М.В. ИР-полнота многокритериальной задачи о назначениях. // Сб.: Современные проблемы математики и информатики. Ярославль. 1997. С. 63-67.

2) Бондаренко В.А., Краснов М.В. К вопросу о многокритериальной оптимизации. //В сб.: "Актуальные проблемы естественных и гуманитарных наук на пороге 21 века. Математика. Информатика и вычислительная техника. Сборник тезисов юбилейной научной конференции, посвященной 30-летию ЯрГУ", Ярославль, ЯрГУ, 2000. С. 33-35

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

4) Краснов М.В. Многокритериальная задача о кратчайших путях для всех пар узлов графа. // Сб.научн.тр. "Современные проблемы математики и информатики", вып.З, Ярославль, ЯрГУ, 2000. С. 62-66.

5) Бондаренко В.А., Краснов М.В. Сложность многокритериальных задач на графах. //В сб.научн.тр. " Математика в Ярославском университете. Сборник обзорных статей. К 25-летию математического факультета.", Ярославль, ЯрГУ, 2001. С. 35-45.

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

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

8) Груздев О.И., Краснов М.В. О сложности одной многокритериальной задачи. // Модел. и анализ информ. систем. Ярославль, ЯрГУ, 2002. Т. 9 №1. С. 15-18.

Лицензия ПД 00661. Формат 60x84 1/16. Печ. л.! .Заказ 1074. Тираж 100. Отпечатано в типографии Ярославского государственного технического университета Ярославль, ул. Советская, 14а. 30-56-63.

«

i

!

i

4

i

I

I

I

!

i

t J

I

i i

i 1

Q-oo? ~f\

№11414

1. Постановка задач и обзор используемых результатов

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

1.2. Краткий обзор известных результатов

2. Анализ полного множества альтернатив

2.1. Общая теорема о полном множестве альтернатив

2.2. Анализ многокритериальной задачи о пути.

3. Сложность в смысле Кука-Карпа многокритериальных задач

3.1. ЛтР-полнота многокритериальных задач на графах

3.2. Замечания о задачах о минимальном остовном дереве и о назначениях.

3.3. Многокритериальная задача о кратчайших путях для всех пар узлов графа.

3.4. Задача о рюкзаке.

4. Анализ лексикографических многокритериальных задач

4.1. Метод линейной свертки для лексикографических задач.

4.2. Линейные разделяющие алгоритмы.V

4.3. Описание модификации для некоторых известных алгоритмов.

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