TEORIA DE REDES LUIS ENRIQUE ALVARADO ATENCIO INGENIERO INDUSTRIAL MAGISTER EN DIRECCION UNIVERSITARIA
CONCEPTOS BASICOS RED: También denominada grafos, es un conjunto de puntos interconectados con líneas. A los puntos se denominan NODOS o VERTICES y a las líneas se laman ARCOS, ARISTAS, FLECHAS. Si las líneas tienen una orientación determinadas se dice que son dirigidas. • FLECHAS O ARCOS: Son los Caminos posibles o Actividades a desarrollar. • NODOS: Sitios o puntos de encuentro donde se ofrece o demanda algo. - Si se ofrece algo aparece un signo +, es decir es un nodo oferente - Sise demanda algo aparece un signo - , es nodo de requerimiento o demandante.
FLUJO: Es el valor asignado a un arco que conecta dos nodos. Por ejemplo cantidad de artículos enviados de una ciudad a otra por carretera. TRAYECTORIA: Es una secuencia de arcos distintos que conectan dos nodos cualesquiera de la red
EJEMPLO DE UNA RED T
A
7
5
2
D
2
O
5
4
B
7 1
1
3
4
C
4
E
ESPECIFICACIONES DE UNA RED Nodos, Sitios
Arcos, Rutas
Flujos
Aeropuertos, Terminales de Transportes
Líneas Aéreas, Carreteras
Aviones, Vehículos, Personas
Bodegas, Almacenes
Calles, Avenidas
Mercancías
Puntos de comunicacion
Canales ó cables
Mensajes, Información
Estaciones de bombeo
Tuberías, Viaductos
Fluidos
Centros de Trabajo
Rutas de manejo de materiales
Trabajos, personas, informacion.
Flujo AB
Arcos Dirigidos
Flujo BA
Flujo Real = Red con Arcos No Dirigidos
Ruta ó Trayectoria
∆ de los Flujos Una Trayectoria entre dos nodos, es una sucesión de Arcos Dirigidos y/o No Dirigidos distintos que conectan dichos nodos. EJM: O-A-B-D-T de Seervada Park
Ciclo
Trayectoria que comienza y finaliza en el mismo nodo
Trayectoria Dirigida
A
D C
B
Trayectoria NoDirigida Ciclo Dirigido
E
Ciclo No-Dirigido
Por ejemplo: BC – CE – ED Por ejemplo: AB – BC – CA – AD
Por ejemplo: DE - ED Por ejemplo: AB – BC – CA
Terminología de REDES Arbol de Expansión
Red de “n” nodos conectados que no ite ciclos, teniendo por tanto (n-1) arcos. A
D
A
C B
D C
E
B
E
Flujo Característico Tipos de NODOS
Capacidad de los ARCOS
Origen
Salidas > Entradas
Destino
Entradas > Salidas
Transbordo
Salidas = Entradas
Cap. Max. De Flujo que circula en un arco dirigido o no dirigido
OBJETIVO: Minimizar los costos de transportar de un origen a varios destinos, respetando las restricciones de capacidades y de costos, mediante unas variables de decisión denominadas Xij . Un modelo de red es llamado en general modelo de trasbordo con capacidades en el que existen una gran variedad de problemas a resolver , sin embargo aquí abordaremos los siguientes casos especiales: El problema de la Ruta Mas Corta El problema del Árbol Expandido Mínimo El Problema del flujo Máximo.
MODELO GENERAL DE TRANSBORDO CON CAPACIDADES En forma general este modelo se formula así:
Min Z = ∑Cjk Xjk Sujeto a: ∑Xjk - ∑ Xkj = Lj con j = 1, 2 …..n
0 ≤ Xij ≤ uij
para todo (i, j) de la red. • El objetivo es minimizar el costo total del flujo a través de la red, teniendo en cuenta los siguientes aspectos:
• ∑Xjk : Es el flujo total que sale del nodo j a cualquier nodo k. • ∑ Xkj : Es el flujo total que entra al nodo j desde cualquier nodo k. • Lj : es la oferta del nodo j: Lo que sale menos lo que entra. • Lj < 0: Es un requerimiento ( nodo destino, sumidero, punto de demanda) • Lj > 0 : Ofertas, fuentes, orígenes • Lj = 0: nodo de transbordo ( ni oferta, ni demanda) • Se supone por comodidad que ∑Li Demanda) y Cij ≥ 0
= 0 (Oferta =
• Uij : son las restricciones de capacidad del flujo en cada arco. Se dice entonces que uij ≥ 0. Consideraciones especiales respecto de uij . • Si uij = ∞ : Se dice que el arco no tiene restricción en su capacidad de tránsito o que tiene una capacidad suficientemente grande. • Si uij =0 : No existe el arco, no hay tránsito en esa ruta. • Los datos necesarios para resolver el modelo son Cij , uij y Lj. • Si los valores anteriores son enteros entonces el problema siempre tendrá una solución entera.
• A cada Arco se le asigna una variable de decisión Xij . • A cada Nodo se le asocia una ecuación ó Restricción. • Los Arcos son normalmente orientado, es decir con flujos en una dirección específica. 2
C uij
5
NOTA: Planteado el problema así, se puede resolver por P.L. ,usando Método simplex u otro algoritmo valido
CASOS PARTICULARES DE REDES EL PROBLEMADE LA RUTA MAS CORTA Consiste en una Red donde a cada Arco (i,j) se asocia una valor Cij (Distancia, Tiempo, Costo, etc), el cual se da entre los nodos i,j lo que determina la ruta que los une. OBJETIVO: Encontrar la ruta mas corta (Económica, rápida) entre un nodo cualquiera y los demás de la Red.
CARACTERISTICAS. • Los Arcos no son orientados: se permite el flujo en cualquiera dirección. • Hay un Origen único Oferente (H). • no se trata de conseguir las Xij optimas, sino, las combinaciones de rutas optimas entre H y los demás nodos de la Red. • Cij ≥ 0, siempre • El algoritmo de solución de Disjktra consta de (n-1) pasos con ( n = número de nodos)
ALGORITMOS DE SOLUCION Permite determinar la ruta mas corta entre el nodo origen y cualquier otro nodo de la red.
Algoritmo de Disjkstra
Permite determinar la ruta mas corta entre cualquier par de nodos de la red (mas general)
Algoritmo de Floyd
Algoritmo de Disjktra
i
dij
j
[uj, i]
Nodo permanente previo
Distancia mas corta “hasta j” desde el origen
Nodos Temporales y Nodos Permanentes
uj = ui + dij
ALGORITMO DE DISJKTRA Este algoritmo usa el sistema de etiquetado, es decir, una señal o código de mejora. • La Etiqueta es temporal en la medida que pueda mejorar, de lo contrario se vueleve permanente. • La etiqueta se representa par una pareja (a , b), donde a corresponde al valor (costo , distancia, tiempo) del Nodo H hasta el nodo j y b indica el nodo precedente Ejemplo: 5 (4, 3): La distancia de H a (5) es
4, y a (5) se llegó del nodo (3)
DESCRIPCION DE ALGORITMO 1. Considere los nodos conectados directamente con el origen H, colóqueles una etiqueta permanente a todos ellos. (C, H) 2. Al nodo de etiqueta temporal de costo mínimo colóquese una etiqueta permanente (los empates rómpalos arbitrariamente) 3. Analice los nodos vecinos del ultimo nodo (K) etiquetado permanente y conectados a él con un solo arco. 4. Calcule para cada nodo vecino su distancia a K mas la etiqueta del nodo K. Si el nodo vecino no tiene etiqueta asígnele una temporal igual a la suma anterior. Si ya tenia etiqueta temporal, cámbiela, solo si la suma recién calculada es menor que la etiqueta actual. Regrese al paso 2.
4. Las etiquetas permanentes indican las distancias mas cortas desde el origen a cada nodo de la red, lo mismo que el nodo precedente. Para encontrar la ruta mínima a un nodo dado, comience en él y retroceda al precedente y continúe retrocediendo hasta llegar al origen. EJEMPLO. Se desea saber cuales son los costos de transporte mínimos para llevar el combustible desde un centro petrolero a seis subestaciones, según la siguiente gráfica. Los números en la flechas son los costos unitarios de transporte entre centros.
1 9 C
4 3
6
4
2
5 3
1
4 5
4
2
6
5
3
6
9,C
1 9
4 3
6,C
C
6
4
2
5 3 5,C
1
4 5
4
2
6
5
3
6
9,C
1 9
4 3
6,C
C
6
4
2
5 3 5,C
1
4 5
4
2
6
5
3
6
9,C
1 9
4 3
6,C
C
6
4
3 5,C
1
4 5
4
2
2
5
8,2
6
5 9 ,4
3
6
9,C
1 9
4 3
6,C
C
6
4
3 5,C
12 , 4
1
4 5
4
2
2
5
8,2
6
5 9 ,4
3
6 12, 5
SOLUCION. NODO RUTA DESDE C 1 C-1 2 C-2 3 C-3 4 C-2-4 5 C- 2-4-5 6 C-2-4-8 6 C-2-4-5-6
DISTANCIA 9 6 5 8 9 12 12
Aplicando el algoritmo de Dijkstra encontrar el COSTO MINIMO desde el nodo inicial 1 hasta el nodo final 9.
26
A 2
2 5
O 4
7
T
5 D
4 B
1
1
3
C
7
E 4
Nodo Permanente
Nodo Temporal a conectar
Etiqueta Nodo Temporal
Anterior Etiqueta
Etiqueta Temporal Nueva
Nuevo nodo Permanente
O [0; -]
A B C
[2; O] [5; O] [4; O]
-
[2; O] [5; O] [4; O]
A [2; O]
A [2; O]
B D
[4; A] [9; A]
[5; O] -
[4; A] [9; A]
B [4; A]
B [4; A]
D E C
[8; B] [7; B] [5; B]
[9; A] [4; O]
[8; B] [7; B] [4; O]
E [7; B]
E [7; B]
D T
[8; E] [14; E]
[8; B] -
[8; E] y [8; B] [14; E]
D [8; E] y [8; B]
D [8; E] y [8; B]
T
[13; D]
[14; E]
[13; D]
T [13; D]
27
EL PROBLEMA DEL ARBOL EXPANDIDO MINIMO ( Enlaces de comunicación) OBJETIVO. Conectar todos los nodos de una red con costo mínimo (Distancia, Tiempo…) ALGORITMO. • Comenzar con cualquier nodo y conectarlo con el mas cercano que salga de este nodo. Estos nodos forman un conjunto conectado, los demás son el conjunto no conectado. Los empates se rompen arbitrariamente. • Se escoge del conjunto no conectado el nodo mas cercano y se conecta, así sucesivamente hasta conectarlos todos.
APLICACIONES Diseño de Redes de Telecomunicaciones (fibra óptica, telefónicas) Diseño de Redes de transporte para minimizar costo total de suministro de material de construcción (vías ferroviarias, carreteras). Diseño de Redes de tuberías para conectar varias sitios. Diseño de Red de cables en sistemas de computación para minimizar la longitud total del cable. Diseño de Red de líneas de transmisión de energía eléctrica de alta tensión. 29