Сетевые математические модели технико-экономических задач

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

Рассмотрим следующие конкретные примеры.

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

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

3. Определение максимальной пропускной способности (в тоннах/год) трубопровода для транспортировки угольной пульпы с шахт на тепловые электростанции.

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

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

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

2) нахождения кратчайшего маршрута (случай 2;

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

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

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

Модель определения потока минимальной стоимости в сети с ограниченными пропускными способностями имеет широкий круг практических приложений. Задачу о кратчайшем пути и задачу о максимальном потоке можно рассматривать как частные случаи транспортной задачи с ограниченными пропускными способностями. Однако метод решения задачи с ограниченными пропускными способностями включает большой объем вычислительных процедур. По этой причине в данном разделе описываются лишь первые три модели из перечисленных выше. При этом преследовалась цель — показать, насколько просто осуществляется решение задач специализированными методами.

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

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