Modelos de redes

INTRODUCCIÓN


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 entreun origen 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 especifico. 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 óptima al problema. Utilizando la terminología utilizada para representarlos como una red.









1- DEFINICIÓN DE RED

La definición de red es un poco abstracta. Las redes son rutas invisibles sobre las cuales se van a mover los "Recursos" o las "Entidades".
Para que una red cumpla con su función, debe estar amarrada a las "Locaciones" pormedio de "Interfaces".
Una red puede estar conformada por muchos tramos, los cuales están separados por "Nodos", y cada "Nodo" debe tener su respectiva "Interfaz". Cuando la red cambia de dirección en un punto que no esté conectado a una "Locación", se habla de "Puntos de Quiebre".
Es un grafo ponderado, con un nodo (a) llamado fuente y otro nodo (z) llamado pozo, terminal o resumidero.


N =( X, U, W)
X = { a, z, xi , 1 £ i £ n-2}
U = { (xi, xj), ........}


Consideramos redes orientadas. Es viable afirmar que una red siempre es orientada.










2- ALGORITMO DE ÁRBOL DE EXPANSION MÍNIMA


Este problema se origina cuando todos los nodos de una red deben conectarse entre si (no pueden formar un loop). Este algoritmo es apropiado para problemas en los que laredundancia es expansiva o el flujo a lo largo de los arcos es instantáneo. Por tanto se refiere a utilizar las ramas o arcos de la red para llegar a todos los nodos que la forman, de manera que se minimiza la longitud total.

Este algoritmo se aplica a problemas en las redes de comunicación eléctrica, telefónica, carretera, ferroviaria, aérea, marítima, etc.… Donde los nodos representan puntosde consumo eléctrico, teléfonos, aeropuertos,…

Si n= numero de nodos entonces la solución óptima debe incluir n-1 arcos.



3- PROBLEMA DE LA RUTA MÁS CORTA

Tenemos una red conexa y no dirigida con dos nodos especiales llamados origen y destino. A cada ligadura (arco no dirigido) se asocia una distancia no negativa. El objetivo es encontrar la ruta más corta (la trayectoria con lamínima distancia total) del origen al destino.

La esencia del procedimiento es que analiza toda la red a partir del origen; identifica de manera sucesiva la ruta más corta a cada uno de los nodos en orden ascendente de sus distancias (más cortas), desde el origen; el problema queda resuelto en el momento de llegar al nodo destino.




- Ejemplos de aplicaciones de la ruta más corta


Esdecir, la ruta más corta corresponde a la ruta ABFJ, la cual suma 30 unidades.


- Algoritmos de ruta más corta

Objetivo de la n-ésima iteración: encontrar el n-ésimo nodo más cercano al origen. (Este paso se repetirá para n=1,2,… hasta que el n-ésimo nodo más cercano sea el nodo destino.)
Datos para la n-ésima iteración: n-1 nodos más cercanos al origen (encontrados en las iteraciones...