容量型最小费用流逆问题的可行性研究

(厦门大学数学科学学院,福建 厦门 361005)

最小费用流; 逆问题; 负费圈; 剩余网络; 可行性

The Feasibility of the Capacity Inverse Minimum Cost Flow Problem
LIU Longcheng*,LI Chao,CUI Jia

(School of Mathematical Sciences,Xiamen University,Xiamen 361005,China)

DOI: 10.6043/j.issn.0438-0479.201702045

备注

针对容量型最小费用流逆问题的可行性及相关优化进行研究,证明了判断容量型最小费用流逆问题是否可行可以在多项式时间内完成.如果容量型最小费用流逆问题不可行,即无论怎样修改容量的上界u和下界l,初始流f0都不能变为新网络的最小费用流.给出了两种调整初始流f0的算法,证明了通过最少修改初始流f0,可以使最小费用流逆问题变为可行.

This paper studies the feasibility of the capacity inverse minimum cost flow problem.First,we verify weather or not the capacity inverse minimum cost flow problem is feasible or not can be finished in polynomial time.Second,if the capacity inverse minimum cost flow problem is infeasible,i.e.,the given feasible flow f0 cannot form a minimum cost flow,regardless how we change the upper bound u and lower bound l.In this case,we present two algorithms to modify the given flow f0 as little as possible to make the capacity inverse minimum cost flow problem feasible.

·