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

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

Определение

Данная сеть потоков $G(V,E)$ с:

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

$u(v,w)$, верхняя граница потока из узла $v$ узел $w$,

$c(v,w)$, стоимость единицы потока на $(v,w)$

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

$l(v,w)\leq f(v,w)\leq u(v,w)$,

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

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

В варианте задачи с минимальной стоимостью минимизируйте

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

Многотоварный оборот

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

$\,f_{i}(v,w)$	Товарный поток $i$ от $v$ к $w$.
$\,f(v,w)=\sum _{i}f_{i}(v,w)$	Общий поток.

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

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

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

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

Решение

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

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

Связанные проблемы

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

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