- Артикул:00-01117536
- Автор: Д. Филлипс, А. Гарсиа-Диас
- Тираж: 10000 экз.
- Обложка: Твердая обложка
- Издательство: МИР (все книги издательства)
- Город: Москва
- Страниц: 496
- Формат: 60х90 1/16
- Год: 1984
Развернуть ▼
В книге американских ученых излагаются методы и алгоритмы оптимизации детерминированных и стохастических сетей различного назначения с помощью теории графов. Книга иллюстрирована большим числом примеров, взятых из различных областей науки и техники.
Для специалистов, занимающихся применением вычислительной техники в экономике, планировании, биологии и медицине. Может быть использована аспирантами и студентами соответствующих специальностей.
Содержание
Предисловие редактора перевода
Предисловие
Глава 1. Введение
1.1. Определения и обозначения
1.2. Матричные представления сетей
1.3. Сохранение потока
1.4. Теорема о максимальном потоке и минимальном разрезе
Упражнения
Литература
Глава 2. Детерминированные потоки в сетях
2.1. Приложения потоковых моделей
2.1.1. Замена оборудования
2.1.2. Планирование работ по осуществлению проекта
2.1.3. Составление расписания движения грузового судна
2.1.4. Задачи о максимальном потоке и потоке минимальной стоимости
2.1.5. Транспортная задача
2.1.6. Задача о поставщике
2.1.7. Календарное планирование трудовых ресурсов
2.1.8. Задача составления расписания движения транспортных судов
2.1.9. Модель производственного планирования (Смита и Джонсона)
2.1.10. Заключение
2.2. Линейное программирование и потоки в сетях
2.3. Задача о кратчайшей цепи. Алгоритм Дейкстры
2.3.1. Итеративная процедура
2.3.2. Пример, иллюстрирующий работу алгоритма Дейкстры
2.3.3. Сведение задачи о покупке автомобиля к задаче о кратчайшей цепи
2.3.4. Описание программы, реализующей алгоритм Дейкстры
2.3.5. Задача, связанная с транспортировкой нефти (Филлипс)
2.4. Задача о многополюсной кратчайшей цепи
2.4.1. Пример задачи о многополюсной кратчайшей цепи
2.4.2. Применение задачи о многополюсной кратчайшей цепи при проектировании системы доставки почты
2.4.3. Описание программы, реализующей алгоритм решения задачи о многополюсной кратчайшей цепи
2.4.4. Составление маршрута перегона вагонов
2.5. Задачи о кратчайшем пути с фиксированными платежами
2.6. Задача о К кратчайших путях
2.6.1. Метод двойного поиска
2.6.2. Применение алгоритма двойного поиска к решению модельной задачи
2.6.3. Описание программы, реализующей алгоритм двойного поиска
2.6.4. Результаты вычислений
2.6.5. Результаты вычислений для задачи нахождения четырех кратчайших путей
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.1. Вычисление нижних границ
2.9.2. Ветвление
2.9.3. Процедура вычислений
2.9.4. Заключительные замечания
2.9.5. Описание программы, реализующей алгоритм решения задачи коммивояжера
2.9.6. Составление маршрута зарубежного путешествия
2.10. Транспортная задача
2.10.1. Математическая постановка
2.10.2. Симплексный алгоритм для транспортной задачи
2.10.3. Сетевая интерпретация симплексного алгоритма решения транспортной задачи
2.10.4. Модель производство - распределение
2.11. Задача о перевозках
2.12. Задача о назначениях
2.12.1. Математическая постановка задачи
2.12.2. Венгерский алгоритм
2.12.3. Решение примера с помощью венгерского алгоритма
2.12.4. Замечания
2.12.5. Задача размещения производства
2.13. Задача о назначениях и задача коммивояжера
2.14. Задача о максимальном потоке
2.14.1. Процедура расстановки пометок для задачи о максимальном потоке
2.14.2. Пример работы алгоритма расстановки пометок
2.14.3. Теорема о максимальном потоке и минимальном разрезе
2.14.4. Проектирование централизованной водоочистной станции
2.14.5. Описание программы, реализующей алгоритм решения задачи о максимальном потоке
2.14.6. Задача о транспортировке и хранении зерна
2.15. Задача о многополюсном максимальном потоке
2.15.1. Алгоритм Гомори - Ху
2.15.2. Обоснование алгоритма
2.15.3. Пример задачи о многополюсном максимальном потоке
2.16. Задача о многополюсной цепи с максимальной пропускной способностью
2.16.1. Оптимальный маршрут перевозки неупакованного груза
2.16.2. Описание программы, реализующей алгоритм решения задачи о многополюсной цепи с максимальной пропускной способностью
2.16.3. Транспортировка космического корабля «Шаттл»
2.17. Повреждения узлов и дуг в сетях
Упражнения
Литература
Глава 3. Алгоритм дефекта. Обобщенный анализ детерминированных сетей с ограниченной пропускной способностью
Часть I. Оптимизация потока, основанная на применении алгоритма дефекта. Описание теории
3.1. Основные понятия
3.2. Сведение исходной задачи к задаче линейного программирования
3.3. Основные теоремы
3.4 Алгоритм дефекта для решения задачи о циркуляции минимальной стоимости
3.5. Процедура расстановки пометок
3.6. Графическая интерпретация алгоритма
3.6.1. Горизонтальные перемещения
3.6.2. Вертикальные перемещения
3.7. Описание шагов алгоритма
3.8. Числовой пример
3.8.1. Числовой пример для алгоритма дефекта
3.9. Заключение
Часть II. оптимизация потока, основанная на применении алгоритма дефекта, построение моделей
3.10. Решение задачи с использованием алгоритма дефекта
3.11. Транспортная задача
3.11.1. Пример постановки транспортной задачи
3.12. Задача о назначениях
3.12.1. Пример постановки задачи о назначениях
3.13. Максимальный поток в сетях с ограниченной способностью
3.14. Задача от кратчайшей цепи
3.15. Задача о дереве кратчайших цепей
3.16. Задача о перевозках
3.17. Нелинейные стоимости
3.18. Задача производственного планирования (Филлипс и Йенсен)
3.19. Заключение
Часть III. приложения алгоритма дефекта
3.20. Проблема узких мест в задаче о назначениях
3.21. Составление графика выполнения заданий с известными временными характеристиками
3.22. Задача о хранении и сбыте товара
3.23. Описание программы, реализующей алгоритм дефекта
3.24. Ректификация и распределение нефти
Упражнения
Литература
Глава 4. Методы управления проектами
Часть I. Управление проектами с помощью МКП и ПЕРТ
4.1 Появление и применение ПЕРТ
4.2. Появление и применение МКП
4.3. Постановка задачи
4.4. Построение сети
4.4.1. Производственная задача
4.5. Наиболее ранний возможный срок появления события
4.6. Наиболее поздний допустимый срок наступления каждого cобытия
4.7. Резерв времени и критический путь
4.8. Составление таблиц наиболее ранних возможных и наиболее поздних допустимых сроков выполнения работ
4.9. Четыре показателя резерва времени при планировании методом критического пути
4.9.1. Процедура вычислений
4.9.2. Вычисление резерва времени
4.9.3. Свободный резерв времени
4.9.4. Независимый резерв времени
4.9.5. Гарантированный резерв времени
4.10. Формулировка задачи в виде модели узел-работа
4.10.1. Построение сети
4.10.2. Процедуры вычислений
4.11. Методы оценки и пересмотра планов (ПЕРТ)
4.11.1. Пример системы ПЕРТ
4.11.2. Вероятности завершения проекта
Часть II. Распределение ресурсов в сетевых графиках проектов
4.12. Соотношение между временем и затратами: распределение денежных средств
4.12.1. Потоковый алгоритм, использующий метод критического пути, в сети с зависимостью между временем и затратами
4.12.2. Применение процедур установления компромиссного соотношения между затратами и продолжительностью проекта
4.13. Распределение ресурсов
4.14. Регулирование потребления ресурсов
4.15. Задание предельного количества ресурсов
4.16. Ограниченные ресурсы
4.16.1. Эвристические методы
4.16.2. Оптимальные решения
Часть III. Сравнение имеющихся машинных программ для решения задач с помощью МКП и ПЕРТ
Упражнения
Литература
Глава 5. Новые вопросы
Часть I. Обобщенные сети. Сети с выигрышами и проигрышами
5.1. Применения обобщенных сетей
5.2. Обобщенная сетевая задача как задача линейного программирования
5.3. Характеристики сети
5.4. Случай I. Обобщенные сети, не содержащие генерирующих и поглощающих циклов
5.4.1. Пример
5.5. Случай II. Обобщенные сети с генерирующими и (или) поглощающими циклами
5.5.1. Шаг 1. Построение начального потока
5.5.2. Шаг 2. Построение маргинальной сети
5.5.3. Шаг 3. Процесс увеличения потока
5.6. Шаг 1. Аугментальная цепь потока минимальной стоимости
5.7. Шаг 2. Построение маргинальной сети
5.8. Увеличение потока
5.9. Пример обобщенной сетевой задачи
5.10. Заключение
Часть II. Стохастические сети, графический метод оценки и пересмотра планов (ГЕРТ)
5.11. Сетевое представление
5.11.1. Входные функции
5.11.2. Выходные функции
5.12. Основные процедуры системы ГЕРТ
5.12.1. Последовательные дуги
5.12.2. Параллельные ветви
5.12.3. Петли
5.13. Основные понятия о потоковых графах
5.14. Определения
5.15. Правило Мейсона для замкнутых потоковых графов
5.16. Вычисления математического ожидания и дисперсии
5.17. Применение системы ГЕРТ
5.17.1. Производство прецизионных деталей
5.17.1. Процесс переработки сырья (Притскер)
5.17.2. Определение вероятностных нормативных времен для задач, решаемых в условиях неопределенности
Часть III. Многопродуктовые потоки в сетях
5.18. Формулировки задач о многопродуктовом потоке в виде задач линейного программирования
5.19. Специальный класс целочисленных задач о многопродуктовом потоке
5.19.1. Транспортировка коробок передач для автомобилей
5.20. Приближенное решение многопродуктовой транспортной задачи методом агрегирования
5.20.1. Задача о транспортировке фруктов
5.21. Границы погрешности при агрегировании
5.22. Максимальные многопродуктовые потоки
5.23. Многопродуктовые потоки в неориентированных сетях
5.23.1. Пример задачи о двухпродуктовом потоке
5.24. Максимальные потоки и воронкообразные узлы
5.25. Приложения задач о многопродуктовом потоке
5.25.1. Составление расписания движения судов
5.25.2. Проектирование городской транспортной сети
5.25.3. Модели вычислительных систем
5.26. Замечания
Упражнения
Литература
Приложение. Описание программы сетевой оптимизации
Пакет сетевой оптимизации