Problema de circulación

El problema de la circulación y sus variantes son una generalización de los problemas de flujo en la red , con la restricción adicional de un límite inferior para los flujos en los bordes y con la necesidad de conservar el flujo para la fuente y el sumidero (es decir, no hay nodos especiales). En las variantes del problema, hay múltiples productos que fluyen a través de la red y un costo para el flujo.

Red de flujo dada con:${\displaystyle G(V,E)}$

${\displaystyle l(v,w)}$, límite inferior del flujo de nodo a nodo ,${\estilo de visualización v}$${\estilo de visualización w}$

${\displaystyle u(v,w)}$, límite superior del flujo de nodo a nodo ,${\estilo de visualización v}$${\estilo de visualización w}$

${\estilo de visualización c(v,w)}$, costo de una unidad de flujo en${\estilo de visualización (v,w)}$

y las restricciones:

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

${\displaystyle \sum_{w\in V}f(u,w)=0}$(el flujo no puede aparecer ni desaparecer en los nodos).

Encontrar una asignación de flujo que satisfaga las restricciones proporciona una solución al problema de circulación dado.

En la variante de costo mínimo del problema, minimizar

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

En un problema de circulación de múltiples productos, también es necesario realizar un seguimiento del flujo de los productos individuales:

${\displaystyle \,f_{i}(v,w)}$	El flujo de mercancías desde a .${\estilo de visualización i}$${\estilo de visualización v}$${\estilo de visualización w}$
${\displaystyle \,f(v,w)=\sum _{i}f_{i}(v,w)}$	El flujo total.

También existe un límite inferior para cada flujo de mercancías.

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

La restricción de conservación debe respetarse individualmente para los productos:

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

Para el problema de circulación se han desarrollado muchos algoritmos polinomiales (por ejemplo, el algoritmo de Edmonds-Karp , 1972; Tarjan 1987-1988). Tardos encontró el primer algoritmo fuertemente polinomial. ^[1]

En el caso de múltiples productos, el problema es NP-completo para flujos enteros. ^[2] Para flujos fraccionarios, se puede resolver en tiempo polinomial , ya que se puede formular el problema como un programa lineal .

A continuación se presentan algunos problemas y cómo resolverlos con la configuración de circulación general indicada anteriormente.

• Problema de circulación de múltiples productos con costo mínimo: utilizando todas las restricciones dadas anteriormente.
• Problema de circulación de costo mínimo: utilizar un solo producto
• Circulación de múltiples mercancías: solucione sin optimizar costos.
• Circulación simple: solo use un producto y sin costo.
• Flujo de múltiples productos : si denota una demanda de un producto de a , crea una arista con para todos los productos . Sea para todas las demás aristas.${\displaystyle K_{i}(s_{i},t_{i},d_{i})}$$estilo de visualización d_{i}}$${\estilo de visualización i}$$estilo de visualización s_{i}}$$estilo de visualización t_{i}}$${\displaystyle (t_{i},s_{i})}$${\displaystyle l_{i}(t_{i},s_{i})=u(t_{i},s_{i})=d_{i}}$${\estilo de visualización i}$${\displaystyle l_{i}(u,v)=0}$
• Problema de flujo de múltiples productos con costo mínimo : igual que el anterior, pero minimizando el costo.
• Problema de flujo de costo mínimo : como el anterior, pero con un producto.
• Problema de flujo máximo : establezca todos los costos en 0 y agregue un borde desde el sumidero hasta la fuente con , ∞ y .${\estilo de visualización t}$${\estilo de visualización s}$${\displaystyle l(t,s)=0}$${\displaystyle u(t,s)=}$${\displaystyle c(t,s)=-1}$
• Problema de caudal máximo y coste mínimo : primero, encuentre la cantidad de caudal máximo . Luego, resuelva con y .${\estilo de visualización m}$${\displaystyle l(t,s)=u(t,s)=m}$${\displaystyle c(t,s)=0}$
• Ruta más corta de una sola fuente : sea y para todos los bordes del gráfico, y agregue un borde con y .${\displaystyle l(u,v)=0}$${\displaystyle c(u,v)=1}$${\estilo de visualización (t,s)}$${\displaystyle l(t,s)=u(t,s)=1}$${\displaystyle c(t,s)=0}$
• Camino más corto para todos los pares : supongamos que todas las capacidades son ilimitadas y encontremos un flujo de 1 para los productos, uno para cada par de nodos.${\displaystyle v(v-1)/2}$