Optimización de Flujo de Redes: Modelos y Algoritmo del Árbol de Mínima Expansión

Introducción

Las **técnicas de flujo de redes** están orientadas a optimizar situaciones vinculadas a diversas infraestructuras: **redes de transporte**, redes de comunicación, sistemas de vuelos de aeropuertos, rutas de navegación de cruceros, estaciones de bombeo que transportan fluidos a través de tuberías, rutas entre ciudades y redes de conductos. Estas situaciones pueden representarse mediante una red donde los **nodos** representan las estaciones o las ciudades; los **arcos** representan los caminos, las líneas aéreas, los cables o las tuberías; y el **flujo** lo representan los camiones, mensajes y fluidos que pasan por la red. El objetivo principal es encontrar la **ruta más corta** (si es una red de caminos) o enviar el **máximo fluido** (si es una red de tuberías).

Modelos de Redes

Los problemas de **optimización de redes** se pueden representar, en términos generales, a través de uno de estos cuatro modelos:

• **Modelo de minimización de redes** (Problema del árbol de mínima expansión).
• Modelo de la ruta más corta.
• Modelo del flujo máximo.
• Modelo del flujo del costo mínimo.

Modelo de Minimización de Redes

El **modelo de minimización de redes**, también conocido como el **problema del árbol de mínima expansión**, se centra en la determinación de los ramales necesarios para unir todos los nodos de una red, de tal manera que se minimice la suma de las longitudes de los ramales escogidos. Es crucial que **no se incluyan ciclos** en la solución del problema.

Características del Árbol de Expansión Mínima

Para crear el árbol de expansión mínima, se deben considerar las siguientes características:

1. Se tienen los nodos de una red, pero no las ligaduras (conexiones). En su lugar, se proporcionan las **ligaduras potenciales** y la longitud positiva para cada una si se inserta en la red. (Las medidas alternativas para la longitud de una ligadura incluyen **distancia, costo y tiempo**).
2. Se desea diseñar la red con suficientes ligaduras para satisfacer el requisito de que haya un **camino entre cada par de nodos**.
3. El objetivo es satisfacer este requisito de manera que se **minimice la longitud total** de las ligaduras insertadas en la red.

Una red con n nodos requiere solo (n-1) ligaduras para proporcionar una trayectoria entre cada par de nodos. Las (n-1) ligaduras deben elegirse de tal manera que la red resultante forme un **árbol de expansión**. Por lo tanto, el problema es hallar el árbol de expansión con la longitud total mínima de sus ligaduras.

Algoritmo para Construir el Á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 conectan estos dos nodos (es decir, se agrega una ligadura entre ellos). Este paso se repite hasta que **todos los nodos están conectados**.
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 de forma arbitraria, y el algoritmo debe llegar a una **solución óptima**. No obstante, estos empates son señal de que pueden existir (aunque no necesariamente) **soluciones óptimas múltiples**. Todas esas soluciones se pueden identificar si se trabaja con las demás formas de romper los empates hasta el final.