Problema de flujo máximo

En la teoría de la optimización , los problemas de caudal máximo implican encontrar un caudal factible a través de una red de caudal que obtenga el caudal máximo posible.

El problema de flujo máximo puede verse como un caso especial de problemas de flujo de red más complejos, como el problema de circulación . El valor máximo de un flujo st (es decir, el flujo desde la fuente s al sumidero t) es igual a la capacidad mínima de un corte st (es decir, el corte seccionando s desde t) en la red, como se indica en el flujo máx. teorema de corte .

El problema de flujo máximo fue formulado por primera vez en 1954 por TE Harris y FS Ross como un modelo simplificado del flujo de tráfico ferroviario soviético. ^{[1] [2] [3]}

En 1955, Lester R. Ford, Jr. y Delbert R. Fulkerson crearon el primer algoritmo conocido, el algoritmo Ford-Fulkerson . ^{[4] [5]} En su artículo de 1955, ^[4] Ford y Fulkerson escribieron que el problema de Harris y Ross se formula de la siguiente manera (ver ^[1] p. 5):

Considere una red ferroviaria que conecta dos ciudades a través de varias ciudades intermedias, donde cada enlace de la red tiene asignado un número que representa su capacidad. Suponiendo una condición de estado estable, encuentre un flujo máximo de una ciudad determinada a la otra.

Fue planteado a los autores en la primavera de 1955 por TE Harris, quien, junto con el general FS Ross (Ret.), Había formulado un modelo simplificado de flujo de tráfico ferroviario, y señaló este problema particular como el central sugerido por el modelo [11].

Red de flujo para el problema: cada ser humano (r i ) está dispuesto a adoptar un gato (w i 1) y / o un perro (w i 2). Sin embargo, cada mascota (p i ) tiene preferencia por solo un subconjunto de los humanos. Encuentre cualquier coincidencia de mascotas con humanos de manera que el número máximo de mascotas sea adoptado por uno de sus humanos preferidos.

Una red de flujo, con fuente sy sumidero t . Los números al lado del borde son las capacidades.

Fig. 4.1.1. Transformación de un problema de flujo máximo de múltiples fuentes y múltiples sumideros en un problema de flujo máximo de un solo sumidero y una sola fuente

Fig. 4.3.1. Transformación de un problema de emparejamiento bipartito máximo en un problema de flujo máximo

Fig. 4.4.1. Transformación de un problema de flujo máximo con restricción de capacidades de vértice en el problema de flujo máximo original mediante división de nodos

Construcción de flujo de red para el problema de eliminación de béisbol.

Imagen original de tamaño 8x8.

Red construida a partir del mapa de bits. La fuente está a la izquierda, el fregadero a la derecha. Cuanto más oscuro es un borde, mayor es su capacidad. a _i es alto cuando el píxel es verde, b _i cuando el píxel no es verde. Las penas p _ij son todas iguales. ^[24]

Corte mínimo mostrado en la red (triángulos VS círculos).