Problema de flujo de costo mínimo

Problema de optimización matemática

El problema de flujo de costo mínimo ( MCFP ) es un problema de optimización y decisión para encontrar la forma más barata posible de enviar una cierta cantidad de flujo a través de una red de flujo . Una aplicación típica de este problema implica encontrar la mejor ruta de entrega desde una fábrica a 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 otros problemas de este tipo se pueden plantear como un problema de flujo de costo mínimo y también se puede resolver de manera eficiente utilizando el algoritmo símplex de red .

Definición

Una red de flujo es un gráfico dirigido con un vértice de origen y un vértice de destino , donde cada arista tiene capacidad , flujo y costo , y la mayoría de los algoritmos de flujo de costo mínimo admiten aristas con costos negativos. El costo de enviar este flujo a lo largo de una arista es . El problema requiere que se envíe una cantidad de flujo desde la fuente hasta el destino . ${\displaystyle G=(V,E)}$ ${\displaystyle s\in V}$ ${\displaystyle t\in V}$ ${\displaystyle (u,v)\in E}$ ${\displaystyle c(u,v)>0}$ ${\displaystyle f(u,v)}$ ${\displaystyle a(u,v)}$ ${\displaystyle (u,v)}$ ${\displaystyle f(u,v)\cdot a(u,v)}$ ${\displaystyle d}$ ${\displaystyle s}$ ${\displaystyle t}$

La definición del problema es minimizar el coste total del flujo en todos los bordes:

${\displaystyle \sum _{(u,v)\in E}a(u,v)\cdot f(u,v)}$

con las restricciones

Relación con otros problemas

Una variación de este problema consiste en encontrar un flujo que sea máximo, pero que tenga el menor costo entre las soluciones de flujo máximo. Esto podría denominarse un problema de flujo máximo y costo mínimo y es útil para encontrar correspondencias máximas y de costo mínimo .

Con algunas soluciones, encontrar el costo mínimo y el caudal máximo es sencillo. Si no, se puede encontrar el caudal máximo realizando una búsqueda binaria en . ${\displaystyle 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. El problema de circulación de costo mínimo no tiene fuente ni sumidero; en cambio, tiene costos y límites inferior y superior en cada borde, y busca cantidades de flujo dentro de los límites dados que equilibren el flujo en cada vértice y minimicen la suma sobre los bordes de costo por flujo. Cualquier instancia de flujo de costo mínimo se puede convertir en una instancia de circulación de costo mínimo estableciendo el límite inferior en todos los bordes a cero y luego haciendo un borde adicional desde el sumidero hasta la fuente , con capacidad y límite inferior , lo que obliga a que el flujo total desde a a también sea . ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle c(t,s)=d}$ ${\displaystyle l(t,s)=d}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle d}$

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

• Problema de ruta más corta (una sola fuente). Se requiere que una solución factible para el problema de flujo de costo mínimo envíe una unidad de flujo desde una fuente designada a un sumidero designado . Otorgue a todos los bordes una capacidad infinita. ${\displaystyle s}$ ${\displaystyle t}$
• Problema de flujo máximo . Elija una demanda grande (lo suficientemente grande como para exceder el flujo máximo; por ejemplo, la suma de las capacidades que salen del vértice de origen). Establezca los costos de todos los bordes en la instancia de flujo máximo en cero e introduzca un nuevo borde desde la fuente hasta el sumidero con un costo y una capacidad unitarios . ${\displaystyle d}$ ${\displaystyle d}$
• Problema de asignación . Supóngase que cada conjunto de partes de la bipartición tiene vértices y denotemos la bipartición con . Démosle a cada oferta y démosle a cada demanda . Cada arista debe tener capacidad unitaria. ${\displaystyle n}$ ${\displaystyle (X,Y)}$ ${\displaystyle x\in X}$ ${\displaystyle 1/n}$ ${\displaystyle y\in Y}$ ${\displaystyle 1/n}$

Soluciones

El problema del flujo de costo mínimo se puede resolver mediante programación lineal , ya que optimizamos una función lineal y todas las restricciones son lineales.

Aparte de eso, existen muchos algoritmos combinatorios. ^[1] Algunos de ellos son generalizaciones de algoritmos de flujo máximo , otros utilizan enfoques completamente diferentes.

