Investigación de Operaciones II

UNIDAD 5. Optimización de redes

5.3.1. Problema de árbol de mínima expansión

PROBLEMA DEL ÁRBOL DE MÍNIMA EXPANSIÓN.

El problema del árbol de expansión mínima tiene algunas similitudes con la versión principal del problema de la ruta más corta.

5.3.1. Problema de árbol de mínima expansión

En ambos casos se considera una red no dirigida y conexa, en la que la información dada incluye alguna medida de longitud positiva (distancia, costo, tiempo, etc.) asociada con cada ligadura.

5.3.1. Problema de árbol de mínima expansión

Los dos problemas involucran también el hecho de seleccionar un conjunto ligaduras de ligaduras que tiene la longitud total más corta entre todos los conjuntos de ligaduras que satisfacen cierta propiedad.

5.3.1. Problema de árbol de mínima expansión

Para el problema de la ruta más corta esta propiedad es que la ligadura seleccionada debe proporcionar una trayectoria entre el origen y el destino.

Para el árbol de expansión mínima la propiedad requerida es que las ligaduras seleccionadas deben proporcionar una trayectoria entre cada par de nodos.

5.3.1. Problema de árbol de mínima expansión

Una red con n nodos requiere sólo (n - 1) ligaduras para proporcionar una trayectoria entre cada par de nodos.

No deben usarse más ligaduras ya que esto aumentaría, sin necesidad, la longitud total de las ligaduras seleccionadas.

5.3.1. Problema de árbol de mínima expansión

Las (n - 1) ligaduras deben elegirse de tal manera que la red resultante (con sólo las ligaduras seleccionadas) forme un árbol de expansión. Por lo tanto, el problema es encontrar el árbol de expansión con la longitud total mínima de sus ligaduras.

5.3.1. Problema de árbol de mínima expansión

Este problema tiene muchas aplicaciones prácticas importantes. Por ejemplo, puede ser útil en la planeación de redes de transporte que no se transitarán mucho y en las que la inquietud principal es proporcionar alguna trayectoria entre todos los pares de nodos de la manera más económica

5.3.1. Problema de árbol de mínima expansión

El problema del árbol de mínima expansión se puede resolver de una forma bastante directa, es ocurre que se trata de uno de los pocos problemas de Investigación de Operaciones en el que ser codicioso en cada etapa del procedimiento de solución ¡conduce al final a una solución óptima!

5.3.1. Problema de árbol de mínima expansión

Así, con el inicio en cualquier nodo, la primera etapa consiste en elegir la rama más corta posible a otro nodo, sin preocuparse del efecto de esta elección pueda tener en las decisiones posteriores.

5.3.1. Problema de árbol de mínima expansión

En la segunda etapa se trata de identificar el nodo no conectado que esté más cerca de cualquiera de los dos que se acaban de conectar y después agregar la ligadura correspondiente a la red. Este proceso se repite hasta que se hayan conectado todos los nodos.

5.3.1. Problema de árbol de mínima expansión

El algoritmo de expansión mínima enlaza los nodos de una red, en forma directa o indirecta, con la mínima longitud de las ramas enlazantes.

La aplicación de este tipo de problemas de optimización se ubica, sobre todo, en las redes de comunicación eléctrica, telefonía, carretera, marítima, etc., donde los nodos representan por a si decirlo las estaciones del ferrocarril.

5.3.1. Problema de árbol de mínima expansión

Algoritmo para el problema del árbol de expansión mínima.

1. Se selecciona, de manera arbitraria, cualquier nodo y se conecta (es decir se pone una ligadura) al nodo más cercano distinto de éste.

2. Se identifica el nodo no conectado más cercano a un nodo conectado, y se conectan estos dos nodos (es decir, se agrega una ligadura entre ellos). Este paso se repite hasta que se hayan conectado todos los nodos.

5.3.1. Problema de árbol de mínima expansión

3. Empates: los empates para el nodo más cercano distinto (paso 1) o para el nodo no conectado más cercano (paso 2), se pueden romper en forma arbitraria y el algoritmo todavía debe llevar a una solución óptima. No obstante, estos empates son señal de que pueden existir (pero no necesariamente) soluciones óptimas múltiples. Todas esas soluciones se pueden identificar si se buscan las demás formas de romper los empates hasta el final. Este algoritmo termina en n- 1 iteraciones.

5.3.1. Problema de árbol de mínima expansión

En el contexto de los problemas de AEM se considera una red no dirigida y conexa. Cada ligadura está asociada a una medida de longitud positiva (distancia, costo, tiempo, etc.).

5.3.1. Problema de árbol de mínima expansión

Se trata de crear un árbol de expansión, problema útil en la planeación de redes de transporte que no se transitarán mucho y en las que la inquietud principal es proporcionar alguna trayectoria entre todos los pares de nodos de la manera más económica.

5.3.1. Problema de árbol de mínima expansión

La resolución del problema consiste en elegir, desde cualquier nodo, la rama más corta posible a otro nodo, simplemente. Este proceso se repite hasta que se hayan conectado todos los nodos. Los empates se rompen en forma arbitraria

5.3.1. Problema de árbol de mínima expansión

El problema se resuelve eficientemente en forma gráfica, como se mostrará. Partimos del siguiente plano, en donde los números sobre las ligaduras representan distancias entre los nodos.

5.3.1. Problema de árbol de mínima expansión

5.3.1. Problema de árbol de mínima expansión

Las líneas delgadas representan ligaduras potenciales. Se selecciona en forma arbitraria el nodo O para comenzar. El más cercano es el A. Se conectan.

5.3.1. Problema de árbol de mínima expansión

El más cercano a cualesquiera de los nodos O o A es el B (más cercano a A). Se conecta B a A.

5.3.1. Problema de árbol de mínima expansión

El más cercano a O, A o B es el nodo C (más cercano a B). Se conecta C a B. Se continúa iterando de esta manera, hasta obtener:

5.3.1. Problema de árbol de mínima expansión

Ahora todos los nodos están conectados, y se ha formado el árbol de expansión mínima.

La longitud total es de 14. La elección del nodo inicial no afecta la solución final. Se puede verificar esto empezando desde cualquier otro nodo.

5.3.1. Problema de árbol de mínima expansión