Computer Engineering and Applications ›› 2015, Vol. 51 ›› Issue (1): 1-4.

Previous Articles     Next Articles

Maximum profit flow problem for network optimization and its flow-augmenting path-based algorithm

MA Yi1, YAN Yusong2, HU Zuo’an1   

  1. 1.School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 610031, China
    2.School of Computer Science, Sichuan Normal University, Chengdu 610068, China
  • Online:2015-01-01 Published:2015-01-06

网络优化的最大利润问题及其增广路算法

马  毅1,严余松2,户佐安1   

  1. 1.西南交通大学 交通运输与物流学院,成都 610031
    2.四川师范大学 计算机科学学院,成都 610068

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

摘要: 仿照最小费用最大流问题的物理意义,将网络上的费用参数转化成为一种利润参数,提出一个最大利润流问题,并建立了该问题的数学规划模型;给出一个求解该问题的最大利润增广路算法,该算法能快速有效地求得该问题的最优解及目标函数值。用示例对算法的求解过程进行了演示,结果表明该算法比一般的线性规划方法更加的方便,且直观得多。

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