Problema de flujo máximo

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 29 de septiembre de 2020; las comprobaciones requieren 11 ediciones .

En la teoría de la optimización y la teoría de grafos , el problema del flujo máximo es encontrar un flujo tal a través de la red de transporte que la suma de los flujos desde la fuente o, de manera equivalente, la suma de los flujos hacia el sumidero, sea máxima.

El problema de flujo máximo es un caso especial de problemas más difíciles, como el problema de circulación .

Historia

Después de la entrada de los Estados Unidos en la Segunda Guerra Mundial en 1941, el matemático George Bernard Dantzig se unió a la oficina de estadísticas de la Fuerza Aérea de los Estados Unidos en Washington DC . De 1941 a 1946 dirigió la Rama de Análisis de Combate, donde trabajó en varios problemas matemáticos. [1] [2] Posteriormente, utilizando el trabajo de Danzig, el problema del flujo máximo se resolvió por primera vez durante la preparación del puente aéreo durante el bloqueo de Berlín Occidental , que tuvo lugar en 1948-1949. [3] [4] [5]

En 1951, George Dantzig formuló por primera vez el problema en términos generales. [6]

En 1955, Lester Ford y Delbert Ray Fulkerson construyeron por primera vez un algoritmo diseñado específicamente para resolver este problema . Su algoritmo se llamó algoritmo Ford-Fulkerson . [7] [8]

En el futuro, la solución del problema se mejoró muchas veces.

En 2010, los investigadores Jonathan Kelner y Aleksander Mądry del MIT , junto con sus colegas Daniel Spielman de la Universidad de Yale y Shen- Hua Teng de la Universidad del Sur de California demostraron otra mejora del algoritmo por primera vez en 10 años. [3] [9] [10]

Definición

Dada una red de transporte con fuente , sumidero y capacidad . ${\ estilo de visualización N = (V, E)}$ ${\ estilo de visualización s \ en V}$ ${\ estilo de visualización t \ en V}$ ${\ estilo de visualización c}$

El valor de flujo es la suma de los flujos de la fuente . En el artículo “ Red de transporte ” se demuestra que es igual a la suma de los caudales al desagüe .

{\ estilo de visualización | f | = \ suma _ {v \ en V} f_ {sv}}

\ \sum _{{w\in V}}f(w,t)

El problema del flujo máximo es encontrar tal flujo, donde el valor del flujo es máximo.

Decisiones

La siguiente tabla enumera algunos algoritmos para resolver el problema.

Método	Complejidad	Descripción
Programación lineal	Depende del algoritmo específico. Para el método simplex, es exponencial.	Presente el problema de flujo máximo como un problema de programación lineal. Las variables son los flujos a lo largo de los bordes y las restricciones son la preservación del flujo y la limitación del rendimiento.
Algoritmo de Ford-Fulkerson	Depende del algoritmo de búsqueda de ruta de aumento. Requiere tales búsquedas. $O(\max \|f\|)$	Encuentre cualquier ruta de aumento. Aumentar el caudal en todos sus bordes al mínimo de sus capacidades residuales. Repita siempre que haya una ruta de aumento. El algoritmo solo funciona para anchos de banda enteros. De lo contrario, puede ejecutarse indefinidamente sin converger a la respuesta correcta.
Algoritmo de Edmonds-Karp	$O(\|V\|\|E\|^{2})$	Ejecutamos el algoritmo de Ford-Fulkerson, eligiendo cada vez la ruta de aumento más corta (encontrada por búsqueda en amplitud ).
algoritmo de Dinit	$O(\|V\|^{2}\|E\|)$ o para capacidades unitarias utilizando árboles dinámicos de Slethor y Tarjan [11] $O(\|V\|\surd \|E\|)$ $O(\|V\|\|E\|\log(\|V\|))$	Mejora del algoritmo de Edmonds-Karp (pero encontrado cronológicamente antes). En cada iteración, utilizando la búsqueda primero en amplitud, determinamos las distancias desde la fuente hasta todos los vértices en la red residual. Construimos un gráfico que contiene solo los bordes de la red residual en los que esta distancia aumenta en 1. Excluimos del gráfico todos los vértices sin salida con bordes incidentes en ellos, hasta que todos los vértices se conviertan en no sin salida. (Un callejón sin salida es un vértice, a excepción de la fuente y el sumidero, que no incluye un solo borde o del que no emanan bordes). En el gráfico resultante, encontramos el camino de aumento más corto (será cualquier camino desde s a t). Excluimos el borde con la capacidad mínima de la red residual, nuevamente excluimos los vértices sin salida, y así sucesivamente hasta que haya una ruta de aumento.
Algoritmo de empuje de preflujo	$O(\|V\|^{2}\|E\|)$	Opera en un preflujo en lugar de una corriente. La diferencia es que para cualquier vértice u, a excepción de la fuente y el sumidero, la suma de los flujos que ingresan para el flujo debe ser estrictamente cero (la condición de conservación del flujo) y para el preflujo debe ser no negativa. Esta suma se llama exceso de flujo al vértice, y un vértice con un exceso de flujo positivo se dice que se desborda . Además, para cada vértice, el algoritmo guarda una característica adicional, la altura , que es un número entero no negativo. El algoritmo utiliza dos operaciones: push , cuando el flujo a lo largo de un borde que va de un vértice superior a un vértice inferior aumenta en la cantidad máxima posible, y lift , cuando se eleva un vértice desbordado, desde el cual es imposible empujar debido a una altura insuficiente. . El empuje es posible cuando un borde pertenece a la red residual, conduce de un vértice superior a uno inferior y el vértice original se desborda. El levantamiento es posible cuando el vértice que se levanta está lleno, pero ninguno de los vértices a los que conducen los bordes de la red residual es más bajo que él. Se realiza hasta una altura superior en 1 al mínimo de las alturas de estos vértices. Inicialmente, la altura de la fuente es V, a lo largo de todos los bordes que emanan de la fuente, fluye el flujo máximo posible y las alturas y flujos restantes son cero. Las operaciones de empuje y elevación se realizan el mayor tiempo posible.
Algoritmo "subir al principio"	$O(\|V\|^{3})$ o usando árboles dinámicos $O(\|V\|\|E\|\log(\|V\|^{2}/\|E\|))$	Una variante del algoritmo anterior que define el orden de las operaciones de empujar y levantar de manera especial.
Algoritmo de flujo de bloqueo binario [1]	$O(\|E\|\min\{\|V\|^{2/3},\surd {\|E\|}\}\log(\|V\|^{2}/\|E\|)\log(\ máximo \|f\|))$

