Modelos de Redes: Árbol de expansión mínima M. En C. Eduardo Bustos Farías

Objetivos   

Conceptos y definiciones de redes. Importancia de los modelos de redes Modelos de programación lineal, representación en redes y soluciones usando el computador para:

* Modelos de asignación * Modelo del vendedor viajero * Modelos de la ruta mas corta * Modelos de la rama mas corta Y otros.

6

8

Un problema de redes es aquel que puede representarse por:

10

9

7

Nodos

10

Arcos

Funciones en los arcos

Introducción 

La importancia de los modelos de redes: * Muchos problemas comerciales pueden ser resueltos a través de modelos redes * El resultado de un problema de redes garantiza una solución entera, dada su estructura matemática. No se necesitan restricciones adicionales para obtener este tipo de solución. * Problemas de redes pueden ser resueltos por pequeños algoritmos , no importando el tamaño del problema, dada su estructura matemática.



Terminología de Redes * Flujo: Corresponde a la cantidad que debe transportarse desde un nodo i a un nodo j a través de un arco que los conecta. La siguiente notación es usada:

Xij= cantidad de flujo Uij= cota mínima de flujo que se debe transportar Lij= cota maxíma de flujo que se puede transportar. * Arcos dirigidos /no dirigidos: Cuando el flujo puede transportarse en una sola dirección se tiene un arco dirigido (la flecha indica la dirección). Si el flujo puede transportarse en ambas direcciones existe un arco no dirigido (sin flecha). * Nodos adyacentes: Un nodo j es adyacente con un nodo i si existe un arco que une el nodo j con el nodo i.



Rutas/Conexión entre nodos *Ruta: Una colección de arcos formados por una serie de nodos adyacentes * Los nodos están conectados si existe una ruta entre ellos.



Ciclos / Arboles /Arboles expandidos * Ciclos : Un ciclo se produce cuando al partir de un nodo por un cierto camino se vuelve al mismo nodo por otra ruta. * Arbol : Una serie de nodos que no contienen ciclos. *Arbol expandido: Es un árbol que conecta todos lo nodos de la red (contiene n-1 arcos).

Árbol de expansión mínima

7

Árbol de expansión mínima 

Este problema surge cuando todos los nodos de una red deben conectar entre ellos, sin formar un loop.



El árbol de expansión mínima es apropiado para problemas en los cuales la redundancia es expansiva, o el flujo a lo largo de los arcos se considera instantáneo.

8

Árbol de expansión mínima ¾

¾

¾ ¾

Este problema se refiere a utilizar las ramas o arcos de la red para llegar a todos los nodos de la red, de manera tal que se minimiza la longitud total. La aplicación de estos problemas de optimización se ubica en las redes de comunicación eléctrica, telefónica, carretera, ferroviaria, aérea, marítima, etc.; donde los nodos representan puntos de consumo eléctrico, teléfonos, aeropuertos, computadoras. Y los arcos podrían ser de alta tensión, cable de fibra óptica, rutas aéreas, etc. Si n = numero de nodos, entonces la solución óptima debe incluir n-1 arcos. 9

Algoritmo de Kruskal

10

Algoritmo de Kruskal 1.

2.

3.

Comenzar en forma arbitraria en cualquier nodo y conectarlo con el mas próximo (menos distante o costoso). Identificar el nodo no conectado que esta más cera o menos costoso de alguno de los nodos conectados. Deshacer los empates de forma arbitraria. Agregar este nodo al conjunto de nodos conectado. Repartir este aso hasta que se hayan conectado todos los nodos. 11

EJEMPLO 1 EL TRANSITO DEL DISTRITO METROPOLITANO Árbol de expansión mínima

12

EL TRANSITO DEL DISTRITO METROPOLITANO 

 



