arbol de minima expansion

-


UNIVERSIDAD NACIONAL
“SANTIAGO ANTUNEZ DE MAYOLO”





FACULTAD : Administración y Turismo
ESCUELA : Administración
CURSO : Análisis Cuantitativo I
DOCENTE : Hernan Ramírez Asis.
CICLO : VII
ALUMNOS : León Castillejo Denitza
Romero Rodríguez Jhon
2012











INTRODUCCIÓN
Mediante el método del Árbol de expansión mínima se buscaminimizar las distancias para obtener costos, distancias, tiempos mínimos y así ayudar en la eficiencia de las diferentes situaciones que se presenten en la vida de un administrador.
El siguiente trabajo explicará mediante la aplicación de algunos algoritmos, creados especialmente para dar solución a este tipo de problemas de forma sencilla y clara.

ÁRBOL DE EXPANSION MINIMA
El árbol demínima expansión comprende la minimización de redes, que es la determinación de los ramales que pueden unir todos los nodos de una red de modo que la suma de las longitudes de los ramales sea la mínima posible. Fue formulado inicialmente por Boruvka en 1926. 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.
Se han desarrollado algoritmos de tiempo polinomial para su resolución (Prim, Kruskal, Dijktra y Sollin). Debido a su complejidad y su explosión combinatoria se pueden emplear algoritmos evolutivos que mejoren larelación (calidad/tiempo) de la solución.
El algoritmo de árbol de expansión minima enlaza los nodos de una red en forma directa o indirecta, con la mínima longitud de las ramas enlazantes. Una aplicación característica es en la construcción de carreteras pavimentadas que unen varias poblaciones. Los caminos entre dos poblaciones puede pasar por uno o más poblaciones adicionales. El diseño máseconómico de sistema de caminos indica que se minimice la distancia total de caminos pavimentados, resultado que se obtiene implementando el algoritmo de árbol de expansion minima.
Los pasos del procedimiento son los siguientes: se N ={1,2,..,n} el conjunto de nodos de la red y se definen
CK = Conjunto de nodos que se han conectado en forma permanente en la iteracion k
CK = Conjunto de nodos quetodavia s edeben conectar en forma permanente.
PASO 0. El conjunto C0 =y C0 = N
PASO 1. Comenzar con cualquier nodo en el conjunto C0 no conectado (“o inconexo”) e igualar C1 ={i} con lo que C1 = N – {i}, igualar k = 2
Paso general k. seleccionar un nodo j en el conjunto no conectado Ck-1 que produzca el arco mas corto a un nodo, en el conjunto conectado Ck-1 y sacarlo de Ck-1, esto es :
CK =CK-1 + {j},CK = CK-1 – {j}
Si el conjunto CK, de nodos no conectados es vacío, detenerse en cualquier otro caso, igualar k = k+1 y repetir el paso
Ejemplo:
Midwey TV cable company esta en el proceso de proporcionar servicio de cable a cinco nuevas áreas habitacionales, en la siguiente figura representa los enlaces posibles de tv entre las cinco áreas. Las millas de cable se muestran en cadaarco, determine la red de cable mas económica.


Solución, el algoritmo comienza en el nodo 1(cualquier otro nodo podria ser), con lo que se obtiene:
C1 = {1}, C1 = {2,3,4,5,6}
Las iteraciones del algoritmo se resumen en la figura 2, los arcos con lineas delgadas son todos los enlaces posibles entre C y C, las ramas gruesas representan los enlaces permanentes entre los nodos del conjuntoconectado (o conexo) C, y la rama con línea interrumpida representa el nuevo enlace (permanente) que se agrega en cada iteracion. Por ejemplo, en la iteracion 1, la rama (1,2) es la mas corta (= 1 milla) entre todas las ramas posibles del nodo 1 a los nodos 2,3,4 y 5 del conjunto no conectado C1, por consiguiente el enlace (1,2) se vuelve permanente y j = 2, con lo que se obtiene:
C2 = {1,2}, C2...