Дискретное программирование

  

Дискретное программирование, А. А. Корбут и Ю. Ю. Финкельштейн. Серия «Экономико-математическая библиотека».

Монография посвящена дискретному программированию (часто называемому также целочисленным и комбинаторным программированием). Задачи дискретного программирования, заключающиеся в нахождении условных экстремумов на конечных множествах (или на целочисленных решетках), являются источником интересных теоретических исследований. С другой стороны, в терминах дискретного программирования формализовано много важных прикладных задач оптимизации, связанных с наличием неделимых факторов, стандартов при проектировании, условий «логического» типа, фиксированных доплат и т. п.

Книга состоит из пяти частей (подразделенных на главы), в которых излагаются основные разделы дискретного программирования. I. Общая характеристика предмета, модели, прикладные задачи. II. Методы отсечения (метод Гомори и др.). III. Комбинаторные методы. IV. Приближенные методы. V. Некоторые теоретические вопросы.

Книга предназначена для математиков, экономистов, инженеров, специалистов в области управления и военного дела. Она может быть также полезна студентам и аспирантам соответствующих специальностей. Желательно, чтобы читатель владел основными понятиями математического программирования. Однако все необходимые сведения сообщаются в тексте.



Оглавление

ПРЕДИСЛОВИЕ РЕДАКТОРА
ЧАСТЬ 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. Теорема Гомори и Баумоля
email@scask.ru