La ciudad de Vancouver esta planificando el desarrollo de una nueva línea en sistemas de tránsito. El sistema debe unir 8 residencias y centros comerciales. El distrito metropolitano de transito necesita seleccionar un conjunto de líneas que conecten todos los centros a un mínimo costo. La red seleccionada debe permitir: - Factibilidad de las líneas que deban ser construidas. - Mínimo costo posible por línea. 13

RED QUE REPRESENTA EL ARBOL EXPANDIDO.

Zona Norte 3

5

30

Distrito Comercial 39 4

34

38

45

32

28

40

43

35 Zona 2 Centro

6

41 37

36

1

Universidad

50

33

Zona Oeste

55

7

Shopping Center

8 Zona Este

44

Zona Sur 14



Solución - Analogía con un problema de redes - El algoritmo que resuelve este problema es un procedimiento muy fácil (“trivial”). - Corresponde a una categoría de algoritmos “ávidos”. - Algoritmo: * Comience seleccionando el arco de menor longitud. * En cada iteración, agregue el siguiente arco de menor longitud del conjunto de arcos disponibles , tomando la precaución de no formar ningún loop. * El algoritmo finaliza cuando todos los nodos están conectados.



Solución mediante el computador

- Los entrada consiste en el número de nodos, el largo de los arcos y la descripción de la red. 15

Solución óptima mediante WINQSB

16

RED QU E REPRESENTA LA SOLUCIÓN ÓPTIMA

3

Zona Norte

5

30

Distrito Comercial 39 4

34 1

Loop

38

45

32

28

40

Universidad

50

33

Zona Oeste

55

43

35 Zona 2 Centro

6

41 37

36

Shopping Center

8 Zona Este

44

Costo Total = $236 millones 7

Zona Sur 17

EJEMPLO 2 RED DE COMUNICACIONES ÀRBOL DE EXPANSIÓN MÍNIMA

18

Ejemplo 1 ¾ Se va a instalar una red de comunicación

entre 12 ciudades. ¾ Los costos de los posibles enlaces directos entre pares permisibles es el que se muestra en la figura. ¾ Cada unidad de costo representa $10,000 dólares.

19

1

4

1

5

6

3

4

9

9

2

6

10

6

7

5

7

5

3

7

1

2

2

3

11

4

8

2

1

12

20

SOLUCIÓN CON WINQSB

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

Solución Interacción

Nodo

Con nodo

Costo ($)

1

1

5

1

2

1

2

4

3

2

6

3

4

6

7

5

5

7

8

2

6

8

4

1

7

7

11

2

8

11

12

1

9

11

10

3

10

10

9

5

11

2

3

6

SUMA

$33 36

Método Tabular 1 1 2

2

4

7 8 9 10 11 12

5

6

7

8

9

10

11

12

1 6

6

4 6

4

4

3 5

3

3 6

7

6

1

1

4 3

4 7

9 5

5 1

7 2

2

2

2

9

5 7

5 2

3 3

2

1 1 37

EJEMPLO 3 winqsb

38

Solucione el siguiente árbol de extensión mínima para la red de comunicaciones de emergencia usando el método tabular. Las unidades son distancias en kms.

39

SOLUCIÓN

40

USANDO EL WINQSB

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

ITERACIÓN

DEL NODO

AL NODO

DISTANCIA

1

1

12

12

2

12

15

13

3

15

14

12

4

14

13

4

5

13

10

5

6

14

7

9

7

7

8

1

8

10

9

10

9

14

11

10

10

11

6

8

11

9

4

12

12

4

3

9

13

3

2

11

14

4

5

13

SUMA

129

57

EJEMPLO 4 CENTRO REGIONAL DE CÓMPUTO Árbol de expansión mínima 58

Un centro regional de cómputo (C.R.C.), debe instalar líneas especiales para comunicación, a fin de conectar a cinco usuarios satélite con una nueva computadora central, la compañía telefónica local es la que instalará la nueva red de comunicaciones, pero es una operación costosa. ¾ Con el propósito de reducir costos, se busca que la longitud total (Kms.) de estas líneas sea la menor posible. 59 ¾ La red para este problema es la siguiente: ¾

