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

《运筹学-网络流问题(名校讲义).ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第二十八、二十九讲网络流问题§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中

2、。§1网络流（2）问题是：求出达到最大运输总量的最优运输方案。图5-31x1v3x2y1v1y213015015070401201005070(+240)(+120)(-200)(-180)v2§1网络流（3）②有关术语运输网络给定有向图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为定义域且取值为非负的函数，

3、又记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’之中

4、间顶点集。②对x’X，用有向边（x，x’）连接顶点x与x’，边之容量命为+或某一具体值（根据实际情况确定）。③同理，对y’Y，用有向边（y，y’）连接顶点y与y’，边的容量亦可命为+或某一具体值。若f是原图G中一个流，则可定义与此相应的新图G’中一个流f’：§1网络流（6）可见，f’便为G’定义一个相应流。反之，若定义G’上一个流f’，则f’落在图G中的部分必是图G上一个相应流。可见，多源多汇网络与单源单汇网络之间转换完全是等效变换。x1图5-32v3x2y1v1y21001301505020301005070v2[例5-11]将图5-31所示图变换成单源单汇网络G’，

5、且将图5-32所示的图G给定流f转换成图G’中的相应流f’。§1网络流（7）[解]1)首先给出G’的单源x和单汇y，并按规则构成新图G’，G’中每边容量C’(e)定义为：2)计算G’与图5-32所示的G中f流的相应流f’，则知：§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以后，一般以分析单源单

6、汇网络为主。§2最大流与最小割（1）1．割的定义及特点设S为V的一个子集，且源为起点在S和终点在中的全体有向边之集合，即，则称：①边集合为网络G的一个割。②为割（集）K的容量，记为C(K)。§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，v

7、4，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的割}②有关定理