Flujo De Costo Minimo 155y3y

El problema del flujo de costo mínimo tiene una posición medular entre los modelos de optimización de redes; primero, abarca una clase amplia de aplicaciones y segundo, su solución es muy eficiente. Toma en cuenta un flujo en una red con capacidades limitadas en sus arcos. Considera un costo (o distancia) para el flujo a través de un arco. Puede manejar varios orígenes (nodo fuente) y varios destinos (nodos demanda) para el flujo, de nuevo con costos asociados.

La razón por la que el problema de flujo de costo mínimo se puede resolver de modo tan eficiente es que se puede formular como un problema de programación línea y es posible resolverlo con una versión simplificada del método símplex llamada método símplex de redes.

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

1. La red es una red dirigida y conexa. 2. Al menos uno de los nodos es un nodo fuente. 3. Al menos uno de los nodos es un nodo de 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 6. La red tiene suficientes arcos con suficiente capacidad para permitir que todos los flujos generados por los nodos fuente lleguen a los nodos de 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.)

Minimizar el costo total de mandar los recursos a través de la red para satisfacer la demanda dada.

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. Este tipo de aplicación siempre incluye determinar un plan para enviar bienes desde las fuentes (fábricas, etc.) a las instalaciones de almacenamiento intermedias (según se necesite) y después a los consumidores

Para la formulación del modelo considere una red conexa dirigida en la que los n nodos incluyen al menos un nodo origen y al menos un nodo destino. Las variables de decisión son:

El objetivo es minimizar el costo total de mandar los recursos disponibles a través de la red para satisfacer la demanda dada. Usando la convención de que las sumas se toman sólo sobre arcos existentes, la formulación de programación lineal de este problema es:

La primera suma en las restricciones de los nodos representa el flujo total que sale del nodo i mientras que la segunda representa el flujo total que entra al nodo i; así, la diferencia es el flujo neto generado en este nodo. No se garantiza que el problema posea soluciones factibles; esto depende en parte de qué arcos están presentes en la red y de sus capacidades.

Propiedades de soluciones factibles: una condición necesario para que un problema de flujo de costo mínimo tenga soluciones factibles es que:

Es decir, el flujo total generado en los nodos origen es igual al flujo total absorbido por los nodos de destino.

En la siguiente figura se muestra un ejemplo del problema de flujo de costo mínimo. Los valores de bi en la figura se muestran entre paréntesis cuadrados cerca de los nodos; entonces, los nodos origen (bi>0) son A y B (las dos fábricas de la compañía), los nodos destino (bi>0) son D y E (los dos almacenes), y el único nodo de trasbordo (bi=0) es C (un centro de distribución). Los valores cij se muestran junto a los arcos. En este ejemplo, todos menos dos de los arcos tienen capacidades que exceden el flujo total generado (90), de manera que uij=∞ para cualquier propósito práctico. Las dos excepciones son el arco A→B, donde uAB=10 y el arco C→E que tiene uCE=80.

Minimizar