Problema de flujo de costo mínimo

El problema de flujo de costo mínimo ( MCFP ) es un problema de optimización y decisión para encontrar la forma más económica posible de enviar una cierta cantidad de flujo a través de una red de flujo . Una aplicación típica de este problema consiste en encontrar la mejor ruta de entrega desde una fábrica hasta un almacén donde la red de carreteras tiene cierta capacidad y costo asociado. El problema de flujo de costo mínimo es uno de los más fundamentales entre todos los problemas de flujo y circulación porque la mayoría de los demás problemas se pueden presentar como un problema de flujo de costo mínimo y también porque se puede resolver de manera eficiente utilizando el algoritmo de red símplex .

Una red de flujo es un gráfico dirigido con un vértice fuente y un vértice receptor , donde cada borde tiene capacidad , flujo y costo , y la mayoría de los algoritmos de flujo de costo mínimo admiten bordes con costos negativos. El costo de enviar este flujo a lo largo de un borde es . El problema requiere que se envíe una cantidad de flujo desde la fuente al sumidero .${\ estilo de visualización G = (V, E)}$${\ estilo de visualización s \ en V}$${\ estilo de visualización t \ en V}$${\ estilo de visualización (u, v) \ en E}$${\ estilo de visualización c (u, v)> 0}$${\ estilo de visualización f (u, v) \ geq 0}$${\ estilo de visualización a (u, v)}$${\ estilo de visualización (u, v)}$${\displaystyle f(u,v)\cdot a(u,v)}$${\ estilo de visualización d}$${\ estilo de visualización}$${\ estilo de visualización t}$

Una variación de este problema es encontrar un flujo que sea máximo, pero que tenga el costo más bajo entre las soluciones de flujo máximo. Esto podría llamarse un problema de flujo máximo de costo mínimo y es útil para encontrar coincidencias máximas de costo mínimo .

Con algunas soluciones, encontrar el flujo máximo de costo mínimo es sencillo. Si no, se puede encontrar el flujo máximo realizando una búsqueda binaria en .${\ estilo de visualización d}$

Un problema relacionado es el problema de circulación de costo mínimo , que se puede utilizar para resolver el flujo de costo mínimo. Esto se logra estableciendo el límite inferior en todos los bordes en cero, y luego haciendo un borde adicional desde el sumidero hasta la fuente , con capacidad y límite inferior , forzando el flujo total de a a también ser .${\ estilo de visualización t}$${\ estilo de visualización}$${\displaystyle c(t,s)=d}$${\ estilo de visualización l (t, s) = d}$${\ estilo de visualización}$${\ estilo de visualización t}$${\ estilo de visualización d}$

Los siguientes problemas son casos especiales del problema de flujo de costo mínimo (proporcionamos breves bosquejos de cada reducción aplicable, a su vez): ^[1]

Reducción de la correspondencia bipartita de peso mínimo con el problema de flujo máximo de costo mínimo