Flujo Maximo - Grupo 3

FLUJO MÁXIMO

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 intermedio y cada arco posee una capacidad que no puede ser excedida y esta no necesariamente debe ser la misma en cada dirección del arco.

Entonces, si se considera una red con un nodo de entrada y un nodo de salida un problema de flujo máximo plantea ¿Cuál es la cantidad de máxima de la variable en estudio que puede circular por los arcos desde el origen hasta el destino?

El objetivo es determinar el patrón 

factible de flujo a través de la red

 que maximice el flujo total 

desde el origen hasta el destino

Características de los problemas de flujo máximo

—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 y esta no necesariamente es la misma en cada dirección 

Tipo de problema

Considere una red con un nodo de origen y uno de destino.

El problema de flujo máximo plantea:

Ejemplo: Flujo Máximo de Vehículos

Una ciudad es atravesada por una red interestatal de carreteras de norte a sur que le permite alcanzar un nivel de 15000 vehículos/hora en el horario pico. 

Debido a un programa de mantenimiento general, el cual exige cerrar dichas vías, un grupo de ingenieros ha propuesto una red de rutas alternas para cruzar la ciudad de norte a sur la cual incorpora avenidas importantes 

1.- ¿Puede la red dar cabida a un flujo máximo de 15000 vehículos por hora de norte a sur?

2.- ¿Cuál es el flujo máximo de vehículos que permite la red cada hora?

3.- ¿Qué flujo se debe canalizar sobre cada rama?

Solucion:

Para este caso se puede realizar una simplificacion del diagrama para evitar numeros grandes y sea mas sencillo el calculo. Al tener el problema resuelto se deben tener en cuenta los miles que se estan simplificando

   Para resolver el problema de flujo máximo propuesto se puede utilizar el TORA

En la sección de “network models” se encuentra la opción “Maximal flow” que es flujo máximo. 

De entrada se deben especificar el nombre del problema y la cantidad de nodos. Y para continuar presionar ENTER

en este caso se tienen el nodo de origen, el de destino y 5 mas para un total de 7 nodos

 Posterior a esto se ingresa a la tabla donde se cargan todos los datos inherentes al problema: nombre de los nodos y cantidades que pueden transitar de uno a otro. Es importante estar atentos si la cantidad de vehículos que pueden transitar de norte a sur es la misma en sentido inverso, para simplificar indicándole al TORA que el problema es simétrico.

se colocan las cantidades de vehiculos que pueden viajar desde el nodo i (columnas) hacia el nodo j (filas). El diagrama indica que del norte al N2 pueden viajar 5 (mil) vehiculos, y de la misma manera se obtienen las cantidades para el resto de los trayectos

Al haber completado todos los datos se hace click en "solve menu" y si se desea guardar la data cargada puede hacerlo. Saldran dos opciones de mostrar la solucion: Maximum Flows e Iterations. Como lo que deseamos saber es el FLUJO MAXIMO se selecciona la primera opcion

 Finalmente se muestra que el máximo flujo de vehículos que pueden transitar son     
14 (mil). Con dicha respuesta se pueden contestar las tres interrogantes:

1.- ¿Puede la red propuesta dar cabida a un flujo máximo de 15000 vehículos por hora de norte a sur?

No, dado que solo soporta un flujo máximo de 14 mil

2.- ¿Cual es  el flujo máximo de vehículos  que permite la red a cada hora?

14000 vehículos por hora.

3.- ¿Qué flujo se debe canalizar en cada vía?

Se deben ver los flujos para cada tramo que calculó el TORA y realizar el diagrama

Es de mucha utilidad el saber resolver problemas de flujo máximo para así poder aprovechar al maximo todas las condiciones dadas en cada situación

Autoras:

Steffany De Andrade

Gerines Faneite

Adriana González

Leidy Henriques