Modelo de Redes

ALCANCE Y DEFINICIÓN DE MODELOS DE REDES
Muchas situaciones de investigación de operaciones pueden modelarse y

resolverse como redes (nodos conectados por ramas); a continuación
tenemos algunos ejemplos de aplicación:
1. Diseño de una red de oleoductos para gas natural a una determinada
distancia de la costa para conectar los cabezales de los pozos en el Golfo de
México a un punto de distribución costero con el objetivo de minimizar el costo
de construcción de los oleoductos.
2. Determinación de la ruta más corta entre dos ciudades en una red existente
de carreteras.
3. Determinación de la capacidad máxima (en toneladas por año) de una red
de oleoductos para lodos de carbón que unen minas de carbón en Wyoming
con plantas eléctricas en Houston (los oleoductos para lodos transportan
carbón al bombear agua a través de tuberías especialmente diseñadas).
4. Determinación del cronograma (fechas de inicio y terminación) para las
actividades de un proyecto de construcción.
5. Determinación del itinerario de flujo de costo mínimo desde campos
petroleros hasta refinerías a través de una red de oleoductos.
La solución de estas situaciones se logra por medio de varios algoritmos de
optimización de redes. Este unidad presenta cuatro de estos algoritmos.
1. Árbol de mínima expansión

2. Ruta más corta
3. Flujo máximo
4. Ruta crítica (CPM)
Definiciones de red
Una red se compone de un conjunto de nodos unidos por arcos (o ramas). La
notación para describir una red es (N,A), donde N es el conjunto de nodos, y
A es el conjunto de arcos. A manera de ilustración, la red de la figura 6.1, se
describe como:
N = {1, 2, 3, 4, 5}
A = {(1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 5)}
Asociado con cada red hay un flujo (por ejemplo, los productos de petróleo
fluyen por un oleoducto y el tráfico de automóviles fluye por las carreteras). El
flujo máximo en una red puede ser finito o infinito, según la capacidad de sus
arcos.
Se dice que un arco está dirigido u orientado si permite el flujo positivo sólo
en una dirección. Una red dirigida tiene todos los arcos dirigidos.
Una ruta es un conjunto de arcos que unen dos nodos distintos, y que pasan
a través de otros nodos en la red. Por ejemplo, en la figura 6.1 los arcos (1,2),
(2,3), (3,4) y (4,5) forman una ruta entre los nodos 1 y 5. Una ruta forma un
ciclo o un bucle si conecta un nodo de vuelta a sí mismo a través de otros
nodos. En la figura 6.1, los arcos (2,3), (3,4) y (4,2) forman un ciclo.
Se dice que una red está conectada si cada dos nodos distintos están
conectados en al menos una ruta. La red en la figura 6.1 muestra este tipo
de red. Un árbol es una red conectada libre de ciclos compuesta de un
subconjunto de todos los nodos, y un árbol de expansión es un árbol que
une todos los nodos de la red. La figura 6.2 proporciona ejemplos de un
árbol y un árbol de expansión de la red de la figura 6.1.
Conceptos básicos en teoría de redes
Gráfica: Una gráfica es una serie de puntos llamados nodos que van unidos
por unas líneas llamadas ramales o arcos.
Red: Una red es una gráfica que presenta algún tipo de flujo en sus ramales.
Por ejemplo una gráfica cuyo flujo en sus ramales sea la electricidad es una
red eléctrica.
En las redes se usa una simbología específica para denotar su tamaño y
elementos que la constituyen, dicha notación es la (N, A) donde N representa
el número de nodos que contiene la red y A representa el número de arcos o
ramales.
Cadena: Una cadena corresponde a una serie de elementos ramales que van
de un nodo a otro. En el siguiente caso se resalta una cadena que va desde el
nodo 1 hasta el nodo 7 y que se compone por los elementos [1-4, 4-7].
Ruta: Una ruta corresponde a los nodos que constituyen una cadena, en el
siguiente caso [1, 4, 7].
Ciclo: Un ciclo corresponde a la cadena que une a un nodo consigo mismo, en

el siguiente ejemplo el ciclo está compuesto por la cadena [4-2, 2-5, 5-7, 7-4].
Ramal orientado: Un ramal o arco orientado es aquel que tiene un sentido
determinado, es decir que posee un nodo fuente y un nodo destino.
Gráfica orientada: Una gráfica orientada es aquella en la cual todos sus

ramales se encuentran orientados.
Árbol: Un árbol es una gráfica en la cual no existen ciclos, como el siguiente
ejemplo.
Árbol de expansión: Un árbol de expansión es aquel árbol que enlaza todos los
nodos de la red, de igual manera no permite la existencia de ciclos.
Nodo fuente: El nodo fuente es aquel nodo en el cual todos sus ramales se
encuentran orientados hacia afuera.
Nodo destino: El nodo destino es aquel nodo en el cual todos sus ramales se
encuentran orientados hacia él.

Modelo de Redes

Cargado por

Copyright:

Formatos disponibles

Modelo de Redes

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Modelo de Redes

Cargado por

Copyright:

Formatos disponibles

ALCANCE Y DEFINICIÓN DE MODELOS DE REDES

Muchas situaciones de investigación de operaciones pueden modelarse y

1. Árbol de mínima expansión

Ciclo: Un ciclo corresponde a la cadena que une a un nodo consigo mismo, en

Gráfica orientada: Una gráfica orientada es aquella en la cual todos sus

También podría gustarte