具有流量为零或介于上下界之间的二态组合约束最小费用流问题的算法

摘要：

对于各弧流量为零或者流量介于非零上下界之间的二态组合约束最小费用流问题,一般在穷举各种状态组合的基础上结合普通最小费用流算法求解,其复杂性为普通最小费用流问题复杂性的2|A|倍(式中,指数|A|为弧的数目).提出了一种新的算法,以具有相应上下界容量约束最小费用流问题的最优解为初值,构建残量网络,消除负费用圈,最后得到最优解.该算法总的复杂性仅为普通最小费用流问题复杂性的2倍.

关键词：最小费用流、有向图、双流网络

所属期刊栏目：22

分类号：O223(运筹学)

资助基金：内蒙古高等学校科研项目NJ02112

在线出版日期：2004-03-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：285-288