PROBLEMA DEL FLUJO DE COSTO MÍNIMO
Enviado por rolanda • 10 de Diciembre de 2012 • Tesis • 531 Palabras (3 Páginas) • 1.353 Visitas
PROBLEMA DEL 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, abarca una clase amplia de aplicaciones y segundo, su solución es muy 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.
A continuación se describe el problema del flujo de costo mínimo:
La red es una red dirigida conexa.
Al menos uno de los nodos es nodo fuente.
Al menos uno de los nodos es nodo demanda.
El resto de los nodos son nodos de trasbordo.
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.)
La red tiene suficientes arcos como suficiente capacidad para permitir que todos lo flujos generados por los nodos fuente lleguen a los nodos demanda.
El costo del flujo a través del arco es proporcional a la cantidad de ese flujo, donde se conoce el costo por unidad.
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.)
FORMULACION DEL EJEMPLO
Problema del flujo de costo mínimo (Ejemplo)
La DISTRIBUTION UNLIMITED CO. Fabricará el mismo nuevo producto en dos plantas distintas y después tendrá que enviarlo a dos almacenes. La red de distribución disponible para el envío de este producto se muestra en la figura, donde A y B son las fábricas, D y E son los almacenes y C es el centro de distribución. Las cantidades que deben enviarse desde A y B se muestran a la izquierda, y las cantidades que deben recibirse en D y E se muestran a la derecha. Cada flecha representa un canal factible de envío. A puede enviar directamente a D y tiene tres rutas posibles (ACE, ABCE y ADE) para mandar bienes a E. La fábrica B tiene solo una ruta a E (BCE) y una a D (BCED). El costo por unidad enviada a través de cada canal se muestra al lado de la flecha. También, junto a AB y CE se muestran las cantidades máximas que se pueden enviar por estos canales. Los otros canales tienen suficiente capacidad para manejar todo lo que las fábricas pueden enviar.
La decisión que
...