12_ind2209_alumno_15

Investigación de OperacionesIND2209

Profesor: Pamela Álvarez M.

Facultad de IngenieríaDepartamento de Ciencias de la Ingeniería

Unidad Nº 6

• ¿Qué más veremos?:

• Ruta más corta

• Flujo máximo

2

Programación en redes

IND2209. Prof.: Pamela Álvarez M.

3IND2209. Prof.: Pamela Álvarez M.

• Problema de Ruta más Corta o Ruta Mínima

• Consiste en encontrar la ruta más corta desde un punto denominado origen

hasta otro llamado destino.

• Es un problema de redes muy importante y bastante común.

• Algunos ejemplos: problemas de inventario, reemplazo de equipos,

asignación de tráfico, etc.

• Suele encontrarse como subproblema en situaciones más complejas.

Programación en redes


• El problema es encontrar un camino dirigido en el grafo que conecte el

nodo de origen (s) con el nodo de destino (t) y que tenga costo mínimo.

• A cada arco (i,j) asociamos un costo cij≥0.

1

3

2

5

4

6

1

5

7

2

1

6 3

6

10

Problema de Ruta más corta


• El problema se formula fácilmente como uno de flujo a costo mínimo:

,

:( , ) :( , )

:( , ) :( , )

:( , ) :( , )

min

. . 1

0 ,

1

0,1 , ( , )

ij iji j A

sj ksj s j A k k s A

ij kij i j A k k i A

tj ktj t j A k k t A

ij

c x

s a x x

x x i s t

x x

x i j A

0 1, ( , )ijx i j A



• ¿Cómo resolverlo?

• Es un problema lineal con variables continuas

• Algoritmo Simplex especializado a redes

• Pero hay otros algoritmos especializados y eficientes

• Algoritmo de las marcas o Algoritmo de Dijkstra

Este algoritmo busca la ruta más corta entre el nodo de origen y TODOS

los otros nodos de la red con distancias no negativas.



• Algoritmo de Dijkstra:

• Calcula en cada iteración la distancia di para cada nodo de la red

• Utiliza esta distancia como una cota superior del camino más corto al

nodo i.

• En cada iteración divide los nodos en 2 conjuntos:

• Aquellos a los que ya se les conoce la ruta mínima entre el origen

y el nodo i (marcados o etiquetados permanentemente)

• Aquellos a los que aún no les conoce la ruta mínima entre el

origen y el nodo i (marcados o etiquetados temporalmente)




beginS:= ; T:=N;d(i):= para cada nodo i N;d(s):= 0 y pred(s):=0;

while |S|<n doBegin

let i T un nodo con d(i)=min{d(j):j T};S:=S U {i};T:=T - {i}

for each (i,j) A(i) do

if d(j)>d(i)+cij then d(j):= d(i) + cij y pred(j):=i;

end;

end;




• La idea es ir pasando los nodos desde el conjunto T al conjunto S.

• En resumen:

• Inicialmente, sea S={s}, dv= ∞ , v S, ds = 0.

• Etapa general: sea i S el último nodo que ingresó a S.

• Actualizar dj ← min{dj , di + cij } , (i,j) A, j S

• Sea k V‐S tal que dk = min{dj : j V‐S }.

• S = S U {k}.



• Ejemplo Algoritmo de Dijkstra:

• Determinar la ruta más corta desde el nodo 1 al nodo 5

1

2

3

4

560

20

15

50430

100



• Ejemplo Algoritmo de Dijkstra:

1

2

3

4

560

20

15

50430

100d1=0

pred(1)=0

d2=49

pred(2)=4

d4=34

pred(4)=3

d3=30

pred(3)=1

d5=84

pred(5)=4



• Ruta más corta:

• Algoritmo de Dijkstra

• Este algoritmo de Dijkstra puede no servir si hay arcos con costo negativo.

• Queremos llegar del nodo 1 al 3. Apliquemos

Dijkstra:

• Iteración 1:

