clase 2
Post on 28-Mar-2016
5 Views
Preview:
DESCRIPTION
TRANSCRIPT
-
Ingeniera Industrial
Investigacin Operativa 2
TEORIA DE REDES (2)
FACULTAD DE
CIENCIAS E
INGENIERIA
Mg. Eduardo Carbajal Lpez
SESION 02
-
SESION 01
Teora de redes
Problema del flujo mximo
Teora de redes (2)
-
1.4
. Pro
ble
ma d
el fl
ujo
mxim
o
Problema del flujo mximo
Objetivo: Consiste en determinar la capacidad de
envo a travs de una red que tiene un nodo de
origen y uno de destino.
Aplicaciones usuales:
Capacidad de redes de agua Capacidad de envo en redes logsticas
Observaciones importantes
Los coeficientes de los arcos representan capacidad mxima de envo.
Se trata de enviar la mxima cantidad posible de unidades a travs de la red desde el origen al
destino.
-
Algoritmo de Ford Fulkerson
Paso 1.- Inicio
Identifique el nodo de origen y de destino de la red. Grafique la red incluyendo la capacidad de cada arco.
Paso 2.- Seleccionar y enviar
Seleccionar un camino factible desde el nodo de origen hasta el destino. Enviar el mximo flujo posible permitido por el camino.
Paso 3.- Actualizacin
Actualizar los arcos del camino empleando el formato: (flujo enviado, capacidad restante)
Si algn arco tiene capacidad restante cero se dice que el arco esta saturado. Repetir paso 2 hasta no encontrar mas caminos factibles.
1.4
. Pro
ble
ma d
el fl
ujo
mxim
o
-
Algoritmo de Ford Fulkerson Ejemplo
Tres ciudades del sur de Francia, J, K y L son
alimentadas de agua gracias a cuatro reservas A,
B, C y D (napas subterrneas, tanques de agua,
plantas de tratamiento, etc....). Las reservas diarias
disponibles son de 15 millones de m3 para A, 10
para B, 15 para C y 15 para D. La red de
distribucin, que comprende tanto acueductos
romanos utilizables as como canalizaciones
recientes se representa en la grafica siguiente (el
valor de flujo mximo de cada arco representa la
cantidad mxima de agua que puede circular entre
dos puntos): 1.4
. Pro
ble
ma d
el fl
ujo
mxim
o
-
Algoritmo de Ford Fulkerson Ejemplo
A
B
C
D
E
F
G
H
I
J
K
L
5
7
7
10
15 5
4
10
15
10
30
4 7
5
15
7
5
1.4
. Pro
ble
ma d
el fl
ujo
mxim
o
-
Algoritmo de Ford Fulkerson Ejemplo
A
B
C
D
E
F
G
H
I
J
K
L
5
7
7
10
15 5
4
10
15
10
30
4 7
5
15
7
5
PASO 1:
ORIGEN
DESTINO
M
M
M
15
10
15
15
1.4
. Pro
ble
ma d
el fl
ujo
mxim
o
-
Algoritmo de Ford Fulkerson Ejemplo
A
B
C
D
E
F
G
H
I
J
K
L
5
7
7
10
15 5
4
10
15
10
30
4 7
5
15
7
5
PASO 2:
ORIGEN
DESTINO
M
M
M
15
10
15
15
Capacidad 15 7 4 7
Flujo a enviar: Min(15,7,4,7) = 4
RUTA: ORIGEN A E H J
Flujo acumulado enviado: 0 + 4 = 4
Iteracin 1
1.4
. Pro
ble
ma d
el fl
ujo
mxim
o
-
7
Algoritmo de Ford Fulkerson Ejemplo
A
B
C
D
E
F
G
H
I
J
K
L
5
7
(4 , 3)
10
15 5
4
10
15
10
30
5
15
7
5
PASO 3:
ORIGEN
DESTINO
M
M
M
15
10
15
15
Aun quedan caminos con capacidad residual al destino se
repite el paso 2
4 7 (4, 0) (4 , 3)
(4,11)
1.4
. Pro
ble
ma d
el fl
ujo
mxim
o
-
Algoritmo de Ford Fulkerson Ejemplo
A
B
C
D
E
F
G
H
I
J
K
L
5
7
10
15 5
4
10
15
10
30
5
15
7
5
PASO 2:
ORIGEN
DESTINO
M
M
M
(4,11)
M
M
M
Capacidad 11 3 15 7 3
Flujo a enviar: Min(11,3,15,7,3) = 3
RUTA: ORIGEN A E I H J
Flujo acumulado enviado: 4 + 3 = 7
Iteracin 2
(4 , 3) (4, 0)
(4 , 3)
1.4
. Pro
ble
ma d
el fl
ujo
mxim
o
-
Algoritmo de Ford Fulkerson Ejemplo
A
B
C
D
E
F
G
H
I
J
K
L
5
7
10
15 5
4
10
15
10
30
5
15
7
5
PASO 3:
ORIGEN
DESTINO
M
M
M
(4,11)
10
15
15
Iteracin 2
(4 , 3) (4, 0)
(4 , 3)
Aun quedan caminos con capacidad residual al destino se
repite el paso 2
(7 , 0)
(3 , 12) (3 , 4)
(7 , 0)
(7 , 8)
1.4
. Pro
ble
ma d
el fl
ujo
mxim
o
-
(3 , 12)
Algoritmo de Ford Fulkerson Ejemplo
A
B
C
D
E
F
G
H
I
J
K
L
5
7
10
5
4
10
15
10
30
5
15
7
5
PASO 2:
ORIGEN
DESTINO
M
M
M
(7 , 8)
10
15
15
Iteracin 3
(4, 0) (7 , 0)
(3 , 4)
(7 , 0)
Capacidad 10 5 15 30 10
Flujo a enviar: Min(10,5,15,30,10) = 5
RUTA: ORIGEN B F I K J
Flujo acumulado enviado: 7 + 5 = 12
1.4
. Pro
ble
ma d
el fl
ujo
mxim
o
-
(3 , 12)
Algoritmo de Ford Fulkerson Ejemplo
A
B
C
D
E
F
G
H
I
J
K
L
5
7
10
5
4
10
15
10
30
5
15
7
5
PASO 3:
ORIGEN
DESTINO
M
M
M
(7 , 8)
10
15
15
Iteracin 3
(4, 0) (7 , 0)
(3 , 4)
(7 , 0)
Aun quedan caminos con capacidad residual al destino se
repite el paso 2
(5, 5)
(5, 0)
(5, 10) (5, 25)
(5, 5)
1.4
. Pro
ble
ma d
el fl
ujo
mxim
o
-
(5, 5)
(5, 0)
(5, 10) (5, 25)
(5, 5)
(3 , 12)
Algoritmo de Ford Fulkerson Ejemplo
A
B
C
D
E
F
G
H
I
J
K
L
5
7
10 4
10
15
5
7
5
PASO 2:
ORIGEN
DESTINO
M
M
M
(7 , 8)
15
15
Iteracin 4
(4, 0) (7 , 0)
(3 , 4)
(7 , 0)
Capacidad 15 10 10 25 5
Flujo a enviar: Min(15,10,10,25,5) = 5
RUTA: ORIGEN C F I K J
Flujo acumulado enviado: 12 + 5 = 17
1.4
. Pro
ble
ma d
el fl
ujo
mxim
o
-
(5, 5)
(5, 0)
(5, 10) (5, 25)
(5, 5)
(3 , 12)
Algoritmo de Ford Fulkerson Ejemplo
A
B
C
D
E
F
G
H
I
J
K
L
5
7
10 4
10
15
5
7
5
PASO 3:
ORIGEN
DESTINO
M
M
M
(7 , 8)
15
15
Iteracin 4
(4, 0) (7 , 0)
(3 , 4)
(7 , 0)
Aun quedan caminos con capacidad residual al destino se
repite el paso 2
(5, 10)
(5, 5)
(10 , 5) (10 , 20)
(10 , 0)
1.4
. Pro
ble
ma d
el fl
ujo
mxim
o
-
(10 , 20) (10 , 5)
(5, 5)
(5, 10)
(5, 5)
(5, 0)
(10, 0)
(3 , 12)
Algoritmo de Ford Fulkerson Ejemplo
A
B
C
D
E
F
G
H
I
J
K
L
5
7
10 4 15
5
7
5
PASO 2:
ORIGEN
DESTINO
M
M
M
(7 , 8)
15
Iteracin 5
(4, 0) (7 , 0)
(3 , 4)
(7 , 0)
Capacidad 10 5 5 20
Flujo a enviar: Min(10,5,5,20) = 5
RUTA: ORIGEN C F I K
Flujo acumulado enviado: 17 + 5 = 22
1.4
. Pro
ble
ma d
el fl
ujo
mxim
o
-
(10 , 5) (15, 0)
(5, 5) (10, 0)
(10 , 20)
(5, 10)
(5, 5)
(5, 0)
(10, 0)
(3 , 12)
Algoritmo de Ford Fulkerson Ejemplo
A
B
C
D
E
F
G
H
I
J
K
L
5
7
10 4 15
5
7
5
PASO 3:
ORIGEN
DESTINO
M
M
M
(7 , 8)
15
Iteracin 5
(4, 0) (7 , 0)
(3 , 4)
(7 , 0)
Aun quedan caminos con capacidad residual al destino se
repite el paso 2
(10, 5) (15, 15)
1.4
. Pro
ble
ma d
el fl
ujo
mxim
o
-
(15, 15) (10, 5)
(10 , 5) (15, 0)
(5, 5) (10, 0) (5, 5)
(5, 0)
(10, 0)
(3 , 12)
Algoritmo de Ford Fulkerson Ejemplo
A
B
C
D
E
F
G
H
I
J
K
L
5
7
10 4 15
5
7
5
PASO 2:
ORIGEN
DESTINO
M
M
M
(7 , 8)
15
Iteracin 6
(4, 0) (7 , 0)
(3 , 4)
(7 , 0)
Capacidad 5 7 15 15
Flujo a enviar: Min(5,7,15,10) = 5
RUTA: ORIGEN C G I K
Flujo acumulado enviado: 22 + 5 = 27
1.4
. Pro
ble
ma d
el fl
ujo
mxim
o
-
(15, 15) (10, 5)
(10 , 5) (15, 0)
(5, 5) (10, 0) (5, 5)
(5, 0)
(10, 0)
(3 , 12)
Algoritmo de Ford Fulkerson Ejemplo
A
B
C
D
E
F
G
H
I
J
K
L
5
7
10 4 15
5
7
5
PASO 2:
ORIGEN
DESTINO
M
M
M
(7 , 8)
15
Iteracin 6
(4, 0) (7 , 0)
(3 , 4)
(7 , 0)
Aun quedan caminos con capacidad residual al destino se
repite el paso 2
(15, 0) (5, 2)
(5, 10)
(20 , 10)
1.4
. Pro
ble
ma d
el fl
ujo
mxim
o
-
(15, 10) (10, 5)
(10 , 5) (15, 0)
(5, 5) (10, 0) (5, 5)
(5, 0)
(10, 0)
(3 , 12)
Algoritmo de Ford Fulkerson Ejemplo
A
B
C
D
E
F
G
H
I
J
K
L
5
7
10 4 15
5
7
5
PASO 3:
ORIGEN
DESTINO
M
M
M
(7 , 8)
15
Iteracin 7
(4, 0) (7 , 0)
(3 , 4)
(7 , 0)
(15, 0) (5, 2)
(5, 10)
(20 , 10)
Capacidad 15 10 10 10
Flujo a enviar: Min(15,10,10,5) = 10
RUTA: ORIGEN D G I K
Flujo acumulado enviado: 27 + 10= 37
1.4
. Pro
ble
ma d
el fl
ujo
mxim
o
-
(10, 5)
(10 , 5) (15, 0)
(5, 5) (10, 0) (5, 5)
(5, 0)
(10, 0)
(3 , 12)
Algoritmo de Ford Fulkerson Ejemplo
A
B
C
D
E
F
G
H
I
J
K
L
5
7
10 4
5
7
5
PASO 3:
ORIGEN
DESTINO
M
M
M
(7 , 8)
15
Iteracin 7
(4, 0) (7 , 0)
(3 , 4)
(7 , 0)
(15, 0) (5, 2)
(5, 10)
(20 , 10)
(10, 5) (10, 0)
(15, 0)
(30, 0)
Ya no hay rutas que alcancen el destino. Se termina el
algoritmo.
1.4
. Pro
ble
ma d
el fl
ujo
mxim
o
-
Algoritmo de Ford Fulkerson Ejemplo
SOLUCION:
FLUJO MXIMO = 37
(10, 5)
(10 , 5) (15, 0)
(5, 5) (10, 0) (5, 5)
(5, 0)
(10, 0)
(3 , 12)
A
B
C
D
E
F
G
H
I
J
K
L
5
7
10 4
5
7
5
ORIGEN
DESTINO
M
M
M
(7 , 8)
15
(4, 0) (7 , 0)
(3 , 4)
(7 , 0)
(15, 0) (5, 2)
(5, 10)
(20 , 10)
(10, 5) (10, 0)
(15, 0)
(30, 0)
1.4
. Pro
ble
ma d
el fl
ujo
mxim
o
top related