Modelos de redes

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:
a) 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.
b) Determinación de laruta más corta que une dos ciudades en una red de caminos existentes.
c) 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.
d) Determinación del programa de flujo de costo mínimo de los campos petrolíferos a refinerías, y finalmente acentros 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:
1. Modelo del árbol de extensión mínima.
2. Modelo de la ruta más corta.
3. Modelo de flujo máximo.
4. Modelo de red capacitada de costo mínimo.
Estos modelos tienen que ver con la determinación de distancias y flujode 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 aconsejable resolverlo 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 o ramas).
A
B
Los arcos se etiquetan para dar nombrea 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.
A
B
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 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 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 ambas direcciones, se dice que el arco es un arco nodirigido. Y con frecuencia se hace referencia a ellos como ligadura.
A
B
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 dirigido del nodo A al nodo B debe etiquetarse como: AB y no como BA.Otra manera de etiquetarlo es A →B.
A
B

RED DIRIGIDA. 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 DIRIGIDA. Una red que tiene solo arcos no dirigidos.
A
B
C
D
TRAYECTORIA. Es aquella 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.
TRAYECTORIA NO DIRIGIDA. Considerando del nodo i al nodo j, es una sucesión de arcos cuya...