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

• Автор: Краснов, Михаил Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Ярославль
• Количество страниц: 74 с. : ил

Содержание
1. Постановка задач и обзор используемых результатов
1.1. Постановка задач
1.2. Краткий обзор известных результатов
2. Анализ полного множества альтернатив
2.1. Общая теорема о полном множестве альтернатив
2.2. Анализ многокритериальной задачи о пути
3. Сложность в смысле Кука-Карпа многокритериальных задач
3.1. ЛгП-полнота многокритериальных задач на графах .
3.2. Замечания о задачах о минимальном остовном дереве
и о назначениях
3.3. Многокритериальная задача о кратчайших путях для всех пар узлов графа
3.4. Задача о рюкзаке
4. Анализ лексикографических многокритериальных задач
4.1. Метод линейной свертки для лексикографических задач.
4.2. Линейные разделяющие алгоритмы
4.3. Описание модификации для некоторых известных алгоритмов
Список литературы

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

количество городов п (заметим, что для задачи коммивояжера эта величина составляет (п — 1)!/2, а для задачи о минимальном остов-ном дереве - ?г"~2). II если для второй задачи известен эффективный ’’жадный” алгоритм, дающий точное решение и позволяющий с помощью современных ЭВМ строить сети для тысяч городов, то для задачи коммивояжера алгоритма с подобными качествами до сих пор не найдено, несмотря на значительные усилия, приложенные в этом направлении. Более того, существуют достаточно веские причины, лишающие надежды отыскать такой алгоритм в ближайшем будущем.
Перейдем к общей постановке задачи дискретной оптимизации в обычной, однокрнтериальной постановке. Пусть задано конечное множество А' н функция /, определенная на этом множестве и принимающая действительные значения. Требуется найти такой элемент х* £ А', для которого /(х*) < /(х) для любого элемента х £ А”.
Как уже отмечалось, любая задача этого класса, с одной стороны, допускает решение переборным способом в силу конечности множества допустимых решений, но в то же время таит в себе возможность ’’комбинаторного взрыва”. Это связано с тем, что количество вариантов может расти экспоненциально в зависимости от размерности задачи, отчего необходимые для полного перебора затраты машинного времени н памяти делают ее решение практически невозможным, даже на самых современных ЭВМ. Поэтому ’’хорошим”, или эффективным, алгоритмом принято считать полиномиальный алгоритм. то есть такой, временная трудоемкость которого оценивается сверху полиномом от длины входа. Алгоритмы, трудоемкость которых не допускает подобной оценки, традиционно считаются неэффективными и представляют собой варианты полного перебора. В свою очередь, задачи, для которых неизвестны полиномиальные алгоритмы, характеризуются как труднорешаемые.
Оказалось, что число задач комбинаторной оптимизации, допускающих эффективное решение, не так велико, соответственно ограничен п список полиномиальных алгоритмов. Это алгоритмы быстрой сортировки, венгерский метод для задачи о назначениях, ’’жадный” алгоритм для задачи о минимальном остовном дереве, алгоритм для

Щ t’3 t’6 V-J
^4s—2 ^4s—
t'O t’1 V l>5 tîg U4i_3 B4s U4s+i

Тогда в графе G = (V, E) рассмотрим независимое множество Vі С V состоящее из следующих вершин:
а) если а,- Є il/і, то включим вершину н4,_з в множество V
б) если а,- Є ММ, ТО И4;_2 включим в множество F'.
Поскольку элемент а і входит или в М или в ММі, то вершины и4,_з и г4;_2 не могут одновременно входить в множество Vі. Причем выполняются условия
E ci(ui) >Ci и E с2(vi) > с2.
v,€V' t/jCK'
Предположим теперь, что существует независимое множество V' С V графа G для которого выполняются условия (18). Легко заметить, что для данного графа вершины и4;_з и и4;_2 не могут одновременно принадлежать множеству Vі, так как существует ребро (е4,-_з, с4,;_2) Є Е. Из выше сказанного, а также из условий: >
Е Ыч) > Сь Е с2(v,-) > С2, Ci = С2 = ^ Е
и.бГ' tijëV" 1 >'=
следует, что для задачи Разбиение выполняется условие
Е а>= Е “<•
ОіЄМі а*Є-МЛ/і
Теорема доказана.
Замечание 3.2. Утверждение Теоремы 3.3 остается верным и при А: > 2, где к количество критериев или параметров.
В этом легко убедиться, поскольку двухкритериальную задачу о независимом множестве можно за полиномиальное время свести к задаче с большим количеством критериев.