• Author / Uploaded
• Danitza Luque

• Categories
• Física y matemáticas
• Matemáticas
• Informática y tecnología de la información
• Ciencia
• Es / Ciencias de la Computación

Citation preview

Redes Flujo máximo 2012 \Apuntes de clase \ Ismael Véliz Vilca

1 6.4

-1

MODELO DE FLUJO MÁXIMO

VER video 0 10

20

4

0 5

5

0

0

30

1 20

30 0

10 20

2

0 40

3

0

Imagine una red de oleoductos que transportan crudo desde los pozos hasta las refinerías. En las distancias intermedias adecuadas están instaladas estaciones de bombeo, para mover el crudo por la red. Cada segmento de tubo tiene un flujo (o capacidad) máximo de crudo. Un Segmento de tubo puede ser uni o bidireccional, dependiendo de su diseño. Un segmento unidireccional tiene una capacidad finita en una dirección, y capacidad cero en la dirección opuesta. La figura 6.27 muestra una red de oleoductos. ¿Cómo se puede determinar la capacidad máxima de la red entre los pozos y las refinerías? La solución del problema propuesto requiere convertir la red en una que tenga una sola fuente y un solo "sumidero" o destino. Este requerimiento se llena usando arcos unidireccionales de capacidad infinita, como indican los arcos de línea interrumpida en la figura 6.27.

FIG 6.27 Red capacitada que une pozos y refinerías pasando por estaciones de bombeo

Redes Flujo máximo 2012 \Apuntes de clase \ Ismael Véliz Vilca

Dado el arco (i, j) con / < j, se usa la notación

-2

para representar las

capacidades de flujo en las dos direcciones, ij y j i, respectivamente. Para eliminar

ambigüedades se pone a

a en el arco junto al nodo i, y

¡ se coloca junto al nodo j,

como se ve en la figura 6.28.

FIGURA 6.28 Flujos en arco: Cij de i y Cij de j  i 6.4.1 Enumeración de cortes Un corte define a un conjunto de arcos que, cuando se eliminan de la red, causan una interrupción total del flujo entre los nodos fuente y sumidero. La capacidad de corte es igual a la suma de las capacidades de los arcos correspondientes. Entre todos los cortes posibles en la red, el que tenga la capacidad menor permite el flujo máximo en la red. Ejemplo 6.4-1 Se tiene la red de la figura 6.29. En los arcos respectivos se indican las capacidades bidireccionales, con la convención de la figura 6.28. Por ejemplo, para el arco (3,4), el límite de flujo es 10 unidades de 3 a 4 y 5 unidades de 4 a 3.

FIGURA 6.29- Ejemplos de corles en redes de flujo En la figura 6.29 se ilustran tres cortes, cuyas capacidades se calculan en la tabla siguiente.

Redes Flujo máximo 2012 \Apuntes de clase \ Ismael Véliz Vilca

Cort e Arcos Asociados 1 (1,2),(1,3),(1,4) (1,3),(1,4),(2,3), 2 (2,5) 3 (2,5),(3,5),(4,5)

Capacidad 22+30+10

-3

60

30+10+40+30 110 30+20+20 70

Nota.- se cortamos con una línea imaginaria por ejemplo el punto 2 va a cortar los arcos (1,3)(1,4)(2,3)(2,5) = en el arco (1,4) fluye de 1 4 =10 y de 4 a 1 0 total de flujo máximo =110 No se puede decir cuál es el flujo máximo en la red, a menos que se enumeren todos los cortes posibles. La única información que se puede obtener de la enumeración parcial de los tres cortes es que el flujo máximo en la red no puede ser mayor que 60 unidades. Desafortunadamente, enumerar todos los cortes no es una tarea sencilla, y entonces se hace necesario desarrollar el eficiente algoritmo en la sección 6.4.2. 6.4.2 Algoritmo de flujo máximo (ver el libro de taha para ver el programa) El algoritmo de flujo máximo se basa en determinar rutas de irrupción que tengan flujo neto positivo entre los nodos fuente y sumidero. Cada ruta comunica parte o todas las capacidades de sus arcos al flujo total en la red. Considérese el arco (i, j) con capacidades iniciales

