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 hasta un almacén donde la red de carreteras tenga 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 similares pueden plantearse como un problema de flujo de costo mínimo y también pueden resolverse eficientemente utilizando el algoritmo simplex de red .

Definición

Una red de flujo es un gráfico dirigido con un vértice de origen y un vértice de sumidero , 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 . ${\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 costo total del flujo en todos los bordes:

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

con las limitaciones

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 de costo mínimo máximo .

Con algunas soluciones, encontrar el flujo máximo de costo mínimo es sencillo. De lo contrario, se puede encontrar el flujo 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. Esto se logra estableciendo el límite inferior en todos los bordes en cero y luego creando un borde adicional desde el sumidero hasta la fuente , con capacidad y límite inferior , lo que obliga al flujo total de a a también ser . ${\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 de flujo de costo mínimo (proporcionamos, a su vez, breves bosquejos de cada reducción aplicable): ^[1]

• Problema del camino más corto (fuente única). Requerir que una solución factible al problema de flujo de costo mínimo envíe una unidad de flujo desde una fuente designada a un sumidero designado . Dale a todos los bordes una capacidad infinita. ${\displaystyle s}$ ${\displaystyle t}$
• Problema de caudal máximo . Dejemos que todos los nodos tengan demanda cero y que el costo asociado con atravesar cualquier borde sea cero. Ahora, introduzca una nueva arista desde el sumidero actual hasta la fuente actual . Estipule que el costo unitario de enviar flujo a través del borde sea igual a y permita una capacidad infinita. (Esta reducción también se menciona en Problema de circulación ). ${\displaystyle (t,s)}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle (t,s)}$ ${\displaystyle -1}$ ${\displaystyle (t,s)}$
• Problema de asignación . Supongamos que cada partición establecida en la bipartición tiene vértices y denota la bipartición por . Dar cada oferta y dar cada demanda . Cada borde 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; para un estudio completo, consulte ^[2] . 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. ^[3]
• Cancelación de corte : un método dual general. ^{[4] [5]}
• Cancelación del ciclo medio mínimo : un algoritmo simple fuertemente polinomial . ^[6]
• Camino más corto sucesivo y escalamiento de capacidad : métodos duales, que pueden verse como la generalización del algoritmo Ford-Fulkerson . ^[7]
• Escalado de costos : un enfoque dual primario, que puede verse como la generalización del algoritmo push-relabel . ^[8]
• Algoritmo simplex de red : una versión especializada del método simplex de programación lineal . ^[9]
• Algoritmo fuera de lugar de DR Fulkerson

Solicitud

Coincidencia bipartita de peso mínimo

Reducir la coincidencia bipartita de peso mínimo con el problema de flujo máximo de costo mínimo

Dado un gráfico bipartito G = ( A ∪ B , E ) , el objetivo es encontrar la cardinalidad máxima coincidente 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 coincidencia bipartita de peso mínimo o problema de asignación consiste en encontrar una coincidencia 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 ) . Asigne la capacidad de todas las aristas en E′ a 1. Agregue un vértice fuente s y conéctelo a todos los vértices en A′ y agregue un vértice sumidero t y conecte 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 coincidencia bipartita perfecta de peso mínimo en G si y solo si existe un flujo de costos mínimo en G′ . ^{[10] [ enlace muerto ]}

Ver también

• LIMÓN (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 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. 
3. ^ Rafael Hassin (1983). "El problema del flujo de costo mínimo: un enfoque unificador de los algoritmos existentes y un nuevo algoritmo de búsqueda de árboles". 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 cortes fuertemente polinomiales para un flujo de red de costo mínimo". Matemática Aplicada Discreta . 4 : 133–165. doi : 10.1016/0166-218x(93)90025-j .
5. ^ Andrew V. Goldberg y Robert E. Tarjan (1989). "Encontrar circulaciones de mínimo coste 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 coste mínimo por aproximaciones sucesivas". 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 simplex de red primaria 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