Название: Введение в прикладное дискретное программирование : модели и вычислительные алгоритмы Автор: Сигал И.Х. , Иванова А.П. Издательство: Физматлит Год: 2007 - 2-е изд., испр. и доп. Cтраниц: 304 Формат: pdf (ocr) / djvu Размер: 30 мб Язык: русский
В переработанном издании книги излагаются современные комбинаторные алгоритмы для решения задач дискретного программирования. Рассматриваются особенности этих задач и алгоритмы их решения. Основное внимание уделяется вычислительной реализации алгоритмов. Приводятся результаты экспериментального исследования алгоритмов для классических задач о ранце и о коммивояжере. Разработаны алгоритмы параллельных вычислений и изложены результаты вычислительных экспериментов для задачи о ранце. Приведены задачи для самостоятельной работы.
СОДЕРЖАНИЕ:
ПРЕДИСЛОВИЕ К ПЕРВОМУ ИЗДАНИЮ 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 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
Скачать Сигал И.Х. , Иванова А.П. - Введение в прикладное дискретное программирование : модели и вычислительные алгоритмы
|