Problema De Flujo De Costo Mínimo

Problema de flujo de costo mínimo
EL problema de flujo de costo mínimo tiene una posición central entre los modelos de optimización de redes; primero, abarca una clase amplia de aplicaciones y,segundo, su solución es muy eficiente. Igual que el problema de flujo máximo, toma en cuenta un flujo en una red con capacidades de arco limitadas. Igual que el problema de la ruta más corta, consideraun costo (o distancia) del flujo a través de un arco. Igual que el problema de transporte o el de asignación del capítulo 8, puede manejar varios orígenes (nodos fuente) y varios destinos (nodosdemanda) del flujo, de nuevo con costos asociados. En realidad, estos cuatro problemas son casos especiales del problema de flujo de costo minimo, como se demostrara en esta sección.
La razón por la queel problema del flujo de costo mínimo se puede resolver de modo más eficiente es que se puede formular como un problema de programación lineal y es posible resolverlo con una versión simplificada delmétodo simplex llamada método simplex de redes .En la siguiente sección se describirá este algoritmo.
A continuación se describe el problema del flujo de costo mínimo.
1. La red es una reddirigida 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. Es el resto de los nodos son nodos de transbordo.
5. Se permite elflujo a través de un arco solo 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, deberepresentarse por un par de arcos con direcciones opuestas)
6. La red tiene suficientes arcos con suficiente capacidad para permitir que todos los flujos generados por los nodos fuente lleguen a losnodos 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...