Para obtener una lista más detallada, consulte [2] y Lista de algoritmos para encontrar el flujo máximo .

Todo el teorema del flujo

Si los rendimientos son enteros, el flujo máximo también es entero.

El teorema se sigue, por ejemplo, del teorema de Ford-Fulkerson .

Generalizaciones que reducen al problema original

Algunas generalizaciones del problema de flujo máximo se reducen fácilmente al problema original.

Número arbitrario de fuentes y/o sumideros

Si hay más de una fuente, agregue un nuevo vértice S, que hacemos la única fuente. Añadimos aristas con capacidad infinita desde S a cada una de las fuentes antiguas.

De manera similar, si hay más de un sumidero, agregamos un nuevo vértice T, que hacemos el único sumidero. Agregamos bordes con capacidad infinita de cada uno de los fregaderos antiguos a T.

Bordes no dirigidos

Cada arista no dirigida (u, v) se reemplaza por un par de aristas dirigidas (u, v) y (v, u).

Límite de ancho de banda de vértice

Dividimos cada vértice v con capacidad limitada en dos vértices v in y v out . Todos los bordes incluidos en v antes de dividir ahora se incluyen en v en . Todos los bordes que se originaron en v antes de dividirse ahora se originan en v out . Agregue un borde (v in , v out ) con capacidad . $CV}$ $CV}$

Limitando la capacidad de los bordes desde abajo