. A medida que

partes de esas capacidades contribuyen al flujo en el arco, se actualizan los residuales (o capacidades remanentes). La red con los residuales actualizados se llama red residual. Se usará la notación (Cij ,Cji) para representar esos residuales. Para un nodo j que recibe flujo del nodo i, se define una etiqueta [Aj,i), donde aj es el flujo del nodo i al nodo j. Los pasos del algoritmo se resumen como sigue. Paso 1. Para todos los arcos (i.j) se iguala la capacidad residual con la capacidad inicial; esto es,

. Sea a{ = ∞ y se etiqueta el nodo fuente 1 con

[∞o, --]. Se iguala i = 1 y se prosigue en el paso 2. Paso 2. Determinar S¡, el conjunto de nodos j no etiquetados que se pueden alcanzar directamente desde el nodo i, con arcos con residuales positivos (esto es. Cij> 0 para toda j Є S¡). Si S1 ≠θ, ir al paso 3. En caso contrario ir al paso 4. Paso 3.

Determinar k Є S1, tal que

Redes Flujo máximo 2012 \Apuntes de clase \ Ismael Véliz Vilca

-4

Igualar ak = cik y etiquetar el nodo k* con [ak, i]. Si k = n, el nodo de sumidero se ha etiquetado, y se ha encontrado una ruta de irrupción; ir al paso 5. En caso contrario, igualar i = k y seguir en el paso 2. Paso 4. (Retroceso). Si i = 1, no hay otras irrupciones posibles; ir al paso 6. En caso contrario, sea r el nodo que se ha etiquetado inmediatamente antes del nodo actual i y quitar i del conjunto de nodos adyacentes a r. Igualar i = r y continuar en el paso 2. Paso 5.

(Determinación de la red residual). Sea Np = (1, k¡, k2,..., n); se definen los

nodos de la p-ésima ruta de irrupción del nodo fuente 1 al nodo sumidero n. Entonces el flujo máximo por la ruta se calcula como fP = mín{a,, ak1, ak2,..., an) La capacidad residual de cada arco a lo largo de la ruta de irrupción se disminuye en fp unidades en la dirección del flujo y se aumenta fp unidades en la dirección contraria; esto es, para los nodos i y j en la ruta, el flujo residual se cambia del actual (cij cji ) a a) (Cij-Fp, Cij +Fp ) si el flujo va de i a j b) B) Cij +Fp ,Cji –fp ) si el flujo va de j a i

Se reinstalan todos los nodos que se hayan eliminado en el paso 4. Poner i = 1 y regresar al paso 2 para intentar una nueva ruta de irrupción. Paso 6. a)

(Solución)

Si se han determinado m rutas de irrupción, el flujo máximo en la red es

F = A+f2+ ••• +fm„ b)

Como los residuales inicial y final del arco (i, j) se obtienen con (C’ij,C’ji) y,(Cij,Cji

respectivamente, el flujo óptimo en el arco (i, j) se calcula como sigue: sea Si α > 0, el flujo óptimo de i a j es α . Si β > 0, el flujo óptimo de i a j es βp. (Es imposible que tanto α y β sean positivos.)1 Se invoca el proceso de retroceso del paso 4 cuando el algoritmo llega a un "punto ciego" por descuido, en un nodo intermedio, antes de poder realizar una irrupción. El ajuste del flujo en el paso 5 se puede explicar con la red de flujo sencilla de la figura 6.30. La red a) 1

