Prototipo de problema de árbol de extensión mínimo
Enviado por Joao Bruno • 5 de Noviembre de 2020 • Tareas • 1.545 Palabras (7 Páginas) • 138 Visitas
- Prootipo de problema de árbol de extensión mínimo.
El ejemplo prototipo que se plantea es el mismo del capítulo 1, se trata de encontrar el árbol de extensión mínimo de la red de la Figura No 4-3,
[pic 1]
Figura No 4-3: modelo prototipo de red para calcular el árbol de mínima expansión
El modelo matemático que representa este problema es:
Xij = Representa el uso de la rama que va del nodo “i” al nodo “j”
F. O minimizar Dt = 15x12+10x13+11x14+11x23+17x25+9x34+13x35+18x36+14x46+15x56
s.a
x12 + x13 + x14 + x23 + x25 + x34 + x35 + x36 + x46 + x56 = 5
x12 + x13 + x14 >=1[pic 2][pic 3]
x12 + x23 + x25 >=1
x13 + x23 + x34 + x35 + x36 >= 1
x14 + x34 + x46 >= 1
x25 + x35 + x56 >=1
x36 + x46 + x56 >=1
[pic 4]
x12 + x14 + x23 + x34 <= 3[pic 5]
x23 + x25 + x34 + x46 + x56 <= 4
x13 + x14 + x36 + x46 <= 3
x12 + x13 + x25 + x35 <= 3
x13 + x14 + x34 <= 2
xij =0,1
- Diseño del cromosoma.
La primera dificultad que se presenta para este modelo es que la red no es completa, es decir no se tienen todas las ramas de cada nodo al resto de nodos, una segunda dificultad es la representación del cromosoma, pues de alguna manera la solución tiene que representar un árbol de los múltiples posibles. El objetivo es construir un algoritmo que supere estos dos inconvenientes.
Un planteamiento inicial es considerar la red completa y donde no hay ramas entre nodos se penaliza con una cantidad muy grande y luego, utilizar la representación natural es decir generar aleatoriamente n-1 ramas enlazadas y sin repetición, donde “n”, es el número de nodos de la red; a continuación se presentan algunas soluciones como ejemplos:[pic 6]
Ejemplo 1:
1 – 2 – 3 – 4 – 5 –6
La rama 4 - 5 no existe
[pic 7][pic 8][pic 9][pic 10][pic 11][pic 12][pic 13][pic 14]
Ejemplo 2: 3 – 5 – 4 – 2 – 1 – 6[pic 15][pic 16][pic 17][pic 18][pic 19]
La rama 5-4 no existe[pic 20][pic 21][pic 22][pic 23][pic 24][pic 25][pic 26]
La rama 4 –2 no existe[pic 27][pic 28][pic 29][pic 30]
La rama 1– 6 no existe[pic 31][pic 32]
[pic 33][pic 34][pic 35][pic 36][pic 37][pic 38]
[pic 39][pic 40][pic 41][pic 42][pic 43][pic 44][pic 45][pic 46][pic 47]
Ejemplo 3: 2 – 3 – 5 – 6 – 4 – 1[pic 48][pic 49][pic 50][pic 51][pic 52][pic 53][pic 54][pic 55][pic 56][pic 57]
[pic 58]
Sin embargo esta representación no admite soluciones como:[pic 59]
Ejemplo 4:[pic 60][pic 61][pic 62][pic 63][pic 64][pic 65][pic 66][pic 67][pic 68][pic 69][pic 70][pic 71][pic 72][pic 73][pic 74][pic 75][pic 76][pic 77][pic 78][pic 79][pic 80][pic 81][pic 82][pic 83]
1– 3 – 2… no se puede representar.[pic 84]
Por lo tanto se planteó otro diseño de cromosoma que siendo también de una representación natural si incluye todas las posibles combinaciones de árboles, esta se basa en la matriz de distancias según la Tabla No 4-3 y la Tabla No 4-4:
...