Flujo

INTRODUCCIÓN
Hay una multitud de situaciones, en investigación de operaciones que se pueden modelar y resolver como redes (nodos conectados por ramas). Algunas encuestas recientes informan que hasta el 70 % de los problemas de programación matemática en el mundo real se pueden representar con modelos relacionados con redes. La lista siguiente ilustra algunas aplicaciones posibles de las redes.1. Diseño de una red de gasoducto marinos para conectar bocas de pozos en el Golfo de México con un punto de entrega en tierra. El objetivo del modelo es minimizar el costo de construcción del gasoducto. 2. Determinación de la ruta más corta en una red de carreteras. 3. Determinación de la capacidad máxima (en toneladas anuales) de una red de tubería para lodo de carbón que une las minas en Wyomingcon las centrales eléctricas en Houston. 4. Determinación del programa de flujo con costo mínimo desde los campos petroleros hasta las refinerías a través de una red de oleoductos. 5. Determinación del cronograma de las actividades en la construcción de proyectos. La solución de esas situaciones y otras pare cuidad se logra con una variedad de algoritmos de optimización de redes. En este trabajode investigación se presentará cinco de esos algoritmos: 1. Árbol de expansión mínima. 2. Algoritmo de la ruta más corta. 3. Algoritmo del flujo máximo. 4. Algoritmo de red capacitada con costo mínimo. 5. Algoritmo de la ruta critica.

1

Las situaciones en las que se pueden aplicar estos algoritmos también se pueden formular y resolver en forma de programas lineales explícitos. Sin embargo,los algoritmos propuestos, basados en redes, son más eficientes que el método símplex. Teniendo como objetivo exponer de una manera clara los conceptos, teoremas y aplicaciones, así como de encontrar maneras de aplicar la Teoría de Redes a situaciones reales y resolver problemas prácticos

2

DESARROLLO Definiciones para redes.
Una red consiste en una serie de nodos enlazados con arcos (oramas). La notación para describir una red es (N, A), donde N es el conjunto de nodos y A es el conjunto de arcos. Por ejemplo, la red de la figura 1. Se describe como sigue:  

Figura 1. Ejemplo de una red (N, A) Fuente: investigación de operaciones autor: Handy A. Taha. Con cada red se asocia algún tipo de flujo (por ejemplo, flujo de productos petroleros en un oleoducto t flujos de tráfico deautomóviles de carreteras). En general, el flujo en una red está limitado por la capacidad de sus arcos, que pueden ser finitos o infinitos.

3

Se dice que un arco es dirigido u orientado si permite un flujo positivo en una dirección, y flujo cero en la dirección opuesta. Una red dirigida tiene todos sus arcos dirigidos. Una ruta es una sucesión de arcos distintos que unen dos nodos pasandopor otros nodos, independiente de la dirección de flujo de cada arco. Una ruta forma un ciclo si conecta un nodo consigo mismo, pasando por otros nodos. Por ejemplo, en la figura 1., los arcos (2,3), (3,5) y (5,2) forman un circuito cerrado. Un ciclo es dirigido si consiste en una ruta de dirigida, por ejemplo (2,3), (3,4) y (4,2) en la figura 1. Una red conectada es que ella en que cada dosnodos distintos están enlazados al menos por una ruta. La red de la figura 1. Es un ejemplo de este tipo. Un árbol es una red conectada que puede consistir sólo en un subconjunto de todos los nodos en ella, donde no se permiten ciclos, y un árbol de expansión en un árbol que enlaza todos los nodos en ella, donde no se permiten ciclos. En la figura 2. Se ven ejemplos de un árbol y de un árbol deexpansión para la red de a figura 1.

Árbol

Árbol de expansión Figura 2. Ejemplos de un árbol y de un árbol de expansión, para la red de la figura 1.

4

Fuente: investigación de operaciones autor: Handy A. Taha.

Algoritmo de árbol de expansión mínima.

El algoritmo de árbol de expansión enlaza los nodos de una red, en forma directa o indirecta, con la mínima longitud de las ramas...