18 simulacion de sistemas semana9 - elvis del aguila lopez
Post on 22-Jul-2015
71 Views
Preview:
TRANSCRIPT
UPOUniversidad Peruana del Oriente
Docente: Ing. Elvis DEL ÁGUILA López
Curso: Teoría de Redes
Diciembre . 2014
Problema de flujo maximo
consiste en determinar la máxima cantidad
de flujo que puede ser enviada a lo largo de
una red dirigida, desde un nodo origen (de
oferta) hasta un nodo destino (de demanda).
Los nodos restantes son los nodos de trasbordo
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 está dada por la capacidad del arco.
El objetivo es maximizar la cantidad total de flujo
de la fuente al destino. Esta cantidad se mide en
cualquiera de las dos maneras equivalentes, esto es,
la cantidad que sale de la fuente o la cantidad que
entra al destino.
Estructura
Para resolver un problema de flujo máximo
se debe seguir los siguientes pasos:
Se identifica el nodo origen y destino.
Se parte desde el nodo de origen y se escoge el arco que posea mayor flujo
Se identifica los nodos de transbordo.
Repetir como si el nodo intermediario fuera el nodo origen.
Se calcula "k" y las capacidades nuevas.
Dado el resultado se cambian las capacidades y se repite el mismo
procedimiento desde el inicio.
Formulario
C= capacidad
i,j= índice de nodos
K= flujo mínimo del camino
seleccionado
Cij,ji= (Ci-k , Cj+k)
Propone buscar caminos en los que se pueda
aumentar el flujo, hasta que se alcance el
flujo máximo. Es aplicable a los Flujos
maximales. La idea es encontrar una ruta de
penetración con un flujo positivo neto que
una los nodos origen y destino.
El algoritmo de Ford - Fulkerson
Método Ford FulkersonEl nodo de origen como se puede observar es el numero 1 de color negro, y el
nodo de destino es el numero 5 de color azul.
Las flechas de color rojo son las mayores capacidades que tienen cada nodo de
flujos de salida y los de color negro los flujos de entrada.
1
32
5
4
0
20
0
30
0
20
0
40
0
20
0
10
5
20
0
10
1. Se escoge desde el nodo de origen aquel flujo que sea el mayor, en
este caso es 30, y va dirigido al nodo numero 3 y sucesivamente hasta
llegar al nodo 5(destino), el cual seria 20.
1
32
5
0 20
30
0
20
0
40
0
20
0
10
20
0
2. Se identifica el nodo de transbordo como [30,1], 30 es la capacidad(que
recibe), y 1 es el nodo del cual proviene la capacidad y luego repetimos todo
el proceso, como si el nodo intermediario fuese el nodo de origen. Se tiene
como flujo mayor 20 del nodo numero 3 al nodo numero 5, con el nodo de
transbordo como [20,3].
1
32
5
410
020
0
300 20
0
40
0
20
0
10
5
[∞,-] [20,3]
[30,1]
20
0
El nodo de transbordo de 1 es ∞
Porque no tiene un flujo
establecido y tampoco Proviene de
otro nodo Por lo que ponemos un -
3. Ahora que hemos llegado al nodo de destino, procedemos a calcular "k" y las
capacidades nuevas.
K=min(∞,30,20)
K=20
C13,31 =(30-20, 0+20)
C13,31 =(10, 20)
C35,53 =(20-20, 0+20)
C35,53 =(0, 20)
1
32
5
410
0 20
0
30
0
20
0
40
0
20
0
10
5
[∞,-]
[30,1]
[20,3]
20
0
4. Luego de haber calculado las nuevas capacidades, es necesario
reemplazarlas tanto de entrada (fucsia) como de salida (rojo).
1
32
5
410
0 20
0
10
2020
0
40
0
0
20
10
5
20
0
5. Se realiza el proceso otra vez, haciendo la ruta con los mayores
flujos
K=min (∞,20,40,10,20)
K= 10
C12,21 =(20-10, 0+10)
C12,21 =(10, 10)
C23,32 =(40-10, 0+10)
C23,32 =(30, 10)
C34,43 =(10-10, 5+10)
C34,43 =(0, 15)
C45,54 =(20-10, 0+10)
C45,54 =(10, 10)
1
32
5
410
020
0
102020
0
40
0
0
20
10
5
[∞,-]
[40,2]
[20,4]
[10,3]
20
[20,1]
0
6. reemplazamos los nuevos valores.
1
32
5
410
010
10
1010 20
0
30
10
0
20
0
15
10
20
7. Volvemos a hacer el proceso y escogemos el camino 1,2. Como se puede
observar si se tomara rumbo del nodo 2 al nodo 3 terminaría trancado,
obligándose a volver al nodo origen, por lo que se toma el camino 2 al 5.
K=min(∞,10,20)
K=10
C12,21 =(10-10, 10+10)
C12,21 =(0, 20)
C25,52 =(20-10, 0+10)
C25,52 =(10, 10)
1
32
5
410
010
10
1010 20
0
30
10
0
20
0
15
10
20
[∞,-]
[10,1]
[20,2]
8. Reemplazamos los nuevos valores
1
32
5
410
0
10
10
2010
10
30
10
20
0
15
0
20
10
0
9. resolver de nuevo. Esta vez empezamos el camino de 1,3.
K=min(∞,10,10,10)
K=10
C13,31 =(10-10, 20+10)
C13,31 =(0, 30)
C32,23 =(10-10, 30+10)
C32,23=(0 , 40)
C25,52 =(10-10, 10+10)
C25,52=(0, 20)
1
32
5
410
010
10
1020 10
10
30
10
0
20
0
15
0
20
[∞,-]
[10,1][10,3]
[10,2]
10. ponemos los nuevos valores
1
32
5
410
0
10
10
0
20 0
20
40
0
0
20
0
15
0
30
11. por ultimo escogemos el camino 1,4.
K=min(∞,10,10)
K=10
C14,41 =(10-10, 0+10)
C14,41 =(0, 10)
C45,54 =(10-10, 10+10)
C45,54 =(0, 40)
1
32
5
410
010
10
020 0
20
0
0
20
0
15
0
30
[∞,-]
[10,1]
[10,4]
40
12. Reemplazamos los nuevos valores
1
32
5
40
100
40
0
20 0
20
0
0
20
0
15
0
30
40
13. Reemplazando las nuevas capacidades, nos queda de la siguiente
forma, las capacidades del nodo de origen quedan como 0, por lo
cual seguimos a sumar a todas las K y ahí conseguimos el
flujo máximo.
Flujo Máximo = Σ K
Flujo Máximo = 20+10+10+10+10
Flujo Máximo = 60
El flujo máximo que puede pasar del nodo origen 1 hasta el nodo destino
es de 60.
1
32
5
40
10 0
40
020 0
20
0
0
20
0
15
0
30
40
Ejercicio propuesto: hallar el flujo máximo
1 3
4
2
76
56
0
3
3
2
2
2
2
60
3
3
1
1
0
5
0
5
0
2
2
2
MUCHAS GRACIAS
top related