• Iteración 2:

• FIN ……. ¿Es correcto?

1

2

3

3

2

‐2

1

2 3

01

dSd d

2 2 12 1

3 3 13 1

, ,3 0 3

, , 2 0 2

1,3

d Min d c d Min

d Min d c d Min

S



• Es posible resolver n veces el algoritmo para encontrar las rutas más cortas entre

todos los nodos de la red.

• Pero hay un algoritmo más eficiente que resuelve lo anterior llamado algoritmo de

Floyd.



• Este es otro problema básicos de flujo en redes.

• Posee aplicaciones directas y también es un subproblema de otros problemas

mayores.

• La pregunta a responder es: ¿cuál es el flujo máximo que se puede enviar entre un

par de nodos?

Problema de Flujo máximo


• Consideramos un grafo DIRIGIDO G = (N,A).

• Cada arco tiene una CAPACIDAD mínima (lij ) y una máxima (uij , eventualmente ∞).

• No hay costos asociados.

• Existen dos nodos especiales:

• 1 V será el “origen”

• n V será el “destino”

• El problema consiste en enviar flujo en la mayor cantidad posible desde 1 con

destino n.

1

4

6

3 5

2(0,3)

(0,5)

(0,2)

(0,5)

(0,4) (0,2)

(0,2) (0,3)

(0,5)



• El problema es enviar la mayor cantidad de flujo desde 1 a n.

1 1: 1, : ,1

: , : ,

: , : ,

. .

0 2,..., 1

,,

0

j kj j A k k A

ij kij i j A k k i A

nj knj n j A k k n A

ij ij

ij ij

Max Fs a x x F

x x i n

x x F

x u i j Ax l i j A

F



• Algunas definiciones:

• Corte: Dado un grafo conexo G=[N,A], se dice que S N define un corte que

separa 1 de n, si 1 S y n N‐S.

• Capacidad del corte:

1

2

3

1

4

2 4

2

3

( , ): ,

( ) iji j i S j N S

C S u



• Capacidad del corte:

• S={1} N‐S={2,3,4} C(S)=5

• S={1,2} N‐S={3,4} C(S)=9

• S={1,3} N‐S={2,4} C(S)=3

• S={1,2,3} N‐S={4} C(S)=5

1

2

3

1

4

2 4

2

3

( , ): ,

( ) iji j i S j N S

C S u



• ¿Qué se puede decir?

• Teorema de Ford Fulkerson (Flujo máximo‐Corte mínimo):

El flujo máximo entre el nodo origen y el destino es igual a la menor

capacidad entre todos los conjuntos de corte que separan el nodo origen y el

destino.



• Algoritmo de Ford Fulkerson :

• La idea es construir iterativamente el flujo máximo, a partir de un flujo factible.

• En cada iteración se identifica un camino de aumento de flujo con respecto al flujo

existente.

• Determinación de la cantidad de flujo adicional máxima que puede transportar el

camino determinado en la primera parte.




• ¿Cómo identificar un camino de aumento de flujo?

• Construir un grafo auxiliar G’ (grafo incremental o residual)

• Los nodos de G’ son los nodos de G

• Los arcos de G’ se calculan así:

• Así si lij<xij<uij en G, se generan 2 arcos en G’

, , 'ij ij

ij ij ij

Si x u enG entonces el arco i j se incorpora a G

concapacidad residual u x

, , 'ij ij

ij ij ij

Si x l enG entonces el arco j i se incorpora a G

concapacidad residual x l




• Construido G’ se calcula un camino C’ (equivalente a un camino C de aumento

de flujo en G) desde el nodo 1 (origen) al nodo n (destino).

• Si no existe C’ en G’, el algoritmo termina.

• Se determina la cantidad máxima de flujo adicional () que el camino C’

admite (viendo los arcos de C’)

• ¿Cómo determinar el nuevo flujo?

• Flujo adicional () se suma al existente en arcos hacia adelante en C

• Flujo adicional () se resta al existente en arcos hacia atrás en C

