一种求解最小双费用流问题的算法

J4 ›› 2014, Vol. 36 ›› Issue (03): 446-451.

一种求解最小双费用流问题的算法

马宇斌，谢政，陈挚

（国防科学技术大学理学院，湖南长沙 410073）

收稿日期:2012-06-21 修回日期:2012-12-19 出版日期:2014-03-25 发布日期:2014-03-25

An algorithm to solving minimum double-cost flow problem

MA Yubin,XIE Zheng,CHEN Zhi

(College of Science,National University of Defense Technology,Changsha 410073,China)

Received:2012-06-21 Revised:2012-12-19 Online:2014-03-25 Published:2014-03-25

摘要/Abstract

摘要：

多目标优化是网络最优化的一个重要子问题。通过实际应用案例，抽象出一种带容量限制的双费用权网络模型，并由此提出了相应的最小双费用流问题。之后，借鉴网络分层的思想，根据双费用权网络的特点设计出一个求解该问题的双层原始对偶算法，并严谨地证明了算法的正确性，估计出算法的复杂度为O(n2v0)。此外，对算法进行了推广改进，使其能求解一般k费用权网络中的最小k费用流问题。最后，通过一个实例来演示算法的执行。

关键词: 双费用权网络, 最小双费用流, 双层原始对偶算法, 复杂度

Abstract:

Multi-objective optimization is a critical part of network optimization. The paper derives a minimum doublecost flow problem in double-cost network model with limitations on capacity from a practical case. According to the thought of hierarchy and the feature of double-cost network, the corresponding minimum double-cost flow problem is introduced and a two-layer primaldual algorithm is proposed to solve it. The correctness of our algorithm is proved and its complexity is estimated as O(n2v0). Besides, the algorithm is improved to solve the minimum kcost flow problem in k-cost network. Finally, a case is used to exhibit how the algorithm works.

Key words: double-cost network;minimum double-cost flow;two-layer primaldual algorithm;complexity

马宇斌，谢政，陈挚. 一种求解最小双费用流问题的算法[J]. J4, 2014, 36(03): 446-451.

MA Yubin,XIE Zheng,CHEN Zhi. An algorithm to solving minimum double-cost flow problem [J]. J4, 2014, 36(03): 446-451.

参考文献

［1］Xie Zheng, Li Jiangping. Network algorithms and complexity theory［M］. 2nd edition. Changsha:National University of Defense Technology Press, 2003.(in Chinese)
［2］Klein M. A primal method for minimal cost flows with applications to the assignment and transportation problems［J］. Management Science, 1967, 14(3):205220.
［3］Edmonds J, Karp R M. Theoretical improvements in algorithmic efficiency for network flow problems［J］. Journal of the ACM, 1972, 19(2):248264.
［4］Ahuja R K, Magnanti T L, Orlin J B. Network flows:Theory, algorithms, and applications［M］. London:Prentice Hall, 1993.
［5］Wang Huanxiong, Li Xijun. Optimal analysis of the path of the network with double weights［J］. Journal of Jilin Institute of Chemical Technology, 2001, 18(2):6466.(in Chinese)
［6］Zhu Detong. Dual theories of general multicommodity minimal cost flow problems［J］. OR Transactions, 2002, 6(3):1726.
［7］Sun Xiaojun, Jiao Jianmin. An algorithm for the problem of finding the minimalcost path with the minimal time［J］. Computer Engineering & Science, 2008, 30(7):7778.(in Chinese)
［8］Coello Coello C A. Evolutionary multiobjective optimization:A historical view of the field［J］. IEEE Computational Intelligence Magazine, 2006, 1(1):2836.
［9］Ao Youyun, Chi Hongqin. Differential evolution algorithm for multiobjective optimization［J］. Computer Engineering & Science, 2011, 33(9):8894.(in Chinese)
［10］Wu Runxiu. Double weighted hierarchical network algorithm based on granular computing［J］. Computer Engineering and Applications, 2011, 47(24):7787.(in Chinese)
附中文参考文献：
［1］谢政，李建平. 网络算法与复杂性理论［M］.第二版. 长沙:国防科技大学出版社, 2003.
［5］王焕雄, 李喜军. 双权网络路径的最优化分析［J］. 吉林化工学院学报, 2001, 18(2):6466.
［7］孙小军, 焦建民. 一种求解最少时间最小费用路问题的算法［J］. 计算机工程与科学, 2008, 30(7):7778.
［9］敖友云, 迟洪钦. 多目标优化差分进化算法［J］. 计算机工程与科学, 2011, 33(9):8894.
［10］吴润秀. 基于粒计算的双权网络分层算法［J］. 计算机工程与应用, 2011, 47(24):7787.

[1]	闫少辉, 施万林, 宋震龙, 王尔童, 孙溪, 黄羿博, . 一个新三维混沌电路设计及其同步控制[J]. 计算机工程与科学, 2022, 44(08): 1409-1417.
[2]	那格思, 赵海燕. 分数阶Rucklidge系统复杂度分析及有限时间同步[J]. 计算机工程与科学, 2020, 42(09): 1625-1631.
[3]	陈芳，张乾. 超立方体网络环诊断策略的研究[J]. 计算机工程与科学, 2019, 41(07): 1191-1196.
[4]	李召义，刘占军，薛亚茹，刘红霞. 基于势博弈的认知全双工中继选择策略研究[J]. 计算机工程与科学, 2019, 41(02): 286-292.
[5]	宋伟1,宋玉1,张帆2,范明1,叶阳东1. 基于排列熵的SAX特征表示方法复杂度及相关特性研究[J]. 计算机工程与科学, 2018, 40(07): 1303-1309.
[6]	毕松松,戴小平,周建钦,王喜凤. 构造给定k错线性复杂度谱的2n周期序列[J]. 计算机工程与科学, 2016, 38(12): 2483-2492.
[7]	崔凯，周宽久，梁浩然，潘杰. Android智能电视测试用例生成方法及应用研究[J]. 计算机工程与科学, 2016, 38(08): 1669-1675.
[8]	周全1,2,3,王中元1,2,3. H.264码率控制跳帧算法的优化[J]. J4, 2016, 38(02): 325-330.
[9]	袁梅冷1，2，杨张2，雷海军2. 一种基于JMVC参考模型的运动估计优化算法[J]. J4, 2015, 37(06): 1208-1213.
[10]	官翔1，魏悦川1，杨晓元1,2. E2算法的中间相遇攻击[J]. J4, 2015, 37(03): 524-528.
[11]	彭武1，何怡刚1,2，方葛丰3，樊晓腾3. 一种靶场电磁环境复杂度评估方法[J]. J4, 2014, 36(01): 105-110.
[12]	杨文川，刘健，于淼. 基于双数组Trie树的中文分词词典算法优化研究[J]. J4, 2013, 35(9): 127-131.
[13]	罗孟宇1，陈志刚1，邝祝芳1，2. 基于频域复杂度分析的频谱感知算法[J]. J4, 2013, 35(6): 52-56.
[14]	张真. 量数据Delaunay三角网的并行构建算法[J]. J4, 2013, 35(4): 1-7.
[15]	李京旭1，张雄明2. 基于分解反折结构的低内存低复杂度离散小波变换[J]. J4, 2013, 35(10): 144-148.