最大流问题2课件

最大流问题主讲:蔡天鸣网络最大流的有关概念A2A4A3S1513107512A1T64弧弧的容量(9)弧的流量(4)(11)(11)(5)(0)(9)(6)如果图中的弧的流量都小于等于弧的容量，并且对于中间点流出量等于流入量，那么起点的流出量或者终点的流入量称为可行流量。可行流量v(f)=6+9=15求可行流量的最大值就是最大流问题最大流问题的实例A2A4A3S1513107512A1T64高速公路的S点到T点之间的网络结构如下图。车流从S点分流后在T点汇合。分流后的车辆可以由A3到A2或者A4到A1之间的单向立交岔道变更主干道。各个路段的最大通过能力分别标在了图上（标准换算单位/h）。现在请求出高速公路S到T之间的最大通过能力是多少？公路运能饱和时，各路段状态如何？最大流的标号算法--Ford-Fulkerson算法链：图中存在点和边的交替序列若其中边ei(i=1,...,k)互不相同，且任意vi-1和vi均相邻，称μ为链。

增广链：如果在网络的发点和收点之间能找出一条链，在这条链上所有指向为s->t的边，存在f<c；所有指向为t->s的边的边，存在f>0，这样的链称增广链。A2A4A3S15(11)13(11)10(9)7(6)5(4)12(9)A1T6(5)4(0)当有增广链存在时，找出 再令 则f′仍是一个可行流，比原来的可行流f流量增大了一个θ值。因此只有网络图中找不到增广链时，s->t的流才不可能进一步增大。

A2A4A3S15(11)13(11)10(9)7(6)5(4)12(9)A1T6(5)4(0)7(7)5(5)6(4)Ford-Fulkerson算法的步骤第一步：给发点s标号(0,ε(s))。第一个数字是使得这个点得到标号的前一个点的代号。第二个数字是从上一个标号点到这个标号点的流量最大允许调整量。A2A4A3S15(11)13(11)10(9)7(6)5(4)12(9)A1T6(5)4(0)(0,∞)Ford-Fulkerson算法的步骤第二步：列出与标号点相邻的所有未标号点： (1)考虑从标号点i出发的边(i,j)，如果有fij=cij，不给点j标号；若有fij<cij，则对点j标号，记为(i,ε(j))。括弧中的i表示点j的标号是从点i延伸过来的，ε(j)=min{ε(i),(cij-fij)}； (2)考虑所有指向标号点i的边(h,i)，如果有fhi=0，对h点不标号；若有fhi>0，则对点h标号，记为(i,ε(h))，其中ε(h)=min{ε(i),fhi}； (3)如果某未标号点k有两个以上相邻的标号点，为减少迭代次数，可按(1)、(2)中所述规则分别计算出ε(k)的值，并取其中最大的一个标记。Ford-Fulkerson算法的步骤重复第二步的操作：A2A4A3S15(11)13(11)10(9)7(6)5(4)12(9)A1T6(5)4(0)(0,∞)(S,1)(S,4)(A2,1)(A1,2)(A3,1)T得到标号，这时可用反向追踪法在网络中找出一条从S->T的由标号及相应的弧连接而成的增广链。Ford-Fulkerson算法的步骤A2A4A3S15(11)13(11)10(9)7(6)5(4)12(9)A1T6(5)4(0)(0,∞)(S,1)(S,4)(A2,1)(A1,2)(A3,1)第三步：修改流量。设图中原有可行流为f，令Ford-Fulkerson算法的步骤A2A4A3S15(12)13(12)10(9)7(7)5(4)12(9)A1T6(5)4(0)(0,∞)(S,1)(S,4)(A2,1)(A1,2)(A3,1)第四步：抹掉图上的标号，重复第一到第四步Ford-Fulkerson算法的步骤标号过程中断，T得不到标号，说明该网络中不存在增广链，给定的流量即为最大流。A2A4A3S15(12)13(12)10(9)7(7)5(4)12(9)A1T6(5)4(0)(0,∞)(S,1)(S,3)(A2,1)(A1,1)(A4,1)10(10)12(10)5(5)(A3,1)Ford-Fulkerson算法练习求下列网络图s->t的最大流109554495613s12345t45641574332613s1234t最大流问题的数学模型决策变量：每条弧上的实际车流量顶点A1A2A3A4tsA1A2A3A4目标函数：从起点S流出的车流量（=流入终点T的车流量）最大约束条件：