*N. del R.T.: Por otro lado, si (β > 0, el flujo óptimo de j a i es β

Redes Flujo máximo 2012 \Apuntes de clase \ Ismael Véliz Vilca

-5

obtiene la primera ruta de irrupción N1 = ( 1,2, 3,4) con su flujo máximo f1, = 5. Así, los residuales de cada uno de los arcos (1,2), (2,3) y (3,4) se cambian de (5,0) a (0,5), según el paso 5. La red b) proporciona ahora la segunda ruta de irrupción N2= {1, 3, 2,4) con f2 = 5. Después de hacer los ajustes necesarios de flujo, se obtiene la red c), donde ya no son posibles más irrupciones. Lo que sucedió en la transición de b) a c) no es más que una cancelación de un flujo antes comprometido en la dirección 23. El algoritmo puede "recordar" que se había comprometido antes un flujo de 2 a 3 sólo porque se ha aumentado la capacidad en la dirección contraria de 0 a 5 (de acuerdo con el paso 5).

FIGURA 6.30 Uso del residual para calcular el flujo máximo Resolver con tora

Redes Flujo máximo 2012 \Apuntes de clase \ Ismael Véliz Vilca

-6

Ejemplo 6.4-2 0 10

20

4

0 5

5

0

0

30

1 20

30 0

10 20

2

0 40

3

0

Determinar el flujo máximo en la red del ejemplo 6.4-1 (Figura 6.29). La figura 6.31 muestra un resumen gráfico de las iteraciones del algoritmo. El lector encontrará útil comparar la descripción de las iteraciones con el resumen gráfico.

Redes Flujo máximo 2012 \Apuntes de clase \ Ismael Véliz Vilca

-7

Figura 6.31 Iteraciones del algoritmo de flujo máximo del ejemplo 6-4-2 Iteración 1. Igualar los residuales iniciales (cij,cjii) a las capacidades iniciales (C’ij ,y, C’ji,). Paso 1.

Igualara a1 = ∞ y etiquetar el nodo 1 con [∞ , —]. Poner i = 1.

Paso 2. S1={2, 3, 4} (≠θ ). Paso 3.

k=3 porque c13 = máx{c12, c13,c14} = máx {20, 30, 10} = 30. Tomar a3 = C13 =

30 y etiquetar el nodo 3 con [30, 1 ]. Igualar i = 3 y repetir el paso 2. Paso 2. S3 = (4, 5). Paso 3.

k = 5 y as = c35 = máx{10, 20} = 20. Etiquetar el nodo 5 con [20, 3].

Se obtuvo una irrupción. Ir al paso 5. Paso 5.

La ruta de irrupción se determina con las etiquetas comenzando en el nodo

5 y terminando en el nodo 1; esto es, (5)  [20, 3] (3) [30, 1] (1). Así, N1 = {1, 3, 5} y f1, = mín{a1,a3,a5} = {∞ , 30, 20} = 20. Las capacidades residuales a lo largo de la ruta N1 son (c13, c31) = (30 - 20, 0 + 20) = (10, 20) (C35, c53) = (20 - 20, 0 + 20) = (0, 20)

Redes Flujo máximo 2012 \Apuntes de clase \ Ismael Véliz Vilca

-8

Iteración 2. Paso 1. • Poner a1 = ∞ y etiquetar el nodo 1 con [∞ , —]. Igualar i = 1. Paso 2. S1 = (2,3,4). Paso 3.

k = 2 y a2 = c12 = máx(20, 10, 10) = 20. Poner i = 2 y repetir el paso 2.

Paso 2.

S2={3,5).

Paso 3. k = 3 y a3 = c23=40. Etiquetar el nodo 3 con [40, 2]. Poner i = 3 y repetir el paso 2. Paso 2. S3 = (4) (observe que c35 = 0; en consecuencia el nodo 5 no puede incluirse en S4). Paso 3.

k = 4 y a4 = c34 = 10. Etiquetar el nodo 4 con [ 10, 3]. Igualar i' = 4 y repetir el

paso 2. Paso 2.

54 = [5] (observe que los nodos 1 y 3 ya se han etiquetado y en consecuencia

no se pueden incluir en S4) . Paso 3.

