Presentaciones Teoria De Redes Unigua 2011 Nov 641k2f

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