每条弧上的实际流量不能超过其最大通过能力…中间结点的车流入量等于车流出量结点A1结点A2结点A3结点A4非负约束起点的流出量等于终点的流入量求解结果A2A4A3S15(12)13(12)10(10)7(7)5(5)12(10)A1T6(5)4(0)最大流：17最大流问题的一般化数学模型给定网络D=(V,A,C)中各弧的流量上界（即容量），求流量分配方案，使从发点到收点的流量最大。若是网络D=(V,A,C)的可行流，为该可行流的流量，那么从发点到收点的最大流问题可转化为如下形式的线性规划模型：

s.t.发点的流出量-流入量=可行流量收点的流出量-流入量=-可行流量其他点的流出量-流入量=0每条弧的流量不能超过容量最大流问题应用

某部队进行实战演习，红军侦获蓝军的物资供给线上的一条江的工事地图如下。在河流A岸和F岸之间的江面上有B、C、D和E四块洲岛，蓝军借助地势搭建了1至13号浮桥。红军指挥员决定由空对地制导轰炸浮桥的方式，彻底切断蓝军的供给线。请帮组红军制定出最有效的轰炸方案，以破坏最少的浮桥达到该战术目的。分析问题画出网络图把实际的军事工事地图抽象成网络图ABCDEF22211131浮桥的数量1截集和截量根据图论中截集的概念：给定网络D=(V,A,C)，若点集V被分割成两个非空集合V1和V2，使

，则把弧集(V1,V2)称为分离vs和vt的截集。 例如：上图中的其中一个截集为{(B,D),(C,D),(A,E)} 截集是图中这样一个边的集合，把这个集合拿走，则网络就分离成两个互不连通的部分。我们应该炸毁哪个截集中的所有桥梁才能使破坏的桥梁最少？截量的概念：给定截集(V1,V2)，把截集(V1,V2)中所有弧的容量之和称为这个截集的截量。找到截量最小的截集也就能使破坏的桥梁最少根据最大流问题最小截量定理：任一个网络D中，从vs到vt的最大流的流量等于分离vs,vt的最小截量。建立最大流问题模型决策变量：每条弧的实际流量顶点BCDEFABCDE目标函数：可行流量最大约束条件：弧的实际流量小于等于弧的容量：A的流出量等于F的流入量：其他顶点流出量与流入量相等：非负及整数约束：求解结果ABCDEF2(1)2(1)2(1)1(1)1(1)1(1)3(2)1(1)容量(实际流量)最少炸毁3个浮桥，要炸毁的是7,9,10号浮桥1(0)最大流问题应用练习有4个公司来某重点高校招聘企业管理(A)、国际贸易(B)、管理信息系统(C)、工业工程(D)、市场营销(E)专业的本科毕业生。经本人报名和两轮筛选，最后可供选择的各专业毕业生人数分别是4,3,3,2,4人。若公司1想招聘A,B,C,D,E各专业毕业生各1人；公司2拟招聘4人，其中C,D专业各1人，A,B,E专业可从任两个专业中各选1人；公司3招聘4人，其中C,B,E专业各1人，再从A或D专业中选1人；公司4招聘3人，其中须有E专业1人，其余2人可从余下A,B,C,D专业中任选其中两个专业各1人。问上述4个公司是否都能招聘到各自需要的专业人才？将此问题归结为求网络最大流问题。原问题转化的赋权有向图sEDCBA4321t2‘3’4‘434325443212注：未标记的弧容量均为1求解结果4个公司都招聘到了自己需要的人才，如下表所示企业管理(A)国际贸易(B)管理信息系统(C)工业工程(D)市场营销(E)公司111111公司21111公司31111公司4111最大流问题应用练习某单位招收懂俄、英、日、德、法文的翻译各一人，有5人应聘。已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文。问这5个人是否都能得到聘用？最多几个得到聘用，招聘后每人从事哪一方面翻译任务？转化的方法：网络结点设置为每种语言和每个应聘人各一个结点，再加上起点和终点。某个应聘人懂某种语言就将语言和应聘人连线，边的权数为1。再将起点与每种语言相连，将终点与每个应聘人相连，边的权数也为1。

将原问题转化为赋权有向图vs俄v1英v2日v3vt德v4法v5甲v6戊v10丁v9丙v8乙v7注：各边的权数为1问题的数学模型决策变量：实际招聘人数顶点俄英日