View
214
Download
0
Category
Preview:
DESCRIPTION
clas 1
Citation preview
Ingeniera Industrial
Investigacin Operativa 2
TEORIA DE REDES (1)
FACULTAD DE
CIENCIAS E
INGENIERIA
Mg. Eduardo Carbajal Lpez
SESION 01
SESION 01
Teora de redes
Terminologa de redes
Problema del rbol de expansin mnimal
Problema de la ruta mas corta
Teora de redes (1)
1. T
eor
a d
e r
edes
Teora de redes
La modelacin de redes permite la resolucin de
mltiples problemas de programacin matemtica
mediante la implementacin de algoritmos
especiales creados para tal fin, conocidos como
Algoritmos de optimizacin de redes
1.
Teo
ra
de
re
de
s
Teora de redes
Dnde podemos aplicar teora de redes?
Sistemas de
Transporte
1.
Teo
ra
de
re
de
s
Teora de redes
Dnde podemos aplicar teora de redes?
Sistemas de
Comunicacin
1.
Teo
ra
de
re
de
s
Teora de redes
Dnde podemos aplicar teora de redes?
Sistemas de
redes sociales
1. T
eor
a d
e r
edes
Teora de redes
Dnde podemos aplicar teora de redes?
Sistemas
logsticos
1. T
eor
a d
e r
edes
Teora de redes
Dnde podemos aplicar teora de redes?
Planificacin de actividades
SESION 01
Teora de redes
Terminologa de redes
Problema del rbol de expansin mnimal
Problema de la ruta mas corta
Teora de redes (1)
1.1
. T
erm
inolo
ga
de r
edes
Red
Una red se compone de arcos y nodos.
La notacin empleada para nombrar una red es
(N, A) donde:
N representa el conjunto de nodos.
A representa el conjunto de arcos.
1.1
. T
erm
inolo
ga
de r
edes
Red Ejemplo
N = {1, 2, 3, 4, 5,6,7}
A = {(1, 2), (1, 3), (1,4), (2, 4), (2, 5), (3, 4), (3,6)
(4, 6), (4, 7), (5,7), (6, 7)}
1.1
. T
erm
inolo
ga
de r
edes
Cadena
Una secuencia de arcos tal que cada arco tiene
exactamente un nodo en comn con el arco previo,
se llama cadena.
Trayectoria
Una trayectoria es una cadena en la que el nodo final de cada arco es idntico al nodo inicial del arco siguiente.
1.1
. T
erm
inolo
ga
de r
edes
Cadena / Trayectoria Ejemplo
(1, 2) - (2, 4) - (2, 5)
es una cadena.
(1, 4) - (4, 7)
es una trayectoria.
1.1
. T
erm
inolo
ga
de r
edes
Ciclo
Un ciclo corresponde a la cadena que une a un
nodo con sigo mismo.
1.1
. T
erm
inolo
ga
de r
edes
Arco dirigido
Un arco dirigido es aquel que tiene un sentido
determinado, es decir que posee un nodo fuente y
un nodo destino.
1.1
. T
erm
inolo
ga
de r
edes
Arco no dirigido
Un arco no dirigido es aquel que no tiene un
sentido determinado, es ambos nodos pueden ser
fuentes y destinos a la vez.
1.1
. T
erm
inolo
ga
de r
edes
Variables asociadas a un grafo
i
j
Xij : flujo que pasa a
travs del arco
Cij : costo de envo a travs del arco
Iij : capacidad inferior
del arco.
Sij : capacidad
superior del arco.
SESION 01
Teora de redes
Terminologa de redes
Problema del rbol de expansin mnimal
Problema de la ruta mas corta
Teora de redes (1)
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Qu es un rbol de expansin?
Un rbol de expansin es aquel rbol que enlaza
todos los nodos de la red, de igual manera no
permite la existencia de ciclos.
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Problema del rbol de expansin minimal
Objetivo: Buscar el rbol de expansin de mnimo
costo, es decir conectar todos los nodos de la red
con el menor costos de conexin posible, sin
formar ciclos.
Aplicaciones usuales:
Redes de comunicacin. Redes de conexin de agua y desage. Redes de trnsito vial Redes ferroviarias Diseo de rutas martimas
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de KRUSKAL
Paso 1.- Inicio
Ordene el conjunto de arcos en forma creciente de acuerdo al costo.
Paso 2.- Aadir arco
Seleccione el arco de menor costo disponible y actvelo, siempre y cuando no forme un circuito cerrado.
Paso 3.- Criterio de terminacin
Si se tienen conectados todos los nodos terminar.
1 2
35
4
1
6
4
5
2
2
42 3
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de KRUSKAL Ejemplo
Halle el rbol de expansin mnima de la siguiente red usando el algoritmo de Kruskal.
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de KRUSKAL Ejemplo
PASO 1:
Arco Valor
(1, 2) 1
(3, 5) 2
(1, 5) 2
(2, 5) 2
(2, 3) 3
(1, 3) 4
(4, 5) 4
(3, 4) 5
(1, 4) 6
1 2
35
4
1
6
4
5
2
2
42 3
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de KRUSKAL Ejemplo
PASO 2 Y 3:
Arco Valor
(1, 2) 1
(3, 5) 2
(1, 5) 2
(2, 5) 2
(2, 3) 3
(1, 3) 4
(4, 5) 4
(3, 4) 5
(1, 4) 6
1 2
35
4
1
6
4
5
2
2
42 3
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de KRUSKAL Ejemplo
PASO 2 Y 3:
Arco Valor
(1, 2) 1
(3, 5) 2
(1, 5) 2
(2, 5) 2
(2, 3) 3
(1, 3) 4
(4, 5) 4
(3, 4) 5
(1, 4) 6
1 2
35
4
1
6
4
5
2
2
42 3
1 2
35
4
1
6
4
5
2
2
42 3
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de KRUSKAL Ejemplo
PASO 2 Y 3:
Arco Valor
(1, 2) 1
(3, 5) 2
(1, 5) 2
(2, 5) 2
(2, 3) 3
(1, 3) 4
(4, 5) 4
(3, 4) 5
(1, 4) 6
1 2
35
4
1
6
4
5
2
2
42 3
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de KRUSKAL Ejemplo
PASO 2 Y 3:
Arco Valor
(1, 2) 1
(3, 5) 2
(1, 5) 2
(2, 5) 2
(2, 3) 3
(1, 3) 4
(4, 5) 4
(3, 4) 5
(1, 4) 6
1 2
35
4
1
6
4
5
2
2
42 3
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de KRUSKAL Ejemplo
PASO 2 Y 3:
Arco Valor
(1, 2) 1
(3, 5) 2
(1, 5) 2
(2, 5) 2
(2, 3) 3
(1, 3) 4
(4, 5) 4
(3, 4) 5
(1, 4) 6
1 2
35
4
1
6
4
5
2
2
42 3
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de KRUSKAL Ejemplo
PASO 2 Y 3:
Arco Valor
(1, 2) 1
(3, 5) 2
(1, 5) 2
(2, 5) 2
(2, 3) 3
(1, 3) 4
(4, 5) 4
(3, 4) 5
(1, 4) 6
1 2
35
4
1
6
4
5
2
2
42 3
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de KRUSKAL Ejemplo
PASO 2 Y 3:
Arco Valor
(1, 2) 1
(3, 5) 2
(1, 5) 2
(2, 5) 2
(2, 3) 3
(1, 3) 4
(4, 5) 4
(3, 4) 5
(1, 4) 6
1 2
35
4
1
6
4
5
2
2
42 3
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de KRUSKAL Ejemplo
Como todos los nodos han sido conectados se
finaliza. El costo del rbol es 1+2+2+4 = 9
Arco Valor
(1, 2) 1
(3, 5) 2
(1, 5) 2
(2, 5) 2
(2, 3) 3
(1, 3) 4
(4, 5) 4
(3, 4) 5
(1, 4) 6
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de PRIM
Paso 1.- Inicio
Elegir un nodo arbitrario.
Paso 2.- Aadir arco
Activar el arco subyacente de mnimo costo al rbol activado que no forme ciclos cerrados.
Paso 3.- Criterio de terminacin
Si se tienen todos los nodos conectados terminar.
1 2
35
4
1
6
4
5
2
2
42 3
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de PRIM Ejemplo
Halle el rbol de expansin mnima de la siguiente red usando el algoritmo de Prim.
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de PRIM Ejemplo
PASO 1:
1 2
35
4
1
6
4
5
2
2
42 3
Se selecciona el
nodo 1 como nodo
inicial.
NODOS ACTIVOS:
1
1 2
35
4
1
6
4
5
2
2
42 3
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de PRIM Ejemplo
PASO 2 y 3:
El arco de menor
costo adyacente a
1 es (1,2).
NODOS ACTIVOS:
1,2
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de PRIM Ejemplo
PASO 2 y 3:
El arco de menor
costo adyacente a
1 2 es (2,5)
1 2
35
4
1
6
4
5
2
2
42 3
NODOS ACTIVOS:
1,2,5
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de PRIM Ejemplo
PASO 2 y 3:
El arco de menor
costo adyacente a
1, 2 o 5 es (3,5)
NODOS ACTIVOS:
1,2,3,5
1 2
35
4
1
6
4
5
2
2
42 3
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de PRIM Ejemplo
PASO 2 y 3:
El arco de menor
costo adyacente a
1, 2, 3 o 5 es (4,5)
NODOS ACTIVOS:
1,2,3,4,5
1 2
35
4
1
6
4
5
2
2
42 3
1 2
35
4
1
6
4
5
2
2
42 3
Como todos los nodos han sido conectados se
finaliza. El costo del rbol es 1+2+2+4 = 9
SESION 01
Teora de redes
Terminologa de redes
Problema del rbol de expansin mnimal
Problema de la ruta mas corta
Teora de redes (1)
1.2
. Pro
ble
ma d
e l
a r
uta
mas c
ort
a.
Problema de la ruta mas corta
Objetivo: Encontrar el camino mas corto desde un
nodo de origen a un nodo de destino.
Consideraciones importantes:
El coeficiente del arco puede definirse como costo, tiempo o distancia.
Los coeficientes deben ser no negativos.
Algoritmo de DIJKSTRA
Paso 1.- Inicio
Definir el nodo de origen y destino
Paso 2.- Aadir arco
Activar el arco de menor costo acumulado respecto al nodo de origen que conecte a un nodo no incluido previamente.
Paso 3.- Criterio de terminacin
Repetir el paso 2 hasta incluir en la seleccin al nodo de destino
1.2
. Pro
ble
ma d
e l
a r
uta
mas c
ort
a.
Algoritmo de DIJKSTRA Ejemplo
Un vuelo de Aerolnea Veloz est a punto de despegar de Lima sin escalas a Londres. Existe cierta flexibilidad para elegir la ruta precisa, segn las condiciones del clima. La siguiente red describe las posibles rutas consideradas donde LI y LO son Lima y Londres, respectivamente; y los otros nodos representan varios lugares intermedios. El viento a lo largo de cada arco afecta de manera considerable el tiempo de vuelo, y por ende, el consumo de combustible. Con base en el informe meteorolgico actual, junto a los arcos se muestran los tiempos de vuelo (en horas). Debido al alto costo de combustible, la administracin ha adoptado la poltica de elegir la ruta que minimiza el tiempo total de vuelo.
1.2
. Pro
ble
ma d
e l
a r
uta
mas c
ort
a.
Algoritmo de DIJKSTRA Ejemplo
1.2
. Pro
ble
ma d
e l
a r
uta
mas c
ort
a.
LI
A
B
C
D
E
F
LO
4.6
4.7
4.2
3.5
3.4
3.2
3.4
3.5
3.4
3.6
3.8
3.6
3.3
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de DIJKSTRA Ejemplo
PASO 1:
El origen es
el nodo LI.
El destino es
el nodo LO.
LI
A
B
C
D
E
F
LO
4.6
4.7
4.2
3.5
3.4
3.2
3.4
3.5
3.4
3.6
3.8
3.6
3.3
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de PRIM Ejemplo
PASO 2 y 3:
El arco de menor
costo es (LI,C)
NODOS ACTIVOS:
LI,C
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de PRIM Ejemplo
PASO 2 y 3:
El arco de menor
costo es (LI,A)
NODOS ACTIVOS:
LI,A,C
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de PRIM Ejemplo
PASO 2 y 3:
El arco de menor
costo es (LI,B)
NODOS ACTIVOS:
LI,A,B,C
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de PRIM Ejemplo
PASO 2 y 3:
El arco de menor
costo es (C,F)
NODOS ACTIVOS:
LI,A,B,C,F
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de PRIM Ejemplo
PASO 2 y 3:
El arco de menor
costo es (B,E)
NODOS ACTIVOS:
LI,A,B,C,E,F
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de PRIM Ejemplo
PASO 2 y 3:
El arco de menor
costo es (LI,C)
NODOS ACTIVOS:
LI,A,B,C,D,E,F
1.2
. Pro
ble
ma d
el rb
ol de e
xpan
si
n m
inim
al.
Algoritmo de PRIM Ejemplo
PASO 2 y 3:
El arco de menor
costo es (E,LO)
NODOS ACTIVOS:
LI,A,B,C,D,E,F,LO
Recommended