6.7最小费用流问题

第七节最小费用流问题最小费用流算法规划形式算法步骤算法复杂性运输问题对偶规划算法步骤规划形式基本假设：给定有向网络G=(N,A,C,W)，其中cij表示弧(i,j)∈A的容量，wij表示单位流通过弧(i,j)∈A的费用。则流x=(xij)的费用为：∑wijxiji,j问题：求一个从s到t,其流值为v的流,使得流的费用达到最小。1.最小费用流算法规划形式续一原始规划PAjicxtsiNixxvxxvxxtsxwijijjjiijjjttjjjssjAjiijij),(,0,,,0)()()(..min),(规划形式续二对偶规划DNiipAjirAjiwripjptsrcvspvtpijijijAjiijij,)(),(,0),(,)()(..)()({max),(无限制其中，p(i)为对应于点i的对偶变量；rij对应于弧(i,j)的对偶变量.对偶规划的松紧条件为:p(j)-p(i)-rijwij⇒xij=0.(6.7.1)rij0⇒xij=cij(6.7.2)如果{p(i),rij},{xij}分别是对偶与原规划的可行解，那么只要满足松紧条件，它们就分别是最优解.因为p(i)无限制，所以可任意给出一组p(i)，令rij＝max{0,p(j)-p(i)-wij}(6.7.3)显然rij≥0,于是得到对偶规划的一组可行解．对偶规划的松紧条件为:p(j)-p(i)-rijwij⇒xij=0.(6.7.1)rij0⇒xij=cij(6.7.2)这时(6.7.1)、(6.7.2)变为:p(j)-p(i)wij⇒xij=0.(6.7.4)p(j)-p(i)wij⇒xij=cij(6.7.5)算法基本思想:这时把原规划中的v改成v0,{xij}就是最优解.因为v0v,所以需要增加流量.在增加流量的过程中，保持{xij}满足原始规划的后面两个约束,同时让条件(6.7.4)、(6.7.5)继续成立,一直到流量为v为止..任给一组p(i)(开始可全为零),由(6.7.3)决定rij,就得到对偶规划的一组可行解,然后再给出一组xij,要求xij满足原始规划的后面两个约束(如xij=0),同时这两组解都满足条件(6.7.4)、(6.7.5).现在这两组解还不是最优解，因为{xij}不一定满足原始规划的前两个约束.如果∑(xsj-xjs)=v0,v0vj增加流量的办法是找增广路.增广路是在xijcij或者xij0的弧上找.为了继续满足条件(6.7.4)、(6.7.5),我们只能在p(j)-p(i)＝wij,xijcij和p(j)-p(i)＝wij,xij0的弧上找增广路.如果找不到,就修改p(i)．最小费用流算法的步骤第1步(开始)让所有的流xij=0，所有点对应的数p(i)=0。第2步(决定哪些弧可以改变流量)用I表示这样的弧集合使p(j)-p(i)=wij，同时xijcij用R表示这样的弧集合使p(j)-p(i)=wij，同时xij0用Q表示不在I∪R中的弧集合。最小费用流算法的步骤续第3步(改变流量)用最大流算法,在I∪R上找增广路,增加流量.如果从s到t的流量已经是v,那么计算停止,已经得到一个流量是v的最小费用流.如果从s到t不能再增加流量,检查在Q∪I∪R中是否能找到增广路.如果不能找到增广路,那么该网络的最大流达不到v；如果在Q∪I∪R中能找到增广路,就转入第4步。第4步(改变顶点的p(i)值)把所有点分成两类：S是标上号的点的集合,T是标不上号的点的集合,让S中的点p(i)值不变,T的点p(i)值全部加1，再转回第2步。例求解下图所示网络中自点s到点t其值为3的最小费用流.其中每条弧上的第一个数表示单位流的费用,第二个数表示容量.stba1,21,21,23,43,1最小费用流算法的复杂性设网络的点数为n，弧数为m，弧的最大容量为w算法的循环次数取决于点的p(i)值修正的次数，最多进行mw次因此第2步的计算量为O(m2w)如果最大流值为v，则留增广最多进行v次所以第3步的计算量为O(nw)第4步的计算量为O(nmw)所以，总的计算量为O(m2w+nmw)运输问题ai表示发点i可供应的产品数量bj表示收点j所需的产品数量wij表示从发点i到收点j的单位产品运输费用xij表示从发点i分配给收点j的产品数量0),,2,1(,),,2,1(,..min,ijjiijijijjiijijxnjbxmiaxtsxw对偶规划s.t.ui+vjwij,i=1,2,…,m,j=1,2,…,nmax{∑aiui+∑bjvj}ij{其中,ui为对应于发点i的对偶变量;vj为对应于收点j的对偶变量对偶规划的松紧条件为:xij0⇒ui+vj=wij(6.7.8)根据对偶理论,如果{xij}是原规划的可行解并与对偶规划的一组解{ui,vj}一起满足(6.7.8)，只要调整对偶解，使其逐步达到可行，则它们分别达到最优．有了原规划的初始可行解后，可找出ui,vj,满足对基变量xij,wij-ui-vj=0,(m+n-1)个方程确定(m+n)未知数.原规划的初始可行解容易给出.因为∑ai=∑bj,原约束条件只有(m+n-1)个独立方程,任给一个支撑树,从任一一度点开始,最大限度满足需求或供应量即可．调整原规划的可行解使对偶解在满足松紧条件下逐步达到可行.令:wij=wij-ui-vjwij也称作检验数.对基变量wij=0;对非基变量若wij≥0对偶解达到可行,于是它们分别达到最优.否则,从负检验数中选择最小的变量,改成基变量,改进当前解,直到达到最优．算法步骤第1步(开始)任给原始规划的可行解{xij}第2步(计算对偶解)对于原始规划的可行解{xij}，计算出对偶规划的一个解{ui,vj}第3步(计算检验数)对于对偶规划的解{ui,vj},计算wij=wij-ui-vj,i=1,2,…,m,j=1,2,…,m若所有的wij均非负,则计算结束,这时得到的{xij}和{ui,vj}分别为原始规划和对偶规划的最优解；否则，转第4步算法步骤续例求如图所示运输问题的最优解143213281065169147131299-45-20-30-30355040第4步(调整原始可行解)令即选择xst进入基。对应于网络中，即在支撑树上加入弧(s,t)，从而得到一个回路。并选择其流量xst=θ，使这个回路上的流量通过加θ或减θ以达到去掉一条弧的目的，从而得到一个新的被改进的原始可行解{xst}，转第2步wst=min{wij|wij0}i,j