运筹学第五章-图与网络分析课件

第第5章章图与网络分析图与网络分析第5章图与网络分析1 1第章图与网络分析第章图与网络分析u.基本概念基本概念u.最小支撑树问题最小支撑树问题u.最短路问题最短路问题u.最大流问题最大流问题第章图与网络分析.基本概念25.基本概念基本概念1.1.图、子图与简单图图、子图与简单图u图：图：由节点和线组成的图形由节点和线组成的图形 记为：记为：G=(V,E)G=(V,E)V=v V=v1 1,v,v2 2,v,vm m节点集节点集,表示研究对象表示研究对象.E=eE=e1 1,e,e2 2,e,en n边集，表示研究对象之边集，表示研究对象之间的关系间的关系.e1e2e3e5e6e4e7v3v2v1v45.基本概念1.图、子图与简单图e1e2e3e5e63e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4图图u子图：子图：图的一部分，记为图的一部分，记为e1e2e3e5e6e4e7v3v2v1v4e2e3e5e64u多重边多重边：两节点之间有多于一条边。：两节点之间有多于一条边。u环：环：首尾相接的边首尾相接的边u简单图：简单图：无环、无多重边的图。无环、无多重边的图。2.有向图与无向图有向图与无向图v有向图有向图：有方向的图。：有方向的图。v无向图无向图：无方向的图。：无方向的图。多重边：两节点之间有多于一条边。环：首尾相接的边简单图：无环5 e1V2V1e2V3 v1 e v23.关联与相邻关联与相邻v关联关联(边与节点的关系边与节点的关系):若若e是是v1、v2两节点间两节点间 的边，记的边，记e=v1，v2，称称v1、v2 与与e关联关联。v相邻相邻（边与边、节点与节点的关系）：（边与边、节点与节点的关系）：点点v1与与v2有公共边，称节点有公共边，称节点v1与与v2相邻相邻；边边e1与与e2 有公共节点，称边有公共节点，称边e1与与e2相邻相邻。e1 V2v1 6圈圈 封闭的链称为封闭的链称为圈圈如：如：=(1,2),(2,4),(3,4),(1,3 链链:由图由图G中的某些相连的边构成的图形（首尾中的某些相连的边构成的图形（首尾不能相接），称为图不能相接），称为图G中的一条中的一条链链。如：如：=(1,2),(3,2),(3,4)4.链、圈与连通图链、圈与连通图42314231圈链:由图G中的某些相连的边构成的图形（首尾不能相接），称为7连通图连通图 任意两个节点之间至任意两个节点之间至少有一条链的图称为少有一条链的图称为连连通图通图42315.网络图网络图 给图中的节点和边赋以给图中的节点和边赋以具体的含义和权数（如距离、具体的含义和权数（如距离、时间、费用、容量等），则时间、费用、容量等），则称这样的连通图为称这样的连通图为网络图网络图。4231 50 70 20 45连通图42315.网络图 给图中的节点和边赋以8v典例:会议日程安排某单位要在今后的三天内召开6个会议,每天上下午各安排一个会议，参加会议的领导如下会议A:朱、马、牛、姬、江、姚会议B:朱、杨、张、江会议C:马、姬、侯、王、姚会议D:朱、姬、张会议E:杨、侯、王会议F:刘、杨、王、江、姚典例:会议日程安排9每位领导每天最多只参加一个会议。会议A要安排在第一天上午,会议F安排在第三天下午，会议B要安排在任何一天的下午。试根据上述要求排出一个会议日程表，使各位领导都能参加相应的会议每位领导每天最多只参加一个会议。会议A要安排在第一天上午,会10ABCDEF会议日程安排如下:上午下午第一天会议AE第二天会议CB第三天会议DF解:用节点表示会议，若两个会议能安排在一天，则用连线连接。ABCDEF会议日程安排如下:解:用节点表示会议，若两115.2 最小支撑树问题最小支撑树问题v树：无圈的连通图，记为树：无圈的连通图，记为T。5.2 最小支撑树问题树：无圈的连通图，记为T。12v树的性质树的性质243512435124351如果树如果树T有有m个节点，则个节点，则边的个数为边的个数为m-1。树中任意两个节点间有树中任意两个节点间有且只有一条链且只有一条链。在树中任意去掉一条边，在树中任意去掉一条边，则不连通则不连通。树的性质243512435124351如果树T有m个节点，则13v图的支撑树图的支撑树图图G1和和G2 的节点相同，但图的节点相同，但图G1边的集合边的集合包包含于含于G2边的集合，且边的集合，且 G1是树图，则是树图，则 图图G1是是G2 的支撑树。的支撑树。一个图的支撑树不是唯一的。一个图的支撑树不是唯一的。图G1图G2图的支撑树图G1和G2 的节点相同，但图G1边的集合包含于G14v最小支撑树树枝总长最短的支撑树。特点：各节点都连通且线路总长最短v最小支撑树的求法1破圈法2避圈法最小支撑树 最小支撑树的求法155.2.1 求解最小支撑树问题的破圈法求解最小支撑树问题的破圈法v方法：去边破圈的过程。方法：去边破圈的过程。v步骤步骤：1）在给定的赋权的连通图上任找）在给定的赋权的连通图上任找 一一 个圈。个圈。2）在所找的圈中去掉一条权数最）在所找的圈中去掉一条权数最 大的边。大的边。3）若所余下的图已不含圈，则计）若所余下的图已不含圈，则计 算结束，余下的图即为最小支撑算结束，余下的图即为最小支撑 树，否则返回树，否则返回 1）。）。5.2.1 求解最小支撑树问题的破圈法方法：去边破圈的过程16v例：用破圈法求右图例：用破圈法求右图 的最小支撑树。的最小支撑树。V4V2V3V13 74 45 5 86 1V4V2V3V1V1V4V2V3V4V2V3V1V4V2V3V1总权数总权数=3+4+1=8例：用破圈法求右图V4V2V3V1 175.2.2 求解最小支撑树的避圈法求解最小支撑树的避圈法v方法：选边的过程。方法：选边的过程。v步骤：步骤：1）从网络中任意选一点）从网络中任意选一点vi，找出找出与与vi相关联的权最小的边相关联的权最小的边vi,vj，得第二个得第二个顶点顶点vj。2）把顶点集）把顶点集V分为互补的两部分分为互补的两部分A,，其中：其中：A：与已选边相关联的点集与已选边相关联的点集 ：不与已选边相关联的点集不与已选边相关联的点集5.2.2 求解最小支撑树的避圈法方法：选边的过程。步骤：18 3)考虑所有这样的边考虑所有这样的边vi,vj，其中其中viA,vj,挑选其中权最小的。挑选其中权最小的。4）重复）重复3），直至全部顶点均属于），直至全部顶点均属于A即即可。可。v例：用避圈法求图的最小例：用避圈法求图的最小 支撑树。支撑树。V4V2V3V13 74 45 5 86 1 3)考虑所有这样的边vi,vj，19任选点任选点v1，挑与之相关挑与之相关联的权最小的边（联的权最小的边（v1,v4）.A=v1,v4,=v2,v3 从边（从边（v1,v2）,（v1,v3）,（v4,v2）,（v4,v3）中选权最小的边（中选权最小的边（v1,v2）。）。V4V2V3V13 74 45 5 86 1A=v1,v2,v4,=v3 从边（从边（v1,v3）,（v2,v3）,（v4,v3）中选中选权最小的边（权最小的边（v2,v3）。）。A=v1,v2,v3，v4任选点v1，挑与之相关联的权最小的边（v1,v4）.A20l网络的生成树和线性规划的关系网络的生成树和线性规划的关系网络的一个生成树对应于线性规划的网络的一个生成树对应于线性规划的一个基一个基生成树上的边对应于线性规划的基变生成树上的边对应于线性规划的基变量量生成树的弦对应于线性规划的非基变生成树的弦对应于线性规划的非基变量量生成树的变换对应于线性规划单纯形生成树的变换对应于线性规划单纯形法的进基和离基变换法的进基和离基变换网络的生成树和线性规划的关系网络的一个生成树对应于线性规划的2171425673734243562412破圈法举例71425673734243562412破圈法举例22避圈法举例1425673734243562412避圈法举例142567373424356241223例例 校园局域网问题校园局域网问题某大学准备把所属个学院办公室的计某大学准备把所属个学院办公室的计算机联网这个网络的可能联通的途径算机联网这个网络的可能联通的途径如图所示边上权数为这条边的长度，如图所示边上权数为这条边的长度，单位为百米试设计一个网络联通个单位为百米试设计一个网络联通个学院办公室，并使总长度为最短学院办公室，并使总长度为最短例 校园局域网问题某大学准备把所属个学院办公室的计算机联24v1v4v5v3v7v6v2513724843103v1v4v5v3v7v6v251372484310325v1v4v5v3v7v6v2137233权和权和v1v4v5v3v7v6v2137233权和26例例 电话线网架设问题电话线网架设问题某个城市之间的道路网如图所示要某个城市之间的道路网如图所示要求沿着已知长度的道路联结个城市的求沿着已知长度的道路联结个城市的电话线网，并使电话线的总长度最短电话线网，并使电话线的总长度最短v1v4v2v6v5v3617524453例 电话线网架设问题某个城市之间的道路网如图所示要求沿27v1v4v2v6v5v312453权和权和v1v4v2v6v5v312453权和285.3 最短路问题最短路问题问题：求网络中一定点到其它点的最短路。问题：求网络中一定点到其它点的最短路。5.3.1 最短路问题的最短路问题的Dijstra解法解法方法：给方法：给vi点标号点标号i,vk 其中：其中：i：vi点到起点点到起点vs的最短距离的最短距离 vk:vi的前接点的前接点5.3 最短路问题问题：求网络中一定点到其它点的最短路。529方法：方法：(1)给起点给起点vs标号标号0，vs。（2）把顶点集）把顶点集v分为互补的两部分分为互补的两部分A和和 其中：其中：A：已：已标号点集号点集 ：未标号点集：未标号点集（3）考虑所有这样的边）考虑所有这样的边vi,vj,其中其中vi A,vj 挑选其中与挑选其中与vs距离最短的点距离最短的点vj标号标号 mini+cij,vi方法：(1)给起点vs标号0，vs。（2）把顶点集v分30(4)重复（重复（3），直至终点），直至终点vt标上号标上号t,vk，则，则 t即为即为vs至至vt的最短距。的最短距。反向追踪可求得最短路。反向追踪可求得最短路。(4)重复（3），直至终点vt标上号t,vk，则31例：求例：求v1至至v8的最短路。的最短路。v2v3v7v1v8v4v5v66134105275934682例：求v1至v8的最短路。v2v3v7v1v8v4v5v632v2v3v7v1v8v4v5v66134105275934682(1)v1:0,v1计算min0+2,0+1,0+3=min2,1,3=1v4:1.v11,v10,v1(2)A=v1检查边（v1,v2),(v1,v4),(v1,v3)v2v3v7v1v8v4v5v66134105275934633v2v3v7v1v8v4v5v66134105275934682(3)A=v1,v4计算min0+2,0+3,1+10,1+2=min2,3,11,3=2v2:2,v10,v11,v12,v1考虑边（考虑边（v1,v2),(v1,v6),(v4,v2),(v4,v7)v2v3v7v1v8v4v5v66134105275934634v2v3v7v1v8v4v5v66134105275934682（4）A=v1,v2,v4计算计算min 0+3,2+6,2+5,1+2 v6:3,v1 =min 3,8,7,3=3 2,v11,v10,v13,v1考虑边（考虑边（v1,v6),(v2,v3),(v2,v5),(v4,v7)v2v3v7v1v8v4v5v66134105275934635v2v3v7v1v8v4v5v66134105275934682(5)A=V1,V2,V4,V6计算计算 min 2+6,2+5,1+2,3+4=min 8,7,3,7=3 v7:3,v42，V11，V10，V13，V13,v4考虑边考虑边(v2,v3),(v2,v5),(v4,v7),(v6,v7)v2v3v7v1v8v4v5v66134105275934636V2V3V7V1V8V4V5V66134105275934682(6)A=V1,V2,，V4,V6,V7计算计算min 2+6,2+5,3+3,3+8=min 8,7,6,11=6 v5:6,v72,v11,v10,v13,v13,v46,v7考虑边考虑边(v2,v3),(v2,v5),(v7,v5),(v7,v8)V2V3V7V1V8V4V5V66134105275934637v2v3v7v1v8v4v5v66134105275934682(7)A=V1,V2,V4,V6,V7计算min2+6,6+9,6+4,3+8=min8,15,10,11=8v3:8,v22,V11,V10,V13,V13,V46,V78,v2考虑边考虑边(v2,v3),(v5,v3),(v5,v8),(v7,v8)v2v3v7v1v8v4v5v66134105275934638v2v3v7v1v8v4v5v66134105275934682(8)A=v1,v2,v3,v4,v6,v7计算min8+6,6+4,3+7=min14,10,11=10v8:10,v52,v11,v10,v13,v13,v46,v78,v210,v5考虑边（考虑边（v3,v8),(v5,v8),(v7,v8)v2v3v7v1v8v4v5v66134105275934639v2v3v7v1v8v4v5v66134105275934682(9)A=v1,v2,v3,v4,v6,v7,v8v1到到v10的最短路径为的最短路径为v1v4v7v5v8，最短路长度，最短路长度为为10。2,v11,v10,v13,v13,v46,v78,v210,v5反向追踪：反向追踪：v8-v5-v7-v4-v1v2v3v7v1v8v4v5v66134105275934640例例6 设备更新问题设备更新问题某厂使用一种设备，每年年初设备科需要对该设某厂使用一种设备，每年年初设备科需要对该设备的更新与否作出决策。五年内：备的更新与否作出决策。五年内：购买新设备购买新设备-购置费；购置费；13，14，16，19，24；使用老设备使用老设备-维护费。维护费。8，10，13，18，27。问：在问：在5年内如何制定更新计划，以便使新设备年内如何制定更新计划，以便使新设备购置费和老设备维修费的总费用最小？购置费和老设备维修费的总费用最小？例6 设备更新问题41341245632131323244622489224563473727v1-v3-v6minL=7834124563213132324462248922456342例例7 7火车调度问题火车调度问题某某火火车车货货运运调调车车场场，主主要要调调运运建建筑筑材材料料中中的的黄黄沙沙、碎碎石石和和水水泥泥。该该调调车车场场有有3 3个个装装运运点点：黄黄沙沙装装运运点点、碎碎石石装装运运点点和和水水泥泥装装运运点点；另另有有2 2个个机机车车挂挂钩钩处处（挂挂火火车车头头的的地地方方），即即图图1 1中中的的节节点点1 1、2 2、5 5和和9 9、1010。货货运运火火车车的的各各节节车车厢厢在在一一个个装装运运点点装装货货后后，必必须须由由调调车车场场的的火火车车头头把把装装好好货货的的车车厢厢拉拉走走，按按调调车车场场的的铁铁路路网网络络的的某某一一路路线线运运行行到到某某一一机机车车挂挂钩钩处处，由由那那里里的的火火车车头头把把满满载载的的车车厢厢拉拉走走。网网络络图图中中，各各条条弧弧代代表表铁铁路路线线，节点代表铁路交叉口，弧旁的节点代表铁路交叉口，弧旁的数字代数字代例7火车调度问题43表距离（单位：百米），这里需注意表距离（单位：百米），这里需注意的是，网络图只是描述了各换轨点的是，网络图只是描述了各换轨点(即即交叉口）、装运点和机车挂钩处之间交叉口）、装运点和机车挂钩处之间的关系，并不表示铁路线的实际走向。的关系，并不表示铁路线的实际走向。调车场的调度室需要解决的问题是：调车场的调度室需要解决的问题是：各车厢在某一装运点装好货后应把它各车厢在某一装运点装好货后应把它拉到哪一个机车挂钩处，而且应走哪拉到哪一个机车挂钩处，而且应走哪一条运行路线最短，从而提高调车场一条运行路线最短，从而提高调车场作业的效率，减少装载的车厢等候挂作业的效率，减少装载的车厢等候挂钩时间而尽快拉离调车场。钩时间而尽快拉离调车场。表距离（单位：百米），这里需注意的是，网络图只是描述了各换轨44分分别别求求出出结结点点1、2、5到到结结点点9和和10的的最最短短路路径径及最小路径值。及最小路径值。分别求出结点1、2、5到结点9和10的最短路径及最小路径值。45结果分析结果分析黄黄沙沙装装运运点点、水水泥泥装装运运点点、碎碎石石装装运运点点到到两两个个机机车车挂钩处的最短路径及最短路径值，如下挂钩处的最短路径及最短路径值，如下 30 30；35 35；27 27；32 32；-19-19；-24-24结果分析465.最大流问题最大流问题v2v3v5v4v6v7v1f=0f=06247437931885.最大流问题v2v3v5v4v6v7v1f=0f=047l问题的一般提法：问题的一般提法：有一网络有一网络D=(V,A;C)其中其中V：点集；：点集；A：弧集；：弧集；C=cij,cij为弧为弧（vi,vj)上的容量。上的容量。现现D上要安排通过一个流上要安排通过一个流f=fij，其中，其中fij为为弧弧(vi,vj)上的流量。上的流量。问题：如何安排流量问题：如何安排流量fij，可使，可使D上通过上通过 的总流量的总流量V(f)最大？最大？问题的一般提法：有一网络D=(V,A;C)问题485.4.1 网络流的基本概念与基本定理网络流的基本概念与基本定理(1)弧的容量和流量弧的容量和流量容量容量cij，流量流量fij(2)可行流可行流 a、每一个节点流量平衡、每一个节点流量平衡b、0fij cij1.弧的容量和流量、可行流5.4.1 网络流的基本概念与基本定理1.弧的容量和流量、49jifij=5cij=5jifij=3cij=52.饱和弧、不饱和弧、流量的间隙（i，j）是饱和的）是饱和的(2)如果如果fij0，弧从弧从j到到i的方向是不饱和的；的方向是不饱和的；（j，i）是不饱和的）是不饱和的间隙为间隙为 ij=fij=5jifij=0cij=5jifij=5cij=5(3)如果f513.可增广链（或可扩充链）可增广链（或可扩充链）网络网络D中中st的链，记为的链，记为 +：前向弧（与：前向弧（与方向一致）方向一致）-：后向弧（与：后向弧（与方向相反）方向相反）若链若链 上的流量满足：所有的前向弧皆未饱和，后向上的流量满足：所有的前向弧皆未饱和，后向 弧皆非零，则称弧皆非零，则称为为D中关于可行流中关于可行流fij的可增广链。的可增广链。(4,2)(3,1)(5,3)(4,1)(3,2)3.可增广链（或可扩充链）网络D中st的链，记为 524.截集与截量截集与截量l截集：将网络图中的起点与终点分开并截集：将网络图中的起点与终点分开并使流中断的一组正向弧的集合。使流中断的一组正向弧的集合。即将顶点即将顶点V分为二个非空互补集分为二个非空互补集E和和，使，使s s E,t ,称弧集称弧集（E，)=(i,j)|i E,j 为为D的截集。的截集。l截量：截集上的容量之和。记为截量：截集上的容量之和。记为C(E,).4.截集与截量截集：将网络图中的起点与终点分开并使流中断的一535.流量与截量的关系流量与截量的关系n任何一个可行流的流量任何一个可行流的流量V(f)都不会超过任一都不会超过任一截量。即截量。即V(f)C(E,)n最大流最大流-最小截定理：最小截定理：max V(f)=minC(E,)n判别最大流的条件：可行流判别最大流的条件：可行流f是最大流是最大流 D中不存在关于中不存在关于f 的可增广链的可增广链5.流量与截量的关系任何一个可行流的流量V(f)都不会超过任545.4.2 最大流问题的标号解法最大流问题的标号解法步骤：先找一个可行流步骤：先找一个可行流检验检验调整调整算法步骤：算法步骤：1.标号找可增广链标号找可增广链5.4.2 最大流问题的标号解法步骤：先找一个可行流检验55（1）给）给vs标号标号,v,vs s,选与选与v vs s相关联的流出未饱相关联的流出未饱和弧和弧(v(vs s,v,vi i)，给，给v vi i标号标号 i i,v,vs s.其中其中i i=csisi-fsisi（3）考虑所有这样的弧）考虑所有这样的弧(vi,vj),其中其中 viE,vj（2）点集点集V=E，其中，其中 E：已标号点集：已标号点集 ：未标号点集：未标号点集（3）考虑所有这样的弧(vi,vj),其中 viE,vj56若若(vi,vj)为流出未饱和弧，则为流出未饱和弧，则vj:j,v,vi j=mincij-fij,i若若(vi,vj)为流入非为流入非0弧，则弧，则vj:j,-vi j=min fij,i (4)直到终点已标号为止直到终点已标号为止,反向追踪便得可增反向追踪便得可增广链广链.若未标到终点若未标到终点,但已标不下去，说明网络但已标不下去，说明网络D中不存在可增广链，便得最大流中不存在可增广链，便得最大流maxV(f),同时同时得得 到最小截集到最小截集min(E，).若(vi,vj)为流出未饱和弧，则vj:j,vi 572.调整流量：调整流量：选择一条可增广链选择一条可增广链,调整流量。调整流量。fij+t (vi,vj)+fij=fij-t (vi,vj)-fij 其它调整后得到新的网络图,重复步骤1.2.调整流量：58例：用标号法求下面网络的最大流。vsv1v3V2v4vt(4,3)(3,3)(1,1)(5,3)(1,1)(3,0)(5,1)(2,1)(2,2)例：用标号法求下面网络的最大流。vs v1 591.标号找可增广链标号找可增广链(1)vs:,v,vs v v1:4,v:4,vs(2)E=v(2)E=vs,v,v1 v v2:1,-v:1,-v1(3)E=v(3)E=vs,v,v1,v,v2 v v4:1,v:1,v2 v v3:1,-v:1,-v2 vsv1v3v2v4vt(4,3)(3,3)(1,1)(5,3)(1,1)(3,0)(5,1)(2,1)(2,2),v,vs 4,vs1,-v11,v21,-v2(4)E=vs,v1,v2,v3,v4vt:1,v4 1,v3可增广链：可增广链：vt-v4-v2-v1-vs vt-v3-v2-v1-vs1,v41,v31.标号找可增广链 vs v1 602.调整流量调整流量(选择一条可增广链选择一条可增广链:vs-v1-v2-v4-vt)调整量调整量 t调整后得到整后得到新流量新流量图.再再标号找增广号找增广链(1)vs:,vs v1:,vs(2)E=vs,v1,但是标号不能进行下去，说明网络图但是标号不能进行下去，说明网络图中已不存在可增广链，即当前流为最大流。中已不存在可增广链，即当前流为最大流。.maxv(f)=3+2=4+1=5vsv1v3v2v4vt(4,4)(1,0)(3,0)(2,2),vs3,vs(3,3)(1,1)(5,4)(5,2)(2,1)5.min(E,5.min(E,)=(v)=(vs s,v,v2 2)，(v(v1 1,v,v3 3)minc(E,minc(E,)=3+2=5)=3+2=52.调整流量(选择一条可增广链:vs-v1-v2-v4-vt61例例10：求结点：求结点v1至结点至结点v v7的最大流，的最大流，同时写出其最小截集及截量。同时写出其最小截集及截量。v2v3v5v4v6v7v1f=0f=0624743793188例10：求结点v1至结点v7的最大流，同时写出其最小截集及截62解：解：（1）给出一个可行流给出一个可行流f=0，找到一条从找到一条从v1到到v7的可增广链的可增广链可增广链为：可增广链为：v7-v6-v3-v1；可调整流量为：；可调整流量为：=1调整链的流量：调整链的流量：xij=xij+；f=f+1=1v2v3v5v4v6v7v1f=0f=0(6,0)(2,0)(4,0)(7,0)(4,0)(3,0)(7,0)(9,0)(3,0)(1,0)(8,0)(8,0)，v18,v13,v21,v31,v6解：（1）给出一个可行流f=0，找到一63（2）调整流量f=1,继续求出网络的一条可增广链。v2v3v5v4v6v7v1f=1f=1(6,0)(3,1)(7,0)(9,0)(2,0)(4,0)(4,0)(3,0)(7,0)(8,1)(1,1)(8,1)可增广链为：可增广链为：v7-v5-v2-v3-v1;可调整流量为：可调整流量为：=1；调调整链的流量为：整链的流量为：xij=xij+1;f=f+1=2,v17,v12,-v32,v22,v5（2）调整流量f=1,继续求出网络的一条可增广链。v2v3v64(3)调整流量f=2,继续求出网络的一条可增广链.v2v3v5v4v6v7v1f=2f=2(6,1)(3,0)(7,1)(9,1)(2,0)(4,0)(4,0)(3,0)(7,0)(8,1)(1,1)(8,1),v17,v15,v25,v5可增广链为：可增广链为：v7-v5-v2-v1;可调整流量为：可调整流量为：=5；调整调整链的流量为：链的流量为：xij=xij+5,f=f+5=2+5=7(3)调整流量f=2,继续求出网络的一条可增广链.v2v3v65(4)调整流量f=7,继续求出网络的一条可增广链.v2v3v5v4v6v7v1f=7f=7(6,6)(3,0)(7,1)(9,6)(2,0)(4,0)(4,0)(3,0)(7,0)(8,1)(1,1)(8,6),v13,v56,v14,v34,v4可增广链为：v7-v5-v4-v3-v1;可调整流量为：=3,调整链上的流量为：xij=xij+3,f=f+3=7+3=10(4)调整流量f=7,继续求出网络的一条可增广链.v2v3v66(5)调整流量f=10,继续求出网络的一条可增广链.v2v3v5v4v6v7v1f=10f=10(3,0)(7,4)(9,9)(2,0)(4,3)(4,3)(3,0)(7,0)(8,1)(8,6),v13,v61,v33,v13,v4(6,6)可增广链为：v7-v6-v4-v3-v1;可调整流量为：=1；调整链上的流量为：xij=xij+1,f=f+1=10+1=11(1,1)(5)调整流量f=10,继续求出网络的一条可增广链.v2v367(6)调整流量f=11,继续求出网络的一条可增广链.v2v3v5v4v6v7v1f=11(3,0)(7,5)(9,9)(2,0)(4,4)(4,3)(3,1)(7,0)(8,2)(8,6),v13,v1(6,6)f=11(1,1)2,v1网络已不存在可增广链，因此，当前流达到网络已不存在可增广链，因此，当前流达到最大流。最大流。(6)调整流量f=11,继续求出网络的一条可增广链.v2v368(7)已求得最大流 f=11v2v3v5v4v6v7v1f=11(6,6)(2,0)(4,3)(3,0)(7,5)(4,4)(3,1)(1,1)(7,0)(9,9)(8,2)(8,6)f=11最小截集为最小截集为(E，)=(v2,v5),(v3,v4),(v3,v5)最小截量为最小截量为C(E，)=f25+f34+f35=6+4+1=11(7)已求得最大流 f=11v2v3v5v4v6v7v1f=69例例11 有限容量限制的调运问题的分析有限容量限制的调运问题的分析 某某产产品品从从仓仓库库Ai（i=1,2,3）运运往往市市场场Bj(j=1,2,3,4)销销售售。已已知知各各仓仓库库的的可可供供量量、各各市市场场的的需需求求量量及及Ai仓仓库库至至Bj市市场场路路径径上上的的容容量量如如表表1所所示示（表表中中数数字字0表表示示两两点点间间无无直直接接通通路路）。试试制制定定一一个个调调运运方方案案使使从从各各仓仓库库调运产品总量最多。调运产品总量最多。市场市场路径容量路径容量cij仓库仓库B1B2B3B4可供量A1301004020A200105020A32010405100需求量20206020例11 有限容量限制的调运问题的分析 70vsA1A2A3B4vtB3B2B152010040103010502010402060202020vsA1A2A3B4vtB3B2B152010040103071由由此此图图看看出出，该该调调运运方方案案并并不不能能完完全全满满足足市市场场要要求求，B3B3市市场场并并未未完完全全饱饱和和，可可以以通通过过增增加加A3A3到到B3B3市市场场的的容容量，使量，使B3B3市场得到完全饱和，增加量最少为市场得到完全饱和，增加量最少为1010。由此图看出，该调运方案并不能完全满足市场要求，B3市场并未完72例例12 发电问题发电问题有三个发电站（节点有三个发电站（节点v1,v2,v3），），发电发电能力分别为能力分别为15、10和和40兆瓦，经输电网兆瓦，经输电网可把电力送到可把电力送到8号地区（节点号地区（节点v8），），电电网的能力如图。求三个发电站输到这地网的能力如图。求三个发电站输到这地区（节点区（节点v8）的最大电力。的最大电力。例12 发电问题73304515102015104015v1v8v7v6v5v4v3v2304515102015104015v1v8v7v6v5v474(30,0)(45,0)(15,0)(10,0)(20,0)(15,0)(10,0)(40,0)(15,0)v1v8v7v6v5v4v3v2v0(15,0)(40,0)(10,0)(30,0)(45,0)(15,0)(10,0)(20,0)75(30,20)(45,35)(15,15)(10,10)(20,20)(15,15)(10,10)(40,20)(15,15)v1v7v6v5v4v3v2v0(15,15)(40,20)(10,10)Maxv(f)=45最小截集最小截集(E，)=（v0,v2),(v6,v5),(v6,v7)最小截量最小截量C(E，)=10+20+15=45v8(30,20)(45,35)(15,15)(10,10)(276