摘要
对于各弧流量为零或者流量介于非零上下界之间的二态组合约束最小费用流问题,一般在穷举各种状态组合的基础上结合普通最小费用流算法求解 ,其复杂性为普通最小费用流问题复杂性的 2 |A| 倍 (式中 ,指数 |A|为弧的数目 ) .提出了一种新的算法 ,以具有相应上下界容量约束最小费用流问题的最优解为初值 ,构建残量网络 ,消除负费用圈 ,最后得到最优解 .该算法总的复杂性仅为普通最小费用流问题复杂性的
A special minimum cost flosw (MCF)problem,in which flow of each arc is zero or between nonzero minimum flow and maximun capacity,is often solved by enumerating whole combination of binary feasible zone of all arcs coupled with an algorithm for ordinary MCF.A simple algorithm is presented which finds the solution by reducing negative cost cycle within the residual network based on the optimal solution of binary-flow network problem.The complexity of the algorithm is much lower than that of other algorithms for MCF under binary feasible zone combinatorial constraint.
出处
《包头钢铁学院学报》
2003年第3期285-288,共4页
Journal of Baotou University of Iron and Steel Technology
基金
内蒙古自治区高等学校科学研究基金资助项目(NJ02112)
关键词
最小费用流
有向图
双流网络
minimum cost flow
directed graph
binary-flow network