k = 5 y as = c45 = 20. Etiquetar el nodo 5 con [20,4). Se ha logrado la irrupción.

Ir al paso 5. Paso 5.

N2 = {1,2, 3,4, 5) y f2 = mín{ ∞ , 20,40, 10, 20) = 10. Los residuales a lo largo de

la ruta N2 son (c12,c21)=(20-10,0+10)=(10,10) (c23,c32)=(40-10,0+10)=(30,10) (c34,c43)=(20-10,510)=(0,15) (c45,c34)=(20-10,0+10)=(10,10) Iteración 3. Paso 1.

Poner a, =∞ y etiquetar el nodo 1 con [∞ , —]; poner i = 1

Paso 2. S1 = (2,3,4). Paso 3.

k = 2 y a2 = cl2 = máx( 10, 10, 10) = 10 (aunque los empates se rompen en forma

arbitraria, TORA selecciona siempre el nodo empatado que tenga el índice menor; usaremos esta convención en el ejemplo). Etiquetar el nodo 2 con [10, 1]. Poner i = 2 y repetir el paso 2. Paso 2.

S2={3,5).

Paso 3.

k = 3 y a3 = c23 = 30. Etiquetar el nodo 3 con [30, 2]. Poner i = 3 y repetir el

paso 2. Paso 2.

S3 = 0 (porque cM = c35 = 0). Ir al paso 4 para retroceder.

Redes Flujo máximo 2012 \Apuntes de clase \ Ismael Véliz Vilca

Paso 4.

-9

La etiqueta [30, 2] en el nodo 3 da el nodo inmediato anterior r = 2. Sacar el

nodo 3 de más consideraciones en esta iteración, tachándolo. Repetir el paso 2 con i = r = 2. Paso 2.

S2 = {5}; nótese que el nodo 3 se ha eliminado en el paso de retroceso.

Paso 3.

k = 5 y a5 = c25 = 30. Etiquetar el nodo 5 con [30, 2] . Se ha logrado la irrupción;

proseguir en el paso 5. Paso 5.

N3 = {1, 2,5} y c5 = mín(oo, 10, 30) = 10. Los residuales a lo largo de la trayec-

toria de N3 son

'

(c,2, c21) = (10 - 10, 10 + 10) = (0, 20) (C25,. C52) = (30 - 10, 0 + 10) = (20, 10) Iteración 4.

En esta iteración se obtiene N4= (1, 3, 2, 5) con f4=10 (¡compruébelo!).

Iteración 5. En esta iteración se obtiene N5= [ 1,4,5) con/5 = 10 (¡compruébelo!). Iteración 6.

Todos los arcos que salen del nodo 1 tienen residuales cero. En

consecuencia no hay más irrupciones posibles. Pasaremos al paso 6 para determinar la solución. Paso 6. El flujo máximo en la red es F =f1+f2 + ... +f5 = 20 + 10 + 10 + 10 + 10 = 60 unidades. El flujo en los distintos arcos se calcula restando los últimos residuales (cij,cji,) en las iteraciones 6 de las capacidades iniciales (C’ j;, C’;/), como se ve en la tabla Arco (1,2) (1.3) (1.4) (2,3) (2,5)