En esta versión del enunciado del problema, el valor del flujo de cada borde está adicionalmente limitado desde abajo por la función . Por lo tanto, el valor de flujo para cualquier borde no puede exceder su capacidad, pero no puede ser inferior al mínimo especificado, es decir . Para resolver el problema, es necesario transformar la red de transporte original en una red de transporte de la siguiente manera: ${\displaystyle c'\dos puntos E\to \mathbb {N} ^{+))$ $c'(e)\leqslant f(e)\leqslant c(e)$ $G=(V,E,s,t,c,c')$ $G'=(V',E',s',t',c'')$

Agregar nueva fuente y sumidero . $s'$ $t'$
Para cada borde : $(v,w)$
1. Crea dos nuevos vértices y . $X$ $y$
2. Instalar y . $c''(v,x)=c(v,w)$ $c''(y,w)=c(v,w)$
3. instalar _ $c''(x,y)=c(v,w)-c'(v,w)$
4. Instalar y . $c''(s',y)=c'(v,w)$ ${\ estilo de visualización c''(x,t')=c'(v,w)}$
instalar _ $c''(t,t')=c''(s,s')=\sum_{e\in E}c(e)$

Se define un flujo en B que cumple la condición de limitar el caudal de bordes desde abajo si y sólo si se define un flujo máximo en el que todos los bordes de la forma y están "saturados". Gracias a esta construcción, el algoritmo para encontrar un flujo acotado por abajo será el siguiente: $GRAMO$ $GRAMO'$ ${\ estilo de visualización (s', y)}$ ${\ estilo de visualización (x, t')}$

Desde la construcción . $GRAMO$ $GRAMO'$
Encuentre el flujo del gráfico , prefiriendo los bordes de la forma y . $F'$ $GRAMO'$ ${\ estilo de visualización (s', y)}$ ${\ estilo de visualización (x, t')}$
Si , ¿dónde está el flujo del gráfico en el que se omite el ancho de banda de los bordes de abajo, entonces no hay solución. $f'<f''+\sum_e\in E(G)}c'(e)$ $F''$ $GRAMO$
De lo contrario, calcule el flujo a partir de flow , es decir . $F$ $F'$ ${\ estilo de visualización f (a, b) = f (a, x)}$

Limitando la capacidad del borde desde abajo con una alternativa

Esta variante del problema es idéntica a la anterior, con la diferencia de que el valor de caudal para cada arista también puede ser igual a , es decir o . A pesar de un ligero cambio en la condición, no hay solución polinomial para este problema si las clases P y NP no son iguales . Como prueba de la afirmación, se puede dar una reducción polinomial al problema Exact-3-SAT . ${\ estilo de visualización 0}$ $c'(e)\leqslant f(e)\leqslant c(e)$ ${\ estilo de visualización f (e) = 0}$

Véase también

Notas

↑ John J. O'Connor y Edmund F. Robertson . George Dantzig (inglés) es una biografía del archivo MacTutor .
↑ Cottle, Richard; Johnson, Ellis; Wets, Roger, "George B. Dantzig (1914-2005)" Archivado el 7 de septiembre de 2015 en Wayback Machine , Notices of the American Mathematical Society , v.54, no.3, marzo de 2007. Cf. p.348
↑ 1 2 Hardesty, Larry, "Primera mejora del algoritmo fundamental en 10 años" Archivado el 28 de marzo de 2014 en Wayback Machine , Oficina de noticias del MIT, 27 de septiembre de 2010
↑ Borndorfer, Ralf; Grotschel, Martín; Löbel, Andreas, "Alcuin's Transportation Problems and Integer Programing" Archivado el 7 de agosto de 2011 en Wayback Machine , Konrad-Zuse-Zentrum für Informationstechnik , Berlín, Alemania, noviembre de 1995. Cf. p.3
↑ Powell, Stewart M., "The Berlin Airlift" , Air Force Magazine , junio de 1998.
↑ Dantzig, GB, "Aplicación del método Simplex a un problema de transporte" Archivado el 19 de julio de 2010 en Wayback Machine , en TC Koopman (ed.): Activity Analysis and Production and Allocation , Nueva York, (1951) 359-373.
↑ Ford, LR, Jr.; Fulkerson, DR, "Flujo máximo a través de una red", Canadian Journal of Mathematics (1956), pp.399-404.
↑ Ford, LR, Jr.; Fulkerson, DR, Flows in Networks , Princeton University Press (1962).
↑ Kelner, Jonathan, "Flujos eléctricos, sistemas laplacianos y aproximación más rápida del flujo máximo en gráficos no dirigidos" Archivado el 24 de junio de 2011 en Wayback Machine , charla en CSAIL, MIT, martes 28 de septiembre de 2010
↑ Flujos eléctricos, sistemas laplacianos y aproximación más rápida del flujo máximo en gráficos no dirigidos Archivado el 29 de noviembre de 2010 en Wayback Machine , por Paul Cristiano et al., 19 de octubre de 2010.
↑ Algoritmo Dinits . Consultado el 28 de octubre de 2010. Archivado desde el original el 7 de mayo de 2015. (indefinido)

Literatura

Schrijver, Alexander, "Sobre la historia del transporte y los problemas de flujo máximo" , Programación matemática 91 (2002) 437-445
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmos: construcción y análisis = Introducción a los Algoritmos / Ed. I. V. Krasikova. - 2ª ed. - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 . . capitulo 26
↑ Andrew V. Goldberg y S. Rao . Más allá de la barrera de descomposición del flujo (neopr.) // J. Assoc. computar Mach.. - 1998. - T. 45 . - S. 753-782 . -doi : 10.1145/ 290179.290181.
↑ Andrew V. Goldberg y Robert E. Tarjan . Un nuevo enfoque al problema del flujo máximo (inglés) // Journal of the ACM : journal. - ACM Press, 1988. - vol. 35 , núm. 4 . - Pág. 921-940 . — ISSN 0004-5411 . -doi : 10.1145/ 48014.61051.
↑ Joseph Cheriyan y Kurt Mehlhorn . Un análisis de la regla de selección de más alto nivel en el algoritmo de preflujo-impulso de flujo máximo // Cartas de procesamiento : diario. - 1999. - vol. 69 , núm. 5 . - pág. 239-242 . - doi : 10.1016/S0020-0190(99)00019-8 .
↑ Daniel D. Sleator y Robert E. Tarjan . Una estructura de datos para árboles dinámicos (inglés) // Journal of Computer and System Sciences : diario. - 1983. - vol. 26 , núm. 3 . - Pág. 362-391 . — ISSN 0022-0000 . - doi : 10.1016/0022-0000(83)90006-5 .
↑ Daniel D. Sleator y Robert E. Tarjan . Árboles de búsqueda binarios autoajustables (inglés) // Journal of the ACM : journal. - ACM Press, 1985. - vol. 32 , núm. 3 . - Pág. 652-686 . — ISSN 0004-5411 . -doi : 10.1145/ 3828.3835.
Eugenio Lawler 4. Flujos de Red // Optimización Combinatoria: Redes y Matroides (Inglés) . - Dover, 2001. - Pág. 109-177. — ISBN 0486414531 .