网络优化的最大利润问题及其破除可增利润圈算法

• 作者: 严余松 马毅
• 来源期刊: 计算机应用研究
• 关键词: 网络优化 最大利润流 破圈算法 最大流 最小费用流 费用圈
• 年，卷（期）: 2015,（8）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 2268-2271
• 页数: 4页
• 分类号: TP393|O221.1
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2015.08.006

摘要

仿照最小费用最大流问题的物理意义,将网络上的费用参数转换成为一种利润参数,提出一个与最小费用最大流问题类似、但意义完全相反的最大利润最小流问题,并建立了该问题的数学规划模型.此外,提出了一个求解该问题最优解的破除可增利润圈算法,该算法通过不断破除网络上的可增利润圈增流,使目标函数值不断增长,最终得到问题的最优解及目标函数值;同时给出了关于该算法正确性的证明过程,并对算法的复杂度进行了分析,最后用示例对算法的求解过程进行了演示.结果表明,该算法能快速有效地求得该问题的最优解及目标函数值,且比一般的线性规划方法更加方便且直观得多.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	严余松	四川师范大学计算机科学学院	15	127	6.0	11.0
2	马毅	西南交通大学交通运输与物流学院	5	36	3.0	5.0