Problema De Flujo Maximo

MARCO TEORICO

MODELOS DE REDES: PROBLEMA DE FLUJO MAXIMO

El problema de flujo máximo pregunta: ¿cuál es la cantidad máxima de vehículos, liquido, peatones o llamadas telefónicas que pueden entrar o salir del sistema en un periodo determinado de tiempo?

En términos generales el problema de flujo máximo se puede describir como sigue:

1. Todo flujo a través de una red conexa dirigida se origina en un nodo llamado fuente y termina en otro nodo llamado destino.

2. Los nodos restantes son nodos de transbordo.

3. Se permite el flujo a través de un arco solo en la dirección indicada por la flecha, donde la cantidad máxima de flujo esta dada por la capacidad del arco, en la fuente todos los arcos señalan hacia afuera, en el destino, todos señalan hacia el nodo.

4. El objetivo es maximizar la cantidad de flujo de la fuente al destino. Esta cantidad se mide en cualquiera de sus dos cantidades equivalentes, esto es, la cantidad que sale de la fuente o la cantidad que entra al destino.

Algunas aplicaciones comunes del problema de flujo máximo son:

• Maximizar el flujo a través de la red de distribución de la compañía de sus fábricas a sus clientes.

• Maximizar el flujo a través de la red de suministros de la compañía de proveedores a sus fábricas.

• Maximizar el flujo de petróleo por un sistema de tuberías.

• Maximizar el flujo de agua a través de un sistema de acueductos.

• Maximizar el flujo de vehículos por una red de transporte.

ALGORITMO DE LA TRAYECTORIA DE AUMENTO PARA EL PROBLEMA DE FLUJO MAXIMO

El problema de flujo máximo se puede formular como un problema de programación lineal, se puede resolver con el método simplex y/o con algún tipo de software. Sin embargo se dispone de un algoritmo de trayectoria aumentadas mucho mas eficiente. Este algoritmo se basa en dos conceptos intuitivos, el de una red residual y el de una trayectoria aumentada.

Una vez que se han asignado flujo a los arcos de la red original, la red residual muestra las capacidades restantes (llamadas capacidades residuales) para asignar flujos adicionales. El número sobre el arco junto a un nodo da la capacidad residual para el flujo desde ese nodo hasta el otro nodo. La trayectoria de aumento es una trayectoria dirigida del nodo fuente al nodo destino en la red residual, tal que todos los arcos de esta trayectoria tienen capacidad residual estrictamente positiva. El mínimo de estas capacidades residuales se llama capacidad residual de la trayectoria de aumento porque representa la cantidad de flujo que es factible agregar en toda la trayectoria. Por lo tanto cada trayectoria se aumento proporciona una oportunidad de aumentar mas el flujo a través de la red original.

En resumen, cada iteración del algoritmo consiste en los tres pasos siguientes:

1. Se identifica una trayectoria de aumento encontrando alguna trayectoria dirigida del origen al destino en la red residual, tal que cada arco sobre esta trayectoria tiene capacidad residual estrictamente positiva. (si no existe una, los flujos netos asignados constituyen un patrón de flujo óptimo).

2. Se identifica la capacidad residual c* de esta trayectoria de aumento encontrando el mínimo de las capacidades residuales de los arcos sobre esta trayectoria. Se aumenta en c* el flujo de esta trayectoria.

3. Se disminuye en c* la capacidad residual de cada arco en esta trayectoria de aumento. Se aumenta en c* la capacidad residual de cada arco en la dirección opuesta en esta trayectoria. Se regresa al paso 1.

PROBLEMA DE FLUJO MAXIMO

Una ciudad es atravesada por una red interestatal de carreteras de norte a sur. Debido a que 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.

¿Cuál es el flujo máximo de vehículos que permite la red por hora? Encuentre el patrón de flujo de vehículos por hora que da el flujo máximo del nodo origen al nodo destino, dado que la capacidad a través del arco que va del nodo i al nodo j es el numero mas cercano (en miles de vehículos) al nodo i del arco entre estos nodos.

SOLUCION

Según el planteamiento de este problema el objetivo es encontrar la máxima cantidad de flujo de vehículos por hora que salga del nodo origen al nodo destino sin exceder la capacidad de los arcos.

Sea

m(i): origen

n(j): destino

Sea X0 la cantidad total de vehículos por hora que transita de norte a sur en la ciudad.

Xij: el flujo de vehículos (miles) desde el nodo i hasta el nodo j

X12: los miles de vehículos que transitan por hora del nodo 1 al nodo 2

X13: los miles de vehículos que transitan por hora del nodo 1 al nodo 3

...