网络优化ppt课件.ppt

1,网 络 优 化,Network Optimizationhttp:/,清华大学数学科学系 谢金星办公室：理科楼2206#（电话：62787812）Email:http:/,清华大学课号：70420133（研）,第7章 最小费用流问题(Minimum Cost Flow Problem)第1讲,2,许多实际问题都可以转化为最小费用流问题,S,T,最小费用流问题的例子,公路交通网络：车辆路线确定,最短路问题,最小费用流问题,1辆车,多辆车:车流,3,定义7.1 在流网络N=(V,A，L,U,D)上增加如下的权函数：C：A R为弧上的权函数，弧（i，j）对应的权 C（i，j）记为cij，称为弧（i，j）的单位流量的成本或费用（cost）;此时网络可称为容量-费用网络(一般仍可简称为网络),记为 N=(V,A,C，L,U,D).,7.1.1 最小费用流问题,di 0:供应点(supply node)或源(source)、起始点或发货点 di 0:需求点(demand node)或汇(sink)、终止点或吸收点 di 0:转运点(transshipment node)或平衡点、中间点,可以把L 0的网络转化为L=0的网络进行研究(思考？)除非特别说明,假设L=0,网络简记为N=(V,A,C，U,D).,4,定义7.2（容量-费用网络中的流(flow)的定义同前一章）流x的（总）费用定义为,通常又称为转运问题(transshipment problem)或容量受限的转运问题(capacitated transshipment problem).,最小费用流问题就是在网络中寻找总费用最小的可行流.,最小费用流问题,引理7.1 最小费用流问题存在可行流的必要条件,经典的最小费用流问题：单源单汇(起点s，终点t)，寻找从s流到t的给定流量(或最大流量、最小流量等)的最小费用流.,线性费用网络,思考：经典问题与一般问题有什么关系？是否等价？,5,例 7.1 最短路问题,在有向网络中，令所有弧上容量下界为0，容量（上界）为1，并令图中节点s的供需量为1，节点t的供需量为-1，则：从s到t的一条有向路正好对应于网络中的一个可行流x（弧(i，j)位于s-t路上：xij=1；弧(i，j)不在s-t路上：xij=0）.如果再令所有弧上的(单位流量)的费用为“弧长”,则此时的最小费用流问题就是第五章讨论过的最短路问题.在第五章我们正是用这样的方式对最短路问题进行建模的,7.1.2 最小费用流模型的特例及扩展,6,例-最大流问题,设s为起点,t为终点,增加弧(t,s),令,7.1.2 最小费用流模型的特例及扩展,而令所有其他弧上的费用为0,所有顶点上的供需量(外部流量)全为0.,7,例-运输问题(transportation Problem)又称Hitchcock问题（Hitchcock,1941年）,完全二部图只有源和汇没有中间转运点,7.1.2 最小费用流模型的特例及扩展,如果每条弧上还有容量(上下限)的限制,则称为容量受限的运输问题(capacitated transportation problem).,有解的必要条件,可以不失一般性,指派问题(assignment problem),8,7.1.2 最小费用流模型的特例及扩展,（1）当一定的流量流过一条弧时，该弧上导致的总费用与流量大小成线性正比关系，这样的流网络一般称为线性费用网络.如果当一定的流量流过一条弧时，该弧上导致的总费用不一定与流量大小成线性正比关系，而是流量大小的一个凹（或凸）函数，则这样的网络称为凹（或凸）费用网络，相应的最小费用流问题称为凹（凸）费用网络上的最小费用流问题.,（2）当流量流过一条弧时，流出该弧的流量（即流入该弧终点的流量）与进入该弧的流量（即流出该弧起点的流量）相等.如果当流量流过一条弧时，流出该弧的流量是进入该弧的流量的一个线性函数，即流出该弧的流量是对进入该弧的流量按一定比例进行放大或缩小的结果，则这样的流网络一般称为带增益(或盈亏)的流网络（flow with gain network）.增益除了可以发生在弧上，类似地可以考虑增益发生在节点上,9,7.1.2 最小费用流模型的特例及扩展,最 小 费 用 流 问 题,狭义模型,广义模型,10,单源单汇网络可行流x的流量（或流值）为v=v（x）=ds=-dt如果我们并不给定ds 和dt,则网络一般记为N=(s,t,V,A,C,U)容量可行且转运点流量守恒的流称为s-t可行流，有时为了方便也称为可行流.最小费用流问题就是在网络N=(s,t,V,A,C,U)中计算流值为v的最小费用流x 或者当不给定流值时,计算流值最大的最小费用流x(此时流x称为最小费用最大流).,7.2 消圈算法与最小费用路算法,最小费用最小流?,11,7.2 消圈算法与最小费用路算法,定义7.3 对网络N=(s,t,V,A,C,U)中给定的s-t可行流x，网络N关于流x的残量网络N(x)=(s,t,V,A(x),C(x),U(x),其中A(x),C(x)，U(x)定义如下：（residual network，或增量网络或辅助网络）,讨论算法复杂度时，假定:弧（i，j）A时，弧（j，i）A；c ij=-cjiA（x）=A(允许容量为0的弧仍然保留在网络中就可以了),其中称,uij(x)为弧(i,j)上的残留容量(residual capacity).,12,定义W的费用为,对于N(x)中的任何一个有向圈W,它一定对应于原网络N中的一个增广圈(增广弧构成的圈)；通过沿W对当前流x进行增广，可以获得流值相等的s-t可行流y.,消圈算法的思想,则当增广的流量为时,只要N中存在费用为负数的增广圈W，即C（W）0，则可以通过沿W 对当前流 x 进行增广，获得流值相等但费用更小的s-t可行流y.,13,设x0为不同于的可行流，但费用低于x的费用，即,7.2.1 消圈算法(cycle-canceling algorithm),定理7.1 可行流x为最小费用流的充要条件是N(x)中不存在负费用增广圈.,令 x1=x0-x,则，即令x1为网络N中的循环流.,一个循环流一定可以表示为至多m个非零圈流之和，所以可以将x1表示为r个非零圈流之和（）。设对应的有向圈为Wk，,至少存在一个费用为负的增广圈.矛盾,必要性是显然的.反证法证明充分性：,14,N(x)中找负圈可用最短路算法(如Bellman-Ford算法，O(m n)则该算法的复杂度为O(n m 2CU),不是多项式时间算法.,STEP 2.沿找到的负圈增广流量,转STEP 1.,Step0可借用最大流算法，复杂度为O(n2m),STEP 0.在网络N=(s,t,V,A,C,U)中计算流值为v的可行流 x.,7.2.1 消圈算法:Klein(1967)等,STEP 1.在残量网络N(x)中判别负圈.若无负圈,则已经找到了最小费用流，结束；否则转STEP 2.,如按一些特定次序消圈,可得到一些多项式时间算法,复杂度？,任何可行流的费用不可能超过mCU设数据是整数,每次消去一个负圈至少使费用下降一个单位设数据是整数,消去负圈的STEP12最多执行O(mCU)次,15,略,7.2.1 消圈算法,例：,16,能否首先在网络N=(s,t,V,A,C,U)中计算流值为v且费用最小的s-t可行流(v v)，然后对它沿增广路增广以增加流值呢?,7.2.2 最小费用路算法,为了获得最小费用流，我们希望沿费用最小的增广路对当前流x进行增广，以最小的费用增加获得流值更大的s-t可行流y,对于N(x)中的一条从s到t的有向路P,它一定对应于原网络N中的一条增广路，即可以通过沿P对当前流x进行增广，获得流值更大的s-t可行流y.定义P的费用为,则当增广的流量为时,17,7.2.2 最小费用路算法,定理7.2 设x为流值为v的最小费用流，P为关于x的从s到t的一条最小费用增广路，且沿P所能增广的流量为，则增广后得到流值为v+的最小费用流y.,只需证明网络中不存在关于y的负费用增广圈.用反证法,假设增广后存在关于y的负费用增广圈W.由于除P以外的弧及其流量在增广前后没有发生改变,于是P和W至少有一条公共弧.不妨假设P和W只有一条公共弧,记为(i,j),如果(i,j)在P中是正向弧,则在W中是反向弧;反之,如果(i,j)在P中是反向弧,则在W中是正向弧,也是网络中关于x的增广路,且,18,7.2.2 最小费用路算法,也称为连续最短路算法,即Successive Shortest Path Algorithm),Jewell(1958),Iri(1960),Busacker&Gowen(1961)独立提出的,STEP 0.取x为任一s-t可行流、且在同一流值的流中费用最小的流(如x=0).,STEP 1.若x的流值达到v,结束；否则在残量网络N(x)中判别最小费用路.若无这样的路,则流值不可达到v,结束；否则STEP 2.,STEP 2.沿该最小费用增广路增广流量(增广后的流值不超过v),转STEP 1.,STEP1可用最短路算法：记最短路算法的复杂度为S(n，m，C),STEP12最多执行O(v)次,复杂度？,最大流流值不超过nU，本算法复杂度为 O(nUS(n，m，C),采用特定的变尺度技术,可以得到一些多项式时间算法,19,略,7.2.2 最小费用路算法,例：,20,7.3.1对偶问题及互补松弛条件,仍然考虑传统的单源单汇网络的最小费用流问题,两类约束分别引入对偶变量和z,则这一问题的对偶问题为,7.3 原始-对偶算法,21,互补松弛条件 设x和(,z)分别为原问题和对偶问题的可行解：,下面我们说明在一定的“约定”下,这一条件可以等价地写成当 时，=0；(7.19)当 时，=；(7.20)当 时，.(7.21),约定:存在对偶可行的变量z，使得上式成立.,定理7.3 设x为原问题的可行解,则x为最小费用流的充要条件是:存在节点的势（）,满足条件(7.19)(7.21).,7.3.1对偶问题及互补松弛条件,记“相对费用”（Reduced Cost）,22,7.3.1对偶问题及互补松弛条件,引理7.2 最优性条件(7.19)(7.21)等价于，对于N(x)中任意的(i,j)弧,0,当 时，即 0,所以=-()=-0,因此(j,i)弧不属于残量网络N(x).所以=0.,当 时，即 0,(i,j)弧不属于残量网络N(x),=,当 时，(i,j),(j,i)弧均属于残量网络N(x).所以,所以,23,思路：从流值不一定达到v的s-t可行流开始，迭代中始终保持最优性条件(7.19)(7.21)成立，直到流值达到v为止.迭代包括两个方面：对弧上流的增广；对节点上势的修改,当N0(x)中找不到增广路且流值小于v时，必须进行下一个过程，修改节点上的势.,原始-对偶算法就是在允许网络N0(x)中寻找增广路并进行增广（最大流）,为保证流的增广过程中始终保持最优性条件(7.19)(7.21)，原始-对偶算法只沿满足 的弧增广流量.,N(x)中满足 的弧组成的子网络称为允许网络（Admissible Network），记为N0(x)=,7.3.2原始-对偶算法 基本思想,N0(x)中的弧就是N(x)中满足=0的弧,24,7.3.2原始-对偶算法 基本思想,当N0(x)中找不到增广路且流值小于v时，必须修改节点上的势.保持最优性条件(7.19)(7.21)，并且希望修改后N0(x)中可以找到增广路,可以证明,修改后最优性条件(7.19)(7.21)仍然成立，且将会有新的弧增加到N0(x)中.,希望把N(x)中一些不满足=0的弧也纳入N0(x)中.,以 为弧长在N(x)中计算从节点s到所有节点i的最短路路长d(i).,25,7.3.2原始-对偶算法：Ford和Forkerson(1957,1962),STEP 0.取x为任一s-t可行流(如x=0)，令初始势=0.,STEP 1.若x的流值达到v,计算结束；否则在残量网络N(x)中，以相对费用为弧长，计算从节点s到所有节点i的最短路路长d(i)，并令i=i-d(i),继续STEP 2.,STEP 2.在允许网络N0(x)中判别从s到t的最大流(如可用第6章介绍的算法).若该最大流流值为0,则原网络中流的流值不可达到v,计算结束；否则沿该最大流确定的增广路增广流量(增广后的流值不超过v),转STEP 1.,26,7.3.2原始-对偶算法 正确性,引理7.3 在算法运行过程中，最优性条件(7.19)(7.21)成立.,证明 算法开始时，最优性条件(7.19)(7.21)显然成立.只需证明：如i满足(7.19)(7.21),则改为i=i-d(i)后,仍满足(7.19)(7.21).,即,由引理7.2，对于N(x)中任意的(i,j)弧,一定有 0，且只需证明,根据最短路方程,d(j)-d(i)=,即 cij-(i-d(i)+(j-d(j)0,27,7.3.2原始-对偶算法 正确性,上面几个引理和讨论说明，前面介绍的算法是正确的.,即,讨论 这一引理说明，只要N(x)中从s到t存在有向路（增广路），则修改为后，将会有新的弧增加到N0(x)中，N0(x)中从s到t存在有向路（增广路），即可以对当前流进行增广。,证明 对于最短路上的弧(i,j)有 d(j)-d(i)=,即 cij-(i-d(i)+(j-d(j)=0,引理7.4 对于N(x)中一条弧(i,j)，如果它位于从起点 s 到某一节点的最短路上（以 为（p，q）弧的弧长），则,28,7.3.2原始-对偶算法-讨论,原始-对偶算法的特点 在运行中始终保持对偶变量为对偶问题的可行解,并始终保持互补松弛条件，但原始变量x在算法终止前通常不是原问题的可行解（即只是伪流，而不是流值为v的可行流）.,最小费用路算法是一种特殊的原始-对偶算法 虽然没有显示地引入对偶变量，但我们也可以与本节介绍的算法一样引入对偶变量，可以认为也是保持对偶可行和互补松弛条件的；特殊性在于要求增广流量时每次沿“一条”最小费用路增广.,下面引理说明：本节介绍的原始-对偶算法实际上也是沿最小费用路增广流值，只是可能每次沿“多条”最小费用路同时增广（即最小费用路最大流增广）.,29,7.3.2原始-对偶算法-讨论,引理7.5 对于N(x)中从任一节点p到另一节点q的一条有向路P，,讨论 对于N(x)中从s到t的一条有向路（增广路）P，一定有 即,直接应用 的定义就可以得到上述结果.,对于给定的对偶变量，由于N(x)中 0，所以满足=0的弧（即允许网络N0(x)中的弧）组成的增广路是N(x)中的最小费用路.,30,N(x)=N,例7.4 用原始-对偶算法计算如图7.5(a)网络中的最小费用流(图中弧上的前一个数字表示弧上的容量,后一个数字表示弧上的单位费用;节点上的数字表示节点的供需量).,7.3.2原始-对偶算法,例：,x=0,=0,计算得到 d=(0,0,0,1,2,1),修改得到=(0,0,0,-1,-2,-1),（uij，cij）,31,7.3.2原始-对偶算法,例,计算得到 d=(0,0,0,1,0,1),修改得到=(0,0,0,-2,-2,-2),最大流流值为2,增广,32,7.3.2原始-对偶算法,例,x的流值达到4得到最小费用流,最大流流值为2,增广,33,7.3.2原始-对偶算法 复杂性分析,算法每次循环迭代修改弧上的流值和节点上的势各一次.由于流值不可能超过nU,且任何节点上的势不可能低于-nC,因此总迭代次数不会超过minnU,nC.,记求解非负弧长网络的最短路算法的复杂度为S(n，m，C),最大流算法的复杂度为M(n，m，U)本算法复杂度为O(minnU,nCS(n，m，nC)+M(n，m，U)这一算法仍然不是多项式时间算法,与最小费用路算法相比,可能会以每次迭代调用一次最大流算法为代价,希望减少一些迭代次数.,34,布 置 作 业,目的,掌握最小费用流问题的基本概念和建模方法；掌握消圈算法与最小费用路算法及其复杂度；掌握原始-对偶算法的基本思想。,内容,网络优化第245-251页3；6；15；（第1讲）,思考,4；5；（不交）,35,网 络 优 化,Network Optimizationhttp:/,清华大学数学科学系 谢金星办公室：理科楼2206#（电话：62787812）Email:http:/,清华大学课号：70420133（研）,第7章 最小费用流问题(Minimum Cost Flow Problem)第2讲,36,(Out-Of-Kilter Algorithm),瑕疵算法(也翻译为“状态算法”)在迭代过程中则对这些条件更为放宽:只要求满足节点上的流量守恒条件,而不要求x为伪流(即可能不满足容量约束),并且也不一定保持互补松弛条件.,最小费用路算法和原始-对偶算法的特点:对偶变量为对偶问题的可行解,并始终保持互补松弛条件；但原始变量x在算法终止前通常不是原问题的可行解（即只是伪流，而不一定满足节点上的流量守恒条件,即不是流值为v的可行流）.,7.4瑕疵算法,37,(Out-Of-Kilter Algorithm),想一想,非循环流的情况是否都可以转化为循环流的情况?,算法的思想：通过一定步骤,使非最优的“程度”不断降低，最后达到最优.可以认为,瑕疵算法是原始-对偶算法的一种变形.,瑕疵算法的考察对象：循环流(Circulation)：流值为0的可行流（没有所谓源点和汇点,网络中的所有节点都是转运点）网络中容量下限 L 不一定为0；,7.4瑕疵算法,38,-Kilter条件,7.4瑕疵算法,L0,L=0,最小费用循环流模型,当 0 时，=0；(7.19)当 0 时，=；(7.20)当 时，=0.(7.21),当 0 时，=；(7.23)当 0 时，=；(7.24)当 时，=0.(7.25),互补松弛条件,Kilter条件（或译为瑕疵条件、状态条件等）,满足该条件的弧为无瑕的(In-Kilter),否则称为有瑕的(Out-Of-Kilter).,39,-Kilter图;Kilter数,7.4瑕疵算法,如果所有弧都是无瑕的,则得到了原问题的最优解.,定义7.4 对于每条弧(i,j),我们定义其Kilter数（瑕疵数、状态数）为将流量xij修正为满足Kilter条件所需要修改的量(假设保持节点上的势不变),记为K(xij)或kij,即,Kilter图（瑕疵图、状态图等）,当 0 时，=；(7.23)当 0 时，=；(7.24)当 时，=0.(7.25),40,-残量网络,7.4瑕疵算法,当xijlij时,则(i,j)N(x),uij(x)=lij-xij,cij(x)=cij,当 xijuij 时,则(j,i)N(x),uji(x)=xij-uij,cji(x)=-cij.,瑕疵算法仍然是在残量网络上对弧上的流量进行操作;由于流不一定满足容量约束,需定义这时残量网络的构造方法:把原网络中可能增加流量的弧(前向弧)、减少流量的弧(反向弧)纳入残量网络.具体方法如下:,瑕疵算法的思想：在算法过程中使弧上的Kilter数不断下降,最后降为0.,当 时:如果xijlij,则(j,i)N(x),uji(x)=xij-lij,cji(x)=-cij.,41,-残量网络,7.4瑕疵算法,可以直接定义弧(i,j)N(x)的Kilter数，分三种情况讨论:,可知:原网络中的任何一条瑕疵弧一定会在残量网络中得到反映(即瑕疵弧不以前向弧的形式出现,就以反向弧的形式出现).,当 时:如果(i,j)是瑕疵弧(0),则其Kilter数必然等于(i,j)的残留容量:kij=uij(x),当xijlij时:如果 0,则kij=uij(x)=lij-xij;如果 0,则kij=uij-xij.,当 xjiuji 时:如果 0(即 0),则kij=xji-lji;如果 0(即 0),则kij=uij(x)=xji-uji.,42,-步骤,7.4瑕疵算法,STEP 0.给出初始势和初始循环流(如=0,x=0).,Yakovleva(1959),Minty(1960),Fulkerson(1961)等提出;Aashtiani和Magnanti(1976)给出一种高效率的实现方法.,STEP 1.计算弧上的Kilter数.若网络中不存在瑕疵弧,则已经得到最优解,计算结束；否则在残量网络N(x)中，选择一条瑕疵弧（p,q）,继续下一步.,STEP 3.若（p,q）仍为瑕疵弧,则沿 P(p,q)确定的增广圈增广流量(增广的流值为该增广圈的容量),转STEP 1;否则直接转STEP 1.,STEP 2.在N(x)(q,p)中,以max0,为（i,j）弧的弧长，计算从节点q到所有节点 i 的最短路路长d(i)，并记从节点q到节点p的最短路为P.令i=i-d(i),继续STEP 3.,主要过程:一是对节点上势的修改;一是沿增广圈增广,43,-正确性,7.4瑕疵算法,证明,引理7.6 在瑕疵算法中,对节点上势的修改不会增加任何弧上的Kilter数.,=-+=-(i-d(i)+(j-d(j)=+(d(i)-d(j)-max0,当 0:-max0,=0(6.26),当 0:-max0,=(6.27),而对于弧（i,j）=(p,q)，由于d(q)=0，d(p)0,所以,=-+=-(i-d(i)+(j-d(j)=+(d(i)-d(j)(6.28),44,-正确性,7.4瑕疵算法,从Kilter数的定义知:当弧上流量保持不变时,只有的符号改变时,弧上的Kilter数才可能改变.下面分别对几种情况讨论:,节点上势的修改不会增加任何弧上的Kilter数.沿增广圈增广呢?,当 时:如果(i,j)关于是无瑕弧,则关于也是无瑕弧;如果(i,j)关于是瑕疵弧(0),则关于可能是无瑕弧,也可能是瑕疵弧(其Kilter数必然等于(i,j)的残留容量:kij=kij=uij(x),当 xjiuji 时:此时在节点上势的修改前后(i,j)一定都是瑕疵弧.与xijlij类似可证,当xijlij时:此时在节点上势的修改前后（i,j）一定都是瑕疵弧.如果 0,则 0,kij=kij=uij(x)=lij-xij不变.如果 0,则:若 0,则kij=kij=uij-xij不变;若 0,则kij=lij-xij uij-xij,45,-正确性,7.4瑕疵算法,引理7.7 在瑕疵算法中,沿增广圈P(p,q)增广流量不会增加任何弧上的Kilter数,且弧(p,q)的Kilter数严格减少,沿增广圈P(p,q)增广流量只可能改变圈上的弧及其反向弧的Kilter数.对于增广圈上容量不可行的弧(i,j),由残量网络的构造方法可知:流量增广后该弧的Kilter数一定严格下降,且不会在残量网络中加入新的弧(j,i).对于增广圈上容量可行的弧,流量增广不改变容量可行弧的容量可行性.,=-+=-(i-d(i)+(j-d(j)=+(d(i)-d(j)0,对于最短路P上的容量可行弧(i,j),由最短路方程有 d(j)=d(i)+max0,d(i)+,若弧(i,j)在原网络中对应的弧为(i,j),则流的增广不会增加其Kilter数，且当 0时实际上会严格减少其Kilter数.,若弧(i,j)在原网络中对应的弧为(j,i),则由=-0可知,流的增广也不会增加其Kilter数，且当 0时实际上会严格减少其Kilter数.,46,-正确性,7.4瑕疵算法,最后看看弧(p,q),也只需要分析它为容量可行的弧的情况.,证毕,注意到沿容量可行弧(i,j)的增广可能会在残量网络中加入新的弧(j,i).但由于=-0,所以在残量网络中新加入的弧(j,i)是满足Kilter条件的.,由算法STEP3,只有它为瑕疵弧时才进行增广,即 0,因此增广会严格减少其Kilter数.,此外,由于=-0,因此增广也不会使(q,p)成为残量网络中的瑕疵弧.,47,-复杂度分析,7.4瑕疵算法,每次循环迭代修改圈上的流值和节点上的势各一次,并使所有弧上的总Kilter数至少下降1个单位.,设初始流和势对应的总Kilter数为K,则总迭代次数不会超过K.记求解非负弧长网络的最短路算法的复杂度为S(n，m，C),则本算法复杂度为O(K S(n，m，nC).,特别地,当取初始流x=0时,由于每条弧上的Kilter数不超过U,算法复杂度可以写成为O(mU S(n，m，nC).由此可以看出,瑕疵算法仍然不是多项式时间算法.,48,-算法思想,对(7.1)引入Lagrange乘子(仍然称为i节点上的势,由于约束(7.1)为等式,所以没有符号限制),则得到如下的Lagrange松弛问题:,7.5 松弛算法（Relaxation Algorithm）,如果 0,则令xij=0(下界);如果 0,则令xij=uij(上界);如果=0,则xij可以是从0到uij的任意值.,如果x是可行流(满足(7.1),则是最小费用流.,互补松弛条件,49,-算法思想,一般情况下,x只是伪流而不是可行流(即满足容量约束而不满足流量守恒条件),此时得到的只是最小费用流问题的一个下界用z*表示最小费用流问题的最优值,则,7.5 松弛算法,定义7.5 对于伪流x,定义,当x是可行流时,所有节点都是平衡点.,松弛算法的思想：不断改进x和,在保持互补松弛条件的情况下,使伪流逐步改进为可行流，即LR()增加直到z*,并称e(i)为节点i的剩余(Surplus)或称不平衡数(Imbalance).e(i)0时,称e(i)为节点i的盈余(Excess);e(i)0时,称-e(i)为节点i的亏空(Deficit);e(i)=0时,称节点i为平衡点.,50,-算法思想,rij为N(x)中(i,j)弧上的残留容量uij(x),7.5 松弛算法,问题：如何使所有节点都变成平衡点？,首先选取一个盈余节点s,并以s为根构造N(x)中的一棵子树,使得树中的弧(i,j)都满足=0,且树中节点都是盈余点或平衡点.,设这棵子树的节点集合为S,在N(x)中S决定割S,记割中的前向弧为(S,),反向弧为(,S).,两种基本改进操作:在势不变的情况下,改进伪流x,使不可行程度降低(盈余、亏空严格减少).同时修改和x,使得LR()严格增加.,51,-算法思想,（case1）若e(S)r(,S):同时修改和x,使得LR()严格增加.,7.5 松弛算法,由（7.29）：LR()增加 e(S)-r(,S),算法首先沿(S,)中满足=0的弧增广流量使之饱和,即流量达到残留容量的上界,相应的弧不再属于残量网络;从(7.29)可知,这样的修改不会改变 c(x,)的值,但使得S中的节点上的总盈余减少为 e(S)-r(,S)（仍然为正数）.,由于算法保持互补松弛条件,对于N(x)中的任意弧一定有 0.增广后前向弧集(S,)中的弧满足 0,记其中的最小值为 0.,N(x)中的任意弧仍有 0：保持互补松弛条件,52,-算法思想,(case2)若e(S)r(,S):不变，修改x,使得e(S)严格减少.,7.5 松弛算法,如果e(j)0,则算法沿子树中从 s 到 j 的一条增广路增广流量.,从(7.29)可知,这样的修改不会改变 c(x,)的值,但使得S中的节点上的总盈余减少,由0e(S)r(,S),(S,)中至少有一条弧(i,j)满足=0,如果0 e(j),则由S的构造方法可知节点 j 可 以加入到S中,并重新开始下一轮迭代.,53,松弛算法 步骤（Bertsekas，1980s),STEP 0.给出初始势和初始流:=0,x=0.,STEP 1.如果网络中不含有任何赢余节点和亏空节点，则已经得到最优解,计算结束；否则在残量网络N(x)中，选择一个赢余节点s,令S=s，继续下一步.,STEP 2.如果e(S)r(,S),则转STEP 3;否则在(S,)中选取一条满足=0的弧（i,j）.若e(j)0，则转STEP 4;否则令pred(j)=i,S=Sj,继续重复STEP 2.,STEP 3.首先沿(S,)中所有满足=0的弧(i,j)增广流量使之饱和,然后将S中的每个节点上的势增加=min|(i,j)(S,),rij0.转STEP 1.,STEP 4.根据pred中记录的节点,确定子树中从s到j的一条增广路P.沿P增广流量.转STEP 1.,54,松弛算法 复杂度分析,当给定的数据都是整数时,算法每执行一次第二类操作,则LR()至少增加1个单位.算法开始时LR()=0,且算法执行过程中LR()不可能超过最小费用的上界mCU.因此STEP 3最多执行mCU次.,算法每执行一次第一类操作,则总赢余至少减少1个单位;而总赢余不可能超过上界(m+n)U,因此在两次连续第二类操作之间,执行第一类操作(STEP 4)的次数不超过(m+n)U=O(mU)次.,执行一次第一类操作(包括构造增广路的STEP2在内)的复杂度为O(mn),因此算法的总时间复杂度为O(mCUmUmn)=O(nm3CU2).,思考：如果不是整数数据，算法一定有限步停止吗？,从理论看,复杂度高；但计算测试表明松弛算法的实际计算效率非常高,是目前实际计算效率最高的两个算法之一(另一个算法是网络单纯形方法,我们将在下一节进行介绍).,55,-例,略,7.5 松弛算法,56,布 置 作 业（第2讲）,目的,掌握瑕疵算法及复杂性分析；掌握松弛算法及复杂性分析,内容,网络优化第245-251页7;17;20（第2讲）,思考,8；10；18（不交）,57,网 络 优 化,Network Optimizationhttp:/,清华大学数学科学系 谢金星办公室：理科楼2206#（电话：62787812）Email:http:/,清华大学课号：70420133（研）,第7章 最小费用流问题(Minimum Cost Flow Problem)第3讲,58,线性规划问题的单纯形算法的一般思路是：首先求得问题的一个基本可行解；如果它不是最优解，则选择一个进基变量(列)和一个出基变量（列），通过旋转（Pivot）变换改进到另一个基本可行解；如此反复迭代，直到检验数（或称相对费用，Reduced Cost）都大于等于0为止，获得最优解.算法的计算过程通常利用单纯形表进行.,对于网络优化问题,基的结构是非常特殊的,因此可以避免显式地列出单纯形表.,7.6 网络单纯形算法(Network Simplex Algorithm)7.6.1 算法的一般思路,不失一般性,以下总是假设流网络是连通的(否则该问题可以自然地分解为几个小问题来考虑).,59,引理7.8 关联矩阵B的列构成一组基的充要条件是它所对应的弧为支撑树(不考虑方向时).,流网络是连通的,所以r(B)=n-1.记B的(n-1)列构成的子矩阵为B1.,6.5 最高标号预流推进算法,-基的特殊性,首先考虑容量无限的最小费用流问题,7.6.1 算法的一般思路,必要性.若B1为一组基,则r(B1)=n-1.B1所对应的n-1条弧如果不连通,则至少含有一个圈,因此r(B1)n-1,矛盾.因此B1所对应的n-1条弧一定是连通的(不考虑方向),即这些弧构成一棵支撑树.,充分性.B1所对应的n-1条弧构成一棵支撑树,则r(B1)=n-1.因此是一组基.,60,把B1所对应的弧集合(支撑树)用T表示，则：所有非树弧（非基弧）对应于非基变量,其上的流量为0;只有T中的弧（树弧，或称基弧）对应于基变量.给定支撑树后,如何确定树弧上的流量并使之满足可行条件？,7.6.1 算法的一般思路 流的计算,流x不一定是可行的,即某些树弧上的流量可能为负数.我们把使得相应的流x为可行流的基称为可行基,支撑树称为可行树.,算法只对可行树操作！,61,-势的计算,容量无限，互补松弛条件：,7.6.1 算法的一般思路,如何获得(即节点上的势)？,单纯形算法中,检验数的值为(C-B),这里为对偶变量.对于最小费用流问题,(i,j)弧对应的检验数的值为,当=0 时，=0；(7.37)当 0 时，=0；(7.38),设给定了一个基本可行解x,基矩阵所对应的可行树为T.由于只有树弧上的流量可以为正数,所以只有树弧才可能满足(7.38).支撑树上的弧共有(n-1)条,而对偶变量(节点上的势)共有n个.在相差一个常数的意义下,由T中的弧满足=0可以唯一地确定对偶变量.,可以任意选定一个节点（这一节点通常称为“根”（Root）,令它的势为0;然后利用(7.38)计算与它相邻的其它节点上的势,如此重复就可以方便地获得所有节点上的势.,如果此时使得(7.37)也成立,则x就是原问题的最优解.,62,7.6.1 算法的一般思路 旋转变换,W为一个负费用圈,所以沿W增广流量将会使得总费用下降.为了在W中找出一条弧出基,我们应当令增广的流量等于W-所有弧上当前流量中的最小值,而取到该最小值的弧出基 如果W-=,则原问题是无界的,即最小费用可以趋于负无穷,为了找出一条弧出基,我们可以看出T(p,q)一定含有唯一的圈W,我们把弧(p,q)的方向定义为W的方向.W的费用为,若x不最优,则存在一条非树弧(p,q)使得(7.37)不成立,即 0，弧(p,q)可以进入基.,63,STEP 0.获得一个初始的可行树T及对应的基本可行解x,-步骤,STEP 1.计算对偶变量.,7.6.1 算法的一般思路,STEP 2.判断是否最优解,若是,则停止;否则选定一个进基变量(即选进基弧(p,q).,STEP 3.选定一个出基变量(即选出基弧),如果找不到这样的弧,则原问题是无界的,停止;否则进行下一步.,STEP 4.设W为T(p,q)所含的圈.沿W的正向增广流量,即修改x 及对应的可行树T,回到STEP 1.,问题,获得一个初始的可行树T及对应的基本可行解x？,退化与循环？90%以上退化,容量有界情形？,复杂度？一般非为多项式算法，但可以设计多项式算法,64,略,7.6.1 算法的一般思路 例,65,计算测试表明，网络单纯形法中往往90%以上的旋转是退化的.能否要求每次所操作的可行树“都不相同”？,7.6.2 处理退化的方法,定义7.6 假定计算节点上的势时所选定的根节点是固定的.对于可行树T中的一条树弧(i,j),如果T中从根到j的路通过节点i，则(i,j)称为远离根节点的弧（Downward Pointing Arc）.如果T中的所有流量为0的弧都是远离根节点的弧，则称可行树T为强可行树（Strongly Feasible Spanning Tree）.,例7.8 假设弧上的数字表示当前可行流.节点1为根节点.T1=(1,3),(3,2),(3,4)为强可行树,T2=(1,3),(2,3),(3,4)不是强可行树,因为T2中(2,3)不是远离根节点的弧.,66,引理7.9 如果网络单纯形算法中生成的所有可行树都是强可行树，则这些树互不相同.,7.6.2 处理退化的方法,如果T为生成树，r为根节点，记,证明:如果网络单纯形算法中的旋转变换不是退化的，则相应的可行树对应的可行流费用互不相同，因此这些树也一定互不相同.所以，我们只需要考虑旋转变换退化的情况.,考虑算法过程中连续生成的两棵强可行树T，=T(p,q)(k,l),即(p,q)为进基弧,(k,l)为出基弧,且从T到 的旋转是退化的.,67,7.6.2 处理退化的方法,记 对应的势为,根据势的确定方法,可以得到(留作练习):,旋转变换前后,(p,q)上的流量都是0,由于 是强可行树,所以(p,q)弧一定是远离根节点r的弧.(p,q)弧将 分解为两棵子树 和,并且p,q分别属于 和,则r.,因此,T和 是两棵不同的强可行树.,所以=+|（0）,68,首先，初始的基本可行解是对应于一棵强可行树；其次，我们要求旋转变换只生成强可行树.,7.6.2 处理退化的方法,设旋转之前，强可行树为T，(p,q)为进基弧,T(p,q)包含的圈为W.假设 W-，令=minxij|(i,j)W-,=(i,j)|xij=,则 为所有可能的出基弧的集合.,记 是T中从根节点r到节点p的路与圈W的第一个交点,令出基弧(k,l)为从 出发沿圈W的正向前进时第一次所遇到的 中的弧,69,7.6.2 处理退化的方法,下面