Проблема с сетевым потоком

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

К конкретным типам проблем с сетевым потоком относятся:

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

Теорема о максимальном потоке и минимальном разрезе приравнивает значение максимального потока к значению минимального разреза — разделения вершин потоковой сети, которое минимизирует общую пропускную способность ребер, пересекающих одну сторону раздела на другую. Приближенные теоремы о максимальном потоке и минимальном сокращении обеспечивают распространение этого результата на задачи многопродуктовых потоков. Дерево Гомори – Ху сети ненаправленных потоков обеспечивает краткое представление всех минимальных разрезов между различными парами конечных вершин.

Алгоритмы построения потоков включают в себя

• Алгоритм Динича , сильно полиномиальный алгоритм максимального потока.
• Алгоритм Эдмондса – Карпа , более быстрый сильно полиномиальный алгоритм для максимального потока.
• Алгоритм Форда-Фалкерсона , жадный алгоритм максимального потока, который, как правило, не является строго полиномиальным.
• Сетевой симплексный алгоритм — метод, основанный на линейном программировании, но специализирующийся на сетевых потоках.
• Нестандартный алгоритм для потока с минимальной стоимостью
• Алгоритм максимального потока push-relabel , один из наиболее эффективных известных методов достижения максимального потока.

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