Flujo maximo
Páginas: 5 (1115 palabras)
Publicado: 5 de abril de 2010
Algoritmo de Ford-Fulkerson: El algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar el flujo, hasta que se alcance el flujo máximo.
La idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos origen y destino.
Consideraremos las capacidades iniciales del arco que une el nodo i y el nodo j como Cij y Cji . Estas capacidades inicialesirán variando a medida que avanza el algoritmo, denominaremos capacidades residuales a las capacidades restantes del arco una vez pasa algún flujo por él, las representaremos como cij y cji .
Para un nodo j que recibe el flujo del nodo i , definimos una clasificación [aj,i] donde aj es el flujo del nodo i al nodo j . Los pasos del algoritmo se definen como sigue:
Paso 1: Inicializamos lascapacidades residuales a las capacidades iniciales, hacemos (cij,cji)=(Cij,Cji) para todo arco de la red. Suponiendo el nodo 1 como el nodo origen, hacemos a1=∞ y clasificamos el nodo origen con [∞,-] . Tomamos i=1 y vamos al paso 2.
Paso 2: Determinamos Si como un conjunto que contendrá los nodos a los que podemos acceder directamente desde i por medio de un arco con capacidad positiva, y que noformen parte del camino en curso. Si Si contiene algún nodo vamos al paso 3, en el caso de que el conjunto sea vacío saltamos al paso 4.
Paso 3: Obtenemos kЄSi como el nodo destino del arco de mayor capacidad que salga de i hacia un nodo perteneciente a Si . Es decir, cik = max{cij} con jЄSi . Hacemos ak=cik y clasificamos el nodo k con [ak,i] . Si k es igual al nodo destino o sumidero,entonces hemos encontrado una ruta de penetración, vamos al paso 5. En caso contrario continuamos con el camino, hacemos i=k y volvemos al paso 2.
Paso 4 (retroceso): Si i=1 , estamos en el nodo origen, y como Si es vacío, entonces no podemos acceder a ningún nodo, ni encontrar algún nuevo camino, hemos terminado, vamos al paso 6.
En caso contrario, i≠1 , le damos al valor i el del nodo que se haclasificado inmediatamente antes, eliminamos i del conjunto Si actual y volvemos al paso 2.
Paso 5: Llegados a este paso tenemos un nuevo camino: Np={1,k1,k2,...,n} , esta será la p-ésima ruta de penetración desde el nodo origen al nodo destino. El flujo máximo a lo largo de esta ruta será la capacidad mínima de las capacidades residuales de los arcos que forman el camino, es decir:fp=min{a1,ak1,ak2,...,an} .
La capacidad residual de cada arco a lo largo de la ruta de penetración se disminuye por fp en dirección del flujo y se incrementa por fp en dirección inversa, es decir, para los nodos i y j en la ruta, el flujo residual se cambia de la (cij,cji) actual a (cij-fp,cji+fp) si el flujo es de i a j , o (cij+fp,cji-fp) si el flujo es de j a i Inicializamos i=1 y volvemos al paso 2para intentar una nueva ruta de penetración.
Paso 6 (solución): Una vez aquí, hemos determinado m rutas de penetración. El flujo máximo en la red será la suma de los flujos máximos en cada ruta obtenida, es decir: F=f1+f2+...+fm . Teniendo en cuenta que las capacidades residuales inicial y final del arco (i, j) las dan (Cij,Cji) y (cij,cji) respectivamente, el flujo máximo para cada arco secalcula como sigue: sea (α, β)=(Cij-cij, Cji-cji) , si α>0 , el flujo óptimo de i a j es α , de lo contrario, si β>0 , el flujo óptimo de j a i es β . Es imposible lograr que tanto α como β sean positivas.
Problema : determinar el flujo maximo al menor costo para el grafico propuesto:
En el nodo inicial escogemos el mayor flujo en este caso 50 (1-4), en el nodo 4 escogemos la ruta de mayorflujo en este caso 70 (7-9) hasta llegar al destino. Con lo anterior ya determinamos la ruta 1-4-7-9 Determinamos el menor valor de 1-9 que sera nuestro valor K en este caso (50)
Aplicamos la formula Cij ji >> (Ci-K, Cj+K) Ci MENOS K 50 `50 120 `50 70 `50 Cj
MAS
C 14,41 C 47,74 C 79, 97
=>> =>> =>>
0 `+ 0 `+ 0 `+
K 50 50 50
C14 0 70 20
C41 50 50 50
Aplicando el algoritmo de...
La idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos origen y destino.
Consideraremos las capacidades iniciales del arco que une el nodo i y el nodo j como Cij y Cji . Estas capacidades inicialesirán variando a medida que avanza el algoritmo, denominaremos capacidades residuales a las capacidades restantes del arco una vez pasa algún flujo por él, las representaremos como cij y cji .
Para un nodo j que recibe el flujo del nodo i , definimos una clasificación [aj,i] donde aj es el flujo del nodo i al nodo j . Los pasos del algoritmo se definen como sigue:
Paso 1: Inicializamos lascapacidades residuales a las capacidades iniciales, hacemos (cij,cji)=(Cij,Cji) para todo arco de la red. Suponiendo el nodo 1 como el nodo origen, hacemos a1=∞ y clasificamos el nodo origen con [∞,-] . Tomamos i=1 y vamos al paso 2.
Paso 2: Determinamos Si como un conjunto que contendrá los nodos a los que podemos acceder directamente desde i por medio de un arco con capacidad positiva, y que noformen parte del camino en curso. Si Si contiene algún nodo vamos al paso 3, en el caso de que el conjunto sea vacío saltamos al paso 4.
Paso 3: Obtenemos kЄSi como el nodo destino del arco de mayor capacidad que salga de i hacia un nodo perteneciente a Si . Es decir, cik = max{cij} con jЄSi . Hacemos ak=cik y clasificamos el nodo k con [ak,i] . Si k es igual al nodo destino o sumidero,entonces hemos encontrado una ruta de penetración, vamos al paso 5. En caso contrario continuamos con el camino, hacemos i=k y volvemos al paso 2.
Paso 4 (retroceso): Si i=1 , estamos en el nodo origen, y como Si es vacío, entonces no podemos acceder a ningún nodo, ni encontrar algún nuevo camino, hemos terminado, vamos al paso 6.
En caso contrario, i≠1 , le damos al valor i el del nodo que se haclasificado inmediatamente antes, eliminamos i del conjunto Si actual y volvemos al paso 2.
Paso 5: Llegados a este paso tenemos un nuevo camino: Np={1,k1,k2,...,n} , esta será la p-ésima ruta de penetración desde el nodo origen al nodo destino. El flujo máximo a lo largo de esta ruta será la capacidad mínima de las capacidades residuales de los arcos que forman el camino, es decir:fp=min{a1,ak1,ak2,...,an} .
La capacidad residual de cada arco a lo largo de la ruta de penetración se disminuye por fp en dirección del flujo y se incrementa por fp en dirección inversa, es decir, para los nodos i y j en la ruta, el flujo residual se cambia de la (cij,cji) actual a (cij-fp,cji+fp) si el flujo es de i a j , o (cij+fp,cji-fp) si el flujo es de j a i Inicializamos i=1 y volvemos al paso 2para intentar una nueva ruta de penetración.
Paso 6 (solución): Una vez aquí, hemos determinado m rutas de penetración. El flujo máximo en la red será la suma de los flujos máximos en cada ruta obtenida, es decir: F=f1+f2+...+fm . Teniendo en cuenta que las capacidades residuales inicial y final del arco (i, j) las dan (Cij,Cji) y (cij,cji) respectivamente, el flujo máximo para cada arco secalcula como sigue: sea (α, β)=(Cij-cij, Cji-cji) , si α>0 , el flujo óptimo de i a j es α , de lo contrario, si β>0 , el flujo óptimo de j a i es β . Es imposible lograr que tanto α como β sean positivas.
Problema : determinar el flujo maximo al menor costo para el grafico propuesto:
En el nodo inicial escogemos el mayor flujo en este caso 50 (1-4), en el nodo 4 escogemos la ruta de mayorflujo en este caso 70 (7-9) hasta llegar al destino. Con lo anterior ya determinamos la ruta 1-4-7-9 Determinamos el menor valor de 1-9 que sera nuestro valor K en este caso (50)
Aplicamos la formula Cij ji >> (Ci-K, Cj+K) Ci MENOS K 50 `50 120 `50 70 `50 Cj
MAS
C 14,41 C 47,74 C 79, 97
=>> =>> =>>
0 `+ 0 `+ 0 `+
K 50 50 50
C14 0 70 20
C41 50 50 50
Aplicando el algoritmo de...
Leer documento completo
Regístrate para leer el documento completo.