Download Alcance y Definición de Modelos de Redes 10 Oct 2016 PDF

TitleAlcance y Definición de Modelos de Redes 10 Oct 2016
TagsOperations Research Physics & Mathematics Mathematical Optimization Mathematical Concepts
File Size538.7 KB
Total Pages4
Document Text Contents
Page 1

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. En esta unidad revisaremos los algoritmos siguientes:

1. Árbol de mínima expansión (situación 1)

2. Algoritmo de la ruta más corta (situación 2)

3. Algoritmo de flujo máximo (situación 3)

4. Algoritmo de la ruta crítica (CPM) (situación 4)

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.

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á

Similer Documents