Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 78
Текст из файла (страница 78)
227. 228 Потоковый граф 393 Пратер 374 Притскер 401 4!О ууроентирование городской транспортной сети 438 — системы доставки почты 73 — централизованной водоочистной станции 171 Прорыв ЗЗЗ Процедура расстановки пометок 165, 233, 329 — — — для обратных дуг 236, 330 — — — — прямых дуг 235, 329 — трассировки 59, 65, 87, 187, 188 Пути, не пересекающиеся по узлам 202 Путь 14 — «угментальный потока 163 — критический 292 — ступенчатый 140 Работа 294 — критичесная 292 — наиболее ранний возможный срок начала 300 — — — — — окончания 301 — — поздний допустимый срок начала 301 — — — — — окончания 301 — резерв врмени 299, 301, 302, 304, 305, 306.
307, 308, 313 — — — гарантированный 308. 313 — — — независимый 307, 313 — — — свободный 306, 313 — — — суммарный 304, 313 — сокращение продолжительностя 300 — сокращенные сроки 319, 320 Разделяющее множество 427 Разрез 22, 23, 168 — минимальный 23, 24. 168 — пропускная способность (величииа) 23, 168 Предметный указатель 491 Расписание движения грузового судна 33 — — судов 436 Распределение средств на ремонт автострады 107 Ректификация и распределение нефти 276 Ресурсы 318, 322 — задание предельного. количества 344 — ограниченные 346 — распределение 339 — — в сетевых графиках проектов 3!7 — регулирование потребления 341 Росс» 108 Саати 10 Сакарович 440 Сеть 12, 225 — ациклаческая !6 — бескаитурная 15 — вполне плоская 427, 428 — двусторонния 252 — конденсированная !80 — маргинальная 374, 376 — матричные представления 18 — несвязная 201 — обобщенная 366 — плоская 427, 428 — связная 16 — с выигрышамн 366 — — зависимостью между временем н затратами 322 — — ограниченной пропускной способно.
стью 34, 226 — — проигрышами 366 — — расстояниями 34 — стахастическая 387 Сименс 338 Смит В. 43 Смит Л. 353 Событие 294 — наиболее поздний допустимый срок наступления 298 — — ранний возможный срок появлении 297 — резерв времени 299 Сток 14 — главный 14 Сьюолл 338 Теорема о максимальяом потоке и минимальном разрезе 22, 168 Теория графов 1О Томас 289, 301 Транспортировка коробок передач 4!8 — носмического корабля «Шаттл» 194 — нефти 61 Трехместная операция 65, 187 Труемпер 37! Уайтхаус 11 Узел 12, 225 — воронкообразный 435 — непросмотренный 235 — повреждение 200 — потенциал 375 — просмотренный 235 — фиктивный 420 Уист 344, 352 Условия абсолютной уннмодулярностк 53 — дополняющей нежесткости 231, 324 Фалкерсон !О, 23, !63, 837 Филлипс С.
338. 344, 353 Филлипс Т. 61, 260 Флойд 63, 101 Фондал ЗЗЗ Форд 1О, 23, 163 Фриш 1О, 20! Фрэнк 10, 201 Хайлер Юз Хелд 109 Хитчкок 1О, 35 Хаеландер 338 Ху 1О, 63, 109, !79, 440 Цепь И вЂ” аугментальная потока мннимальяой стоимости 374 — выигрыш 371 — изменение 370, 371 — кратчайшая 54 — — многопалюсная 63 — многополюсная с максимальной пропускной способностью 186 — проигрыш 371 Ц РЗ вЂ” генерирующий 37! — изменение 370 — поглощающий 371 Циркуляция 226 Чернее Збз Частичный разрыв 201 Штраф вторичный 115 за выполнение поворота 79 Эванс 410, 440 Эйлер 10 Элмаграбн 1О ОГЛАВЛЕНИЕ Предисловие редактора перевода Предисловие .
Глава 1. Введемие 1.1. Определения и обозначения 1.2. Матричные представления сетей 1.3. Сохранение потока 1.4. Теорема о максимальном потоке и минимальном разрезе . Упражнения Литература 12 16 22 22 25 27 43 45 47 54 56 56 74 75 78 83 84 2.6.2. Применение алгоритма двойного поиска к решению модельной задачи 88 2.6.3. Описание программы, реализующей алгоритм двойного поиска 2.6.4. Результаты вычислений 2.6.5. Результаты вычислений для задачи нахождения четырех кратчайших путей . 92 95 Глава 2. Детерминированные потоки в сетях 2.1.
Г1риложения потоковых моделей 2.!.1. Замена оборудования 2.1.2. Планирование работ по осуществлению проекта . 2.!.3. Составление расписания движения грузового судна 2.1.4. Задачи о максимальном потоке и потоке минимальной стоимости . . . . . . . . . .
. . . 34 2.1.5. Транспортная задача . . . . . . . . . . 35 2.1.6. Задача о поставщике......... 36 2.1.7. Календарное планирование трудовых ресурсов . . 38 2.1.8. Задача составления расписания движения транспорт-' ных судов . . . . . . . . . . . . . 39 2.1.9. Модель производственного планирования (Смита и Джонсона) 2.1.10. Заключение 2.2. Линейное программирование и потоки в сетях 2.3. Задача о кратчайшей цепи. Алгоритм Дейкстры 2.3.1, Итеративная процедура 2.3.2. Пример, иллюстрирующий работу алгоритма Дейкстры 2.3.3. Сведение задачи о покупке автомобиля к задаче о кратчайшей цепи...,,,....
59 2.3.4. Описание программы, реализующей алгоритм Дейкстры 2.3.5. Задача, связанная с транспортировкой нефти (Филлипс) 2.4. Задача о многополюсной кратчайшей цепи 2.4.1. Пример задачи о многополюсной кратчайшей цепи 2.4.2. Применение задачи о многополюсной кратчайшей цепи при проектировании системы доставки почты . . . 72 2.4.3. Описание программы, реализующей алгоритм решения задачи о многополюсной кратчайшей цепи 2.4.4. Составление маршрута перегона вагонов .
2.5. Задачи о кратчайшем пути с фиксированными платежами 2.6, Задача о К кратчайших путях . 2.6.1. Метод двойного поиска . Оглавление 493 2.7. Анализ алгоритмов поиска кратчайших путей и оценка их сложности 2,7.1. Вычислительная сложность метода Дейкстры, 2,7.2. Вычислительная сложность алгоритма Флойда 2.7.3. Вычислительная сложность метода двойного поиска 2.8. Задача о кратчайшем остовном дереве .
2.8.1. Алгоритм построения кратчайшего остовного дерева 2.8.2. Пример поиска решения с помощью «поедающего» алгоритма (рис. 2.28) 2.8.3. Описание программы, реализующей алгоритм построения кратчайшего остова . 2.8.4. Распределение средств на ремонт автострады 2.8.5. Применения задачи о кратчайшем остове . 2.9. Задача коммивояжера 2.9.!. Вычисление нижних границ .
2.9.2. Ветвление 2.9.3. Процедура вычислений 2.9.4. Заключительные замечания 2.9.5. Описание программы, реализующей алгоритм решения задачи коммивояжера 2.9.6. Составление маршрута зарубежного путешествия . 2.10. Транспортная задача 2,!ОЛ. Математическая постановка . 2.10.2. Снмплексный алгоритм для транспортной задачи . 2.10.3. Сетевая интерпретация симплексного алгоритма решения транспортной задачи 2.10.4. Модель производство — распределение . 2.!1, Задача о перевозках 2.12. Задача о назначениях 2.12.!. Математическая постановка задачи 2.12.2. Венгерский алгоритм 2.12.3. Решение примера с помощью венгерского алгоритма 2.12.4.
Замечания . 2.12.5. Задача размещения производства 2.13. Задача о назначениях и задача коммивояжера 2.14. Задача о максимальном потоке 2.14.!. Процедура расстановки пометок для задачи о максимальном потоке 2.14.2. Пример работы алгоритма расстановки пометок . 2.14.3. Теорема о максимальном потоке и минимальном разрезе 2.14.4. Проектирование централизованной водоочистной станции 2.14.5.
Описание программы, реализующей алгоритм решения задачи о максимальном потоке . 2.!4.6. Задача о транспортировке и хранении зерна . 2.15. Задача о многополюсном максимальном потоке . 2,15.1, Алгоритм Гомори — Ху 2.15.2. Обоснование алгоритма 2.15.3. Пример задачи о многополюсном максимальном потоке . 2.16. Задача о многополюсной цепи с максимальной пропускной способностью 2.16.1. Оптимальный маршрут перевозки неупакованного груза 2.16.2. Описание программы, реализующей алгоритм решения задачи о многополюсной цепи с максимальной пропускной способностью !00 101 101 102 103 103 106 107 108 109 11О 113 114 .
122 123 123 125 127 130 142 147 148 149 150 153 157 157 159 163 165 166 168 171 174 175 178 179 182 183 186 188 193 Оглавление 494 194 200 205 220 224 Часть 1. ГОРИТМА 3.1. 3.2. 225 227 231 3.3 3.4 3.5 3.6 3.7 3.8 3.9 вре- 289 290 291 2.16.3. Транспортировка космического корабля «Шаттл» . 2.17. Повреждения узлов и дуг в сетях . Упражнения Литература Глава 3. Алгоритм дефекта. Обобщемный анализ детерминированмых сетей с ограниченной пропускной способностью ОПТИМИЗАЦИЯ ПОТОКА, ОСНОВАННАЯ НА ПРИМЕНЕНИИ АЛ- ДЕФЕКТА. ОПИСАНИЕ ТЕОРИИ Основные понятия Сведение исходной задачи к задаче линейного программи- рования Основные теоремы Алгоритм дефекта для решения задачи о циркуляции мини- мальной стоимости Процедура расстановки пометок Графическая интерпретация алгоритма дефекта 3.6.1.
Горизонтальные перемещения 3.6.2. Вертикальные перемещения . Описание шагов алгоритма . Числовой пример 3.8.1. Числовой пример для алгоритма дефекта . Заключение Часть П ОптимизАциЯ пОтОкА, ОснОВАннАЯ нА пРименении АлГОРИТМА ДЕФЕКТА. ПОСТРОЕНИЕ МОДЕЛЕИ 3,10. Решение задачи с использованием алгоритма дефекта 3.11.
Транспортная задача 3.11.1, Пример постановки транспортной задачи . 3.!2. Задача о назначениях 3.!2.1. Пример постановки задачи о назначениях . 3,13. Максимальный поток в сетях с ограниченной пропускной способностью . 3.14. Задача от кратчайшей цепи . 3.15. Задача о дереве кратчайших цепей 3.16. Задача о перевозках 3.17. Нелинейные стоимости 3.18. Задача производственного планирования (Филлипс и Р!енсен) 3.19. Заключение Часть !П ПРИЛОЖЕНИЯ АЛГОРИТМА ДЕФЕКТА 3.20.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