Un centro regional de cómputo (C.R.C.), debe instalar líneas especiales para comunicación, a fin de conectar a cinco usuarios satélite con una nueva computadora central, la compañía telefónica local es la que instalará la nueva red de comunicaciones, pero es una operación costosa. Con el propósito de reducir costos, se busca que la longitud total (Kms.) de estas líneas sea la menor posible. La red para este problema es la siguiente:

60

SOLUCIÓN

61

Desarrollo del algoritmo: · Ubicarse en el nodo 3 (puede ser en cualquier otro nodo) y se encuentra que el nodo más próximo es el 4 (10 Kms.) · El siguiente nodo más cercano al 3 o 4 es el nodo 6 (20 Kms). · Repitiendo el paso anterior tenemos el siguiente árbol de extensión mínima: 62

Con una extensión de 110 Kms. 63

Interacción

Nodos

1 2 3 4 5

3-4 4-6 3-5 4-1 1-2

Distancia (Km.) 10 20 30 30 20 110 Km.

64

MÉTODO TABULAR 1 1 2

20

3

40

4

30

5

50

6

40

2

3

4

5

6

20

40

30

50

40

40 10

40

30

10

20

30

40 20

40 65

PROBLEMA PARA RESOLVER CAMINOS EN EL PARQUE RUTA MÁS CORTA

66

67

SOLUCIÓN

68

69

70

71

72

73

74

Modelos de Redes: Problema del flujo máximo M. En C. Eduardo Bustos Farías

75

Problema del flujo máximo

76

Problema del flujo máximo  

 

Este modelo se utiliza para reducir los embotellamientos entre ciertos puntos de partida y destino en una red. Existe un flujo que viaja desde un único lugar de origen hacia un único lugar destino a través de arcos que conectan nodos intermedios Cada arco tiene una capacidad que no puede ser excedida La capacidad no debe ser necesariamente la misma para cada dirección del arco.

77

¾ Considere una red con un nodo de

entrada (o fuente) y un nodo de salida (o antifuente). ¾ El problema del flujo máximo pregunta: ¾ ¿Cuál es la cantidad máxima de vehículos, líquido, peatones o llamadas telefónicas que pueden entrar y salir del sistema en un periodo determinado de tiempo?

78

¾ En este tipo de problemas se intenta

conducir el flujo por las ramas o arcos de la red en forma óptima, aunque dicho flujo está limitado por restricciones diversas tales como: condiciones de la carpeta asfáltica, diámetros de tubería, etc. ¾ Al límite máximo de flujo de una rama se le denominará capacidad de flujo. 79

Se quiere transportar la máxima cantidad de flujo desde un punto de partida (fuente) o un punto final (pozo) ie.

Al respecto diremos que existen muchos algoritmos especializados para dar solución a los P.F.M.

80

Observación: 1.Se debe considerar una red dirigida. 2.Tiene una fuente y un pozo. 3.Los otros nodos son de trasbordo. 4.Capacidad de los arcos. 5.El objetivo es determinar el patrón factible de flujo a través de la red que maximice el flujo total desde la fuente de destino. 81



Definición del Problema - Existe un nodo origen (con el número 1), del cual los flujos emanan. - Existe un nodo terminal (con el número n), en el cual todos los flujos de la red son depositados. - Existen n-2 nodos (númerados del 2, 3,....,n-1), en el cual el flujo que entra es igual al flujo que sale. - La capacidad Cij que transita del nodo i al nodo j, y la capacidad Cji para la dirección opuesta.

82

El objetivo es encontrar la máxima cantidad de flujo que salga del nodo 1 al nodo n sin exceder la capacidad de los arcos.

83

