Глава 3. Унимодулярные задачи целочисленного программирования...84
Оглавление.
Введение…………………………………………………………………...8
Глава 1. Общие сведения о задачах дискретной и комбинаторной оптимизации и методах их решения……………………………………….18
1.1. Исторические сведения о дисциплине……………………………..18
1.2. Основные понятия: задачи комбинаторной и дискретной оптимизации, Модели дискретного программирования. Постановка задачи, примеры…………………………………………………………….20
1.3. Особенности задач. Общие сведения о методах решения задач: методы отсечения, комбинаторные методы, приближенные методы. Целочисленные многогранные множества……………………………………43
ЗАДАЧИ……………………………………………………………………47
Глава 2. Современные алгебраические языки моделирования ……….55
2.1. Общие сведения……………………………………………………………..55
Автоматизация построения математических моделей оптимизации….55
2.1.2. О методологических вопросах моделирования ………………………...60
2.1.3. Подходы к представлению и созданию моделей………………………..62
2.1.4. Основные черты языков моделирования………………………………..65
2.2. Алгебраический язык моделирования AMPL……………………………..67
2.2.1 Основные особенности программирования на AMPL………………...67
2.2.2 Декларации компонент модели…………………………………………76
ЗАДАЧИ………………………………………………………………………...82
Глава 3. Унимодулярные задачи целочисленного программирования...84
3.1. Определение унимодулярной задачи целочисленного программирования………………………………………………………..84
3.2. Задачи транспортного типа………………………………………………85
3.3. Задачи оптимального резервирования (темпоральные задачи о ранце)87
Вопросы и задачи.……………………………………………………………….92
Глава 4. Экстремальные задачи теории графов……………………………94
4.1. Основные понятия теории графов…………………………………...94
4.1.1 Основные определения теории графов……………………………….94
4.1.2. Графы как модели программ, данных и процессов. Графы как объекты обработки информации…………………………………………101
4.1.3. Задачи о покрытиях графов………………………………………...115
4.1.4. Задача об изоморфизме графов……………………………………..118
4.2. Экстремальные задачи на графовых структурах……………….122
4.2.1. Задачи о раскрасках графов ……………………………..…………122
4.2.2. Построение остовного дерева минимального веса…………………125
4.2.3. Другие важные экстремальные задачи на графах…………………..129
Вопросы, задачи……………………………………………………………..131
Глава 5. Сложность алгоритмов дискретной оптимизации…………133
5.1. Основные понятия теории сложности…………………………..133
5.1.1. Алгоритмы и сложность………………………………………………133
5.1.2. Временная сложность………………………………………………….134
5.1.3. Машина Тьюринга……………………………………………………..135
5.1.4. Понятие о NP-полных задачах………………………………………...135
5.1.5. Задачи распознавания. Языки и кодирование………………………..136
5.1.6. Детерминированные машины Тьюринга и класс Р………………….140
5.1.7. Недетерминированные машины Тьюринга и класс NP……………..142
5.2. Использование теории сложности в дискретной оптимизации.145
5.2.1. Соотношение между классами Р и NP………………………………..145
5.2.2. Полиномиальная сводимость и NP-полные задачи………………….145
5.2.3. Теорема Кука…………………………………………………………...147
5.2.4. Полиномиальная сложность задач линейного программирования…150
5.2.5. Сложность задач дискретной оптимизации…………………………..152
Вопросы и задачи..…………………………………………………………….158
Глава 6. Комбинаторные методы решения задач дискретной оптимизации………………………………………………………………….159
6.1. Общая схема метода ветвей и границ……………………………159
6.1.1. Поиск с возвратами…………………………………………………159
6.1.2. Схема метода ветвей и границ для общей задачи дискретного программирования…………………………………………………………161
6.1.3. Понятие релаксации (комбинаторная релаксация, линейная релаксация, ранцевая релаксация, релаксация Лагранжа)……………….168
6.2. Применение метода ветвей и границ для решения задач дискретной оптимизации……………………………………………….171
6.2.1. Метод Ленд и Дойг для задачи частично целочисленного линейного программирования………………………………………………………….171
6.2.2. Метод ветвей и границ для задачи о ранце…………………………172
6.2.3. Применение метода ветвей и границ для задачи коммивояжера…173
6.2.4. Современные программные системы, реализующие метод ветвей и границ………………………………………………………………………..181
Вопросы и задачи…..……………………………………………………….183
Глава 7. Другие методы решения задач дискретной оптимизации.........184
7.1. Методыотсечения и методы ветвлений и отсечений …………...184
7.1.1. Методы отсечения…………………………………………………...184
7.1.2. Методы ветвлений и отсечений…………………………………….188
7.1.3. Препроцессинг в современных программных системах решения задач дискретной оптимизации……………………………………………190
7.2. Приближенные алгоритмы………………………………………….191
7.2.1. Метод вектора спада для приближенного решения задач дискретной оптимизации…………………………………………………………………191
7.2.2. «Жадные» алгоритмы решения задачи о ранце……………………197
Вопросы и задачи..………………………………………………………….198
Глава 8. Несериальное динамическое программирование и локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации………………………………………………………………….199
8.1. Теория локальных алгоритмов Ю.И.Журавлева……………….199
8.2. Локальные алгоритмы в дискретной оптимизации……………204
8.2.1. О локальных алгоритмах для задач дискретной оптимизации…204
8.2.2. Локальный алгоритм A……………………………………………205
8.2.3. Локальный декомпозиционный алгоритм ABT решения задач дискретной оптимизации с блочно-древовидной структурой…………208
8.3. Локальные элиминационные алгоритмы……………………….216
8.3.1. Основные определения……………………………………………..216
8.3.2. Локальные элиминационные алгоритмы в задачах дискретной оптимизации………………………………………………………………..218
8.3.3. Задание структуры разреженных задач дискретной оптимизации с помошью графового и гиперграфового представлений…………………219
8.3.4. Локальные алгоритмы элиминации переменных, использующие в качестве структурного графа граф взаимосвязей переменных задачи….221
8.3.5. Графовые структуры локального элиминационного алгоритма..234
8.3.6. Блочно-элиминационные локальные алгоритмы, учитывающие подобие окрестностей отдельных переменных…………………………..237
8.3.7. Локальные алгоритмы, использующие древовидную структурную декомпозицию………………………………………………………………248
8.3.8. Алгоритмы выделения блочно-древовидных структур в разреженных графах взаимосвязей дискретных задач, позволяющих применение локальных элиминационных алгоритмов для решения этих задач…………………………………………………………………………250
Вопросы и задачи.…………………………………………………………254
Глава 9. Дискретные задачи теории расписаний и календарного планирования…………………………………………………………………..256
9.1. Постановка задачи календарного планирования………………..256
9.2. Сетевой график «вершины-работы»………………………………269
9.3. Диаграмма Гантта……………………………………………………272
9.4. Календарное планирование с ограниченными ресурсами……..274
9.5. Управление проектами с ограниченными ресурсами…………..277
Вопросы и задачи…………………………………………………………282
Глава 10. Дискретные задачи удовлетворения ограничений (УО) и алгоритмы их решения………………………………………………………284
10.1. Основные понятия теории удовлетворения ограничений………..284
10.1.1. Определение задачи удовлетворения ограничений …………….284
10.1.2. Примеры задач удовлетворения ограничений…………………...286
10.1.3. Бинарные и общие задачи удовлетворения ограничений………294
10.1.4. Графовые представления структуры задачи удовлетворения ограничений …………………………………………….…………………300