1. MODELO DE REDES FRANCISCO VARGAS INGENIERO DE SISTEMAS ESPECIALISTA EN GERENCIA DE SISTEMAS INFORMTICOS MAGSTER EN CIENCIAS DE LA INFORMACIN Y LAS COMUNICACIONES CON NFASIS EN TELEINFORMTICA CANDIDATO A DOCTOR EN CIENCIA Y TECNOLOGA INFORMTICA 2015 2. MODELO DE REDES Problemas de transporte ( o distribucin) Envo de mercancas entre fuentes y destinos0. GENERALIDADES Con costos de transporte mnimo Modelo de red Se representa y resuelve Ejemplos: a. Diseo red de tubera de gas natural, conectar fuentes del Golfo de Mxico con un punto de entrega en tierra objetivo minimizar el costo de construccin del conducto. b. Determinacin de la ruta ms corta que une 2 ciudades en una red de caminos existente c. Determinacin del programa de flujo de costo mnimo de los campos petrolferos a refineras , y finalmente a centros de distribucin. Se puede enviar petrleo y derivados en buques, oleoductos y/o camiones. Conclusiones: Los problemas de optimizacin de redes se pueden representar en trminos generales a travs de uno de cuatro modelos: 1. Modelo del rbol de extensin mnima 2. Modelo de la ruta ms corta 3. Modelo del flujo mximo 4. Modelo de red capacitada de costo mnimo 3. MODELO DE REDES 1. DEFINICIN DE REDES RED Nodo 1 Nodo 2 Nodo n . . . Arcos o ramas Ejemplo: Red de transporte Notacin: Red G G = (N, A), donde N es el conjunto de nodos y A es el conjunto de ramas 3 2 4 5 1 Figura 1. La red de la figura se describe as: 5 nodos, 8 ramas N= 1,2,3,4,5 A= (1,3), (1,2), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5) 4. MODELO DE REDES 1. DEFINICIN DE REDES El flujo de una rama est limitado por su capacidad que puede ser finita o infinita Rama dirigida u orientada: Si permite un flujo positivo en una direccin, y cero flujo en la direccin opuesta. Red dirigida: Red con todas sus ramas dirigidas. Trayectoria: Es una secuencia de ramas distintas que conectan 2 nodos sin considerar la orientacin de las ramas individuales. Por ejemplo: en la figura 1 las ramas (1,3), (3,2), y (2,4) constituyen una trayectoria del nodo 1 al 4. Una trayectoria forma un lazo o ciclo si conecta un nodo consigo mismo. Por ejp en la figura 1 las ramas (2,3), (3,4), y (4,2) forman un lazo. Lazo dirigido o circuito es un lazo donde todas las ramas tienen la misma direccin u orientacin. Red conectada, Es una red donde cada dos nodos distintos estn conectados por una trayectoria como se observa en la figura 1. rbol: Es una red conectada que puede constar solo de un subconjunto de los nodos. rbol extenso: Es una red conectada que incluye todos los nodos de la red sin lazos. 3 2 1 4 3 2 1 4 5 rbol extensorbol 5. MODELO DE REDES 2. PROBLEMA DEL ARBOL DE EXTENSIN MINIMA Escenario: Crear una red de caminos pavimentados para conectar x # de poblaciones rurales. Limitaciones: Presupuestales, # de km de caminos por construirse debe ser el mnimo absoluto que permita la conexin directa o indirecta del trfico entre las poblaciones. Representar por una red donde las poblaciones representan nodos y los caminos propuestos representan ramas. Situacin Modelo resultante es caracterstico del problema del rbol de extensin mnima, donde se desea determinar el rbol extenso que proporciona la suma mnima de ramas conectoras. 6. MODELO DE REDES 2. PROBLEMA DEL ARBOL DE EXTENSIN MINIMA Inicio Comenzar con cualquier nodo y conectar a ste con el ms cercano de la red Los dos nodos resultantes forman un conjunto conectado C y los nodos restantes constituyen el conjunto no conectado C El algoritmo del rbol de extensin mnima necesita: A continuacin, se escoge un nodo del conjunto no conectado que sea el ms cercano (que tenga la rama de longitud ms corta) a cualquier nodo del conjunto conectado. conj unto cone ctad o conjunto no conectado vaco? El nodo escogido se elimina del conjunto no conectado y se une al conjunto conectado No Fin Nota: Un empate puede romperse arbitrariamente . Sin embargo , los empates evidencian que existen soluciones alternativas. 7. MODELO DE REDES 2. Ejemplo 1. Una TV Cable Company, est planeando una red para dar servicio de TV por cable a cinco nuevas reas de desarrollo habitacional. La red del sistema de cable se resume en la figura 2. Los nmeros asociados con cada rama representan la longitud de cable (en millas) que se necesita para conectar dos sitios. El nodo 1 representa la estacin de TV por cable y los nodos restantes (2 a 6) representan las cinco reas de desarrollo. Una rama faltante entre dos nodos implica que es prohitivamente costoso o fsicamente imposible conectar las reas de desarrollo asociadas. Se necesita determinar los enlaces que originarn el uso mnimo de cable a la vez que se garantiza que todas las reas se conecten (directa o indirectamente) a la estacin de TV por cable. La solucin grfica se resume en la figura 2 mediante iteraciones. El procedimiento puede iniciarse desde cualquier nodo, terminando siempre con la misma solucin ptima. En el ejemplo de la TV por cable, es lgico empezar a realizar los clculos con el nodo 1. 4 1 2 3 5 6 1 4 9 5 7 6 3 (millas) 10 8 3 5 Figura 2 8. MODELO DE REDES 2. Ejemplo 1. Por lo tanto, el nodo 1 representa el conjunto de nodos conectados. El conjunto de nodos no conectados lo representan los nodos 2,3,4,5 y 6. En forma simblica escribimos esto como : Iteracin 1: El nodo 1 debe conectarse al nodo 2, que es el nodo ms prximo en C = 2,3,4,5,6 tanto, la iteracin 1 de la figura 3 muestra que: Iteracin 2: Los nodos 1 y 2 ahora estn unidos permanentemente. En la iteracin 2 seleccionamos un nodo en C = 3,4,5,6 que est ms prximo a un nodo en C = 1,2 . Como la distancia ms corta ocurre entre 2 y 5, tenemos: C = 1 C = 2,3,4,5,6 C = 1,2 C = 3,4,6C = 1,2,5 C = 3,4,5,6 Iteracin 3: Los nodos 2 y 4 estn conectados , lo q produce C = 1,2,4,5 C = 3,6 Iteracin 4: Los nodos 4 y 6 deben estar conectados. Por lo tanto obtenemos C = 1,2,4,5,6 C = 3 9. MODELO DE REDES 2. Ejemplo 1. Iteracin 5: En esta iteracin se tiene un empate que se puede romper arbitrariamente. Esto quiere decir que ponemos conectar 1 y 3 o 4 y 3, ambas soluciones nos conducen a: C = 1,2,3,4,5,6 C = O Como todos los nodos estn conectados , el procedimiento est completo . La longitud mnima (en millas) de cable que se utiliza para conectar las reas de desarrollo habitacional a la estacin de TV es igual a 1+3+4+3+5=16 milla 10. MODELO DE REDES 2. Ejemplo 1. 11. MODELO DE REDES 2. Ejercicio 1. Resuelva el ejemplo 1 mediante el uso del nodo 4 como el conjunto conectado inicial; es decir, C inicial = 4 . Siga el procedimiento grfico explicado. 1. EL TRANSITO DEL DISTRITO METROPOLITANO La ciudad de Tunja esta planificando el desarrollo de una nueva lnea en sistemas de trnsito, dentro de los requisitos a tener en cuenta, se tienen: El sistema debe unir 8 residencias y centros comerciales El distrito metropolitano de trnsito necesita seleccionar un conjunto de lneas que conecten todos los centros a un mnimo costo. La red seleccionada debe permitir: Factibilidad de las lneas que deban ser construidas, mnimo costo posible por lnea EJERCICIOS PLANTEADOS 12. EL TRANSITO DEL DISTRITO METROPOLITANO 13. EL TRANSITO DEL DISTRITO METROPOLITANO (Solucin) 14. EJERCICIO 2 15. EJERCICIO 3 16. 4. PROBLEMA PARA RESOLVER CAMINOS EN EL PARQUE La administrador del parque del Chicamocha necesita determinar los caminos bajo los cuales se deben tender comunicaciones para conectar todas las estaciones con una longitud total mnima de cable. Dada la red indicada en la siguiente figura, se selecciona O como nodo inicial. 17. PROBLEMA PARA RESOLVER CAMINOS EN EL PARQUE (Solucin) 18. MODELO DE REDES 3. ALGORITMOS DE LA RUTA MAS CORTA Red acclica: No contiene lazos Red cclica: Contiene lazos 3.1 Algoritmo acclico: dij Sumidero o destino Inicial Uj Distancia ms corta entre el nodo 1 y el nodo j Figura 3. 19. MODELO DE REDES 3. ALGORITMOS DE LA RUTA MAS CORTA Uj Se calcula en forma recursiva por medio de la siguiente frmula: Uj = mn i La distancia Ui ms corta a un nodo i inmediatamente anterior ms La distancia dij entre el nodo actual j y su predecesor i Uj = mn Ui + dij i Procedimiento de etiquetado o de rotulacin: etiqueta del nodo j = Uj , n n Nodo que precede inmediatamente a j Uj = mn Ui + dij i = Un + dnj Ejemplo: 0,- Etiqueta del nodo 1, indicando que es el nodo fuente. 20. MODELO DE REDES 3. ALGORITMOS DE LA RUTA MAS CORTA Los clculos se pueden resumir en una tabla tal como se ilustra en la tabla 1 o en la figura de la red directamente, como se ilustra en la figura 3. (7) 13,5 (5) 7,2 (2) 2,1 (1) Ruta ptima 21. MODELO DE REDES 3. Ejercicios RUTA MAS CORTA redes Acclicas 1. Encontrar la distancia ms corta entre el nodo A y el nodo G 2. Encontrar la distancia ms corta entre el nodo 1 y el nodo 9 22. MODELO DE REDES 3. ALGORITMOS DE LA RUTA MAS CORTA 3.2 Algoritmo cclico (de Dijkstra) El algoritmo acclico no funciona de forma correcta con redes que posean lazos dirigidos (circuitos). Usa dos tipos de etiquetas : Temporal y permanente; formato de las dos etiquetas d,n d distancia ms corta disponible hasta el momento, a un nodo desde el origen n es el nodo inmediato precedente al cual la distancia es igual a d Nodo fuente que lleva etiqueta 0,- Consideramos todos los nodos que se pueden alcanzar directamente desde el nodo fuente y determinamos sus etiquetas asociadas. Las etiquetas recin creadas se designan como temporales La siguiente etiqueta permanente se selecciona como aquella , de entre las etiquetas temporales corrientes , que tenga la menor d en la etiqueta d,n (los empates se rompen arbitrariamente) El proceso se repite para el ltimo nodo que se ha designado permanente. En tal caso, una etiqueta temporal de un nodo se puede cambiar solo si la nueva etiqueta da una distancia d menor. Inicio Fin 23. MODELO DE REDES 3. ALGORITMOS DE LA RUTA MAS CORTA Aplicar el procedimiento a la red en la figura 4. Figura 4. 24. MODELO DE REDES 3. ALGORITMOS DE LA RUTA MAS CORTA Aplicar el procedimiento a la red en la figura 4. 25. MODELO DE REDES 3. ALGORITMOS DE LA RUTA MAS CORTA La siguiente figura 5 muestra la solucin. 26. MODELO DE REDES 3. ALGORITMOS DE LA RUTA MAS CORTA Ejercicio. El siguiente ejemplo se desarrollar con el fin de encontrar el camino ms corto desde 1 hasta 4: Ejercicio. El siguiente ejemplo se desarrollar con el fin de encontrar el camino ms corto desde 1 hasta 8: 27. MODELO DE REDES 4. MODELO DEL FLUJO MXIMO Rama (i,j) puede tener 2 capacidades distintas Flujo de i a j Flujo de j a i Ejp: Calle, lnea telefnica, etc (1 sentido y 2 sentidos) 0 1 2 3 4 5 6 7 8 9 Fuente Destino Refineras Estaciones de bombeo Terminales Flujo en una sola direccin: 1,2,3, 7, .. Flujo en cualquier direccin: 4,5,6 28. MODELO DE REDES 4. MODELO DEL FLUJO MXIMO 1 Determinar el flujo mximo entre los nodos origen y destino de la siguiente red: 4 2 5 3 20 30 10 0 5 20 0 0 0 20 10 0 0 40 30 0 Notacin: C Capacidad i,j ndices de los nodos k Flujo mnimo del camino seleccionado C i,j , j,i =( C - k, C + k )i j Algoritmo: 1. Identificar los nodos origen y destino 2. Identificar la capacidad ms alta que sale del nodo origen 3. Identificar el nodo intermediario con [a , i] 4. Repetir como si el nodo intermediario fuera el nodo origen a Cantidad de flujo mximo que recibe el nodo i Nodo del que proviene el FM f FM = k f 29. MODELO DE REDES 4. MODELO DEL FLUJO MXIMO Ejercicio 1: 30. MODELO DE REDES 4. MODELO DEL FLUJO MXIMO Ejercicio 1: 31. MODELO DE REDES 4. MODELO DEL FLUJO MXIMO Ejercicio 1: 32. MODELO DE REDES 4. MODELO DEL FLUJO MXIMO Ejercicio 2: 33. MODELO DE REDES 4. MODELO DEL FLUJO MXIMO Ejercicio 2: 34. MODELO DE REDES 4. MODELO DEL FLUJO MXIMO Ejercicio 2: 35. MODELO DE REDES 4. MODELO DEL FLUJO MXIMO 36. MODELO DE REDES 4. MODELO DEL FLUJO MXIMO 37. MODELO DE REDES 4. MODELO DEL FLUJO MXIMO 38. MODELO DE REDES 4. MODELO DEL FLUJO MXIMO 39. MODELO DE REDES 4. MODELO DEL FLUJO MXIMO 40. MODELO DE REDES 4. MODELO DEL FLUJO MXIMO