Проблема с кровообращением

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

Определение [ править ]

Данная проточная сеть с:${\ Displaystyle G (V, E)}$

${\ displaystyle l (v, w)}$, нижняя граница потока от узла к узлу ,${\ displaystyle v}$${\ displaystyle w}$

${\ Displaystyle и (v, w)}$, верхняя граница потока от узла к узлу ,${\ displaystyle v}$${\ displaystyle w}$

${\ displaystyle c (v, w)}$, стоимость единицы расхода на ${\ displaystyle (v, w)}$

и ограничения:

${\ Displaystyle l (v, w) \ leq f (v, w) \ leq u (v, w)}$,

${\ Displaystyle \ сумма _ {вес \ в V} е (и, ш) = 0}$ (поток не может появиться или исчезнуть в узлах).

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

В минимально затратном варианте задачи минимизировать

${\ displaystyle \ sum _ {(v, w) \ in E} c (v, w) \ cdot f (v, w).}$

Многотоваровое обращение [ править ]

В задаче оборота нескольких товаров также необходимо отслеживать поток отдельных товаров:

${\ Displaystyle \, е_ {я} (в, ш)}$	Поток товаров из в .${\ displaystyle i}$${\ displaystyle v}$${\ displaystyle w}$
${\ Displaystyle \, е (v, ш) = \ сумма _ {я} f_ {я} (v, ш)}$	Общий расход.

Также существует нижняя граница для каждого товарного потока.

${\ Displaystyle \, l_ {я} (v, w) \ leq f_ {i} (v, w)}$

Ограничение консервации должно соблюдаться индивидуально для товаров:

${\displaystyle \ \sum _{w\in V}f_{i}(u,w)=0.}$

Решение [ править ]

Для проблемы циркуляции было разработано много полиномиальных алгоритмов (например, алгоритм Эдмондса и Карпа , 1972; Tarjan 1987-1988). Тардос нашел первый сильно полиномиальный алгоритм. ^[1]

В случае нескольких товаров проблема NP-полная для целочисленных потоков. ^[2] Для дробных потоков она разрешима за полиномиальное время , так как задачу можно сформулировать как линейную программу .

Связанные проблемы [ править ]

Ниже приведены некоторые проблемы и способы их решения с помощью приведенной выше общей схемы циркуляции.

• Задача об обращении нескольких товаров с минимальными затратами - Использование всех ограничений, указанных выше.
• Проблема обращения с минимальными затратами - используйте один товар
• Многотоварный оборот - решайте без оптимизации затрат.
• Простое обращение - используйте только один товар и бесплатно.
• Multi-поток товаров - Если обозначает спрос на товар от до , создать край с для всех товаров . Пускай для всех остальных ребер.${\displaystyle K_{i}(s_{i},t_{i},d_{i})}$${\displaystyle d_{i}}$${\displaystyle i}$${\displaystyle s_{i}}$${\displaystyle t_{i}}$${\displaystyle (t_{i},s_{i})}$${\displaystyle l_{i}(t_{i},s_{i})=u(t_{i},s_{i})=d_{i}}$${\displaystyle i}$${\displaystyle l_{i}(u,v)=0}$
• Проблема с потоком нескольких товаров с минимальными затратами - То же, что и выше, но минимизация затрат.
• Проблема потока минимальных затрат - Как указано выше, с 1 товаром.
• Задача максимального потока - установите для всех затрат значение 0 и добавьте край от стока к источнику с помощью , ∞ и .${\displaystyle t}$${\displaystyle s}$${\displaystyle l(t,s)=0}$${\displaystyle u(t,s)=}$${\displaystyle c(t,s)=-1}$
• Задача минимальной стоимости максимального потока - Сначала найдите максимальный объем потока . Затем решите с помощью и .${\displaystyle m}$${\displaystyle l(t,s)=u(t,s)=m}$${\displaystyle c(t,s)=0}$
• Кратчайший путь из одного источника - Пусть и для всех ребер в графе, и добавьте ребро с помощью и .${\displaystyle l(u,v)=0}$${\displaystyle c(u,v)=1}$${\displaystyle (t,s)}$${\displaystyle l(t,s)=c(t,s)=1}$${\displaystyle a(t,s)=0}$
• Кратчайший путь для всех пар - пусть все емкости неограничены, и найдите поток из 1 для товаров, по одному для каждой пары узлов.${\displaystyle v(v-1)/2}$

Ссылки [ править ]