(C’ij,C’ji)-(Cij,Cji (20, 0) - (0, 20) = (20, -20) (30, 0) - (0, 30) = (30, -30) (10, 0)-(0, 10) =(10, -10) (40, 0) - (40, 0) = (0, 0) (30, 0) - (10, 20) = (20, -20) (3,4) (10.5) -(0, 15) = (10. -10) (3,5) (20, 0) - (0, 20) = (20, -20) (4.5) (20, 0) - (0, 20) = (20, -20)

Flujo 20 30 10 0 20 10 20 20

Dirección 12 13 14 — 25 34 35 45

Puede usted usar TORA para resolver el modelo de flujo máximo en una forma automatizada, o para producir las iteraciones que se describieron arriba. Partiendo del menú SOLVE/ MODIFY

(resolver/modificar), seleccione solve Probiem (resolver problema). Después

de especificar el formato de los resultados, pase a la pantalla de resultados y seleccione Máximum

FIOWS

(flujos máximos) o iterations (iteraciones). La figura 6.32 muestra las dos

primeras iteraciones del ejemplo 6.4-2 (archivo ch6ToraMaxFlowEx6-4-2.txt).

Redes Flujo máximo 2012 \Apuntes de clase \ Ismael Véliz Vilca

- 10

Redes Flujo máximo 2012 \Apuntes de clase \ Ismael Véliz Vilca

- 11

FIGURA 6.32 Iteraciones de flujo máximo para el ejemplo 6.4-2 con TORA Las mismas iteraciones con Excel

ITERACION 1 DE\A

1

2

2 3 3 20 0 4 0 0

3

0

0

4 5

0 0

0 5 0 0

1

Flujo ITERACION 2 DE\A

1

2 3 1 1 20 0 4 2 0 0 3 20 0

fluj flujo 4 5 o acum RUTA 1 0 0 30 1,3 3 0 0 1 2 0 0 20 5 2 0 0 20 20 1,3,5 fluj flujo 4 5 o acum 1 0 0 20 3 0 0 40 1 0 10

RUTA 1,2 3 4

Redes Flujo máximo 2012 \Apuntes de clase \ Ismael Véliz Vilca

- 12

0 4

0

5

0

0 5 2 0 0 0

Flujo ITERACION 3 DE\A

1 1 2 10 3 20 4

0

5

0

2 3 1 10 0 3 0 10 1 0 5 2 0 0

Flujo ITERACION 4 DE\A

1 1 2 20 3 20 4

0

5

0

2 3 1 0 0 3 0 10 1 0 5 2 10 0

Flujo ITERACION 5

2 0

20

5

10

1,2,3,4 30 ,5

fluj flujo 4 5 o acum RUTA 1 0 0 10 1,2 3 0 0 30 5 0 0 1 0 1 0 10 40 1,2,5 fluj flujo 4 5 o acum RUTA 1 0 0 10 1,3 2 0 0 20 0 0 10 2 1 0 1 0 10 50 1,3,2,5

Redes Flujo máximo 2012 \Apuntes de clase \ Ismael Véliz Vilca

DE\A

1 1 2 20 3 30 4

0

5

0

2 3 0 0 4 0 0 1 0 5 2 20 0

Flujo ITERACION 6 DE\A

1 1 2 20 3 30 4 10 5

Flujo

0

- 13

fluj flujo 4 5 o acum RUTA 1 0 0 10 1,4 1 0 0 0 0 1 0 10 5 1 0 10 60 1,4,5

fluj flujo 2 3 4 5 o acum RUTA 0 0 0 0 10 4 0 0 0 0 0 0 1 0 5 0 10 2 2 20 0 0 0 60

Iteracio Camino seleccionado n 1 1,3,5 2 1,2,3,4,5 3 1,2,3,2,5 4 1,3,2,5 5 1,4,5 SOLUCION CON WINQSB

flujo 30,20 20,40,10,2 0 10,30,20 10,10,20 10.1

Flujo

flujo acum 20 10 10 10 10

20 30 40 50 60

Redes Flujo máximo 2012 \Apuntes de clase \ Ismael Véliz Vilca

SOLUCION DE FLUJO MAXIMO CON POMS

- 14

Redes Flujo máximo 2012 \Apuntes de clase \ Ismael Véliz Vilca

- 15

Pruebe que el flujo de 1 a 40 el flujo es 20 Pruebe que no hay flujo de 4 1 1

y el

El flujo de

4 a 3 es 5

Redes Flujo máximo 2012 \Apuntes de clase \ Ismael Véliz Vilca

Programa con visual c++ modo consola // *** otros.h void iniciarVector(int A[], int n) { for (int i=1;i