论文部分内容阅读
给定网络N(V,A,u,l,c,s,t),所谓的最小费用流问题就是求一个达到给定流量(一般就是网络的最大流)而费用达到最小的可行流。而最小费用流逆问题则是,给定初始网络N(V,A,u,l,c,s,t)和初始可行流f0,在当前参数下,f0不是网络N的最小费用流,我们要通过最少的改变某些参数,使得f0在新的参数下是最小费用流。本文考虑的最小费用流逆问题改变的参数是容量的上界u和下界l,我们称之为容量型最小费用流逆问题。 本文主要针对容量型最小费用流逆问题的可行性及相关优化问题展开研究。所谓的可行性,就是给定网络N(V,A,u,l,c,s,t)和可行流f0,在当前参数下,f0不是网络N的最小费用流,我们是否可以通过改变容量的上界u和下界l,从而使得f0在新的参数下是最小费用流。首先我们证明了判断容量型最小费用流逆问题是否可行可以在多项式时间内完成。其次如果容量型最小费用流逆问题不可行,即无论如何修改容量的上界u和下界l,f0都不能成为N的最小费用流,则我们希望通过最少改变f0来使得最小费用流逆问题变得可行。这里我给出了两个算法来调整流f0。最后,我们给出了例子来进一步展示我们的算法。