Источник:
Хэмди А. Таха. "Введение в исследование операций", 6-е издание:
Пер. с англ. - М.: Издательский дом "Вильямс", 2001.
СЕТЕВЫЕ МОДЕЛИ. ОБЗОР ПРИМЕНЕНИЯ СЕТЕВЫХ МОДЕЛЕЙ
В рамках теории исследования операций рассматривается большое количество практических задач, которые можно сформулировать и решить как сетевые модели. Приведем несколько конкретных примеров.
- Проектирование газопровода, соединяющего буровые скважины морского базирования с находящейся на берегу приемной станцией. Целевая функция соответствующей модели должна минимизировать стоимость строительства газопровода.
- Нахождение кратчайшего маршрута между двумя городами по существующей сети дорог.
- Определение максимальной пропускной способности трубопровода для транспортировки угольной пульпы от угольных шахт к электростанциям.
- Определение схемы транспортировки нефти от пунктов нефтедобычи к нефтеперерабатывающим заводам с минимальной стоимостью транспортировки.
- Составление временного графика строительных работ (определение дат начала и завершения отдельных этапов работ).
Решение приведённых задач (как и многих других подобных задач) требует примене-ния различных сетевых оптимизационных алгоритмов. В большинстве случаев рассматриваются следующие пять алгоритмов.
- Алгоритм нахождения минимального остовного дерева.
- Алгоритм нахождения кратчайшего пути.
- Алгоритм определения максимального потока.
- Алгоритм минимизаций стоимости потока в сети с ограниченной пропускной способностью.
- Алгоритм нахождения критического пути.
Задачи, вытекающие из перечисленных примеров, можно сформулировать и решать как задачи линейного программирования. Однако специфическая структура этих задач позволяет разработать специальные сетевые алгоритмы, более эффективные, чем стандартный симплекс-метод.
© Денис Шумейко, 2003