Algoritmos fundamentales conocidos (tienen muchas variaciones):

• Cancelación de ciclos : un método primario general. ^[2]
• Cancelación de cortes : un método dual general. ^{[3] [4]}
• Cancelación del ciclo medio mínimo : un algoritmo simple y fuertemente polinomial . ^[5]
• Camino más corto sucesivo y escalamiento de capacidad : métodos duales, que pueden considerarse como la generalización del algoritmo de Ford-Fulkerson . ^[6]
• Escalamiento de costos : un enfoque primal-dual, que puede verse como la generalización del algoritmo push-relabel . ^[7]
• Algoritmo simplex de red : una versión especializada del método simplex de programación lineal . ^[8]
• Algoritmo fuera de lugar de DR Fulkerson

Solicitud

Peso mínimo de emparejamiento bipartito

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

Dado un grafo bipartito G = ( A ∪ B , E ) , el objetivo es encontrar la correspondencia de cardinalidad máxima en G que tenga un costo mínimo. Sea w : E → R una función de peso en los bordes de E . El problema de correspondencia bipartita de peso mínimo o problema de asignación es encontrar una correspondencia perfecta M ⊆ E cuyo peso total se minimice. La idea es reducir este problema a un problema de flujo de red.

Sea G′ = ( V′ = A ∪ B , E′ = E ) . Asignemos la capacidad de todas las aristas en E′ a 1. Añadamos un vértice fuente s y conéctelo a todos los vértices en A′ y añadamos un vértice sumidero t y conectemos todos los vértices dentro del grupo B′ a este vértice. La capacidad de todas las nuevas aristas es 1 y sus costos son 0. Se demuestra que existe una correspondencia bipartita perfecta de peso mínimo en G si y solo si existe un flujo de costo mínimo en G′ . ^[1]

Véase también

• LEMON (biblioteca C++)
• Kit de programación lineal GNU
• Problema de flujo de red

Referencias

1. Ravindra K. Ahuja ; Thomas L. Magnanti y James B. Orlin (1993). Flujos de red: teoría, algoritmos y aplicaciones . Prentice-Hall, Inc. ISBN 978-0-13-617549-0.
2. Morton Klein (1967). "Un método primario para flujos de costos mínimos con aplicaciones a los problemas de asignación y transporte". Management Science . 14 (3): 205–220. CiteSeerX 10.1.1.228.7696 . doi :10.1287/mnsc.14.3.205. 
3. Refael Hassin (1983). "El problema del flujo de costo mínimo: un enfoque unificador para los algoritmos existentes y un nuevo algoritmo de búsqueda de árbol". Programación matemática . 25 : 228–239. doi :10.1007/bf02591772.
4. Thomas R. Ervolina y S. Thomas McCormick (1993). "Dos algoritmos de cancelación de corte fuertemente polinomiales para flujo de red de costo mínimo". Matemáticas Aplicadas Discretas . 4 (2): 133–165. doi : 10.1016/0166-218x(93)90025-j .
5. Andrew V. Goldberg y Robert E. Tarjan (1989). "Encontrar circulaciones de costo mínimo cancelando ciclos negativos". Revista de la ACM . 36 (4): 873–886. doi :10.1145/76359.76368.
6. Jack Edmonds y Richard M. Karp (1972). "Mejoras teóricas en la eficiencia algorítmica para problemas de flujo de red". Revista de la ACM . 19 (2): 248–264. doi : 10.1145/321694.321699 .
7. Goldberg, Andrew V. y Tarjan, Robert E. (1990). "Encontrar circulaciones de costo mínimo mediante aproximación sucesiva". Matemáticas de la investigación de operaciones . 15 (3): 430–466. doi :10.1287/moor.15.3.430.
8. James B. Orlin (1997). "Un algoritmo símplex de red primal de tiempo polinomial para flujos de costo mínimo". Programación matemática . 78 (2): 109–129. doi :10.1007/bf02614365. hdl : 1721.1/2584 .

Enlaces externos

• Biblioteca LEMON C++ con varios algoritmos de circulación de flujo máximo y costo mínimo
• La biblioteca de proyectos C++ MCFClass con algunos algoritmos de flujo de costo mínimo y ruta más corta