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 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 otros problemas de este tipo pueden plantearse como un problema de flujo de costo mínimo y también pueden resolverse de manera eficiente utilizando el algoritmo de red simplex .
Definición
Una red de flujo es un gráfico dirigido con un vértice fuente y un vértice de sumidero , donde cada borde tiene capacidad , flujo y costo , con la mayoría de los algoritmos de flujo de costo mínimo que admiten bordes con costos negativos. El costo de enviar este flujo a lo largo de un borde es . El problema requiere una cantidad de flujo para ser enviado desde la fuente hundir .
La definición del problema es minimizar el costo total del flujo en todos los bordes:
con las limitaciones
Limitaciones de capacidad : Simetría sesgada : Conservación de flujo : Flujo requerido :
Relación con otros problemas
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 denominarse 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.
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 a cero y luego haciendo un borde adicional desde el fregadero. a la fuente , con capacidad y límite inferior , forzando el flujo total de a ser tambien .
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]
- Problema de la ruta más corta (fuente única). Requerir que una solución factible al problema de flujo de costo mínimo envíe una unidad de flujo de una fuente designada a un fregadero designado . Dale a todos los bordes una capacidad infinita.
- Problema de flujo máximo . Deje que todos los nodos tengan demanda cero y que el costo asociado con atravesar cualquier borde sea cero. Ahora, presenta una nueva ventaja desde el fregadero actual a la fuente actual . Estipular que el costo unitario de enviar flujo a través del borde es igual a y permitir capacidad infinita. (Esta reducción también se menciona en Problema de circulación ).
- Problema de asignación . Suponga que cada conjunto de partitos en la bipartición tiene vértices, y denotar la bipartición por . Dar cada uno suministro y dale a cada uno demanda . Cada borde debe tener capacidad unitaria.
Soluciones
El problema de 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, para una encuesta completa, ver [1] . Algunos de ellos son generalizaciones de algoritmos de flujo máximo , otros utilizan enfoques completamente diferentes.
Algoritmos fundamentales bien conocidos (tienen muchas variaciones):
- Cancelación de ciclo : un método primario general. [2]
- Cancelación de ciclo medio mínimo : un algoritmo simple fuertemente polinomial . [3]
- Ruta sucesiva más corta y escalamiento de capacidad : métodos duales, que pueden verse como la generalización del algoritmo de Ford-Fulkerson . [4]
- Escala de costos : un enfoque dual primario, que puede verse como la generalización del algoritmo de inserción y re-etiqueta . [5]
- Algoritmo de red simplex : una versión especializada del método simplex de programación lineal . [6]
- Algoritmo fuera de lugar por DR Fulkerson
Solicitud
Coincidencia bipartita de peso mínimo
Dado un gráfico bipartito G = ( A ∪ B , E ), el objetivo es encontrar la máxima coincidencia de cardinalidad en G que tenga un costo mínimo. Deje w : E → R una función de peso en los bordes de E . El problema de emparejamiento bipartito de peso mínimo o el problema de asignación es encontrar un emparejamiento perfecto M ⊆ E cuyo peso total se minimice. La idea es reducir este problema a un problema de flujo de red.
Deje G ′ = ( V ′ = A ∪ B , E ′ = E ). Asigne la capacidad de todas las aristas en E ′ a 1. Agregue un vértice fuente sy conéctelo a todos los vértices en A ′ y agregue un vértice sumidero ty conecte todos los vértices dentro del grupo B ′ a este vértice. La capacidad de todas las aristas nuevas es 1 y su costo es 0. Se comprueba que hay un peso mínimo de coincidencia bipartita perfecta en G si y solo si hay un flujo de costo mínimo en G ′ . [7] [ enlace muerto ]
Ver también
Referencias
- ↑ Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993). Flujos de red. Teoría, algoritmos y aplicaciones . Prentice Hall.
- ^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.
- ^Morton Klein (1967). "Un método primordial para flujos de costo mínimo con aplicaciones a los problemas de asignación y transporte". Ciencias de la gestión . 14 (3): 205–220. CiteSeerX 10.1.1.228.7696 . doi : 10.1287 / mnsc.14.3.205 .
- ^Andrew V. Goldberg y Robert E. Tarjan (1989). "Encontrar circulaciones de coste mínimo cancelando ciclos negativos". Revista de la ACM . 36 (4): 873–886. doi : 10.1145 / 76359.76368 .
- ^Jack Edmonds y Richard M. Karp (1972). "Mejoras teóricas en eficiencia algorítmica para problemas de flujo de red". Revista de la ACM . 19 (2): 248–264. doi : 10.1145 / 321694.321699 .
- ^Andrew V. Goldberg y Robert E. Tarjan (1990). "Encontrar circulaciones de mínimo coste por aproximación sucesiva". Matemáticas. Oper. Res . 15 (3): 430–466. doi : 10.1287 / moor.15.3.430 .
- ^James B. Orlin (1997). "Un algoritmo simplex 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 MCFClass C ++ con un flujo de costo mínimo y algoritmos de ruta más corta