Modelos de redes

Solo disponible en BuenasTareas
  • Páginas : 4 (821 palabras )
  • Descarga(s) : 0
  • Publicado : 1 de diciembre de 2011
Leer documento completo
Vista previa del texto
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.

Problema del Arbol de Minima Expansion

El modelo del problema del árbolde 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 debenincluir ciclos en al solución del problema.

Para crear el á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 seproporcionan 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. Sedesea 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 lalongitud 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 elegirsede tal manera que la red resultante formen un árbol de expansión. Por tanto el problema es hallar el árbol de expansión con la longitud total mínima de sus ligaduras.

Modelo de Flujo Máximo

Setrata de enlazar un nodo fuente y un nodo destino a través de una red de ramas dirigidas. Cada rama tiene una capacidad máxima de flujo admisible. El objetivo es el de obtener la máxima capacidad deflujo entre la fuente y el destino.

Características:

1. Todo flujo a través de una red se origina en un nodo fuente y termina en otro nodo llamado destino.
2. Los nodos restantes son nodos...
tracking img