Введение
1. Постановка задач и обзор используемых результатов 9
1.1. Постановка задач 9
1.2. Краткий обзор известных результатов 12
2. Анализ полного множества альтернатив 14
2.1. Общая теорема о полном множестве альтернатив 14
2.2. Анализ многокритериальной задачи о пути 16
3. Сложность в смысле Кука-Карпа многокритериальных задач 19
3.1. ЛтР-полнота многокритериальных задач на графах 20
3.2. Замечания о задачах о минимальном остовном дереве и о назначениях 38
3.3. Многокритериальная задача о кратчайших путях для всех пар узлов графа 42
3.4. Задача о рюкзаке 45
4. Анализ лексикографических многокритериальных задач 57
4.1. Метод линейной свертки для лексикографических задач. 57
4.2. Линейные разделяющие алгоритмы 59
4.3. Описание модификации для некоторых известных алгоритмов 04
Список литературы !... G9
