Оптимизация максимального потока методом анализа сети

В теории оптимизации и теории графов, задача о максимальном потоке является одной из самых важных. Она является частным случаем более трудных задач, как например задача о циркуляции. Благодаря алгоритмам, решающих данную задачу, обеспечивается работа всех современных программ, связанных с сетевыми структурами [1, 2]. Решение подобных задач может потребовать огромных ресурсов и времени, поэтому особенно актуально рассмотреть методы, которые позволят оптимизировать базовые алгоритмы по решению данной задачи.

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

Задачи о потоках в сетях можно сформулировать как задачи линейного программирования. Потоковые задачи обладают определенной структурой и для них разработано большое число эффективных алгоритмов и методов [3, 4]. В отличие от задач линейного программирования, решениями большинства таких задач являются целочисленные значения.

При этом, для того, чтобы оценить качество полученного решения и сделать выводы о том, достаточно ли исходной информации для получения надежного решения, удовлетворяет ли поставленным требованиям алгоритм решения, необходимо определять интервальные оценки решения [3]. При определении интервальных оценок решения необходимо учитывать неопределенности исходных данных, что значительно повышает достоверность принимаемых решений [4, 5].

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

Основным подходом в таких методах является процесс сжатия нескольких узлов в один узел. При этом дуги между всеми «сжимаемыми» узлами получают бесконечную пропускную способность. Некоторый узел, не принадлежащий числу сжимаемых, и связанный со всеми сжимаемыми узлами, заменяются одной дугой с пропускной способностью, равной сумме пропускных способностей заменяемых связывающих дуг. Таким образом, если в сети имеется p узлов, то для определения величины максимальных потоков не нужно проводить вычисления p(p —1)/2 раз максимальных потоков между каждой парой узлов, а достаточно решить лишь решить p — 1 задач о максимальном потоке, причем каждый раз задача решается в более простой сети, чем исходная.

Для произвольной сети N , состоящей из n узлов определяются величины максимальных потоков между заданными p узлами сети N . Эти p узлов, между которыми ищется максимальный поток, называются полюсами, а остальные n- p узлов обычными или промежуточными узлами. Можно допустить, что имеется некоторая другая сеть N ′ , которая состоит из p узлов, причем величины макси- мальных потоков между p полюсами сети N равны величинам максимальных потоков между p узлами сети N ′ . Две сети, имеющие равные величины максимальных потоков между некоторым множеством узлов, называются потокоэквивалентными или просто эквивалентными относительно этого множества узлов. Тогда можно найти искомые величины максимальных потоков между p узлами, рассматривая сеть N ′ . Оказывается, что для каждой сети N всегда существует эквивалентная ей сеть N ′ , являющаяся деревом.

Рассмотрим алгоритм, который позволяет по сети N построить эквивалентное ей дерево N ′ . Процесс нахождения максимальных потоков между p полюсами сети состоит из двух этапов. Действия этапов повторяются до тех пор, пока не будет построено дерево N ′ , эквивалентное исходной сети N .

Этап 1: между двумя выбранными полюсами решается задача о максимальном потоке. Эта задача решается в сети, меньшей, чем исходная сеть N , поскольку некоторое множество узлов сжато в один узел. При нахождении максимального потока выделяют минимальный разрез.

Этап 2: для выделенного минимального разреза определяется очередная дуга дерева. Выбирается некоторая новая пара полюсов и осуществляется сжатие некоторых подмножеств узлов исходной сети, в результате чего получается сеть и переходят в этапу 1. Алгоритм заканчивается, когда найдено p — 1 дуг дерева.

Метод анализа сети позволяет строить эквивалентную сеть, которая является деревом. Можно построить много деревьев, которые являются потоко-эквивалентными заданной сети. При этом, иногда при по- строении потоко-эквивалентное дерево обладает особенностью: каждая ветвь этого дерева соответствует некоторому минимальному разрезу в исходной сети. Такое дерево называется деревом разрезов. Дерево разрезов, содержащее n узлов, изображает n — 1 минимальных разрезов исходной сети, которые не пересекаются друг с другом.

Метод анализа сети может быть использован при оптимизации транспортной сети [6], в частности при создании интеллектуальной системы управления городскими транспортными потоками для анализа информации [7] и выбора оптимальных управленческих решений.