В библиотеку

Источник:
Хэмди А. Таха. "Введение в исследование операций", 6-е издание:
Пер. с англ. - М.: Издательский дом "Вильямс", 2001.

СЕТЕВЫЕ МОДЕЛИ. ОБЗОР ПРИМЕНЕНИЯ СЕТЕВЫХ МОДЕЛЕЙ

    В рамках теории исследования операций рассматривается большое количество практических задач, которые можно сформулировать и решить как сетевые модели. Приведем несколько конкретных примеров.

  1. Проектирование газопровода, соединяющего буровые скважины морского базирования с находящейся на берегу приемной станцией. Целевая функция соответствующей модели должна минимизировать стоимость строительства газопровода.
  2. Нахождение кратчайшего маршрута между двумя городами по существующей сети дорог.
  3. Определение максимальной пропускной способности трубопровода для транспортировки угольной пульпы от угольных шахт к электростанциям.
  4. Определение схемы транспортировки нефти от пунктов нефтедобычи к нефтеперерабатывающим заводам с минимальной стоимостью транспортировки.
  5. Составление временного графика строительных работ (определение дат начала и завершения отдельных этапов работ).
    Решение приведённых задач (как и многих других подобных задач) требует примене-ния различных сетевых оптимизационных алгоритмов. В большинстве случаев рассматриваются следующие пять алгоритмов.
  1. Алгоритм нахождения минимального остовного дерева.
  2. Алгоритм нахождения кратчайшего пути.
  3. Алгоритм определения максимального потока.
  4. Алгоритм минимизаций стоимости потока в сети с ограниченной пропускной способностью.
  5. Алгоритм нахождения критического пути.
    Задачи, вытекающие из перечисленных примеров, можно сформулировать и решать как задачи линейного программирования. Однако специфическая структура этих задач позволяет разработать специальные сетевые алгоритмы, более эффективные, чем стандартный симплекс-метод.


К началу


©  Денис Шумейко, 2003