Читать онлайн «Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы»

УДК 519. 8 ББК 22. 18 С 34 Сигал И. Х. , Иванова А. П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособие. — М. : ФИЗМАТЛИТ, 2002. — 240 с. — ISBN 5-9221-0189-7. Излагаются современные комбинаторные алгоритмы для решения за- задач дискретной оптимизации с применением компьютерных средств. Рас- Рассматриваются: особенности задач дискретной оптимизации и их общие свой- свойства; алгоритмы гарантированного функционирования; алгоритмы типа «greedy»; комбинированные алгоритмы различных типов для приближенно- приближенного и точного решения задач; задачи большой размерности (параметризация и реализация). Основное внимание уделяется вычислительной реализации алгоритмов. Приводятся результаты вычислительного исследования алго- алгоритмов для классических задач дискретной оптимизации — задачи о ранце и задачи о коммивояжере. Приведено много примеров для самостоятельной работы. Для студентов, обучающихся по специальности «Прикладная матема- математика» и близких к ней, а также для научных сотрудников, аспирантов и специалистов, связанных с решением задач дискретной оптимизации. Табл. 20. Ил. 57. Библиогр. 45 назв. Рецензенты: доктор физико-математических наук, профессор, академик РАЕН Шкурба В. В. (Московский государственный университет управления); доктор технических наук, профессор, академик РАЕН Бурков В. Я. (Институт проблем управления РАН). © ФИЗМАТЛИТ, 2002 ISBN 5-9221-0189-7 © И. Х. Сигал, А. П. Иванова, 2002 Оглавление ПРЕДИСЛОВИЕ РАЗДЕЛ I ПРЕДМЕТ И МОДЕЛИ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ Глава 1. Постановка и особенности задач дискретного программирования 17 1. 1. Постановка задачи, примеры 17 1. 2. Особенности задач 20 1. 3. Общие сведения о методах решения задач 22 1. 3. 1. Методы отсечения B2). 1. 3. 2. Комбинаторные мето- методы B4). 1. 3. 3. Приближенные методы B5). 1. 4. Целочисленные многогранные множества 25 Глава 2. Модели дискретного программирования 29 2. 1. Задачи транспортного типа 29 2. 1. 1. Транспортная задача в матричной постановке. Це- лочисленность опорных планов B9). 2. 1. 2. Задача о наз- назначении (задача выбора) C1). 2. 1. 3. Задача коммивояже- коммивояжера C3). 2. 1. 4. Транспортная задача с фиксированными доплатами C9). 2. 1. 5. Распределительная задача D2) 2. 2. Задача о ранце 44 2. 2. 1. Задача об одномерном ранце D4). 2. 2. 2. Задача о много- многомерном ранце D4). 2. 2. 3. Общие свойства задач о ранце D5). 2. 2. 4. Алгоритм Данцига для линейной одномерной задачи о ранце D6). 2. 2. 5. Алгоритмы последовательного назначения единиц для приближенного решения задачи об одномерном ранце D8). 2. 2. 6. Алгоритмы приближенного решения зада- задачи о многомерном ранце E5). 2. 2. 7. Алгоритмы улучшения начального решения E7). 2. 2. 8. Алгоритмы «генетического» Оглавление типа E8). 2. 2. 9. Комбинированные эвристические алгоритмы для задачи о ранце E9). 2. 2. 10. Экспериментальные исследо- исследования системы комбинированных эвристических алгоритмов для приближенного решения задачи о ранце E9). 2. 3. Задачи теории графов 63 2. 3. 1.