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

来源：计算机技术与发展杂志2017年第04期北京时间：

作者：赵礼峰;刘艳清

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

关键词：最小双费用流算法;余网络;邻接矩阵;Ford算法;费用差