El problema de flujo máximo a coste mínimo dependiente del flujo

Abstract

El problema de flujo máximo a coste mínimo juega un papel esencial en la optimización de redes. El objetivo principal es determinar el coste mínimo para enviar el máximo flujo posible a través de una red. Estas redes de transporte pueden representar multitud de problemas reales, como el transporte de mercancías o personas, flujo en tuberías, redes de distribución eléctrica, etc. En este Trabajo se explica la resolución del problema empleando el algoritmo Primal-Dual, así como su implementación en MATLAB. Se diferenciarán dos versiones del algoritmo: costes constantes o dependientes del flujo. Se exige que los costes no constantes sean continuos y estrictamente convexos. En ese caso, la estrategia es resolver de manera sucesiva el problema tomando los costes marginales de los arcos como constantes en cada iteración. El algoritmo Primal-Dual no es el único que permite resolver el problema de flujo máximo a coste mínimo. Existen otros algoritmos competitivos como el algoritmo de cancelación de ciclo, los algoritmos basados en ténicas de escalado o algoritmos no lineales como los algoritmos de colonización de hormigas o los algoritmos genéticos.

Minimum cost flow problem plays an essential role in network optimization. The main objective is to determine the minimum cost to send the maximum possible flow through a network. These transport networks can represent a multitude of real problems, such as the transport of commodities or people, flow in pipelines, electrical distribution networks, etc. This work explains the resolution of the problem using the Primal-Dual algorithm, as well as its implementation in MATLAB. Two versions of the algorithm will be differentiated: constant or flowdependent costs. Non-constant costs are required to be continuous and strictly convex. In this case, the strategy is to successively solve the problem by taking the marginal costs of the arcs as constant in each step. Primal-Dual algorithm is not the only one that allows solving the minimum cost flow problem. There are other competitive algorithms such as the cycle cancelying algorithm, algorithms based on scaling techniques or nonlinear algorithms such as ant colony optimization algorithm or genetic algorithms.