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

《一种求解最小双费用流问题的算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、CN43—1258／TP计算机工程与科学第36卷第3期2ol4年3月ISSN1007—13OXComputerEngineering&ScienceVO1．36．No．3。Mar．2Ol4文章编号：1007—130X(2014)03—0446—06一种求解最小双费用流问题的算法马宇斌，谢政，陈挚(国防科学技术大学理学院，湖南长沙410073)摘要：多目标优化是网络最优化的一个重要子问题。通过实际应用案例，抽象出一种带容量限制的双费用权网络模型，并由此提出了相应的最小双费用流问题。之后，借鉴网络分层的思想，根据双费用权网络的特点设计出一个求解该问题的双层原始对偶算法，并严谨地证明了算法

2、的正确性，估计出算法的复杂度为0(n。。)。此外，对算法进行了推广改进，使其能求解一般k费用权网络中的最小k费用流问题。最后，通过一个实例来演示算法的执行。关键词：双费用权网络；最小双费用流；双层原始对偶算法；复杂度中图分类号：TP301．6文献标志码：Adoi：10．3969／．issn．1007—13OX．2014．03．012Analgorithmtosol'vi"ng~milnilmumdouble-costflowo0roblemMAYu—bin，XIEZheng，CHENZhi(CollegeofScience，NationalUniversityofDefenseTec

3、hnology，Changsha410073，China)Abstract：Multi—objectiveoptimizationisacriticalpartofnetworkoptimization．Thepaperderivesaminimumdouble——costflowprohlemindouble—costnetworkmodelwithlimitationsoncapacityfromapracticalcase．Accordingtothethoughtofhierarchyandthefeatureofdouble—costnetwork，thecorre—spo

4、ndingminimumdouble—costflowproblemisintroducedandatwo——layerprimal—dualalgorithmispro—posedtosolveit．ThecorrectnessofouralgorithmisprovedanditscomplexityisestimatedasO(n0)．Besides，thealgorithmisimprovedtosolvetheminimumk-costflowproblemink-cOStnetwork．Fi—natty，acaseisusedtoexhibithowthealgorith

5、mworks．Keywords：double—costnetwork；minimumdouble—cOStflow；tWO—layerprimal—dualalgorithm；corn—plexity代价和丢包率这两个重要参数看成是特殊的“费1引言用”，再辅以链路带宽约束，则问题就变成一个带容量限制的双费用权问题。对于双费用权问题，传统网络多目标优化问题作为组合最优化和网络的网络流算法已经不再奏效。王焕雄等从图论的一个交叉问题，一直以来在工程规划、地理不同角度讨论了含有弧容量和弧费用的双权有向信息系统、通信网络和交通运输等领域有着十分广网络，给出了计算两个节点问的使费用与容量之比泛的

6、应用。尤其是近年来，随着通信和航天技术的最小的路径的多项式算法，但这种“双权”包括了容发展，各国都在大力研发天基信息网络系统，以争量，实质仍是单费用网络；ZhuDe—tongl6针对广义取在海、陆、空、天等领域取得自主控制权；而对天多品种最小费用流问题，提出一种对偶理论，将问基信息网络的研究归根到底就是求解一个多权网题转化成一对含有内、外层问题的双水平规划，并络最优化问题，其求解目标会因研究侧重点或分析导出相应的Kuhn—Tucker条件，但未给出具体算方法的不同而不同。若将网络链路上的信息通行法及复杂性分析；孙小军等提出了单费用运输网收稿日期：2o12-062l；修回日期：2012

7、-12—19通信地址：410073湖南省长沙市国防科学技术大学理学院学员五队Address：Team5，CollegeofScience，NationalUniversityofDefenseTechnology，Changsha410073，Hunan，P．R．China马宇斌等：一种求解最小双费用流问题的算法447络中的最少时间最小费用路问题，即要求找出通行的网络均是简单的。时间最短的最小费用路，并给出了一个求解算法；Coello[8于2006年针对双