Problema De Flujo Maximo
Enviado por Anyluu • 11 de Febrero de 2013 • 897 Palabras (4 Páginas) • 968 Visitas
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
...