ПРЕДИСЛОВИЕ К ПЕРВОМУ ИЗДАНИЮ 9
ПРЕДИСЛОВИЕ КО ВТОРОМУ ИЗДАНИЮ 15
РАЗДЕЛ I. ПРЕДМЕТ И МОДЕЛИ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ 19
Глава 1. Постановка и особенности задач дискретного программирования 21
1.1. Постановка задачи, примеры 21
1.2. Особенности задач 25
1.3. Общие сведения о методах решения задач 27
1.4. Целочисленные многогранные множества 31
Глава 2. Модели дискретного программирования 37
2.1. Задачи транспортного типа 37
2.2. Задача о ранце 50
2.3. Задачи теории графов 73
2.4. Задача о покрытии конечного множества системой его подмножеств 81
РАЗДЕЛ II. КОМБИНАТОРНЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ 85
Глава 3. Метод ветвей и границ 87
3.1. Схема метода для общей задачи дискретного программирования 87
3.2. Метод Лэнд и Дойг для задачи частично целочисленного линейного программирования 90
3.3. Метод Лэнд и Дойг для задачи о ранце 92
3.4. Применение метода ветвей и границ для задачи о коммивояжере 111
3.5. Применение метода ветвей и границ для симметричной задачи о коммивояжере 122
3.6. Некоторые вопросы вычислительной реализации алгоритмов с древовидной схемой поиска оптимального решения 129
3.7. Алгоритм ветвей и границ нахождения множества всех R-близких решений в общей задаче и некоторые его применения 134
3.8. Параллельная реализация метода ветвей и границ для решения задач дискретного программирования 137
Глава 4. Применение метода динамического программирования для решения некоторых аддитивных задач дискретного программирования 146
4.1. Задача о распределении ресурсов между проектами 146
4.2. Задача о ранце 152
4.3. Задача о минимизации суммы функций двух переменных 159
РАЗДЕЛ III. ПРИБЛИЖЕННЫЕ МЕТОДЫ И АЛГОРИТМЫ В ДИСКРЕТНОМ ПРОГРАММИРОВАНИИ 165
Глава 5. Постановка задачи о поиске приближенного решения, некоторые общие вопросы и применение алгоритма ветвей и границ для нахождения приближенного решения 167
5.1. Постановка задачи 167
5.2. Общая характеристика алгоритмов приближенного решения и их классификация 169
5.3. Локальные и глобальные подходы к повышению эффективности алгоритмов решения задач дискретного программирования 170
5.4. ?-оптимальный алгоритм ветвей и границ для задачи о ранце 174
5.5. Комбинированные алгоритмы ветвей и границ 181
Глава 6. Алгоритмы гарантированного функционирования 188
6.1. Задача об одномерном ранце 188
6.2. Метрическая задача о коммивояжере на плоскости 192
6.3. Задачи о покрытиях графов 196
Глава 7. Локальная оптимизация, эвристические и комбинированные алгоритмы 199
7.1. Локальная оптимизация 199
7.2. Эвристические алгоритмы 201
7.3. Комбинированные алгоритмы для задачи о коммивояжере 215
7.4. Экспериментальное исследование системы комбинированных эвристических алгоритмов для приближенного решения задачи о коммивояжере 216
7.5. Общие сведения об алгоритмах муравьиных колоний 219
Глава 8. Применение эвристических алгоритмов для решения некоторых прикладных задач 221
8.1. Распределение ресурсов на сетевых графиках 221
8.2. Определение рейтинга объектов 231
8.3. Определение оптимальной очередности обслуживания объектов с учетом замены оборудования 236
РАЗДЕЛ IV. ЗАДАЧИ БОЛЬШОЙ РАЗМЕРНОСТИ 239
Глава 9. Математические модели процесса решения и параметризация 241
9.1. Понятие о задачах большой размерности для общей задачи дискретного программирования 241
9.2. Математические модели и основные параметры 244
9.3. Условия реализуемости алгоритмов решения задач 250
9.4. Параметризация 252
9.5. Оценки мощностей разветвляемых подмножеств 260
9.6. О применении полученных результатов при решении задач 262
Глава 10. Алгоритмы приближенного решения задачи о коммивояжере большой размерности 266
10.1. Постановка задачи и общие сведения об алгоритмах ее решения 266
10.2. Декомпозиция 267
10.3. Решение подзадач 277
10.4. Формирование приближенного решения задачи из решений подзадач 280
10.5. Бикритериальная задача о коммивояжере 284
ЗАДАЧИ 288
СПИСОК ЛИТЕРАТУРЫ 290
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