Hispanopedia WikiEn 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 las restricciones de capacidad y que tengan un flujo entrante igual al flujo saliente en todos los vértices excepto en ciertas terminales designadas. [1]
Los tipos específicos de problemas de flujo de red incluyen:
- El problema del flujo máximo , en el que el objetivo es maximizar la cantidad total de flujo que sale de las terminales de origen y entra en las terminales de destino [1] : 166–206
- El problema del flujo de costo mínimo , en el que los bordes tienen costos además de capacidades y el objetivo es lograr una cantidad dada de flujo (o un flujo máximo) que tenga el costo mínimo posible [1] : 294–356
- El problema del flujo de múltiples productos , en el que se deben construir múltiples flujos para diferentes productos cuyos montos de flujo totales en conjunto respeten las capacidades [1] : 649–694
- Flujo sin 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 cruzan de un lado de la partición al otro. Los teoremas aproximados de corte mínimo de flujo máximo proporcionan una extensión de este resultado a los problemas de flujo de múltiples productos. 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 el caudal máximo [1] : 221–223
- El algoritmo Edmonds-Karp , un algoritmo fuertemente polinomial más rápido para el flujo máximo
- El algoritmo de Ford-Fulkerson , un algoritmo voraz para el flujo máximo que en general no es fuertemente polinomial
- El algoritmo símplex de red , un método basado en programación lineal pero especializado para el flujo de red [1] : 402–460
- El algoritmo desequilibrado para el flujo de costo mínimo [1] : 326–331
- El algoritmo push-relabel de flujo máximo , una de las técnicas más eficientes conocidas 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.
Referencias
- ^ abcdefg Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Flujos de red: teoría, algoritmos y aplicaciones . Prentice Hall.
Si un enlace interno lo llevó aquí por error, puede cambiar el enlace para que apunte directamente al artículo deseado.
