clase 2

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


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


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


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


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


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


Iteracin 2

(4 , 3) (4, 0)

(4 , 3)

1.4

. Pro

ble

ma d

el fl

ujo

mxim

o


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)


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)


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


RUTA: ORIGEN B F I K J


1.4

. Pro

ble

ma d

el fl

ujo

mxim

o

(3 , 12)


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)


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)


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


RUTA: ORIGEN C F I K J


1.4

. Pro

ble

ma d

el fl

ujo

mxim

o

(5, 5)

(5, 0)

(5, 10) (5, 25)

(5, 5)

(3 , 12)


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)


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)


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


RUTA: ORIGEN C F I K


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)


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)


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)


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


RUTA: ORIGEN C G I K


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)


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)


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)


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


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)


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


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

clase 2

Documents