Problema de flujo de red - Network flow problem
En la optimización combinatoria , los problemas de flujo de red son una clase de problemas computacionales en los que la entrada es una red de flujo (un gráfico con capacidades numéricas en sus bordes), y el objetivo es construir un flujo , valores numéricos en cada borde que respeten la capacidad. restricciones y que tienen un flujo entrante igual al flujo saliente en todos los vértices excepto en ciertas terminales designadas.
Los tipos específicos de problemas de flujo de red incluyen:
- El problema de flujo máximo , en el que el objetivo es maximizar la cantidad total de flujo que sale de las terminales fuente y entra en las terminales del sumidero.
- El problema de flujo de costo mínimo , en el que los bordes tienen costos además de capacidades y el objetivo es lograr una cantidad determinada de flujo (o un flujo máximo) que tenga el costo mínimo posible
- El problema del flujo de múltiples productos básicos , en el que se deben construir flujos múltiples para diferentes productos cuyas cantidades de flujo total juntas respetan las capacidades.
- Flujo en ninguna parte cero , un tipo de flujo estudiado en combinatoria en el que las cantidades de flujo están restringidas a un conjunto finito de valores distintos de cero.
El teorema de corte mínimo de flujo máximo equipara el valor de un flujo máximo con el valor de un corte mínimo , una partición de los vértices de la red de flujo que minimiza la capacidad total de los bordes que se cruzan de un lado de la partición al otro. Los teoremas aproximados de flujo máximo y corte mínimo proporcionan una extensión de este resultado a los problemas de flujo de múltiples productos básicos. El árbol de Gomory-Hu de una red de flujo no dirigido proporciona una representación concisa de todos los cortes mínimos entre diferentes pares de vértices terminales.
Los algoritmos para construir flujos incluyen
- Algoritmo de Dinic , un algoritmo fuertemente polinomial para un flujo máximo
- El algoritmo de Edmonds-Karp , un algoritmo fuertemente polinomial más rápido para un flujo máximo
- El algoritmo de Ford-Fulkerson , un algoritmo codicioso para el flujo máximo que en general no es fuertemente polinomial
- El algoritmo de red simplex , un método basado en programación lineal pero especializado para el flujo de red
- El algoritmo fuera de lugar para un flujo de costo mínimo
- El algoritmo de flujo máximo push-rebelde , una de las técnicas conocidas más eficientes para el flujo máximo
De lo contrario, el problema puede formularse como un programa lineal más convencional o similar y resolverse utilizando un solucionador de optimización de propósito general.
|
Este artículo incluye una lista de elementos relacionados que comparten el mismo nombre (o nombres similares). Si un enlace interno lo condujo incorrectamente aquí, es posible que desee cambiar el enlace para que apunte directamente al artículo deseado. |
