Antología de Investigación de Operaciones
Ingeniería en Sistemas Computacionales
Algunas aplicaciones
A continuación se proporciona una lista de algunos tipos importantes de aplicaciones de este
problema:
1. Diseño e redes de telecomunicaciones – redes de fibra óptica, de computadoras, telefónicas, de
televisión por cable, etcétera - .
2. Diseño de redes de transporte para minimizar el costo total de proporcionar las ligaduras – vías
ferroviarias, carreteras, etcétera -.
3. Diseño de una red de líneas de transmisión de energía eléctrica de alto voltaje.
4. Diseño de una red de cableado de equipo eléctrico – como sistemas de cómputo – para
minimizar la longitud total del cable.
5. Diseño de una red de tuberías para conectar varias localidades.
Un Algoritmo
El problema del árbol de expansión mínima se puede resolver una forma bastante directa, puesto
que se trata de uno de los pocos problemas de la IO en el que se puede ser codicioso en cada etapa del
procedimiento de solución conduce al final de una solución óptima. 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 que esta
elección pueda tener en las decisiones posteriores. 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, según el resumen que se presenta a continuación,
hasta conectar todos los nodos. (Obsérvese que este proceso se ilustró en la figura 2.3. para construir el
árbol de expansión, pero ahora con la regla específica para seleccionar cada ligadura nueva.) Se garantiza
que la red resultante es un árbol de expansión mínima.
Algoritmo del problema del árbol de expansión mínima
1. Se selecciona, de manera arbitraria, cualquier nodo y se conecta – es decir, se agrega una
ligadura – al nodo distinto más cercano.
2. Se identifica el nodo no conectado más cercano a un nodo conectado y se conecta estos dos
nodos – es decir, se agrega una ligadura entre ellos -. Este paso se repite hasta que todos los
nodos están conectados.
3. Rompimiento de empates: los empates para el nodo más cercano distinto (paso 1) o para el nodo
conectado más cercano (paso 2), se pueden romper en forma arbitraria, pero el algoritmo debe
llegar a una solución óptima. No obstante, estos empates son señal de que puede existir (pero no
necesariamente) soluciones óptimas múltiples. Todas esas soluciones se pueden identificar si se
trabaja con las demás formas de romper los empates al final.
La manera más rápida de ejecutar este algoritmo en forma manual es el enfoque gráfico (ver
ejemplo).
La administración de Seervada Park necesita determinar los caminos bajo los cuales se deben tender
las líneas telefónicas para conectar todas las estaciones con una longitud total mínima de cable. Se
46