Modelos De Redes

Modelo de Flujo Máximo

Se trata de enlazar un nodo fuente y un nodo destino a través de una red de arcos dirigidos. Cada arco tiene una capacidad máxima de flujo admisible. El objetivo es el de obtener la máxima capacidad de flujo entre la fuente y el destino.

Características:

1. Todo el flujo a través de la red que se origina un nodo, llamado origen y termina en otro nodo llamado destino.

2. Todos los nodos restantes son nodos de transbordo.

3. Solo está permitido el flujo a través de un arco en la dirección indicada por la flecha, donde la cantidad máxima de flujo está dada por la capacidad de ese arco.

4. El objetivo es maximizar la cantidad total del flujo del origen al destino. Esta cantidad esta medida en una de 2 formas equivalentes, que son la cantidad que sale del origen o la cantidad que entra en el destino.

5. Los arcos tienen una capacidad máxima de flujo, y se trata de enviar desde la fuente al sumidero la mayor cantidad posible de flujo, de tal manera que:

a. El flujo es siempre positivo y con unidades enteras.

b. El flujo a través de un arco es menor o igual que la capacidad.

c. El flujo que entra en un nodo es igual al que sale de él.

En el caso de que el origen o el destino no existan en el problema, se añaden ficticiamente utilizando arcos unidireccionales de capacidad infinita, como en grafo mostrado a continuación:

DIFERENCIAS ENTRE COSTO MINIMO Y COSTO MAXIMO

El origen y el destino de un problema de flujo máximo son análogos a los nodos de recursos y demanda en el problema del flujo del costo mínimo. Estos son los únicos nodos que no cuentan con conservación de flujo.

PROBLEMA DE FLUJO DE COSTO MÍNIMO.

El problema de flujo de costo mínimo tiene una posición medular entre los problemas de optimización de redes; primero, porque abarca una clase muy amplia de aplicaciones y segundo, porque su solución es en extremo eficiente.

Igual que el problema del flujo máximo, toma en cuenta un flujo en una red con capacidades limitadas en sus arcos.

Igual que el problema de la ruta más corta, considera un costo (o distancia) para el flujo a través de un arco.

Igual que el problema de transporte o el de asignación, puede manejar varios orígenes (nodos fuente) y varios destinos (nodos demandas) para el flujo, de nuevo con costos asociados. De hecho, estos cuatro problemas son casos especiales del problema de flujo de costo mínimo.

La razón por la que el problema del flujo de costo mínimo se puede resolver de manera tan eficiente es que se puede formular como un problema de programación lineal.

A continuación se describe el problema del flujo de costo mínimo:

1. La red es una red dirigida conexa.

2. Al menos uno de los nodos es nodo fuente.

3. Al menos uno de los nodos es nodo demanda.

4. El resto de los nodos son nodos de trasbordo.

5. Se permite el flujo a través de un arco sólo en la dirección indicada por la flecha, donde la cantidad máxima de flujo está dada por la capacidad del arco. (Si el flujo puede ocurrir en ambas direcciones, debe representarse por un par de arcos con direcciones opuestas.)

6. La red tiene suficientes arcos como suficiente capacidad para permitir que todos lo flujos generados por los nodos fuente lleguen a los nodos demanda.

7. El costo del flujo a través del arco es proporcional a la cantidad de ese flujo, donde se conoce el costo por unidad.

8. El objetivo es minimizar el costo total de enviar el suministro disponible a través de la red para satisfacer la demanda dada. (Un objetivo alternativo es maximizar la ganancia total del envío.)

Aplicaciones del problema del flujo de costo mínimo

El tipo más importante de aplicación del problema del flujo de costo mínimo es en la operación de la red de distribución de una compañía. En la siguiente tabla se muestran algunos tipos de aplicaciones comunes del problema de del flujo de costo mínimo:

Tipo de Aplicación Nodos Fuentes Nodos de Trasbordo Nodos de Demanda

Operación de una red de distribución Fuentes de bienes Almacenes intermedios Consumidores

Administración de desechos sólidos Fuente de desechos sólidos Instalaciones de procesamiento Rellenos

Operación de una red de suministros Agentes de ventas Almacenes intermedios Instalaciones de procesamiento

Coordinación de mezcla de productos en plantas plantas Producción de u artículo específico Mercado del producto específico

Administración de flujo de efectivo Fuentes de efectivo en tiempos específicos Opciones de inversión a corto plazo Necesidades de efectivo en tiempos específicos

PROGRAMACION LINEAL EN TEORIA DE REDES

La Teoría de Redes es un área de conocimiento dentro del campo de la Investigación de Operaciones. Los problemas que estudia dicha teoría, son principalmente, de naturaleza combinatoria, es decir, relaciona rutas, cortes, árboles y otros objetos. Para obtener las soluciones de estos problemas, se requiere diseñar algoritmos. Algunos son más eficientes que otros, y su selección depende de las características del problema.

Los modelos de redes han ocupado un lugar muy importante en el progreso de la Investigación de Operaciones y de las Ciencias Administrativas. Estos modelos junto con la teoría de la Programación Lineal han mantenido una estrecha relación en su desarrollo. Lo que a su vez ha propiciado avances en el campo de la Programación Entera.

Otro aspecto es el adelanto de códigos más rápidos para los problemas de flujo en redes, lo cual favorece la relación entre la Investigación de Operaciones y las Ciencias de la Computación. Por otro lado, la investigación en modelos de redes a la par con la Ciencia de la Computación, ha propiciado la construcción de estructuras para el manejo de datos, haciendo más eficientes los algoritmos de redes.

La estructura de los problemas de redes se puede representar gráficamente. Esto ha permitido visualizar problemas en áreas como: telecomunicaciones, transporte, distribución, planeación de proyectos, localización de instalaciones, etc.

Los problemas de redes pueden clasificarse esencialmente en cinco áreas: Ruta más corta, Flujo máximo, Árbol de expansión mínima, Flujo a costo mínimo y, Planeación y control de proyectos [Hillier y Lieberman, 1991].

En esta agrupación, el Problema de la Ruta más Corta, es considerado por los investigadores como

...