赵礼峰，刘艳清

(南京邮电大学 理学院，江苏 南京 210003)

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

赵礼峰，刘艳清

(南京邮电大学 理学院，江苏 南京 210003)

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

最小双费用流算法；余网络；邻接矩阵；Ford算法；费用差

0 引 言

最小双费用流问题是网络优化中的一个核心问题，许多网络优化问题都可归结为最小双费用流问题的特例，如最短路[1-2]、最大流[3-5]以及最小费用最大流[6-8]问题，这些网络优化问题都可归为单可行流算法研究。随着物流运输的发展，这些单可行流算法研究已经满足不了运输行业不断发展的需要。由此，谢政和汤泽滢根据一个实例建立了在容量—费用双流网络中求最小费用最大双流的模型[9]，提出了最小费用最大双流和双流增量网络的充要条件，该算法证明了最小费用最大双流算法的正确性。……