Problema De Flujo Maximo

5.4 Problema Flujo Máximo

Este modelo se utiliza para reducir los embotellamientos entre ciertos puntos de partida y destino en una red.

Existe un flujo que viaja desde un único lugar de origen hacia un único lugar de destino a través de arcos que conectan nodos intermedios.

Cada arco tiene una capacidad que no puede ser excedida.

La capacidad no debe ser necesariamente la misma para cada dirección del arco.

Considere una red con un nodo de entrada (o fuente) y un nodo de salida (o antifuente).

El problema del flujo máximo pregunta: vehículos, líquido, peatones o llamadas telefónicas que pueden entrar y salir del sistema en un periodo determinado de tiempo.

En este tipo de problemas se intenta conducir el flujo por las ramas o arcos

De la red en forma óptima, aunque dicho flujo está limitado por restricciones diversas tales como: condiciones de la carpeta asfáltica, diámetros de tubería, etc.

Al límite máximo de flujo de una rama se le denominara capacidad de flujo.

Se quiere transportar la máxima cantidad de flujo desde un punto de partida (fuente) a un punto final (pozo).

Al respecto diremos que existen muchos algoritmos especializados para dar solución a los problemas de flujo máximo.

Observación:

Se debe considerar una red dirigida.

Tiene una fuente y un pozo.

Los otros nodos son de trasbordo.

Capacidad de los arcos.

El objetivo es determinar el patrón factible de flujo a través de la red que maximice el flujo total desde la fuente de destino.

DEFINICIÓN DEL PROBLEMA

Existe un nodo origen (con el numero 1), del cual los flujos emanan.

Existe un nodo terminal (con el numero n), en el cual todos los flujos de la red son depositados.

Existen n-2 nodos (numerados del 2,3,…, n-1), en el cual el flujo que entra es igual al que sale.

La capacidad Cij que transita del nodo i al nodo j. y la capacidad Cji para la dirección opuesta.

El objetivo es encontrar la máxima cantidad de flujo que salga del nodo 1 al nodo n sin exceder la capacidad de los arcos.

El problema consiste en encontrar la máxima cantidad de flujo total que puede circular a través de la red en una unidad de tiempo.

El único requerimiento en ello es que para cada nodo (que no sea la fuente o el destino) la relación de equilibrio debe cumplirse:

Flujo que sale = Flujo que entra

Dicho en términos formales, siendo f= flujo, n= destino, I= origen:

Maximizar f sujeto a:

∑_j▒x_ij - ∑_j▒x_ji =

0≤x_ij ≤U_ij de la Red

∀_(i,j)

U_ij= capacidades en el flujo por unidad de tiempo de los diversos arcos.

El algoritmo de flujo maximo se fundamenta en pasos de sentido comun: encontrar un camino que inicie en la fuente y concluya en la antifuente, que tenga capacidad de flujo en el sentido deseado y mayor a cero para todas las ramas que integran el camino o ruta.

Debemos continuar buscando caminos que vayan de fuentes a depositos y que sigan teniendo capacidad mayor a cero para todas las ramas en el sentido del flujo.

PASOS DEL ALGORITMO PARA RESOLVER PROBLEMAS DE FLUJO MÁXIMO:

Encontrar un camino que vaya del origen al destino y que tenga capacidad mayor a cero en el sentido deseado.

Encontrar la rama de menor capacidad (Pf) del camino seleccionado en el paso anterior y programar el envio de dicha capacidad (Pf).

Para el camino elegido en el paso 1 reducir la cantidad Pf en las ramas involucradas y aumentar dicha cantidad en el sentido contrario.

Repetir

...