Modelos de redes

Solo disponible en BuenasTareas
  • Páginas : 6 (1462 palabras )
  • Descarga(s) : 4
  • Publicado : 24 de abril de 2010
Leer documento completo
Vista previa del texto
MODELOS DE REDES
INTRODUCCIÓN
El modelo de transporte y sus variantes es uno de los muchos problemas que se pueden representar y resolver como una red. Por ejemplo:
Diseño de una red de tubería de gas natural mar adentro, que conecta fuentes del Golfo de México con un punto de entrega en tierra, con el objetivo de minimizar el costo de construcción de la red.Determinación de la ruta más corta que une dos ciudades en una red de caminos existentes.
Determinación de la capacidad anual máxima en toneladas de una red de conductos de pasta aguada de carbón, que enlaza las minas carboneras de Wyoming con las plantas generadoras de electricidad de Houston.
Determinación del programa de flujo de costo mínimo de los campos petrolíferos arefinerías, y finalmente a centros de distribución.
Los problemas de optimización de redes se pueden representar en términos generales, a través de cualquiera de los siguientes cuatro modelos:
Modelo del árbol de extensión mínima.
Modelo de la ruta más corta.
Modelo de flujo máximo.
Modelo de red capacitada de costo mínimo.
Estos modelos tienen que vercon la determinación de distancias y flujo de material en un sentido literal. Sin embargo, también pueden representar otras propiedades como flujo de inventario o de dinero.
Los modelos de redes pueden representarse y, resolverse como programas lineales. Pero, debido al gran número de variables y restricciones que normalmente acompañan a un modelo de redes común se hace poco aconsejableresolverlo directamente por el método simplex.
DEFINICIONES DE REDES
RED. Consiste en un conjunto de puntos y un conjunto de líneas que unen ciertos pares de puntos.
NODO. Los puntos que se encuentran en una red se llaman nodos (o vértices), y su representación gráfica de manera general es un círculo.
ARCO. Las líneas que unen los puntos en una red se llaman arcos (o ligaduras, aristas oramas).
{draw:g} Los arcos se etiquetan para dar nombre a los nodos en sus puntos terminales; ejemplo: AB es el arco entre los nodos A y B.
FLUJO. Los arcos de una red pueden tener un flujo de algún tipo que pasa por ellos.
{draw:g} ARCO DIRIGIDO.Si el flujo a través de un arco se permite sólo en una dirección, se dice que el arco es un arco dirigido. La dirección se indica agregando unacabeza de flecha al final de la línea que representa el arco. Al etiquetar un arco dirigido con el nombre de los nodos que une, siempre se pone primero el nodo de donde viene y después el nodo a donde va. Ejemplo, un arco dirigido del nodo A al nodo B debe etiquetarse como: AB y no como BA. Otra manera de etiquetarlo es A →B.
*ARCO NO *DIRIGIDO. Si el flujo a través de un arco se permite en ambasdirecciones, se dice que el arco es un arco no dirigido. Y con frecuencia se hace referencia a ellos como ligadura.
{draw:g} La dirección se indica agregando una cabeza de flecha al final de la línea que representa el arco. Al etiquetar un arco dirigido con el nombre de los nodos que une, siempre se pone primero el nodo de donde viene y después el nodo a donde va. Ejemplo, un arco dirigidodel nodo A al nodo B debe etiquetarse como: AB y no como BA. Otra manera de etiquetarlo es A →B.
{draw:g}
RED DIRIGID*A*. Una red que tiene solo arcos dirigidos. Una red con una mezcla de arcos dirigidos y no dirigidos (o incluso todos sus arcos no dirigidos) se puede convertir en una red dirigida.
RED NO DIRIGID*A*. Una red que tiene solo arcos no dirigidos.
{draw:g} *TRAYECTORIA.** Esaquella sucesión de arcos distintos que une dos nodos. Ejemplo: **A →* *B * *→* *C →* *D** o representado como **AB – BC *–* CD*.
TRAYECTORIA DIRIGIDA. Considerando del nodo i (origen) al nodo j (destino), es una sucesión de arcos cuya dirección es hacia el nodo j, de manera que el flujo del nodo i al nodo j, a través de esta trayectoria es factible, pero no asì en sentido contrario....
tracking img