Clase Practica N 15 - Redes

Vista previa del material en texto

CLASE PRACTICA: Investigación Operativa
Trabajo Practico Nº 8 – Modelos de Optimización de Redes 
Profesores: JTP. Ing. Néstor O. Cruz
AY1. Ing. Mariela E. Rodríguez
Facultad de Ingeniería
Universidad Nacional de Jujuy
A
B
C
D E
3
4
2
1
5
6
2
3
4
[0, - ](0)
Algoritmo de Dijkstra
Definición: “Es un algoritmo para la determinación del camino más corto, desde 
un vértice origen, al resto de vértices en un grafo, con pesos en cada nodo.”
Red de Asignación 
A
B
C
D E
3
4
2
1
5
6
2
3
4
[0, - ](0)
NODO
DISTANCIA de los NODOSETIQUETA
[Distancia, Procedencia](iteración)
Y
X Nodo Permanente
Nodo Temporal
Algoritmo de Dijkstra
A
B
C
D E
3
4
2
1
5
6
2
3
4
Resolución de ejemplo en la Red
[0, - ](0)
El método permite encontrar la distancia mínima
entre un nodo inicial y los restantes hasta llegar a
nuestro nodo destino.
Se empieza del nodo indicado como inicial al que
llamaremos nodo permanente, y conoceremos
las distancias cercanas a los nodos aledaños, a
los que llamaremos nodos temporales.
Evaluamos las distancias desde los nodos
permanentes a los nodos temporales y cuando
encontramos la mínima distancia conocida al
próximo convertiremos el nodo temporal en
nodo permanente.
Algoritmo de Dijkstra
A
B
C
D E
3
4
2
1
5
6
2
3
4
[0, - ](0)
Resolución de ejemplo en la Red
1. Haremos nodo permanente al nodo inicial.
2. Conocemos las distancias a los nodos
aledaños que se denominan nodos
temporales.
3. Elegimos como nodo permanente al nodo de
mínima distancia de los temporales.
El nodo seleccionado fue el B con distancia 3
[3, A](1)
[4, A](1)
Algoritmo de Dijkstra
A
B
C
D E
3
4
2
1
5
6
2
3
4
[0, - ](0)
Resolución de ejemplo en la Red
1. Haremos nodo permanente al nodo inicial.
2. Conocemos las distancias a los nodos
aledaños que se denominan nodos
temporales.
3. Elegimos como nodo permanente al nodo de
mínima distancia de los temporales.
El nodo seleccionado fue el B con distancia 3
4. Conocemos las distancias del nuevo nodo
permanente a los nodos temporales. La
distancia será la suma de la distancia actual
más la distancia a llegar al nodo.
5. Seleccionamos el nuevo nodo permanente.
El nodo seleccionado con menor distancia es C.
[3, A](1)
[4, A](1)
[8, B](2)
[4, B](2)
[9, B](2)
Existe un empate en la distancia del nodo C. 
Quiere decir, que se puede llegar a este nodo 
por el camino A – C o por el camino A – B - C
Algoritmo de Dijkstra
A
B
C
D E
3
4
2
1
5
6
2
3
4
[0, - ](0)
Resolución de ejemplo en la Red
1. Haremos nodo permanente al nodo inicial.
2. Conocemos las distancias a los nodos
aledaños que se denominan nodos
temporales.
3. Elegimos como nodo permanente al nodo de
mínima distancia de los temporales.
El nodo seleccionado fue el B con distancia 3
4. Conocemos las distancias del nuevo nodo
permanente a los nodos temporales. La
distancia será la suma de la distancia actual
más la distancia a llegar al nodo.
5. Seleccionamos el nuevo nodo permanente.
El nodo seleccionado con menor distancia es C.
6. Repetimos los pasos 2 y 3.
7. Vemos que el nodo D tiene dos distancias y
nos quedamos con la menor distancia.
8. Ahora el nuevo nodo permanente será D.
[3, A](1)
[4, A](1)
[8, B](2)
[4, B](2)
[9, B](2)
[7, C](3)
[8, C](3)
Algoritmo de Dijkstra
A
B
C
D E
3
4
2
1
5
6
2
3
4
[0, - ](0)
Resolución de ejemplo en la Red
9. Calculamos la distancia del último nodo
temporal.
10. En el nodo E tenemos distancias alternativas
y eliminamos la de mayor distancia.
[3, A](1)
[4, A](1)
[8, B](2)
[4, B](2)
[9, B](2)
[7, C](3)
[8, C](3)
[9, D](4)
Algoritmo de Dijkstra
A
B
C
D E
3
4
2
1
5
6
2
3
4
[0, - ](0)
Resolución de ejemplo en la Red
9. Calculamos la distancia del último nodo
temporal.
10. En el nodo E tenemos distancias alternativas
y eliminamos la de mayor distancia.
11. El nuevo nodo permanente es E.
12. Llegamos al final haciendo permanente al
nodo consignado como objetivo.
[3, A](1)
[4, A](1)
[8, B](2)
[4, B](2)
[9, B](2)
[7, C](3)
[8, C](3)
[9, D](4)
Existe un empate en la distancia del nodo E. 
Quiere decir, que se puede llegar a este nodo 
desde B o C.
Algoritmo de Dijkstra
A
B
C
D E
3
4
2
1
5
6
2
3
4
[0, - ](0)
Obtenemos el camino y la Distancia.
La distancia del Nodo A a E es 8.
Para obtener el camino empezamos del nodo
final E.
Camino: E
Vemos que con distancia 8 llegamos por dos
caminos por B o C.
Camino 1: B - E
Camino 2: C - E
Para el camino 1 debemos ir por A y para el
camino 2 hay dos opciones:
Camino 1: A - B - E
Camino 2: A - C - E
Camino 3: A - B - C - E
[3, A](1)
[4, A](1)
[8, B](2)
[4, B](2)
[9, B](2)
[7, C](3)
[8, C](3)
[9, D](4)
Algoritmo de Dijkstra
** Resolver en clase por algoritmo de Dijkstra, subir al aula Virtual:
Identificar el camino mas corto del nodo 1 al nodo 5.
Algoritmo de Dijkstra
Problema del Flujo Máximo
Algoritmo de Ford-Fulkerson
El algoritmo de Ford-Fulkerson propone 
buscar rutas en una red de distribución en las 
que se pueda aumentar el flujo, hasta que se 
alcance el flujo máximo. La idea es encontrar 
una ruta con un flujo positivo neto que una 
los nodos origen y destino.
B
10
0 4
7
5
5
0 10
0
DA
C
8 04
Ejemplo:
Determínese el flujo máximo de material que puede ser enviado de la fuente A al destino D, a
través de la red que se muestra en la figura.
Recordar:
Pueden transportarse 10 unidades de
A a B a lo largo de AB,
De B a A (en la dirección opuesta)
sólo pueden transportarse 0
unidades.
En contraste, los flujos a lo largo de
BC pueden moverse en ambas
direcciones, con una capacidad de 5
unidades en ambos sentidos.
Problema del Flujo Máximo
Algoritmo de Ford-Fulkerson
B
10
0 4
7
5
5
0 10
0
DA
C
8 04
Problema del Flujo Máximo
Algoritmo de Ford-Fulkerson
B
10
0 4
7
5
5
0 10
0
DA
C
8 04
B
10
0 4
7
5
5
0 10
0
DA
C
8-8=0
4
0+8=8
Problema del Flujo Máximo
Algoritmo de Ford-Fulkerson
B
10
0 4
7
5
5
0 10
0
DA
C
8 04
B
10-5=5
0+5=5 4
7
5-5=0
5+5=10
0 10-5=5
0+5=5
DA
C
8-8=0
4
0+8=8
8+5=13
B
5
5 4
7-5=2
0
10
0+5=5 5-5=0
5+5=10
DA
C
0
4
8
Problema del Flujo Máximo
Algoritmo de Ford-Fulkerson
B
5
5 4
7
0
10
0 5
5
DA
C
0
4
8
8+5=13 8+5+5=18
B
5-4=1
5+4=9 4-4=0
7
5
5
0 10
0
DA
C
0
4+4=8 8
Problema del Flujo Máximo
Algoritmo de Ford-Fulkerson
B
5
5 4
2
0
10
5 0
10
DA
C
0
4
8
8+5+5=18
8+5+5+4=22
B
1
9 0
7
5
5
0 10
0
DA
C
0
8 8
8+5+5+4=22
Problema del Flujo Máximo
Algoritmo de Ford-Fulkerson
B
10
0 4
7
5
5
0 10
0
DA
C
8 04
20
10
20Fuente Destino
4
10
0 20
30
5
0
30
0
0 51
2 30
40 0
0
0
Resolver por Flujo máximo
0
0
0Fuente Destino
4
0
10 0
0
15
20
10
20 51
2 320
40 0
30
20
Resultado
20
10
20Fuente Destino
4
10
0 20
30
5
0
30
0
0 51
2 30
40 0
0
0
Árbol de expansión Mínima
1
2
6
5
3
4
1
2
6
5
3
4
1
3
9
5
7
5 10
4
8
3
6
Árbol de expansión Mínima
1
2
6
5
3
4
1
2
6
5
3
4
1
3
9
5
7
5 10
4
8
3
6
C1 = {1} , C1 = {2,3,4,5,6}
1
Árbol de expansión Mínima
1
2
6
5
3
4
1
2
6
5
3
4
1
3
9
5
7
5 10
4
8
3
6
C2 = {1,2} , C2 = {3,4,5,6}
1
3
Árbol de expansión Mínima
1
2
6
5
3
4
1
2
6
5
3
4
1
3
9
5
7
5 10
4
8
3
6
C3 = {1,2,5} , C3 = {3,4,6}
1
3
Árbol de expansión Mínima
1
2
6
5
3
4
1
2
6
5
3
4
1
3
9
5
7
5 10
4
8
3
6
C4 = {1,2,4,5} , C4 = {3,6}
1
3
4
Árbol de expansión Mínima
1
2
6
5
3
4
1
2
6
5
3
4
1
3
9
5
7
5 10
4
8
3
6
C5 = {1,2,4,5,6} , C5 = {3}
1
3
4
3
Árbol de expansión Mínima
1
2
6
5
3
4
1
2
6
5
3
4
1
3
9
5
7
5 10
4
8
3
6
C6 = {1,2,3,4,5,6} 
1
3
4
3
5
5
Solución: 1+3+4+3+5 = 16
Preguntas