定流值比例的最小双费用流算法研究

• 作者: 刘艳清 赵礼峰
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 最小双费用流算法 余网络 邻接矩阵 Ford算法 费用差
• 年，卷（期）: 2017,（4）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 94-97,103
• 页数: 5页
• 分类号: TP301.6
• 字数: 4513字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2017.04.021

摘要

现有最小双费用流算法只能求解网络的最大双流问题,并不能得到定流值比例.为此,提出了一种定流值比例的最小双费用流新算法,在求解最小双流和最小费用的基础上,在调整双流值保证定流值比例的同时得到最小费用流.所提出的新算法定义了余网络和费用差,以邻接矩阵为网络数据存储结构,使用Ford算法分别得到两费用的最短增广链,选择费用最小的增广链增广并求出其对应的费用差,从费用差最小的开始调整流值就得到定流值比例下的最小费用.应用该新算法构建定流值比例的最小双费用流算法的运输网络模型,就可以获得最优运输方案.逻辑推理和仿真实验结果均表明,所提出的算法可行、有效,能较好地解决稀疏网络以及复杂网络中定流值比例的最小双费用流问题.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵礼峰	南京邮电大学理学院	47	251	9.0	12.0
2	刘艳清	南京邮电大学理学院	2	5	2.0	2.0