El problema de circulación y sus variantes son una generalización de los problemas de flujo de la red , con la restricción adicional de un límite inferior en los flujos de borde, y con la conservación del flujo que también se requiere para la fuente y el sumidero (es decir, no hay nodos especiales). En variantes del problema, hay múltiples productos que fluyen a través de la red y un costo en el flujo.
Definición
Red de flujo dada con:
- , límite inferior del flujo desde el nodo al nodo ,
- , límite superior del flujo desde el nodo al nodo ,
- , costo de una unidad de flujo en
y las limitaciones:
- ,
- (el flujo no puede aparecer ni desaparecer en los nodos).
Encontrar una asignación de flujo que satisfaga las restricciones da una solución al problema de circulación dado.
En la variante de costo mínimo del problema, minimice
Circulación de múltiples productos básicos
En un problema de circulación de varios productos básicos, también debe realizar un seguimiento del flujo de los productos individuales:
El flujo de mercancías de a . El flujo total.
También hay un límite inferior en cada flujo de productos básicos.
La restricción de conservación debe mantenerse individualmente para los productos básicos:
Solución
Para el problema de la circulación, se han desarrollado muchos algoritmos polinomiales (por ejemplo, el algoritmo de Edmonds y Karp , 1972; Tarjan 1987-1988). Tardos encontró el primer algoritmo fuertemente polinomial. [1]
Para el caso de varios productos básicos, 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 .
Problemas relacionados
A continuación se presentan algunos problemas y cómo resolverlos con la configuración de circulación general que se proporciona anteriormente.
- Problema de circulación de múltiples productos básicos de costo mínimo: utilizando todas las restricciones dadas anteriormente.
- Problema de circulación de costo mínimo: use un solo producto
- Circulación de múltiples productos básicos: resuelva sin optimizar el costo.
- Circulación simple: solo use un producto y sin costo.
- Flujo de múltiples productos básicos - Si denota una demanda de para la mercancía de a , crea una ventaja con para todos los productos básicos . Dejar para todos los demás bordes.
- Problema de flujo de múltiples productos básicos de costo mínimo : como se indicó anteriormente, pero minimice el costo.
- Problema de flujo de costo mínimo : como arriba, con 1 producto.
- Problema de flujo máximo : establezca todos los costos en 0 y agregue un borde desde el fregadero a la fuente con , ∞ y .
- Problema de flujo máximo de costo mínimo : primero encuentre la cantidad de flujo máximo. Luego resuelve con y .
- Ruta más corta de una sola fuente - Let y para todas las aristas del gráfico y agregue una arista con y .
- Ruta más corta de todos los pares : deje que todas las capacidades sean ilimitadas y encuentre un flujo de 1 para productos básicos, uno para cada par de nodos.
Referencias
- ^ Éva Tardos. "Un algoritmo de circulación de coste mínimo fuertemente polinomial". Combinatorica . 5 : 247-255. doi : 10.1007 / BF02579369 .
- ^ S. Even y A. Itai y A. Shamir (1976). "Sobre la complejidad de la tabla de tiempo y los problemas de flujo de múltiples productos básicos" . Revista SIAM de Computación . SIAM. 5 (4): 691–703. doi : 10.1137 / 0205048 . Archivado desde el original el 12 de enero de 2013.