Пер. с англ. — М.: Мир, 1984. — 496 с.: ил.
В книге американских ученых излагаются методы и алгоритмы
оптимизации детерминированных и стохастических сетей различного
назначения с помощью теории графов. Книга иллюстрирована большим
числом примеров, взятых из различных областей науки и техники.
Для специалистов, занимающихся применением вычислительной техники в
экономике, планировании, биологии и медицине. Может быть
использована аспирантами и студентами соответствующих
специальностей.
Предисловие редактора перевода.
Предисловие.
Введение .
Определения и обозначения.
Матричные представления сетей.
Сохранение потока.
Теорема о максимальном потоке и минимальном разрезе.
Упражнения.
Литература.
Детерминированные потоки в сетях .
Приложения потоковых моделей.
Линейное программирование и потоки в сетях.
Задача о кратчайшей цепи. Алгоритм Дейкстры.
Задача о многополюсной кратчайшей цепи.
Задачи о кратчайшем пути с фиксированными платежами.
Задача о К кратчайших путях.
Анализ алгоритмов поиска кратчайших путей и оценка их сложности.
Задача о кратчайшем остовном дереве.
Задача коммивояжера.
Транспортная задача.
Задача о перевозках.
Задача о назначениях.
Задача о назначениях и задача коммивояжера.
Задача о максимальном потоке.
Задача о многополюсном максимальном потоке.
Задача о многополюсной цепи с максимальной пропускной способностью.
Повреждения узлов и дуг в сетях.
Упражнения.
Литература.
Алгоритм дефекта. Обобщенный анализ детерминированных сетей с ограниченной пропускной способностью.
Оптимизация потока, основанная на применении алгоритма дефекта. Описание теории.
Основные понятия.
Сведение исходной задачи к задаче линейного программирования.
Основные теоремы.
Алгоритм дефекта для решения задачи о циркуляции минимальной стоимости.
Процедура расстановки пометок.
Графическая интерпретация алгоритма дефекта.
Описание шагов алгоритма.
Числовой пример.
Заключение.
Оптимизация потока, основанная на применении алгоритма дефекта. Построение моделей.
Решение задачи с использованием алгоритма дефекта.
Транспортная задача.
Задача о назначениях.
Максимальный поток в сетях с ограниченной пропускной способностью.
Задача от кратчайшей цепи.
Задача о дереве кратчайших цепей.
Задача о перевозках.
Нелинейные стоимости.
Задача производственного планирования (Филлипс и Иенсен).
Заключение.
Приложения алгоритма дефекта.
Проблема узких мест в задаче о назначениях.
Составление графика выполнения заданий с известными временными характеристиками.
Задача о хранении и сбыте товара.
Описание программы, реализующей алгоритм дефекта.
Ректификация и распределение нефти.
Упражнения.
Литература.
Методы управления проектами.
Управление проектами с помощью МКП И ПЕРТ.
Появление и применение ПЕРТ.
Появление и применение МКП.
Постановка задачи.
Построение сети.
Наиболее ранний возможный срок появления события.
Наиболее поздний допустимый срок наступления каждого события.
Резерв времени и критический путь.
Составление таблиц наиболее ранних возможных и наиболее поздних допустимых сроков выполнения работ.
Четыре показателя резерва времени при планировании методом критического пути.
Формулировка задачи в виде модели узел-работа.
Методы оценки и пересмотра планов (ПЕРТ).
Распределение ресурсов в сетевых графиках проектов.
Соотношение между временем и затратами: распределение денежных средств.
Распределение ресурсов.
Регулирование потребления ресурсов.
Задание предельного количества ресурсов.
Ограниченные ресурсы.
Сравнение имеющихся машинных программ для решения задач с помощью МКП и ПЕРТ.
Упражнения.
Литература.
Новые вопросы.
Обобщенные сети. Сети с выигрышами и проигрышами.
Применения обобщенных сетей.
Обобщенная сетевая задача как задача линейного программирования.
Характеристики сети.
Случай I. Обобщенные сети, не содержащие генерирующих и поглощающих циклов.
Случай II. Обобщенные сети с генерирующими и (или) поглощающими циклами.
Шаг первый. Аугментальная цепь потока минимальной стоимости.
Шаг второй. Построение маргинальной сети.
Увеличение потока.
Пример обобщенной сетевой задачи.
Заключение.
Стохастические сети. Графический метод оценки и пересмотра планов (ГЕРТ).
Сетевое представление.
Основные процедуры системы ГЕРТ.
Основные понятия о потоковых графах.
Определения.
Правило Мейсона для замкнутых потоковых графов.
Вычисления математического ожидания и дисперсии.
Применение системы ГЕРТ.
Многопродуктовые потоки в сетях.
Формулировки задач о многопродуктовом потоке в виде задач линейного программирования.
Специальный класс целочисленных задач о многопродуктовом потоке.
Приближенное решение многопродуктовой транспортной задачи методом агрегирования.
Границы погрешности при агрегировании.
Максимальные многопродуктовые потоки.
Многопродуктовые потоки в неориентированных сетях.
Максимальные потоки и воронкообразные узлы.
Приложения задач о многопродуктовом потоке.
Замечания.
Упражнения.
Литература.
Приложение. Описание программы сетевой оптимизации.
Пакет сетевой оптимизации.
Предисловие.
Введение .
Определения и обозначения.
Матричные представления сетей.
Сохранение потока.
Теорема о максимальном потоке и минимальном разрезе.
Упражнения.
Литература.
Детерминированные потоки в сетях .
Приложения потоковых моделей.
Линейное программирование и потоки в сетях.
Задача о кратчайшей цепи. Алгоритм Дейкстры.
Задача о многополюсной кратчайшей цепи.
Задачи о кратчайшем пути с фиксированными платежами.
Задача о К кратчайших путях.
Анализ алгоритмов поиска кратчайших путей и оценка их сложности.
Задача о кратчайшем остовном дереве.
Задача коммивояжера.
Транспортная задача.
Задача о перевозках.
Задача о назначениях.
Задача о назначениях и задача коммивояжера.
Задача о максимальном потоке.
Задача о многополюсном максимальном потоке.
Задача о многополюсной цепи с максимальной пропускной способностью.
Повреждения узлов и дуг в сетях.
Упражнения.
Литература.
Алгоритм дефекта. Обобщенный анализ детерминированных сетей с ограниченной пропускной способностью.
Оптимизация потока, основанная на применении алгоритма дефекта. Описание теории.
Основные понятия.
Сведение исходной задачи к задаче линейного программирования.
Основные теоремы.
Алгоритм дефекта для решения задачи о циркуляции минимальной стоимости.
Процедура расстановки пометок.
Графическая интерпретация алгоритма дефекта.
Описание шагов алгоритма.
Числовой пример.
Заключение.
Оптимизация потока, основанная на применении алгоритма дефекта. Построение моделей.
Решение задачи с использованием алгоритма дефекта.
Транспортная задача.
Задача о назначениях.
Максимальный поток в сетях с ограниченной пропускной способностью.
Задача от кратчайшей цепи.
Задача о дереве кратчайших цепей.
Задача о перевозках.
Нелинейные стоимости.
Задача производственного планирования (Филлипс и Иенсен).
Заключение.
Приложения алгоритма дефекта.
Проблема узких мест в задаче о назначениях.
Составление графика выполнения заданий с известными временными характеристиками.
Задача о хранении и сбыте товара.
Описание программы, реализующей алгоритм дефекта.
Ректификация и распределение нефти.
Упражнения.
Литература.
Методы управления проектами.
Управление проектами с помощью МКП И ПЕРТ.
Появление и применение ПЕРТ.
Появление и применение МКП.
Постановка задачи.
Построение сети.
Наиболее ранний возможный срок появления события.
Наиболее поздний допустимый срок наступления каждого события.
Резерв времени и критический путь.
Составление таблиц наиболее ранних возможных и наиболее поздних допустимых сроков выполнения работ.
Четыре показателя резерва времени при планировании методом критического пути.
Формулировка задачи в виде модели узел-работа.
Методы оценки и пересмотра планов (ПЕРТ).
Распределение ресурсов в сетевых графиках проектов.
Соотношение между временем и затратами: распределение денежных средств.
Распределение ресурсов.
Регулирование потребления ресурсов.
Задание предельного количества ресурсов.
Ограниченные ресурсы.
Сравнение имеющихся машинных программ для решения задач с помощью МКП и ПЕРТ.
Упражнения.
Литература.
Новые вопросы.
Обобщенные сети. Сети с выигрышами и проигрышами.
Применения обобщенных сетей.
Обобщенная сетевая задача как задача линейного программирования.
Характеристики сети.
Случай I. Обобщенные сети, не содержащие генерирующих и поглощающих циклов.
Случай II. Обобщенные сети с генерирующими и (или) поглощающими циклами.
Шаг первый. Аугментальная цепь потока минимальной стоимости.
Шаг второй. Построение маргинальной сети.
Увеличение потока.
Пример обобщенной сетевой задачи.
Заключение.
Стохастические сети. Графический метод оценки и пересмотра планов (ГЕРТ).
Сетевое представление.
Основные процедуры системы ГЕРТ.
Основные понятия о потоковых графах.
Определения.
Правило Мейсона для замкнутых потоковых графов.
Вычисления математического ожидания и дисперсии.
Применение системы ГЕРТ.
Многопродуктовые потоки в сетях.
Формулировки задач о многопродуктовом потоке в виде задач линейного программирования.
Специальный класс целочисленных задач о многопродуктовом потоке.
Приближенное решение многопродуктовой транспортной задачи методом агрегирования.
Границы погрешности при агрегировании.
Максимальные многопродуктовые потоки.
Многопродуктовые потоки в неориентированных сетях.
Максимальные потоки и воронкообразные узлы.
Приложения задач о многопродуктовом потоке.
Замечания.
Упражнения.
Литература.
Приложение. Описание программы сетевой оптимизации.
Пакет сетевой оптимизации.