运筹学-网络流问题(名校讲义)

第二十八、二十九讲网络流问题§1网络流§2最大流与最小割§3最大流算法§4最小费用流§1网络流（1）1．网络流的概念①问题的提出简而言之，流就是将目标或对象由一个地点送至另一个地点。希望在已有的物理网络图中，从一个地点输送至另一个地点的运输最大，或者要求从一个地点经运输网络系统将一定数量物品送至另一个地点所花费用达到最小。[例5-10]运输公司接受任务，需将产地x1及x2两处所存物资经由v1，v2，v3等三个中转站运往用户y1及y2两处。公司所获利润与运输总量成正比。已知x1，x2有物资分别为120吨和240吨，y1及y2各需180吨和200吨，全部交通网络布置及交通干线容量示于图5-31中。§1网络流（2）问题是：求出达到最大运输总量的最优运输方案。图5-31x1v3x2y1v1y213015015070401201005070(+240)(+120)(-200)(-180)v2§1网络流（3）②有关术语i)运输网络给定有向图G＝(V，E)，对每条边都给出相应的非负数c(e)，且已取定V的两个非空子集X（发点集）和Y（收点集），XY=，则称图G=（V，E，C，X，Y）为一个运输网络。同时，称c(e)为边e之容量，X中的顶点x为G之源，Y中顶点y为G之汇。而顶点集合I=V－(XY)称为G之中间顶点。ii)网络流设f(e)为一个以E为定义域且取值为非负的函数，又记f+(v)和f－(v)分别为以v点为始点和以v点为终点的所有有向边的相应函数值之和，若对网络G中，f(e)满足下述条件：0f(e)c(e)，eE（约束条件）§1网络流（4）f+(v)=f－(v)，vI（守恒条件）则称f为G的一个网络流或流。f(e)称为f在边e上的流量。任一网络G，至少存在一个流，若每条边的f(e)=0，则称为零流。2．单源和单汇运输网络实际问题往往存在多源多汇网络（例如图5-31便是双源双汇网络）。为了计算的规格化，可将多源多汇网络G化成单源单汇网络G’。§1网络流（5）①在原图G中增加两个新的顶点x和y，令为新图G’中之单源和单汇，则G中所有顶点V成为G’之中间顶点集。②对x’X，用有向边（x，x’）连接顶点x与x’，边之容量命为+或某一具体值（根据实际情况确定）。③同理，对y’Y，用有向边（y，y’）连接顶点y与y’，边的容量亦可命为+或某一具体值。若f是原图G中一个流，则可定义与此相应的新图G’中一个流f’：)()()()()()()()()(yyeYyyfyfxxeXxxfxfGEeefef，且，当，且，当当§1网络流（6）可见，f’便为G’定义一个相应流。反之，若定义G’上一个流f’，则f’落在图G中的部分必是图G上一个相应流。可见，多源多汇网络与单源单汇网络之间转换完全是等效变换。x1图5-32v3x2y1v1y21001301505020301005070v2[例5-11]将图5-31所示图变换成单源单汇网络G’，且将图5-32所示的图G给定流f转换成图G’中的相应流f’。§1网络流（7）[解]1)首先给出G’的单源x和单汇y，并按规则构成新图G’，G’中每边容量C’(e)定义为：2)计算G’与图5-32所示的G中f流的相应流f’，则知：200)(180)(240)(120)()()(22112211的收量＝，，的收量＝，的发量＝，，的发量＝，yyyCyyyCxxxCxxxCeCeC2003015020)()()()(15010050)()()(230130100)()()(1205070)()()()()(2322212131113222221111yfyfyfyyfyfyfyyfxfxfxxfxfxfxxfefef，，，，，，，，，，，，，§1网络流（8）具体结果示如图5-33中（图中，箭头旁边有两个数字，前面表示该边容量c’(e)，后边表示实际给定流量f’）。y200,200v2x120,120x1图5-33v3x2y1v1y2130,10070,5070,70150,15040,2050,50100,100180,150240,230150,130120,30以后，一般以分析单源单汇网络为主。§2最大流与最小割（1）1．割的定义及特点设S为V的一个子集，且源为起点在S和终点在中的全体有向边之集合，即，则称：①边集合为网络G的一个割。②为割（集）K的容量，记为C(K)。），＝（。令，汇－＝，SSKSySVSSxSSSuuK，，|)(SSK，Keec)(§2最大流与最小割（2）[5-12]给定图G为图5-34所示，求与给定的Sj（j=1，2，3）相对应的割集容量C(Kj)。[解]1)取S1={x，v1}，则：K1={(v1，v3)，(v1，v2)，(x，v2)}和C(K1)=10+6+9=252）取S2={x，v1，v2，v4}，则：K2={(v1，v3)，(v4，v5)，(v2，v5)}和C(K2)=10+6+13=293）取S3={x，v1，v2，v4，v5}，则：K3={(v1，v3)，(v5，y)}和C(K3)=10+10=20图5-34v3xv191361513105610v2yv5v4§2最大流与最小割（3）2．最大流与最小割的关系定理。①定义：记f流的流值为V(f)，则定义i)满足下式的f*称为G的最大流V(f*)=max{V(f)f为G的流}ii)满足下式的K*称为G的最小割C(K*)=min{C(K)K为G的割}②有关定理定理1设f和分别为图G中任一流和任一割，则必存在：V(f)=f+(s)－f－(s)，其中，即图G中任一截面之净流值V(f)，必是任何一个横截面的输出量减去输入量（亦即代数和）。)(SSK，)()()()()()(SSeSSeefsfefsf，，，§2最大流与最小割（4）有关其它术语：若f为图G上的一个流，对eE，则定义：若f(e)=c(e)，称边e为f的饱和边；若f(e)c(e)，称边e为f的不饱和边；若f(e)0，称边e为f的正边；若f(e)=0，称边e为f的零边。§2最大流与最小割（5）定理2设f和K分别为图G中任一流和任一割，则必存在：i)V(f)C(K)ii)V(f)=C(K)的充要条件为：定理3设f和K分别是图G的一个流和一个割，且满足等式V(f)=C(K)。则：f和K必分别是图G的最大流和最小割。为零边，任意边为饱和边，任意边)()(SSeSSe§2最大流与最小割（6）3．增广链及应用定理①有关术语和定义i)若G中有u到v的有向边(u，v)，则称(u，v)为Q的前向边。ii)若G中有v到u的有向边(v，u)，则称(v，u)为Q的后向边。iii)若f为G上的流，对eE(Q)，则定义：iv)当l(Q)=0，称Q为f的饱和链。当l(Q)0，称Q为f的不饱和链。)(min)()()()()(elQlQeefQeefecelQe的后向边是当的前向边是当§2最大流与最小割（7）[5-13]图5-35给出具有流f的图G，试分析上述有关术语和定义。[解]1)首先取Q1=xv2v1v3v4，则知：·前向边为(x，v2)，(v1，v3)和(v3，v4)，其l值为l(x，v2)=2，l(v1，v3)=0，l(v3，v4)=2。·后向边为(v1，v2)，其l(v1，v2)=0。则知l(Q1)=0，因此，Q1为f的饱和链。图5-35v3xv19,713,76,315,1013,710,105,36,010,10v2yv5v4§2最大流与最小割（8）2)取Q2=xv2v5v4v3y，则知：·前向边为(x，v2)，(v2，v5)和(v3，y)，其l值为l(x，v2)=2，l(v2，v5)=6，l(v3，y)=6。·后向边为(v4，v5)和(v3，v4)，其l值为l(v4，v5)=3，l(v3，v4)=3。则知l(Q2)=20，因此，Q2为f的不饱和链。从上面分析中看出：若Q为f的饱和链，则链中只少有一条前向边为f饱和边或至少有一条后向边为f的零边；相反，若Q为f的不饱和链，则链中不存在饱和前边和零后边。§2最大流与最小割（9）v)一条从源x至汇y的不饱和链，称为f的增流链。vi)若网络G中存在一条f增流链，则可得到G上的一个新流，其各边流量值为：此时，新流值则称为f基于Q链的修改流，对于而言，Q是的饱和链。fˆ其它边的后向边是当的正向边是当)()()()()()(ˆefQeQlefQeQlefef)()()ˆ(QlfVfVfˆfˆfˆ§2最大流与最小割（10）例如图5-35中，Q=xv2v5v4v3y是一条增流链，其l(Q)=2，将其修改，使f变为后，示于图5-36中。②有关定理定理4流f为G的最大流的充要条件为G中不存在f增流链。fˆ图5-36v3xv19,913,96,115,1013,910,105,16,010,10v2yv5v4§3最大流算法（1）1．算法思路判别图G中当前给定的f是否存在的增流链，若没有，则该流f即为最大流；否则，求出修改流，然后把看成f，再进行判断和计算，直到找到最大流为止。2．算法步骤（标号算法）)()()ˆ(QlfVfVfˆfˆ§3最大流算法（2）[例5-14]图5-38所示图G中，已给出现有流（边旁边的前后两个数字分别表示容量和实际流量），试用标号法求出最大流。[解]1)根据图5-38所给出的初始流，为图G所有点标号，标号过程示于表5-11中。图5-38v3xv19,94,33,114,1416,155,56,313,1212,10v2yv5v4v66,615,919,1022,227,5§3最大流算法（3）检查点xv2v2v3v5v5v4新生点xv2v3v5v4v1v6y新生点标号+∞+6－6+2+1+2+1+1表5-11从表5-11中得知，Qy=xv2v3v4y，l(Qy)=l(y)=1，故可得基于Qy的修改流并示于图5-39中。2)针对图5-39，在顶点继续标号，结果示于表5-12。（略）图5-39v3xv19,94,43,114,1416,155,56,313,1212,10v2yv5v4v66,515,1019,1122,227,5§4最小费用流（1）1．应用背景及有关术语①问题的提出（应用背景）如何求出一个流，既满足运输量又使费用最小？这就是最小费用流问题。②有关术语具有点集合V、边集合E、边容量C、源点x和汇点y的运输网络G=(V，E，C，x，y)中，又增一项集合W。§4最小费用流（2）i)若fA为G的一个流，其流值V(f)=A，则定义W(fA)=为流fA的费用。它表示在图G中，从x至y沿着流fA运送A个单位所需总费用。ii)一般流值为A的流不止一个，则定义符合下述条件的流值A的流为图G中流值为A的最小费用流：W()=min{W(f)f为G的网络流，且流值V(f)=A}若A为G中最大流值时，则称为G的最小费用最大流。AfAf§4最小费用流（3）2．流f的伴随网络定义1：设f为G=(V，E，C，W，x，y)的一个网络流，则按下述办法构造的新网络称为f的伴随网络Gf：①顶点V(Gf)=V(G)②边E(Gf)=E+(Gf)E－(Gf)，其中i)E+(Gf)={(u，v)(u，v)E(G)，f(u，v)c(u，v)}，正规边ii)E－(Gf)={(v，u)(u，v)E(G)，f(u，v)0}，非正规边§4最小费用流（4）③Gf中的边容量c’(e)及费用w’(e)规定为i)若e=(u，v)E+(Gf)，取c’(u，v)=c(u，v)－f(u，v)，w’(u，v)=w(u，v)ii)若e=(v，u)E－(Gf)，取c’(v，