Problema de circulación

El problema de la circulación y sus variantes constituyen una generalización de los problemas de flujo en redes , con la restricción adicional de un límite inferior para los flujos en las aristas y la exigencia de conservación del flujo tanto para el origen como para el destino (es decir, no existen nodos especiales). En las variantes del problema, circulan múltiples mercancías por la red y se aplica un coste a dicho flujo.

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

${\displaystyle l(v,w)}$, límite inferior del flujo desde el nodo${\displaystyle v}$al nodo${\displaystyle w}$,

${\displaystyle u(v,w)}$, límite superior del flujo desde el nodo${\displaystyle v}$al nodo${\displaystyle w}$,

${\displaystyle c(v,w)}$, costo de una unidad de flujo en${\displaystyle (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 planteado.

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

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

Para el problema de la 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 ]}

Para el caso de múltiples productos básicos, el problema es NP-completo para flujos enteros. ^{[ 2 ]} Para flujos fraccionarios, es resoluble 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 descrita anteriormente.

• Problema de circulación de múltiples productos básicos con coste mínimo: utilizando todas las restricciones dadas anteriormente.
• Problema de circulación de costo mínimo: utilice un solo producto.
• Circulación de múltiples productos básicos: solución sin optimización de costes.
• Circulación sencilla: solo se utiliza un producto, y sin coste alguno.
• Flujo de múltiples productos básicos - Si${\displaystyle K_{i}(s_{i},t_{i},d_{i})}$denota una demanda de${\displaystyle d_{i}}$para productos básicos${\displaystyle i}$de${\displaystyle s_{i}}$a${\displaystyle t_{i}}$crear un borde${\displaystyle (t_{i},s_{i})}$con${\displaystyle l_{i}(t_{i},s_{i})=u(t_{i},s_{i})=d_{i}}$para todos los productos básicos${\displaystyle i}$. Dejar${\displaystyle l_{i}(u,v)=0}$para todos los demás bordes.
• Problema de flujo de múltiples productos básicos con costo mínimo : igual que el anterior, pero minimizando el costo.
• Problema de flujo de costo mínimo : igual que el anterior, con 1 producto.
• Problema de flujo máximo : establezca todos los costos en 0 y agregue una arista desde el fregadero.${\displaystyle t}$a la fuente${\displaystyle s}$con${\displaystyle l(t,s)=0}$,${\displaystyle u(t,s)=}$∞ y${\displaystyle c(t,s)=-1}$.
• Problema de flujo máximo de costo mínimo : primero, encontrar la cantidad máxima de flujo.${\displaystyle m}$. Luego resuelve con${\displaystyle l(t,s)=u(t,s)=m}$y${\displaystyle c(t,s)=0}$.
• Ruta más corta desde un único origen - Deje${\displaystyle l(u,v)=0}$y${\displaystyle c(u,v)=1}$para todas las aristas del grafo, y agregar una arista${\displaystyle (t,s)}$con${\displaystyle l(t,s)=u(t,s)=1}$y${\displaystyle c(t,s)=0}$.
• Camino más corto entre todos los pares : Supongamos que todas las capacidades son ilimitadas y encontremos un flujo de 1 para${\displaystyle v(v-1)/2}$productos básicos, uno por cada par de nodos.