Дискретное программирование
ОглавлениеПРЕДИСЛОВИЕ РЕДАКТОРАЧАСТЬ I. ПРЕДМЕТ И МОДЕЛИ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ § 1. Предмет дискретного программирования § 2. Классификация математических моделей § 3. Классификация прикладных задач § 4. Классификация численных методов ГЛАВА 2. МАТЕМАТИЧЕСКИЕ МОДЕЛИ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ § 1. Транспортная задача § 2. Задачи с неделимостями § 3. Задачи комбинаторного типа § 4. Задачи на невыпуклых и несвязных областях § 5. Задачи с разрывной целевой функцией § 6. Некоторые многоэкстремальные задачи ГЛАВА 3. ПРИКЛАДНЫЕ ЗАДАЧИ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ § 1. Задачи планирования перевозок § 2. Задачи размещения и специализации § 3. Задачи логического проектирования § 4. Задачи теории расписаний § 5. Другие прикладные задачи ЧАСТЬ II. МЕТОД ОТСЕЧЕНИЯ ГЛАВА 4. НЕКОТОРЫЕ ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ § 1. Основные понятия линейного программирования § 2. Выпуклые множества § 3. Выпуклые многогранные множества и линейное программирование § 4. Лексикография § 5. Симплексные таблицы, планы и псевдопланы § 6. Метод последовательного улучшения плана (прямой симплекс-метод) § 7. Метод последовательного уточнения оценок (двойственный симплекс-метод) § 8. Задача целочисленного линейного программирования ГЛАВА 5. ИДЕЯ МЕТОДА ОТСЕЧЕНИЯ. ПЕРВЫЙ АЛГОРИТМ ГОМОРИ § 1. Идея метода отсечения § 2. Первый алгоритм Гомори § 3. Доказательство конечности первого алгоритма Гомори ГЛАВА 6. ВТОРОЙ АЛГОРИТМ ГОМОРИ И ДРУГИЕ ОБОБЩЕНИЯ ПЕРВОГО АЛГОРИТМА § 2. Второй алгоритм Гомори § 3. Алгоритм Дальтона и Ллевелина § 4. В-алгоритм для решения задач целочисленного линейного программирования с булевыми переменными § 5. Алгоритм Данцига ГЛАВА 7. ТРЕТИЙ АЛГОРИТМ ГОМОРИ И ЕГО МОДИФИКАЦИЯ § 2. Построение целочисленного правильного отсечения. Третий алгоритм Гомори § 3. Доказательство конечности третьего алгоритма Гомори § 4. Модификация третьего алгоритма Гомори ГЛАВА 8. О РЕШЕНИИ ЦЕЛОЧИСЛЕННЫХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПРОИЗВОЛЬНЫМИ ДОПОЛНИТЕЛЬНЫМИ УСЛОВИЯМИ § 2. Построение отсечений для выпуклых и некоторых невыпуклых задач § 3. Применение третьего алгоритма Гомори ГЛАВА 9. ОБ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ МЕТОДА ОТСЕЧЕНИЯ § 2. Результаты вычислительных экспериментов § 3. Некоторые выводы ЧАСТЬ III. КОМБИНАТОРНЫЕ МЕТОДЫ ГЛАВА 10. МЕТОД ВЕТВЕЙ И ГРАНИЦ § 2. Метод Лэнд и Дойг § 3. Алгоритм Литтла, Мурти, Суини и Кэрел для задачи коммивояжера ГЛАВА 11. АДДИТИВНЫЙ АЛГОРИТМ § 2. Общая схема метода § 3. Описание алгоритма § 4. Пример и заключительные замечания ГЛАВА 12. ПРИМЕНЕНИЕ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ § 1. Обобщенная задача о ранце § 2. Задача о коммивояжере § 3. Задача теории расписаний для случая двух машин (алгоритм Джонсона) ГЛАВА 13. ЛОКАЛЬНЫЙ ПОДХОД к ЗАДАЧАМ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ § 2. Алгоритм ГЛАВА 14. НЕКОТОРЫЕ ДРУГИЕ МЕТОДЫ § 1. Метод Фора и Мальгранжа § 2. Метод последовательных расчетов ЧАСТЬ IV. ПРИБЛИЖЕННЫЕ МЕТОДЫ ГЛАВА 15. МЕТОДЫ СЛУЧАЙНОГО ПОИСКА § 2. Случайный поиск с локальной оптимизацией ГЛАВА 16. ДЕТЕРМИНИРОВАННЫЕ МЕТОДЫ § 1. Приближенные методы для транспортной задачи с фиксированными доплатами § 2. Некоторые обобщения ЧАСТЬ V. НЕКОТОРЫЕ ТЕОРЕТИЧЕСКИЕ ВОПРОСЫ ГЛАВА 17. ЦЕЛОЧИСЛЕННЫЕ МНОГОГРАННЫЕ МНОЖЕСТВА § 2. Задачи транспортного типа ГЛАВА 18. ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ И ДВОЙСТВЕННЫЕ ОЦЕНКИ § 2. Теорема Гомори и Баумоля |
