Транспортная задача (и ее варианты) – лишь одна из многочисленных задач, которые можно сформулировать и решить с помощью сетевых моделей.

Рассмотрим конкретные примеры:

а) проектирование нефтепровода, соединяющего буровые скважины в Каспийском море с находящейся на берегу приемной станцией. Следует выбрать проект, в котором строительство нефтепровода имеет минимальную стоимость (наименьшую протяженность);

б) определение кратчайшего пути между двумя городами, проходящего по существующей сети шоссейных дорог;

в) определение максимальной пропускной способности (тонна/год) газопровода для транс

портировки газа с мест добычи к месту переработки (потребления);

г) определение наиболее экономичной (имеющей минимальную стоимость) схемы транспортировки нефти из пунктов нефтедобычи на перерабатывающие заводы и далее в центры распределения (потребления). Здесь, помимо условий, определяющих верхний предел для добычи нефти и нижний предел для удовлетворения спроса на нее, необходимо принимать во внимание ограничения по мощности нефтеперерабатывающих (предприятий) заводов и пропускных способностей соответствующих транспортных коммуникаций.

Анализ примеров показывает, что оптимизационные задачи на сетях можно описать следующими четырьмя типами моделей:

1) минимизация сети (случай a);

2) нахождение кратчайшей цепи в сети (случай б);

3) определение максимального потока в сети (случай в);

4) минимизация стоимости потока в сети с ограниченными пропускными способностями коммуникаций (случай г).

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

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

Специальная структура этих задач позволяет разработать эффективные алгоритмы, которые в большинстве своем основываются на линейном программировании, но вычислительные схемы, которых значительно проще и нагляднее.