El problema consiste en encontrar la máxima cantidad de flujo total que puede circular a través de la red en una unidad de tiempo. El único requerimiento en ellos es que para cada nodo (que no sea la fuente o el destino) la relación de equilibrio debe cumplirse: flujo que sale = flujo que entra

84

Dicho en términos formales, siendo f = flujo, n = destino, l = origen: Maximizar f sujeto a:

∑ x −∑ x j

ij

j

= f, si i = 1 ji

=

= -f, si j = n = 0 en otro caso

0 ≤ xij ≤ U ij de la red ∀i, j

U ij =

capacidades en el flujo por unidad de tiempo de los diversos arcos. 85

¾

¾

El algoritmo de flujo máximo se fundamenta en pasos de sentido común: encontrar un camino que inicie en la fuente y concluya en la antifuente, que tenga capacidad de flujo en el sentido deseado y mayor a cero para todas las ramas que integran el camino o ruta. Debemos continuar buscando caminos que vayan de fuentes a depósitos y que sigan teniendo capacidad mayor a cero para todas las ramas en el sentido del flujo.

86

PASOS DEL ALGORITMO ¾

¾

¾

¾

1. Encontrar un camino que vaya del origen al destino y que tenga capacidad mayor a cero en el sentido deseado. 2. Encontrar la rama de menor capacidad (Pf) del camino seleccionado en el paso anterior y programar el envío de dicha capacidad (Pf). 3. Para el camino elegido en el paso 1 reducir la cantidad Pf en las ramas involucradas y aumentar dicha cantidad en el sentido contrario. 4. Repetir el procedimiento desde el paso 1.

87

EJEMPLO 1 Flujo máximo

88

¾

¾

Una ciudad es atravesada por una red interestatal de carreteras de norte a sur que le permite alcanzar un nivel de 15,000 vehículos/hora en el horario “pico”. Debido a un programa de mantenimiento general, el cual exige cerrar dichas vías, un grupo de ingenieros ha propuesto una red de rutas alternas para cruzar la ciudad de norte a sur, la cual incorpora avenidas importantes.

89

La red propuesta es la siguiente. Incluye el número de vehículos (miles) que pueden circular por dichas vías. 90

1. ¿Puede la red propuesta dar cabida a un flujo máximo de 15,000 v/h de norte a sur? 2. ¿Cuál es el flujo máximo de vehículos que permite la red cada hora? 3. ¿Qué flujo se debe canalizar sobre cada rama?

91

SOLUCIÓN

92

0

5

2

3

1. 1-2-5-7

3

93

0

5

2

0

1

1

3 6 1. 1-2-5-7 3 2. 1-3-6-7 6

94

0

5

2

1

0 3 6 1

1

0

4 4

1. 1-2-5-7 3 2. 1-3-6-7 6 3. 1-4-6-7 1

95

0

5

4

2

0 1

0 3 6 1 1

1

0

4 3 4

3

1. 2. 3. 4.

1-2-5-7 3 1-3-6-7 6 1-4-6-7 1 1-4-6-5-7 1

96

SOLUCIÓN FINAL 0

2

5

4

2

0

0

1

0 1

0 4 3

4 3+6+1+1+2=13

3

1

0

1. 2. 3. 4. 5.

1-2-5-7 3 1-3-6-7 6 1-4-6-7 1 1-4-6-5-7 1 1-2-3-5-7 2

97

0

2

5

4

2

0

0

1 1

0 3 6 1 1 2

0

0

1

4 3 4

3

3 5

2

6 2

1

6

6

2

2

7

98

Deducción del modelo de programación lineal para el problema del flujo máximo

99

¾ El problema es enviar gas natural

desde un campo de producción a una ciudad a través de gaseoductos.

100

0

3

8

El planteamiento con estos datos sería: Máx f sujeto a: 7

0

0

0

6

x12 ≤ 10

x12 + x13 = f x12 − x 23 − x 24 = 0 x13 + x 23 − x34 − x35 = 0 x 24 + x34 − x 45 = 0 x35 + x 45 = f

