Tenemos el conocido problema de flujo máximo o maximal: ¿cuál es la tasa mayor a la cual el material puede ser transportado de la fuente al sumidero sin violar ninguna restricción de capacidad?
En otras palabras, el problema consiste en determinar la máxima capacidad de flujo que puede ingresar a través de la fuente y salir por el nodo de destino.
El procedimiento para obtener el flujo máximo de una red, consiste en seleccionar repetidas veces cualquier trayectoria de la fuente al destino y asignar el flujo máximo posible en esa trayectoria.
Capacidad residual: es la capacidad adicional de flujo que un arco puede llevar:
§ Dada una red de flujo máximo, plantee la red residual asociada.
§ Encuentre la trayectoria de la fuente al destino con capacidad de flujo estrictamente positivo (si no existe alguno, es por que se ha encontrado el óptimo).
§ Examine estas trayectorias para encontrar la rama o arco con la menor capacidad de flujo restante e incremente en éste valor, la capacidad del flujo en sentido contrario.
§ Determine todas las trayectorias estrictamente positivas, hasta que no se permita flujo del nodo a un nodo destino.
Podemos, mediante el Algoritmo de Ford-Fulkerson, encontrar el flujo máximo de una red.
En el siguiente video podremos ver de manera mas detallada como funciona el algoritmo de flujo maximo.
No hay comentarios:
Publicar un comentario