Redes

1.
INTRODUCCION
Las técnicas de flujo de redes están orientadas a optimizar situaciones vinculadas a las redes de transporte, redes de comunicación, sistema de vuelos de los aeropuertos, rutas de navegación de los cruceros, estaciones de bombeo que transportan fluidos a través de tuberías, rutas entre ciudades, redes de conductos y todas aquellas situaciones que puedan representarse medianteuna red donde los nodos representan las estaciones o las ciudades, los arcos los caminos, las líneas aéreas, los cables, las tuberías y el flujo lo representan los camiones, mensajes y fluidos que pasan por la red. Con el objetivo de encontrar la ruta mas corta si es una red de caminos o enviar el máximo fluido si es una red de tuberías.
Cuando se trata de encontrar el camino más corto entre unorigen y un destino, la técnica, algoritmo o el modelo adecuado es el de la ruta más corta; aunque existen otros modelos de redes como el árbol de expansión mínima, flujo máximo y flujo de costo mínimo cada uno abarca un problema en particular. En este trabajo se mencionan los modelos de redes existentes y los problemas que abarca cada uno de ellos, además se describen los algoritmos que aplicanestos modelos para encontrar la solución optima al problema. Utilizando la terminología utilizada para representarlos como una red.
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.
* Modelodel flujo máximo.
* Modelo del flujo del costo mínimo.
Modelo de minimización de redes
El modelo de minimización de redes o problema del árbol de mínima expansión tiene que ver con la determinación de los ramales que pueden unir todos los nodos de una red, tal que minimice la suma de las longitudes de los ramales escogidos. No se deben incluir ciclos en al solución del problema.
Para crearel árbol de expansión mínima tiene las siguientes características:
1. Se tienen los nodos de una red pero no las ligaduras. 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 ligaduraspara 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 sólo (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 formen un árbolde expansión. Por 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 conectanestos 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 en forma arbitraria y el algoritmo debe llegar a una solución optima. No obstante, estos empates son señal de que pueden existir (pero nonecesariamente) soluciones optimas múltiples. Todas esas soluciones se pueden identificar si se trabaja con las demás formas de romper los empates hasta el final.
Modelo de Flujo Máximo
Se trata de enlazar un nodo fuente y un nodo destino a través de una red de arcos dirigidos. Cada arco tiene una capacidad máxima de flujo admisible. El objetivo es el de obtener la máxima capacidad de flujo...