x13 ≤ 6 x 23 ≤ 3 x 24 ≤ 5 x34 ≤ 7 x35 ≤ 8 x 45 ≤ 8 xij ≥ 0101, ∀ij

¾

¾

Este planteamiento no se ajusta a la formulación estándar de programación lineal de costo mínimo, puesto que se desconoce f y aparece simultáneamente en la función objetivo y en el lado derecho de las restricciones. Si se plantea así no es posible utilizar el algoritmo de programación lineal, por ello utilizaremos el artificio de agregar un arco ficticio entre los nodos inicial y final (x51), con ello ahora el planteamiento sería:

102

103

0

6

x12 ≤ 10 x13 ≤ 6

x51 − x12 − x13 = 0 x12 − x23 − x24 = 0 x13 + x23 − x34 − x35 = 0 x24 + x34 − x45 = 0 − x51 + x35 + x45 = 0 MAX

f = x51

x 23 ≤ 3 x 24 ≤ 5 x34 ≤ 7 x35 ≤ 8 x 45 ≤ 8 xij ≥ 0, ∀ij 104

Ejercicio para resolver Flujo máximo

105

Un conjunto de vías rápidas tiene las siguientes capacidades (miles de vehículos/hora).

1. 2.

Determinar el flujo máximo de vehículos/hora que pueden pasar por el sistema. ¿Cuántos vehículos/hora deben pasar por cada vía para lograr el flujo máximo? 106

SOLUCIÓN

107

3

6

1

2 3

5

3

1

2

SELECCIONADO

Pf (vehículos/hora)

FLUJO TOTAL DESPUÉS DE LA ITERACIÓN

1

1-4-6

(1-4) 3,000

3,000

2

1-2-5-6

(1-2) 3,000

6,000

3

1-3-6

(3-6) 2,000

8,000

4

1-3-4-2-5-6

(2-5) 1,000

9,000

5

1-3-4-5-6

(3-4) 2,000

11,000

ITERACIÓN

CAMINO

108

PROBLEMA LINEAL

109

110

111

112

EJEMPLO 4 CENTRO REGIONAL DE CÓMPUTO Árbol de expansión mínima 113

Un centro regional de cómputo (C.R.C.), debe instalar líneas especiales para comunicación, a fin de conectar a cinco usuarios satélite con una nueva computadora central, la compañía telefónica local es la que instalará la nueva red de comunicaciones, pero es una operación costosa. ¾ Con el propósito de reducir costos, se busca que la longitud total (Kms.) de estas líneas sea la menor posible. 114 ¾ La red para este problema es la siguiente: ¾

Un centro regional de cómputo (C.R.C.), debe instalar líneas especiales para comunicación, a fin de conectar a cinco usuarios satélite con una nueva computadora central, la compañía telefónica local es la que instalará la nueva red de comunicaciones, pero es una operación costosa. Con el propósito de reducir costos, se busca que la longitud total (Kms.) de estas líneas sea la menor posible. La red para este problema es la siguiente:

115

SOLUCIÓN

116

Desarrollo del algoritmo: · Ubicarse en el nodo 3 (puede ser en cualquier otro nodo) y se encuentra que el nodo más próximo es el 4 (10 Kms.) · El siguiente nodo más cercano al 3 o 4 es el nodo 6 (20 Kms). · Repitiendo el paso anterior tenemos el siguiente árbol de extensión mínima: 117

Con una extensión de 110 Kms. 118

Interacción

Nodos

1 2 3 4 5

3-4 4-6 3-5 4-1 1-2

Distancia (Km.) 10 20 30 30 20 110 Km.

119

MÉTODO TABULAR 1 1 2

20

3

40

4

30

5

50

6

40

2

3

4

5

6

20

40

30

50

40

40 10

40

30

10

20

30

40 20

40 120