关键词: 网络优化, 最大利润流, 最小费用流, 增广路, 最长路

Abstract: By imitating the physical meaning of minimum cost flow theory, a maximum profit problem is proposed by converting cost as profit. Then the mathematical programming model for this problem is built. Furthermore, a flow-augmenting algorithm is proposed to solve this problem. The optimum solution and the corresponding objective function value of this problem can be figured out rapidly and effectively by using this algorithm. Finally, a study case is given to demonstrate the calculation process of this algorithm. The results show the designed algorithm is more convenient and intuitionistic than general linear programming algorithm.

Key words: network optimization, maximum profit flow, minimum cost flow, flow-augmenting path, the longest path