Введение
Глава 1. Классическая задача о ранце в однокритериальной и многокритериальной постановках. алгоритмы решения 10
1.1. Классическая задача о ранце и алгоритмы поиска точного решения 10
1.2. Многомерная задача о ранце 26
1.3. Алгоритмы синтеза Парето-оптимальных решений для многокритериальной задачи о ранце на основе принципа динамического программирования 36
1.4. Синтез полной совокупности эффективных оценок многокритериальной задачи о ранце методом ветвей и границ 43
Глава 2. Синтез представительных совокупностей эффективных оценок для многокритериальной задачи о ранце 53
2.1. Концепция оператора, строящего представительную совокупность. Понятие консервативного оператора 54
2.2. Алгоритм синтеза совокупностей эффективных оценок, удовлетворяющих пороговым ограничениям 56
2.3. Синтез -разреженных совокупностей эффективных оценок 57
2.4. Алгоритмы построения совокупностей эффективных оценок получаемых применениями типовых схем компромисса при варьируемых параметрах этих схем 58
2.4.1. Метод последовательных уступок 58
2.4.2. Линейная свертка критериев 59
2.4.3. Метод главного критерия 61
2.4.4. Метод идеальной точки 62
2.5. Результаты вычислительных экспериментов 64
Глава 3. Подходы к ускорению счета при поиске решений многокритериальной задачи о ранце 69
3.1. Эффективные оценки. Синтез совокупностей - эффективных оценок методом ветвей и границ 69
3.2. Применение эволюционно-генетических алгоритмов для получения эвристических решений 72
3.3. Комбинированные алгоритмы решения задач о ранце 81
3.4. Некоторые вопросы эффективности программной реализации сложных вычислительных алгоритмов 85
Глава 4. Некоторые модификации задачи о ранце и методы их решения 89
4.1. Задача о ранце с аддитивным и точечным критериями 89
4.1.1. Математическая постановка задачи и алгоритмы ее точного решения.. 89
4.1.2. Эволюционно-генетический алгоритм решения задачи 94
4.2. Задачи с несколькими ранцами 97
4.2.1. Математические постановки задач с несколькими ранцами и алгоритмы их точного решения 97
4.3.2. Эволюционно-генетические алгоритмы решения задач 105
Глава 5. Об одной задаче выбора ограниченного представительного подмножества объектов 108
5.1. Математическая модель задачи и ее интерпретация. Алгоритм поиска точного решения 108
5.2. Эвристические алгоритмы поиска решения 111
Заключение 118
Литература 120
Приложение
