最小费用流问题的研究

《最小费用流问题的研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、最小费用流问题的研究摘要本文主要研究的是最小费用流问题C在给岀一些定义定理的基础上进一步求解最小费用流问题从而得到更好的算法。关键字最小费用流问题剩余网络容许网络算法复杂度1最小费用流问题的概述给定一个有向网络G=(N,A)0其中N={1,2,3,...」,..」}表示顶点集合,A表示G中的所冇弧构成的一个集合。任意的弧(z,j)GA,用J表示弧QJ)上单位流量的费用，用竹表示弧仏刀上的最大流量，任意的iwN用b(i)表示在i层:-点处所提供的流量或所需要的流量。当b(i)>0时，表示在i这一点处所提供的流量为b(i),当/?(/)<0时，表示

2、在2°这一点处所需要的流量为b(i)oM小费用流问题是指在冇容量约束的网络中，当网络容量带冇费用约束的时候，我们希望一定的流量在通过网络的时候的费用最小，这就形成了最小费用流模型。模型如下：MinZ(x)=工CjjXjj(jj)"Subjecttoz矿zXji=b(i)foralliwN,{_/：(/」•)"}{_/：(•)"}0

3、弧QJ)的费用用s来表示，弧(i,./)的剩余容量用r..=Ujj-Xy来表示,弧(7，/)费用用Cm=一w来表示,,弧(川)的剩余容量用m來表示。去掉剩余容量为非正的弧后所构成的图形用g(x)表示。我们把G(x)叫做剩余网络。定理2.1(NegativeCycleOptimalityConditions)设尢是最小费用流问题的一个可行解,*那么x是最小费用流问题的一个最优解当且仅当满足negativecycleoptimalityconditions:剩余网络G(T)屮不存在负圈。根据负圈的最优条件，为了得到可行流X,我们可以利用找最大流的算

4、法建立一个可行流X,再根据可行流X构造剩余网络G(x)o在剩余网络G(x)中找负圈W,収5:=min{©:亿j)eW}沿着W上的弧增广5个单位的流，消去负费用的圈W。更新G⑴,再找负圈，重复上述过程，直到G(jc)中不存在负圈为止。这样的算法称为cycle-cancelingalgorithmo2.1算法的具体步骤如卜•：algorithmcycle-canceling:beginestablishafeasibleflowxinthenetwork;whileG(x)containsanegativecycledobeginusesomeal

5、gorithmtoidentifyanegativecycleW;8:=min{©:(z,j)eIVjaugment8unitsofflowinthecycleWandupdateG(x);end;end;2.2算法的复杂度分析在剩余网络G(x)'l'用标签法找负圈时，其时间复杂度为05加)。算法的主要工作量在于连续寻找负圈并消去负圈。我们用C表示弧上的费用中的最大者，用U表示所冇弧上的容量屮的最人者，由于任何可行流的费用不可能超过加C",而每次消去一个负圈至少使得费用下降一个单位，一次消去负圈最多执行0(mCU)o由此可知，该算法的时间复杂度

6、为0(nm2CU)3successiveshortestpathalgorthmi定义3.1任意的顶点iwN,我们用龙(,)表示顶点i的势，川向量兀表示图屮所有顶点的势,用磅表示弧(ij)±的减少费用，且规定:C#二J—兀(i)+7T(j)。定理3.1(ReducedCostOptimalityConditions)设兀*是最小费用流问题的一个可行解,那么/是最小费用流问题的一个最优解当且仅当表示顶点势的向量龙满足reducedcostoptimalityconditions：对于任意一条弧(Z,j)eG(T),都有cf>()成立。定义3.2设

7、兀是一个流，当兀满足容量的限制和非负的限制，但不满足点的平衡条件的限制时,我们把兀叫做pseudoflowso对于任意一个psedudoflowsx,当iGN是一个不平衡的点吋，我们有e(i)=b(i)+工心-{_/：(")}{JVM对于任意的iwN,当£(0〉0时，表示顶点i为过剩的点；当e(i)<0时，表示顶点i为不足的点；当6>(z)=0时，表示顶点,为平衡的点。所以有工啲=工处)=0ieNieN故有工W)二-&⑴iwDiwE其中D={ib⑴>0,VieN}E={ib(i)<0,VzeN}。由上口J知，一个冇向网络G=(N,A)中如果

8、含冇一个过剩点，那么在这个网络中至少含有一一个不足点。推论3.2假设pseudoflows兀和顶点势的向量乃满足减少费用的最优条件。设向量d表示剩余网