Flujo De Redes En Investigación De Operaciones

INTRODUCCIÓN.

El modelo de red es un Modelo de base de datos concebido como un modo flexible de representar objetos y su relación. El inventor original del modelo de red fue Charles Bachman, y con ello fue desarrollado en una especificación estándar publicada en 1969 por CODASYL.
En 1969, la Conferencia de Lenguajes en Sistemas de Datos (CODASYL) estableció la primera especificación delmodelo de base de datos de red. Esto fue seguido de una segunda publicación en 1971, que se hizo la base para la mayor parte de puestas en práctica. El trabajo subsecuente continuado en principios de los años 1980, que culminan en una especificación de ISO, pero esto tenía poca influencia sobre estos productos.
Las técnicas de flujo de redes están orientadas a optimizar situaciones vinculadas alas 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 mediante una 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 un origen y un destino, la técnica, algoritmo o el modelo adecuado es el de la ruta más corta; aunque existenotros 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 aplican estos modelos para encontrar la solución optima al problema. Utilizando la terminología utilizada pararepresentarlos como una red.



MARCO TEÓRICO
Definiciones de Redes
Una red consta de un conjunto de nodos por arcos o ramas. Asociada a casa rama se tiene un flujo de algún tipo. La notación estándar para describir una red es G=(N,A), donde N es el conjunto de de nodos y A él de ramas.
En general el flujo de una rama está limitado por su capacidad que puede ser medible como puede no serlo.Una rama está dirigida u orientada si permite un flujo positivo en una dirección y cero flujo en la dirección opuesta.
* Red dirigida: Es cuando todas sus ramas permiten el flujo en solo sentido.
* Trayectoria: Es una secuencia de ramas distintas que conectan dos nodos sin tomar en cuenta la dirección de las ramas individuales.
* Lazo o ciclo: Es una trayectoria donde su nodoinicial coincide con el final.
* Circuito o lazo dirigido: es un lazo donde todas las ramas tienen la misma dirección.
* Red conectada: Es una red donde cada dos nodos distintos están conectados por una trayectoria.
* Árbol: Es una red conectada que puede constar solo de un subconjunto de nodos.
* Árbol extenso: es una red conectada que incluye todos los lazos de la red sin lazos.Figura 1. Red G=(8, 8).

Problema del árbol de extensión mínima.
En el problema del árbol de extensión mínima se busca determinar el árbol extenso que proporciona la suma mínima de ramas conectoras. El problema consiste en encontrar las conexiones más “eficientes” entre los nodos de la red las que no deben incluir ningún ciclo.
Algoritmo de solución:
Se comienza con cualquier nodo y seconecta con el nodo más cercano a este de la red. Los dos nodos resultantes forman un conjunto conectado llamado C y los restantes constituyen el conjunto no conectado llamado C. El siguiente paso es escoger el nodo del conjunto no conectado, que tenga la rama de longitud más corta, a cualquier nodo del conjunto conectado, este nodo dejar de ser parte del conjunto no conectado para pertenecer al...