Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы : учебное пособие для студентов

Description

Титульный лист Выходные данные Оглавление Предисловие к первому изданию Предисловие ко второму изданию РАЗДЕЛ I. ПРЕДМЕТ И МОДЕЛИ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ Глава 1. Постановка и особенности задач дискретного программирования 1.1. Постановка задачи, примеры 1.2. Особенности задач 1.3. Общие сведения о методах решения задач 1.3.1. Методы отсечения 1.3.2. Комбинаторные методы 1.3.3. Приближенные методы 1.4. Целочисленные многогранные множества 1.4.1. Теоремы о целочисленных многогранных множествах. Примеры 1.4.2. Целочисленность опорных планов транспортной задачи Глава 2. Модели дискретного программирования 2.1. Задачи транспортного типа 2.1.1. Задача о назначении (задача выбора) 2.1.2. Задача о коммивояжере 2.1.3. Транспортная задача с фиксированными доплатами 2.1.4. Распределительная задача (49) 2.2. Задача о ранце 2.2.1. Задача об одномерном ранце 2.2.2. Задача о многомерном ранце 2.2.3. Общие свойства задач о ранце 2.2.4. Алгоритм Данцига для линейной одномерной задачи о ранце 2.2.5. Геометрическая интерпретация правила Данцига 2.2.6. Алгоритмы последовательного назначения единиц для приближенного решения задачи об одномерном ранце 2.2.7. Алгоритмы приближенного решения задачи о многомерном ранце 2.2.8. Алгоритмы улучшения начального решения 2.2.9. Алгоритмы «генетического» типа 2.2.10. Комбинированные эвристические алгоритмы для задачи о ранце 2.2.11. Экспериментальные исследования системы комбинированных эвристических алгоритмов для приближенного решения задачи о ранце 2.3. Задачи теории графов 2.3.1. Задачи о покрытиях графов 2.3.2. Задача об изоморфизме графов 2.3.3. Задачи о раскрасках графов 2.4. Задача о покрытии конечного множества системой его подмножеств РАЗДЕЛ II. КОМБИНАТОРНЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ Глава 3. Метод ветвей и границ 3.1. Схема метода для общей задачи дискретного программирования 3.2. Метод Лэнд и Дойг для задачи частично целочисленного линейного программирования 3.3. Метод Лэнд и Дойг для задачи о ранце 3.3.1. Основной алгоритм 3.3.2. Модифицированный алгоритм 3.3.3. Замечания о трудоемкости алгоритма 3.3.4. Задача о построении всех близких к оптимуму решений и ее приложение 3.3.5. Примеры 3.4. Применение метода ветвей и границ для задачи о коммивояжере 3.4.1. Постановка задачи 3.4.2. Приведение матрицы расстояний 3.4.3. Ветвление 3.4.4. Общий шаг алгоритма 3.4.5. Пример 3.4.6. Пример решения симметричной задачи 3.4.7. Замечание о приведении матрицы расстояний 3.4.8. Применение задачи о назначении для вычисления оценки и ветвления 3.5. Применение метода ветвей и границ для симметричной задачи о коммивояжере 3.5.1. Определение 1-дерева 3.5.2. Ветвление 3.5.3. Пример 3.5.4. Некоторые рекомендации для практического решения задач 3.6. Некоторые вопросы вычислительной реализации алгоритмов с древовидной схемой поиска оптимального решения 3.6.1. Структура информации о дереве подзадач 3.6.2. Операции на дереве подзадач 3.6.3. Структура информации о подзадаче 3.7. Алгоритм ветвей и границ нахождения множества всех R-близких решений в общей задаче и некоторые его применения 3.7.1. Алгоритм нахождения множества всех R-близких решений 3.7.2. Аппроксимационно-комбинаторный метод решения задач дискретной оптимизации 3.8. Параллельная реализация метода ветвей и границ для решения задач дискретного программирования 3.8.1. Общие сведения о многопроцессорных вычислительных комплексах (МВК) 3.8.2. Общие характеристики реализации метода ветвей и границ в многопроцессорном вычислительном комплексе 3.8.3. Алгоритм «управляющий-рабочие» без перераспределения заданий 3.8.4. Алгоритм «управляющий-рабочие» с перераспределением заданий 3.8.5. Другие варианты параллельной реализации метода ветвей и границ 3.8.6. Некоторые особенности реализации метода ветвей и границ в распределенной среде Глава 4. Применение метода динамического программирования для решения некоторых аддитивных задач дискретного программирования 4.1. Задача о распределении ресурсов между проектами 4.1.1. Простой пример 4.1.2. Алгоритм динамического программирования Беллмана для решения задачи 4.1.3. Принцип оптимальности 4.2. Задача о ранце 4.2.1. Принцип оптимальности Беллмана 4.2.2. Алгоритм решения задачи 4.2.3. Примеры применения алгоритма для решения задач 4.3. Задача о минимизации суммы функций двух переменных 4.3.1. Постановка задачи и общая схема решения 4.3.2. Алгоритм анализа вариантов 4.3.3. Алгоритм «киевский веник» 4.3.4. Принцип оптимальности РАЗДЕЛ III. ПРИБЛИЖЕННЫЕ МЕТОДЫ И АЛГОРИТМЫ В ДИСКРЕТНОМ ПРОГРАММИРОВАНИИ Глава 5. Постановка задачи о поиске приближенного решения, некоторые общие вопросы и применение алгоритма ветвей и границ для нахождения приближенного решения 5.1. Постановка задачи 5.2. Общая характеристика алгоритмов приближенного решения и их классификация 5.3. Локальные и глобальные подходы к повышению эффективности алгоритмов решения задач дискретного программирования 5.3.1. Локальные подходы 5.3.2. Глобальные подходы. Переход к ε-оптимизации 5.4. ε-оптимальный алгоритм ветвей и границ для задачи о ранце 5.4.1. Постановка задачи и алгоритм 5.4.2. Оценка для числа ε-существенных переменных 5.4.3. Замечания о полиномиальной трудоемкости алгоритма 5.4.4. Примеры 5.5. Комбинированные алгоритмы ветвей и границ 5.5.1. Выбор множества для ветвления 5.5.2. Выбор способа ветвления 5.5.3. Выбор алгоритмов вычисления оценок 5.5.4. Выбор алгоритмов формирования приближенных решений в процессе ветвления 5.5.5. Изменение точности в процессе решения задачи 5.5.6. Правила отсева 5.5.7. Параметризация комбинированных алгоритмов 5.5.8. Выбор управляющих параметров комбинированных алгоритмов в зависимости от вычислительных ресурсов 5.5.9. Метод ветвей и границ и метод динамического программирования Глава 6. Алгоритмы гарантированного функционирования 6.1. Задача об одномерном ранце 6.1.1. Задача об одномерном целочисленном ранце 6.1.2. Задача об одномерном булевом ранце 6.2. Метрическая задача о коммивояжере на плоскости 6.2.1. Первый алгоритм 6.2.2. Второй алгоритм 6.3. Задачи о покрытиях графов 6.3.1. Задача о вершинном покрытии 6.3.2. Задача о реберном покрытии Глава 7. Локальная оптимизация, эвристические и комбинированные алгоритмы 7.1. Локальная оптимизация 7.1.1. Общая схема локальной оптимизации 7.1.2. Примеры определения окрестности 7.2. Эвристические алгоритмы 7.2.1. Задача о коммивояжере 7.2.2. Задачи теории графов 7.3. Комбинированные алгоритмы для задачи о коммивояжере 7.3.1. Построение начального решения 7.3.2. Улучшение начального решения 7.3.3. Вычисление нижней оценки для задачи о коммивояжере 7.3.4. Постановка задачи о формировании комбинированного алгоритма 7.4. Экспериментальное исследование системы комбинированных эвристических алгоритмов для приближенного решения задачи о коммивояжере 7.5. Общие сведения об алгоритмах муравьиных колоний Глава 8. Применение эвристических алгоритмов для решения некоторых прикладных задач 8.1. Распределение ресурсов на сетевых графиках 8.1.1. Общие сведения о сетевых графиках 8.1.2. Постановка задачи распределения ресурсов 8.1.3. Алгоритмы решения задачи 8.1.4. Вычисление значений приоритетов работ 8.1.5. Пример 8.1.6. Пример 8.2. Определение рейтинга объектов 8.2.1. Постановка задачи определения рейтинга объектов 8.2.2. Алгоритмы решения задачи 8.3. Определение оптимальной очередности обслуживания объектов с учетом замены оборудования 8.3.1. Постановка задачи 8.3.2. Алгоритм решения задачи РАЗДЕЛ IV. ЗАДАЧИ БОЛЬШОЙ РАЗМЕРНОСТИ Глава 9. Математические модели процесса решения и параметризация 9.1. Понятие о задачах большой размерности для общей задачи дискретного программирования 9.2. Математические модели и основные параметры 9.2.1. Задача 1 9.2.2. Задача 2 9.3. Условия реализуемости алгоритмов решения задач 9.3.1. Общие условия для обеих задач 9.3.2. Условия для задачи 2 9.4. Параметризация 9.4.1. Задачи, не имеющие большой размерности 9.4.2. Оценки параметров для задачи большой размерности 9.4.3. Оценки параметров для задачи (9.1.2) 9.4.4. Приложение для оценки параметров ε-оптимального алгоритма в задаче о ранце 9.5. Оценки мощностей разветвляемых подмножеств 9.6. О применении полученных результатов при решении задач 9.6.1. Общая схема определения параметра p_0(n) 9.6.2. Экспериментальные исследования зависимости параметра p_0(n) от размерности в задаче о коммивояжере Глава 10. Алгоритмы приближенного решения задачи о коммивояжере большой размерности 10.1. Постановка задачи и общие сведения об алгоритмах ее решения 10.1.1. Постановка задачи 10.1.2. Декомпозиционный подход 10.2. Декомпозиция 10.2.1. Постановка задачи разбиения 10.2.2. Задание начального разбиения 10.2.3. Построение начального разбиения 10.2.4. Улучшение начального разбиения 10.2.5. Корректирующие процедуры 10.2.6. Иерархические процедуры декомпозиции 10.2.7. Последовательная (древовидная) декомпозиция 10.2.8. Практическое решение задачи разбиения 10.3. Решение подзадач 10.3.1. Построение начальных решений 10.3.2. Улучшение начальных решений 10.3.3. Оценка точности приближенных решений 10.3.4. Диалоговые процедуры 10.4. Формирование приближенного решения задачи из решений подзадач 10.4.1. Построение начальной последовательности подмножеств, оценка трудоемкости 10.4.2. Улучшение последовательности подмножеств 10.4.3. Формирование решений 10.4.4. Алгоритм объединения решений подзадач и оценка его трудоемкости 10.5. Бикритериальная задача о коммивояжере 10.5.1. Постановка задачи 10.5.2. Оптимизация свертки критериев Задачи Список литературы Предметный указатель