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