Problema del flujo de costo mínimo

El problema del flujo de costo mínimo tiene una posición medular ente los modelos de optimización de redes; primero,  porque abarca una clase muy amplia de aplicaciones y segundo, porque su solución es en extremo eficiente. Al igual que el problema del flujo máximo, toma en cuenta un flujo a través de una red con capacidades limitadas en sus arcos. Al igual que el problema de la ruta más corta, considera un costo (o distancia) para el flujo a través de un arco. Al igual que el problema de transporte o el problema de asignación del capítulo 7, puede manejar varios orígenes (nodos fuente) y varios destinos (nodos demanda) para el flujo, también con costos asociados. Al igual que el problema de trasbordo del capítulo 7, puede considerar varios puntos de conexión (nodos de trasbordo) entre los orígenes y los destinos para este flujo. De hecho, estos cinco problemas estudiados son casos especiales del problema del flujo de costo mínimo, como se verá enseguida.

La razón por al 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, y por tanto, se puede resolver mediante una versión simplificada del método símplex llamada método símplex de redes. En la siguiente sección se describirá este algoritmo.