• Nuevo valor: F’=F +

1 2, ,min min , minij ij ij iji j C B i j C B

u x x l



• Algoritmo de Ford Fulkerson:

1. Inicialización: determinar un flujo factible F

Si lij= 0 (i,j) , F=0 y xij=0 (i,j) es factible

2. Construir el grafo auxiliar G’=[N, A’] y definir B1=B2=

Determinar A’:

• Si xij<uij, entonces el arco (i,j) se incorpora a A’ y B1=B1 {(i,j)} y ij=uij-xij

• Si xij>lij, entonces el arco (j,i) se incorpora a A’ y B2=B2 {(j,i)} y ij=xij-lij

3. Determinar un camino C’ en G’ desde el nodo 1 al n

• Si no existe ningún C’, el flujo actual es máximo

• Si existe, determinar el flujo máximo adicional que admite el camino de

aumento de flujo C

1 2, ,min min , minij iji j C B i j C B



• Algoritmo de Ford Fulkerson:

4. Nuevo flujo factible F

Volver a 2

1

2

si ,

si ,ij ij

ij ij

F F

x x i j C B

x x i j C B



• Ejemplo:

• Sea el siguiente grafo G

• lij= 0 (i,j) A

• Flujo factible: xij= 0 (i,j) puesto que lij= 0 y F=0

1

5

6

3 4

22

3

1

3

1 1

1 3

3F

uij

F



• Ejemplo:

• Iteración 1

1

5

6

3 4

20

0

0

0

0 0

0 0

00 0

1

5

6

3 4

22

3

1

3

1 1

1 3

3

G G’

1

5

6

3 4

22

3

1

3

1 1

1 3

3F F

ij



• Ejemplo:

• Iteración 1

1

5

6

3 4

22

3

1

3

1 1

1 3

3

G’

1

5

6

3 4

22

3

1

3

1 1

1 3

3F F

ijCamino de aumento de flujo C

Flujo adicional

1‐2‐5‐6 2


2


• Ejemplo:

• Iteración 2

1

5

6

3 4

22

0

0

2

0 0

0 0

22 2

1

5

6

3 4

22

3

1

1

1 1

1 3

1

G G’

1

5

6

3 4

22

3

1

3

1 1

1 3

3F F

2


2


• Ejemplo:

• Iteración 2

1

5

6

3 4

22

3

1

1

1 1

1 3

1

G’

1

5

6

3 4

22

3

1

3

1 1

1 3

3F F

2Camino de aumento de flujo C

Flujo adicional

1‐3‐5‐4‐6 1


22

2


• Ejemplo:

• Iteración 3

1

5

6

3 4

22

1

0

2

1 1

0 1

23 3

1

5

6

3 4

22

1

1

1 1

1

1

G G’

1

5

6

3 4

22

3

1

3

1 1

1 3

3F F

2

11


22

2


• Ejemplo:

• Iteración 3

1

5

6

3 4

22

1

1

1 1

1

1

G’

1

5

6

3 4

22

3

1

3

1 1

1 3

3F F

2

11

Camino de aumento de flujo C

Flujo adicional

1‐3‐4‐6 1


11

2


• Ejemplo:

• Iteración 4

1

5

6

3 4

22

2

0

2

1 1

1 2

24 4

1

5

6

3 4

22

1

1

1 1

1

1

G G’

1

5

6

3 4

22

3

1

3

1 1

1 3

3F F

2

22


11

2


• Ejemplo:

• Iteración 4

1

5

6

3 4

22

1

1

1 1

1

1

G’

1

5

6

3 4

22

3

1

3

1 1

1 3

3F F

2

22

Camino de aumento de flujo C

Flujo adicional

………………… 0



• Ejemplo:

• Solución óptima:

1

5

6

3 4

22

2

0

2

11

1 2

24 4

G

1

5

6

3 4

22

3

1

3

1 1

1 3

3F F


12_ind2209_alumno_15

Documents