《运筹学基础图论方法课件》由会员分享，可在线阅读，更多相关《运筹学基础图论方法课件（27页珍藏版）》请在金锄头文库上搜索。
1、6.4 最大流量问题当以物体、能量或信息等作为流量流过网络时，怎样使流过网络的流量最大，或者使流过网络的流量费用或时间最小。通常把设计为样的流量模型问题，叫做网络的流量问题。 本节主要讨论最大流量问题。即在一定条件下，要求流过流过网络的流量为最大网络的流量为最大。12346 6565 53 34 47 75 57 73 32 2在有一个起点起点和一个终点终点的网络中，最大流量问题是企图找出，在一定时期内，能在起点进入，并通过这个网络，在终点输出的最大流量。(一一) 网路的最大流的相关概念网路的最大流的相关概念st53424(0)3(0)2(0)1(0)1(0)5(0)3(0)2(0)5(0)定
2、义网路上支路的容量容量容量容量为其最大通过能力,记为 cij ,支路上的实际流量流量流量流量记为 fij图中规定一个发点s，一个收点tcij( fij )容量限制条件：0fij cij，当支路上 fij = cij，称为饱和弧饱和弧平衡条件：viA(vi)B(vi)满足上述条件的网路流称为可行流，总存在最大可行流（二）截集与截集容量st42319(4)6(1)9(9)2(0)5(4)7(5)8(8)10(8)5(5)截集截集截集截集：把网路中的发点和收点分开，并使st的流中断的正向弧的集合，也叫做割。n 福特福特福特福特- -富克森定理富克森定理富克森定理富克森定理：网路的最大流等于最小截集容
3、量网路的最大流等于最小截集容量n 一般包含 s 点的成分中的节点集合用V表示，包含 t 点的成分中的节点集合用 表示n 截集容量截集容量截集容量截集容量是指截集中弧的容量之和网路的最大流网路的最大流就是就是最小截集最小截集容量为容量为14截集1=（s,1），（s,2）（三）确定网路最大流的标号法n 从任一个初始可行流出发，如 0 流。n 若在当前可行流下再也找不到增广链，则已得到最大流若在当前可行流下再也找不到增广链，则已得到最大流!n 增广链增广链是从发点到收点的一条链，该链上所有指向为st的前向弧前向弧前向弧前向弧，存在f fc c；所有指向为ts的后向弧后向弧后向弧后向弧，存在f f0
4、0，这样的链叫增广链。n 基本算法：找一条从 s 到 t 点的增广链。st54323(0)5(3)1(1)5(1)1(1)q qs2=4q q5t=2q q45=3q q43=1q q32=1增广量增广量 q q = min q qij= min (4,1,1,3,2)= 1st54323(1)5(4)1(0)5(2)1(0)n 增广过程：前向弧前向弧前向弧前向弧 f f ij ij= =f fij ij+ + , 后向弧后向弧后向弧后向弧 f f ij ij= =f fij ij ,增广后仍是可行流 欲求增广量欲求增广量找最小截集的标号法步骤第一步：标号过程，找一条增广链第一步：标号过程，找
5、一条增广链1、给源点 s 标号s+,q(s)=，表示从 s 点有无限流出潜力2、找出与已标号节点已标号节点已标号节点已标号节点 i i 相邻相邻相邻相邻的所有未标号节点节点 j，若(1) (i, j)是前向弧且饱和饱和饱和饱和，则节点 j 不标号（即此路不通）不标号（即此路不通）不标号（即此路不通）不标号（即此路不通）；(2) (i, j)是前向弧且未饱和，则节点 j 标号为i+,(j)，表示从节点 i 正向流出，可增广 (j)=min(i), c cij ij f fij ij ；(3) (j, i)是后向弧，若 f fji ji=0=0，则节点 j 不标号（即此路不通）不标号（即此路不通）
6、不标号（即此路不通）不标号（即此路不通） ；(4) (j, i)是后向弧，若 fji0，则节点 j 标号为i, (j)，表示从节点 j 流向 i，可增广 (j)=min(i), f fji ji ；最大流最小截集的标号法步骤3、重复步骤 2，可能出现两种情况：(1)节点 t 获得标号，找到一条增广链，由节点 t 标号回溯可找出该增广链；到第二步(2) 节点 t 尚未标号，但无法继续标记，说明网路中已不存在增广链，当前流 v(f) 就是最大流；所有获标号的节点在 V 中，未获标号节点在 中，V 与 间的弧即为最小截集，最小截集容量即为该网络最大流量最大流量；算法结束最大流最小截的标号法步骤第二步
7、：增广过程第二步：增广过程1、对增广链中的前向弧，令 f=f +q (t)，q(t) 为节点 t 的标记值2、对增广链中的后向弧，令 f=fq (t)3、非增广链上的所有支路流量保持不变第三步：抹除图上所有标号，回到第一步第三步：抹除图上所有标号，回到第一步 以上算法是按广探法描述的，但在实际图上作业时，按深探法进行更快捷一次只找一条增广链，增广一次换一张图一次只找一条增广链，增广一次换一张图最后一次用广探法，以便找出最小截集最后一次用广探法，以便找出最小截集最大流最小截集的标号法举例st42319(4)6(1)9(9)2(0)5(4)7(5)8(8)10(8)5(5)(s+, )(s+,2)
8、(2-,2)(1+,2)(3-,1)(4+,1)第一条链：第一条链：(s+, )(s+,2) (2-,2) (1+,2) (3-,1) (4+,1) q = 1前向弧前向弧前向弧前向弧 f f ij ij=f=fij ij+ + 后向弧后向弧后向弧后向弧 f f ij ij=f=fij ij st42319(4)6(1)9(9)2(0)5(4)7(5)8(8)10(8)5(5)st42319(5)6(0)9(9)2(0)5(3)7(6)8(8)10(9)5(5)(s+, )(s+, 1)(2-, 1)(1+, 1)第二条链：第二条链：(s+, )(s+,1) (2-,1) (1+,1)截止截止
9、最大流量为最大流量为5+914最小截集最小截集又例：利用标号法（确定最小截集）求最大流量又例：利用标号法（确定最小截集）求最大流量第二条链：第二条链：(s+, )(s+,1) 截止截止(s+, )(2+,1)第一条链：第一条链：(s+, )(s+,2) (2+,1) (5+,1) (3-,1) (1+,1) (4+,1) 最小截集最小截集最大流量为最大流量为5+3+513(s+,2)st52413(2)2(0)5(4)3(3)3(3)6(4)5(5)6(6)8(6)32(0)4(4)2(2)(5-,1)(3-,1)(1+,1)(4+,1)增广量q = 1(s+, )(s+,1)前向弧前向弧前向
10、弧前向弧 f f ij ij=f=fij ij+ + 后向弧后向弧后向弧后向弧 f f ij ij=f=fij ij st52413(2)2(0)5(4)3(3)3(3)6(4)5(5)6(6)8(6)32(0)4(4)2(2)st52413(3)2(0)5(5)3(2)3(3)6(5)5(5)6(6)8(7)32(0)4(4)2(1)（四）应用举例例某河流中有几个岛屿，从两岸至各岛屿及岛屿之间的桥梁如图。在一次军事行动中，问至少炸断几座桥，才能完全切断两岸的交通联系？ADBCDEFAFDECB2(0)1(0)3(0)1(0)2(0)1(0)2(0)1(0)1(0)AFDECB2(0)1(0)
11、3(0)1(0)2(0)1(0)2(0)1(0)1(0)(A+, )(A+,2)(B+,2)(D+,1)AFDECB2(1)1(1)3(0)1(0)2(0)1(0)2(1)1(0)1(0)(A+, )(A+,2)(C+,1)(D+,1)(E+,1)AFDECB2(1)1(1)3(1)1(0)2(1)1(0)2(1)1(1)1(1)(A+, )(A+,1)(E+,1)AFDECB2(1)1(1)3(2)1(0)2(1)1(1)2(1)1(1)1(1)(A+, )(A+,1)(B+,1)(D-,1)至少炸断桥AE，DE，DF，才能完全切断两岸的交通联系q = 1q = 1q = 1例匹配问题例匹配
12、问题 有三根相同的轴（编号为1,2,3），又有三个的齿轮（编号为4,5,6），由于精度不高，不能任意匹配，配合情况如图所示，部如何选择装配方案，以得到轴和齿轮的最大数。1234561(0)123456St1(0)1(0)1(0)1(0)1(0)1(0)1(0)1(0)1(0)1(0)1(0)(s+, )(s+,1)(1+,1)(4+,1)1(1)123456St1(0)1(0)1(1)1(0)1(0)1(0)1(0)1(0)1(1)1(0)1(0)(s+, )(s+,1)(2+,1)(5+,1)(s+, )(s+,1)(3+,1)1(1)123456St1(1)1(0)1(1)1(0)1(1)
13、1(0)1(0)1(0)1(1)1(1)1(0)(5+,1)(2+,1)(6+,1)1(1)123456St1(1)1(1)1(1)1(0)1(0)1(1)1(1)1(0)1(1)1(1)1(1)1 14 4，2 26 6，3 35 5q q = 1q q = 1q q = 1（五）多端网路问题（五）多端网路问题18764352(15, 0)(10, 0)(20,0)(5,0)(5,0)(5,0)(5,0)(5,0)(10,0)(10, 0)(10,0)(10,0)发点发点120发点发点220收点收点115收点收点220(5,0)事实上事实上18764352(15,10)(10,10)(20,
14、5)(5,5)(5,5)(5,5)(5,5)(5,0)(10,5)(10,10)(10,5)(10,0)虚发点虚发点虚收点虚收点st(20,15)(20,15)(20,15)(15,15)(5,0)S13254截止截止最大流量为最大流量为15+5+5+5303简化标注：求最大流量简化标注：求最大流量1653429( )6( )9( )2( )5( )7( )8( )10( )5( )简化标注：求最大流量简化标注：求最大流量1653429( )6( )9( )2( )5( )7()8( )10( )5( )1356=71246=512356=21243截止截止截止，最大流量截止，最大流量9+51
15、4（或者最大流量（或者最大流量7+5+2147775557299（六）利用（六）利用EXCELEXCEL求求网络最大流量网络最大流量第一步：建立各结点间的流量矩阵第一步：建立各结点间的流量矩阵利用利用EXCELEXCEL求求网络最大流量网络最大流量第二步：定义最大流量方案第二步：定义最大流量方案 第三步：利用规划求解第三步：利用规划求解30(30)80(80)60(60)10(10)100(70)70(70)20(20)10(10)40(40)6.5 最小费用流量问题实际物资调配问题，既要考虑流量通过各条弧时的容量限制，也需要考虑调动费用的节省，这就是最小费用流最小费用流要研究的问题。 若在最
16、小费用流问题中，将单位流量通过弧的费用费用当成是距离距离，则求从发点至收点调运一单位流量的最小费用，也就等价于求该两点之间的最短距离。 因此，最小费用流是最短距离和最大流量的综合考量。最小费用流量图例设网络有n个点，cij为该弧的容量，bij为在弧(i,j)上通过单位流量时的费用，fij为弧(i,j)上的流量。s32t1(7,6) 0 (5,2) 0 (6,1) 0 (2,3) 0 (3,2) 0 (8,4) 0 (4,1) 0(cij , bij ) fij 试求将发点物资调运到收点（或从发点按最大流量调运到收点），使总调运费用最小的问题。求最小费用流的步骤第一步：从零流第一步：从零流f0开
17、始，找一条使开始，找一条使总费用最小总费用最小的的增广链增广链n 该链上的总费用为该链上的总费用为：qW(i,j)； 其中，q是该链上增加的流量， W(i,j)是该链上增广一单位流量，弧(i,j) “增加增加”的费用。第二步：重复第一步，一直到再也找不到增广链为止第二步：重复第一步，一直到再也找不到增广链为止注：用标号法的简单形式注：用标号法的简单形式n 增广链增广链：是从发点到收点的一条链，该链上所有指向为st的前向弧前向弧前向弧前向弧，存在f fc c；所有指向为ts的后向弧后向弧后向弧后向弧，存在f f0 0，这样的链叫增广链。n n 费用：费用：弧(i,j)为前向弧时， W(i,j)=
18、 bij； 弧(i,j)为反向弧时， W(i,j)= -bij例例s32t1(4,9) 0 (8,4) 0 (10,9) 0 (3,2) 0 (2,5) 0 (8,7) 0 (5,8) 0(cij , bij ) fij=3=2=5截止截止最大流量最大流量8+412W =14s32t1(4,9) 0 (8,4) 3 (10,9) 0 (3,2) 3 (2,5) 0 (8,7) 0 (5,8) 3W =17s32t1(4,9) 2 (8,4) 3 (10,9) 0 (3,2) 3 (2,5) 0 (8,7) 0 (5,8) 5W =20s32t1(4,9) 2(8,4) 8 (10,9) 5(3
19、,2) 3 (2,5) 0 (8,7) 5 (5,8) 5=2W =21最小流量费用最小流量费用(q q *W )=218s32t1(4,9) 4(8,4) 8 (10,9) 5(3,2) 3 (2,5) 2 (8,7) 7 (5,8) 5s13t824538s1t8924s23t7948105s21t759322s23179-2153又例又例(cij , bij ) fij=3=1=1截止截止最大流量最大流量4+59W =6W =6W =7=3W =8最小流量费用最小流量费用 (q *W )= 63s32t1(7,6) 0 (5,2) 0 (6,1) 0 (2,3) 0 (3,2) 0 (8
20、,4) 0 (4,1) 0s32t1(7,6) 0 (5,2) 3 (6,1) 3 (2,3) 0 (3,2) 3(8,4) 0 (4,1) 3s32t1(7,6) 0 (5,2) 4 (6,1) 3 (2,3) 1 (3,2) 3(8,4) 0 (4,1) 4s32t1(7,6) 0 (5,2) 5 (6,1) 4 (2,3) 1 (3,2) 3(8,4) 1 (4,1) 4s32t1(7,6) 3 (5,2) 5 (6,1) 4 (2,3) 1 (3,2) 0(8,4) 4(4,1) 4=1W =8s32t1(7,6) 4 (5,2) 5 (6,1) 5 (2,3) 0 (3,2) 0(8,4) 5(4,1) 4s13t112224365s13t132122s23t412831s21t4-26737s21t4-36314214s234131（六）利用（六）利用EXCELEXCEL求求网络最大流量网络最大流量第一步：建立各结点间的流量矩阵和单位费用矩阵第一步：建立各结点间的流量矩阵和单位费用矩阵利用利用EXCELEXCEL求起点到终点的最短路径求起点到终点的最短路径第二步：定义最大流量方案第二步：定义最大流量方案 第三步：利用规划求解第三步：利用规划求解
