Методы анализа сетей

Филлипс Д., Гарсиа-Диас А.

Table of contents :
Обложка ……Page 1
Титульный лист оригинала ……Page 2
Титульный лист ……Page 3
Аннотация ……Page 4
Предисловие редактора перевода ……Page 5
Предисловие ……Page 7
Глава 1. Введение ……Page 9
1.1. Определения и обозначения ……Page 12
1.2. Матричные представления сетей ……Page 18
1.4. Теорема о максимальном потоке и минимальном разрезе ……Page 22
Упражнения ……Page 25
Литература ……Page 27
Глава 2. Детерминированные потоки в сетях ……Page 29
2.1.1. Замена оборудования ……Page 30
2.1.2. Планирование работ по осуществлению проекта ……Page 31
2.1.3. Составление расписания движения грузового судна ……Page 33
2.1.4. Задачи о максимальном потоке и потоке минимальной стоимости ……Page 34
2.1.5. Транспортная задача ……Page 35
2.1.6. Задача о поставщике ……Page 36
2.1.7. Календарное планирование трудовых ресурсов ……Page 38
2.1.8. Задача составления расписания движения транспортных судов ……Page 39
2.1.9. Модель производственного планирования (Смита и Джонсона) ……Page 43
2.1.10. Заключение ……Page 45
2.2. Линейное программирование и потоки в сетях ……Page 47
2.3. Задача о кратчайшей цепи. Алгоритм Дейкстры ……Page 54
2.3.2. Пример, иллюстрирующий работу алгоритма Дейкстры ……Page 56
2.3.3. Сведение задачи о покупке автомобиля к задаче о кратчайшей цепи ……Page 59
2.3.5. Задача, связанная с транспортировкой нефти (Филлипс) ……Page 61
2.4. Задача о многополюсной кратчайшей цепи ……Page 63
2.4.1. Пример задачи о многополюсной кратчайшей цепи ……Page 67
2.4.2. Применение задачи о многополюсной кратчайшей цепи при проектировании системы доставки почты ……Page 72
2.4.3. Описание программы, реализующей алгоритм решения задачи о многополюсной кратчайшей цепи ……Page 74
2.4.4. Составление маршрута перегона вагонов ……Page 75
2.5. Задачи о кратчайшем пути с фиксированными платежами ……Page 78
2.6. Задача о К кратчайших путях ……Page 83
2.6.1. Метод двойного поиска ……Page 84
2.6.2. Применение алгоритма двойного поиска к решению модельной задачи ……Page 88
2.6.3. Описание программы, реализующей алгоритм двойного поиска ……Page 92
2.6.4. Результаты вычислений ……Page 95
2.6.5. Результаты вычислений для задачи нахождения четырех кратчайших путей ……Page 98
2.7. Анализ алгоритмов поиска кратчайших путей и оценка их сложности ……Page 100
2.7.2. Вычислительная сложность алгоритма Флойда ……Page 101
2.7.3. Вычислительная сложность метода двойного поиска ……Page 102
2.8.1. Алгоритм построения кратчайшего остовного дерева ……Page 103
2.8.2. Пример поиска решения с помощью «поедающего» алгоритма (рис. 2.28) ……Page 104
2.8.3. Описание программы, реализующей алгоритм построения кратчайшего остова ……Page 106
2.8.4. Распределение средств на ремонт автострады ……Page 107
2.8.5. Применения задачи о кратчайшем остове ……Page 108
2.9. Задача коммивояжера ……Page 109
2.9.1. Вычисление нижних границ ……Page 110
2.9.2. Ветвление ……Page 113
2.9.3. Процедура вычислений ……Page 114
2 .9.4. Заключительные замечания ……Page 122
2.9.6. Составление маршрута зарубежного путешествия ……Page 123
2.10. Транспортная задача ……Page 125
2.10.1. Математическая постановка ……Page 127
2.10.2. Симплексный алгоритм для транспортной задачи ……Page 130
2.10.3. Сетевая интерпретация симплексного алгоритма решения транспортной задачи ……Page 142
2.11. Задача о перевозках ……Page 147
2.12. Задача о назначениях ……Page 148
2.12.1. Математическая постановка задачи ……Page 149
2.12.2. Венгерский алгоритм ……Page 150
2.12.3. Решение примера с помощью венгерского алгоритма ……Page 153
2.12.5. Задача размещения производства ……Page 157
2.13. Задача о назначениях и задача коммивояжера ……Page 159
2.14. Задача о максимальном потоке ……Page 163
2.14.1. Процедура расстановки пометок для задачи о максимальном потоке ……Page 165
2.14.2. Пример работы алгоритма расстановки пометок ……Page 166
2.14.3. Теорема о максимальном потоке и минимальном разрезе ……Page 168
2.14.4. Проектирование централизованной водоочистной станции ……Page 171
2.14.5. Описание программы, реализующей алгоритм решения задачи о максимальном потоке ……Page 174
2.14.6. Задача о транспортировке и хранении зерна ……Page 175
2.15. Задача о многополюсном максимальном потоке ……Page 178
2.15.1. Алгоритм Гомори — Ху ……Page 179
2.15.2. Обоснование алгоритма ……Page 182
2.15.3. Пример задачи о многополюсном максимальном потоке ……Page 183
2.16. Задача о многополюсной цепи с максимальной пропускной способностью ……Page 186
2.16.1. Оптимальный маршрут перевозки неупакованного груза ……Page 188
2.16.2. Описание программы, реализующей алгоритм решения задачи о многополюсной цепи с максимальной пропускной способностью ……Page 193
2.16.3. Транспортировка космического корабля «Шаттл» ……Page 194
2.17. Повреждения узлов и дуг в сетях ……Page 200
Упражнения ……Page 205
Литература ……Page 220
Часть I. Оптимизация потока, основанная на применении алгоритма ДЕФЕКТА. ОПИСАНИЕ ТЕОРИИ ……Page 224
3.1. Основные понятия ……Page 225
3.2. Сведение исходной задачи к задаче линейного программирования ……Page 227
3.3. Основные теоремы ……Page 231
3.4. Алгоритм дефекта для решения задачи о циркуляции минимальной стоимости ……Page 232
3.5. Процедура расстановки пометок ……Page 233
3.6. Графическая интерпретация алгоритма дефекта ……Page 239
3.6.1. Горизонтальные перемещения ……Page 241
3.6.2. Вертикальные перемещения ……Page 242
3.7. Описание шагов алгоритма ……Page 243
3.8.1. Числовой пример для алгоритма дефекта ……Page 244
3.9. Заключение ……Page 249
3.10. Решение задачи с использованием алгоритма дефекта ……Page 250
3.11. Транспортная задача ……Page 251
3.12. Задача о назначениях ……Page 253
3.13. Максимальный поток в сетях с ограниченной пропускной способностью ……Page 255
3.15. Задача о дереве кратчайших цепей ……Page 256
3.16. Задача о перевозках ……Page 257
3.17. Нелинейные стоимости ……Page 258
3.18. Задача производственного планирования (Филлипс и Иенсен) ……Page 260
3.19. Заключение ……Page 267
3.20. Проблема узких мест в задаче о назначениях ……Page 268
3.21. Составление графика выполнения заданий с известными временными характеристиками ……Page 271
3.22. Задача о хранении и сбыте товара ……Page 274
3.24. Ректификация и распределение нефти ……Page 275
Упражнения ……Page 280
Литература ……Page 288
Часть I. УПРАВЛЕНИЕ ПРОЕКТАМИ С ПОМОЩЬЮ МКП И ПЕРТ ……Page 289
4.1 Появление и применение ПЕРТ ……Page 290
4.2. Появление и применение МКП ……Page 291
4.3. Постановка задачи ……Page 292
4.4. Построение сети ……Page 294
4.4.1. Производственная задача ……Page 295
4.5. Наиболее ранний возможный срок появления события ……Page 297
4.6. Наиболее поздний допустимый срок наступления каждого события ……Page 298
4.7. Резерв времени и критический путь ……Page 299
4.8. Составление таблиц наиболее ранних возможных и наиболее поздних допустимых сроков выполнения работ ……Page 300
4.9. Четыре показателя резерва времени при планировании методом критического пути ……Page 301
4.9.1. Процедура вычислений ……Page 302
4.9.2. Вычисление резерва времени ……Page 304
4.9.3. Свободный резерв времени ……Page 306
4.9.4. Независимый резерв времени ……Page 307
4.9.5. Гарантированный резерв времени ……Page 308
4.10.1. Построение сети ……Page 309
4.10.2. Процедуры вычислений ……Page 311
4.11. Методы оценки и пересмотра планов (ПЕРТ) ……Page 313
4.11.1. Пример системы ПЕРТ ……Page 314
4.11.2. Вероятности завершения проекта ……Page 316
Часть II. РАСПРЕДЕЛЕНИЕ РЕСУРСОВ В СЕТЕВЫХ ГРАФИКАХ ПРОЕКТОВ ……Page 317
4.12. Соотношение между временем и затратами: распределение денежных средств ……Page 318
4.12.1. Потоковый алгоритм, использующий метод критического пути, в сети с зависимостью между временем и затратами ……Page 322
4.12.2. Применение процедур установления компромиссного соотношения между затратами и продолжительностью проекта ……Page 337
4.13. Распределение ресурсов ……Page 339
4.14. Регулирование потребления ресурсов ……Page 341
4.15. Задание предельного количества ресурсов ……Page 344
4.16.1. Эвристические методы ……Page 346
4.16.2. Оптимальные решения ……Page 350
Часть III.СРАВНЕНИЕ ИМЕЮЩИХСЯ МАШИННЫХ ПРОГРАММ ДЛЯ РЕШЕНИЯ ЗАДАЧ С ПОМОЩЬЮ МКП И ПЕРТ ……Page 353
Упражнения ……Page 356
Литература ……Page 363
Часть I. ОБОБЩЕННЫЕ СЕТИ. СЕТИ С ВЫИГРЫШАМИ И ПРОИГРЫШАМИ ……Page 366
5.1. Применения обобщенных сетей ……Page 367
5.2. Обобщенная сетевая задача как задача линейного программирования ……Page 369
5.3. Характеристики сети ……Page 370
5.4. Случай I. Обобщенные сети, не содержащие генерирующих и поглощающих циклов ……Page 371
5.4.1. Пример ……Page 372
5.6. Шаг 1. Аугментальная цепь потока минимальной стоимости ……Page 374
5.7. Шаг 2. Построение маргинальной сети ……Page 376
5.8. Увеличение потока ……Page 377
5.9. Пример обобщенной сетевой задачи ……Page 379
Часть II. CТОХАСТИЧЕСКИЕ СЕТИ. ГРАФИЧЕСКИЙ МЕТОД ОЦЕНКИ И ПЕРЕСМОТРА ПЛАНОВ (ГЕРТ) ……Page 386
5.11.1. Входные функции ……Page 387
5.11.2. Выходные функции ……Page 388
5.12. Основные процедуры системы ГЕРТ ……Page 389
5.12.2. Параллельные ветви ……Page 391
5.12.3. Петли ……Page 392
5.13. Основные понятия о потоковых графах ……Page 393
5.14. Определения ……Page 394
5.15. Правило Мейсона для замкнутых потоковых графов ……Page 397
5.17.1. Производство прецизионных деталей ……Page 400
5.17.2. Процесс переработки сырья (Притскер) ……Page 401
5.17.3. Определение вероятностных нормативных времен для задач, решаемых в условиях неопределенности [31] ……Page 403
Часть III. МНОГОПРОДУКТОВЫЕ ПОТОКИ В СЕТЯХ ……Page 410
5.18. Формулировки задач о многопродуктовом потоке в виде задач линейного программирования ……Page 412
5.19. Специальный класс целочисленных задач о многопродуктовом потоке ……Page 415
5.19.1. Транспортировка коробок передач для автомобилей ……Page 418
5.20. Приближенное решение многопродуктовой транспортной задачи методом агрегирования ……Page 419
5.20.1. Задача о транспортировке фруктов ……Page 422
5.21. Границы погрешности при агрегировании ……Page 423
5.22. Максимальные многопродуктовые потоки ……Page 426
5.23. Многопродуктовые потоки в неориентированных сетях ……Page 429
5.23.1. Пример задачи о двухпродуктовом потоке ……Page 432
5.24. Максимальные потоки и воронкообразные узлы ……Page 434
5.25.1. Составление расписания движения судов ……Page 436
5.25.2. Проектирование городской транспортной сети ……Page 438
5.25.3. Модели вычислительных систем ……Page 439
5.26. Замечания ……Page 440
Упражнения ……Page 441
Литература ……Page 448
Пакет сетевой оптимизации ……Page 451