Modelo de redes.

UNIVERSIDAD AUTONOMA DE CHIAPAS.
FACULTAD DE CONTADURIA Y ADMINISTRACION.
CAMPUS 1.

INVESTIGACION DE OPERACIONES.

“MODELO DE REDES”

DOCENTE: María de Lourdes Solís Betanzos.

ALUMNOS:

Nancy Karina Medina Vázquez
Adhela del Carmen Moreno Alvarado
Erik Geovanny Jiménez Méndez.

Tuxtla Gutiérrez, Chiapas a 27 de Octubre del 2011.

INTRODUCCION.

Las técnicas de flujo de redesestá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 mediante una red donde los nodos representan las estacioneso 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 más 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 elmodelo 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 aplican estos modelos para encontrar la solución óptima alproblema. 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.
* Modelo del flujo máximo.
* Modelo del flujo delcosto 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 la solución del problema.
Para crear el árbol de expansión mínima tiene lassiguientes 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 ligaduras para satisfacer el requisito de que haya un caminoentre 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 árbol de expansión. Por tanto el problema es hallarel á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 ligaduraentre 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 óptima. No obstante, estos empates son señal de que pueden existir (pero no necesariamente) soluciones optimas múltiples....