Flujo Mínimo
En este apartado es el estudiar un mínimo de cantidad que puede pasar por el arco, que es exactamente a la inversa del problema de flujo máximo.
Existen situaciones donde, a menudo, se desean transportar cantidades mínimas de flujo, de un punto de partida (Inicio) a un punto terminal (Final). A estos problemas se le denomina PROBLEMAS DE FLUJO MÍNIMO y se puede describir de la siguiente manera:
-
Todo flujo a través de una red conexa dirigida, se origina de un nodo llamado fuente (nodo oferta) y termina en otro llamado destino (nodo demanda). Los nodos restantes son nodos de transbordo.
-
El flujo que va de un arco, se dirije en la dirección de la flecha, donde la capacidad del arco debe estar definida.
-
El objetivo es minimizar la cantidad total de flujo que va del origen al destino.
-
En el nodo fuente, todos los arcos salen de él.
-
En el nodo destino, todos los arcos llegan a él.
-
Minimizar la cantidad total de flujo que va del origen al destino.
Algunas aplicaciones son:
-
Distribución de bienes, desde sus fábricas hasta sus clientes.
-
Flujo de petróleo por un sistema de tubería.
-
Flujo de agua en un sistema de ductos.
-
Flujo de autos en un sistema de transporte.
Los métodos por los cuales se pueden resolver estos tipos de problemas son:
-
Ford y Fulkerson.
-
Flujo mínimo.
La red debe cumplir con:
-
Ser una red dirigida.
-
Ser una red conexa.
-
Tener un solo nodo inicial.
-
Tener un solo nodo terminal.
