Глава 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. Локальный декомпозиционный алгоритм A_BT решения задач дискретной оптимизации с блочно-древовидной структурой…………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