运筹学-图论PPT课件

图论第五章图与网络分析主要内容：1图的基本概念与基本定理2树和最小支撑树3最短路问题4最大流问题5最小费用流问题什么是图？图论中所谓的图是由一些点(vertices)，和一些连接兩点的边(edges)所形成的5.1图的基本概念与基本定理图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论、信息论、工程技术、交通运输、经济管理、电子计算机等各项领域。对于科学研究、市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如：各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决问题。关于图的第一篇论文是瑞士数学家欧拉（E.Euler）在1736年发表的解决“哥尼斯堡”七桥难题的论文。德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，当地的居民热衷于这样一个问题：一个散步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，1736年欧拉将这个问题抽象成图所示图形的一笔画问题。Königsberg(Koenigsberg)哥尼斯堡，原为东普鲁士(Prussia)首府，现属俄罗斯(飞地)，名为加里宁格勒(Kaliningrad)哥尼斯堡七桥问題:要如何走过每座桥恰一次，再返回出发点？普瑞格爾河哥尼斯堡七桥问题ABCD哥尼斯堡七桥问题可简化为以下图形其中的四个顶点都是奇顶点ABCDCADB哥尼斯堡七橋問題可以看成是：对这样一个封闭的图形，是否可以一笔画完成它并且回到原点数学家欧拉(Euler,1707-1783)于1736年严格地证明了上述哥尼斯堡七桥问题无解，并且由此开创了图论的典型思维方式及论证方式即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。图论应用举例例如，在组织生产中，为完成某项任务，各工序之间怎样衔接，才能使生产任务完成得既快又好。一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。各种通信网络的合理架设交通网络的合理分布等生活中的一些例子台大网路架构图例5.1图5.2是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。石家庄太原北京天津塘沽济南青岛徐州连云港南京上海郑州武汉重庆图5.3例5.2有六支球队进行足球比赛，我们分别用点v1，…，v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用图5.3所示的有向图反映出来v3v5v2v4v6v1从以上的几个例子可以看出，我们用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。通常用点表示研究对象，用点与点之间的线表示研究对象之间的特定关系。由于在一般情况下，图中对象的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图、工程图等本质上是不同的。图论中的图是由点、点与点之间的线所组成的。通常，我们把点与点之间不带箭头的线叫做边，带箭头的线叫做弧。如果一个图是由点和边所构成的，那么称为无向图，记作G=(V，E)，其中V表示图G的点集合，E表示图G的边集合。连接点vi,vjV的边记作[vi,vj]，或者[vj,vi]。如果一个图是由点和弧所构成的，那么称为它为有向图，记作D=(V,A)，其中V表示有向图D的点集合，A表示有向图D的弧集合。一条方向从vi指向vj的弧，记作(vi,vj)。图的基本概念图5.4是一个无向图G=（V，E），其中V={v1,v2,v3,v4}E={[v1,v2],[v2,v1],[v2,v3],[v3,v4],[v1,v4],[v2,v4],[v3,v3]}v3v2v1v4图5.4图5.5是一个有向图D=（V，A）其中V={v1,v2,v3,v4,v5,v6,v7}A={(v1,v2),(v1,v3),(v3,v2)(v3,v4),(v2,v4),(v4,v5),(v4,v6),(v5,v3),(v5,v4),(v5,v6),(v6,v7)}图5.5v7v5v3v4v2v6v1图的基本概念一个图G或有向图D中的点数，记作P(G)或P(D)，简记作P；边数或者弧数，记作q(G)或者q(D)，简记作q。如果边[vi,vj]E，那么称vi,vj是边的端点，或者vi,vj是相邻的。如果一个图G中，一条边的两个端点是相同的，那么称为这条边是环，如图5.4中的边[v3,v3]是环。图的基本概念如果两个端点之间有两条以上的边，那么称为它们为多重边，如图5.4中的边[v1,v2],[v2,v1]。v3v2v1v4v1v5v4v3v2简单图（2）（4）（3）（3）（2）多重图v1v5v4v3v2（4）（6）（3）（3）（2）一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。以点v为端点的边的个数称为点v的度（次），记作d(v),如图5.4中d(v1)=3，d(v2)=4，d(v3)=4，d(v4)=3。度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。端点的度d(v)：点v作为端点的边的个数奇点：d(v)=奇数；偶点：d(v)=偶数；悬挂点：d(v)=1；悬挂边：与悬挂点连接的边；孤立点：d(v)=0；空图：E=，无边图v1v2v3v4v5v6v1v7v6v5v4v3v2V={v1,v2,v3,v4,v5,v6,v7}d(v1)=3;d(v2)=5;d(v3)=4;d(v4)=4;d(v5)=1;d(v6)=3;d(v7)=0其中v5为悬挂点，v7为孤立点。图5.7定理5.1所有顶点度数之和等于所有边数的2倍。证明：因为在计算各个点的度时，每条边被它的两个端点个用了一次。定理5.2在任一图中，奇点的个数必为偶数。证明：设V1，V2分别是图G中奇点和偶点的集合，由定理5.1，有因为是偶数，也是偶数，因此也必是偶数，从而V1中的点数是偶数。图的连通性：链：由两两相邻的点及其相关联的边构成的点边序列。如:v0,e1,v1,e2,v2，e3,v3,…,vn-1,en，vn;v0，vn分别为链的起点和终点。记作（v0,v1,v2，,v3,…,vn-1,vn）简单链：链中所含的边均不相同；初等链：链中所含的点均不相同,也称通路；圈：若v0≠vn则称该链为开链，否则称为闭链或回路或圈；简单圈：如果在一个圈中所含的边均不相同初等圈：除起点和终点外链中所含的点均不相同的圈；v1v2v4v3v5v6v7初等链:(v1,v2,v3,v6,v7,v5)初等圈：(v1,v2,v3,v5,v4,v1)简单链：(v1,v2,v3,v4,v5,v3)简单圈：(v4,v1,v2,v3,v5,v7,v6,v3,v4)以后除特别声明，均指初等链和初等圈。v1v2v3v4v5不连通图v1v5v4v3v2v6连通图：图中任意两点之间均至少有一条通路，否则称为不连通图。连通图有向图：关联边有方向弧：有向图的边a=(u,v),起点u,终点v；路：若有从u到v不考虑方向的链,且各方向一致,则称之为从u到v的路；初等路:各顶点都不相同的路；初等回路:u=v的初等路;连通图：若不考虑方向是无向连通图;强连通图：任两点有路;基本概念点边，弧无向图链端点关联边有向图圈始点，终点多重边简单图初等链/圈度（次）环多重图简单链/圈奇点，偶点连通图基础图悬挂点悬挂边不连通图路弧立点回路例一摆渡人欲将一只狼、一头羊、一篮菜从河西渡过河到河东，由于船小，一次只能带一物过河，并且狼与羊,羊与菜不能独处。给出渡河方法。解：用四维0-1向量表示(人,狼,羊,菜)在河西岸的状态(在河西岸则分量取1,否则取0)，共有24=16种状态，在河东岸的状态类似记作。由题设,状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的，从而对应状态(1,0,0,1),(1,1,0,0),(1,0,0,0)也是不允许的。以可允许的10个状态向量作为顶点，将可能互相转移的状态用线段连接起来构成一个图。根据此图便可找到渡河方法。(1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)(1,0,1,0)(0,0,0,0)(0,0,0,1)(0,0,1,0)(0,1,0,0)(0,1,0,1)(0,1,0,1)(0,1,0,0)(0,0,1,0)(0,0,0,1)(0,0,0,0)(1,0,1,0)(1,0,1,1)(1,1,0,1)(1,1,1,0)(1,1,1,1)河西=(人,狼,羊,菜)河东=(人,狼,羊,菜)将10个顶点分别记为A1,A2,…,A10,则渡河问题化为在该图中求一条从A1到A10的路.从图中易得到两条路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.图的矩阵表示1.邻接矩阵Adjacencymatrix表示图中两点之间的相互关系两点之间有弧或边的，用1表示，否则用0表示，构成一个矩阵Av2v4v6v5v1v3v1v2v3v4v5v6v1011000v2101110v3110010v4010011v5011101v6000110有向图v1v7v2v5v3v4v6v8v9v1v2v3v4v5v6v7v8v9v1011100000v2000010000v3010100000v4000001000v5000101110v6000010100v7000000010v8000000000v9000010010矩阵A的元素全为0的行所对应的点称为汇点上图v8矩阵A的元素全为0的列所对应的点称为源点上图v1、v95.2树和最小支撑树一、树及其性质在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。例5.3已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。如果用六个点v1…v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。表示任意两个城市之间均可以通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。图5.2.1是一个不含圈的连通图，代表了一个电话线网。图5.2.1v6v3v4v2v5v1树及其性质树：既简单又很有用树：一个无圈的连通图组织结构图ManagerSubordSubord荣国公贾代善贾赦贾政贾琏贾珠贾宝玉贾环贾兰定理定理1：设G=(V,E)是一个树，p(G)>=2，则G中至少有两个悬挂点。定理2：图G=(V,E)是一个树的充要条件是G不含圈，且恰有p-1条边。定理3：图G=(V,E)是一个树的充要条件是G是连通图，且q(G)=p(G)-1。定理4：图G=(V,E)是一个树的充要条件是任意两个顶点之间恰有一条链。推论从一个树中去掉任意一条边，则余下的图是不连通的。在树中不相邻的两个点间添上一条边，则恰好得到一个圈图的支撑树设图T=(V,E')是图G=(V,E)的一个支撑子图，如果T是一个树，则称T是G的一个支撑树定理5：图G有支撑树的充要条件是图G是连通的。破圈法：任取一个圈，从中去掉一条边，再对余下的图重复直到不再含图时为止。破圈法避圈法在图中任取一条边，找到一条与之不构成圈的边，再找一条前两边不构成圈的边重复直到不再能进行为止取出的边数为p-1条避圈法最小支撑树问题给定图G=(V,E)，对G中的每一条边[vi,vj]，相应地有一个数wij，则称这样的图为赋权图wij称为边[vi,vj]上的权权是与边有关的数量指标，可以是距离、时间、费用等。赋权图不仅指出各个点之间的邻接关系，而且同时也表示出各点之间的数量关系广泛应用于解决工程技术及管理等领域的最优化问题最小支撑树问题就是赋权图上的最优化问题之一。设有一个连通图G=(V,E)，每一边e=[vi,vj]有一个非负权w(e)=wij(wij>0)如果T=(V,E')，是G的一个支撑树，称E'中所有边的权之和为支撑树T的权，记为w(T)如果支撑树T*的权w(T*)是G的所有支撑树的权中最小者，则称T*是G的最小支撑树（最小树），即式中对G的所有支撑树T取最小最小支撑树问题就是要求G的最小支撑树。方法有二：避圈法Kruskal破圈法常见求赋权图的最小树。例5.4某厂内联结六个车间的道路网如下所示，已知每条路的长，要求沿道路架设联结六个车间的电话线网，使电话线的总长最小。v1v2v4v6v3v5657152344避圈法求最小支撑树v1v2v4v6v3v515234i=1,E0=Φ。从E中选最小权边。依次选最小权边，并使之不构成圈。共选5条边v1v2v4v6v5657152344最后，电话线总长1+2+3+4+5=15v3破圈法求最小支撑树任取一个圈，从中去掉一条权最大的边。依次重复，直到不含圈为止。v1v2v4v6v5657152344最后，电话线总长1+2+3+4+5=15v3矩阵计算方法TTTTTTTTTTTTTTTTTTTTT矩阵计算结果一.引言最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，设备更新等等。也可以用于解决其它的最优化问题。 5.3最短路问题例5.6如图所示的单行线交通网，每弧旁的数字表示这条单行线的距离。现在某人要从v1出发，通过这个交通网到达v8，求使总距离最短的旅行线路。v1v7v2v5616321v32v4v610310v8v9246234?路很多v1v7v2v5616321v32v4v610310v8v92462341+10+2+4=176+1+6=133+2+1+3+4=133+2+10+10+6=31哪一条最短？最短路算法如果P是D中从vs到vi的最短路，vi是P中的一个点，那么从vs沿P到vi的路是从vs到vi的最短路。1.图形的标号法2.所有wij≥0的情形—Dijkstra法19591.图形的标号法先标出离终点最近的一段，然后标号与该点距离最短的点，继续逆推至始点。C4AB1B2C1C2C3D1D2D3E1E2E3F1F2G5313668766688222255333333443510437597681310913121618从A到G的最短路为：A-B1-C2-D1-E2-F2-G2.Dijkstra法基本思路：从vs出发，逐步地向外探寻最短路。执行过程中，与每个点对应， 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 下一个数(称为此点的标号)，它或者表示从vs到该点的最短路的权(称为P标号)或者是从vs到该点的最短路的权的上界(称为T标号)方法的每一步是修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的点多一个，如此经过p-1步，就可以求出从vs到各点的最短路。Dijkstra法具体步骤开始(i=0)，令S0={vs},P(vs)=0,λ(vs)=0,对每一个v≠vs，令T(v)=+∞,λ(v)=M,令k=s1.如果Si=V，算法终止，这时，对每个vSi，d(vs,v)=P(v)；否则转入步骤22.考察每个使(vk,vj)A且vjSi的点vj。如果T(v)>P(vk)+wkj，则把T(vj)修改为P(vk)+wkj，把λ(vj)修改为k；否则转入步骤33.令T(vji)=min{T(vj)}如果T(vji)<∞则把vji的T标号变为P标号P(vji)=T(vji)，令Si+1=SiU{vji}，k=ji,把i换成i+1，转入步骤1；否则终止，这时对每一个，而对每一个vSi，d(vs,v)=T(v)v1v2v3v4v5v6v7v80v2v3v4v5v6v7v8PTλ0∞0M∞M∞M∞M∞M∞M∞Mv1v7v2v5616321v32v4v610310v8v9246234若T(v)>P(vk)+wkj则T(v)=P(vk)+wkjλ(vj)修改为k找到min{T(vj)}，将其TP标号P(vj)=T(vj)，S={v1，}6311111v4,v3,1143535v2,626v5,105951259v7,10v6,12v8v1到v8最短路V13258求s到t的最短路。s3t267452418291415530204416116196s3t2674524182914155302044161161960S={}PQ={s,2,3,4,5,6,7,t}s3t2674524182914155302044161161960S={}PQ={s,2,3,4,5,6,7,t}s3t267452418291415530204416116196159140S={s}PQ={2,3,4,5,6,7,t}XXXs3t267452418291415530204416116196159140S={s}PQ={2,3,4,5,6,7,t}XXXs3t267452418291415530204416116196159140S={s,2}PQ={3,4,5,6,7,t}XXXs3t267452418291415530204416116196159140S={s,2}PQ={3,4,5,6,7,t}XXXX33s3t267452418291415530204416116196159140S={s,2}PQ={3,4,5,6,7,t}XXXX33s3t267452418291415530204416116196159140S={s,2,6}PQ={3,4,5,7,t}XXXX3344XX32s3t267452418291415530204416116196159140S={s,2,6}PQ={3,4,5,7,t}XXX44XX33X32s3t2674518291415530204416116196159140S={s,2,6,7}PQ={3,4,5,t}XXX44X35X59X24X33X32s3t267452418291415530204416116196159140S={s,2,6,7}PQ={3,4,5,t}XXX44X35X59XX33X32s3t267452418291415530204416116196159140S={s,2,3,6,7}PQ={4,5,t}XXX44X35X59XX51X34X33X32s3t2674518291415530204416116196159140S={s,2,3,6,7}PQ={4,5,t}XXX44X35X59XX51X34X33X3224s3t2674518291415530204416116196159140S={s,2,3,5,6,7}PQ={4,t}XXX44X35X59XX51X3424X50X45X33X32s3t2674518291415530204416116196159140S={s,2,3,5,6,7}PQ={4,t}XXX44X35X59XX51X3424X50X45X33X32s3t2674518291415530204416116196159140S={s,2,3,4,5,6,7}PQ={t}XXX44X35X59XX51X3424X50X45X33X32s3t2674518291415530204416116196159140S={s,2,3,4,5,6,7}PQ={t}XXX44X35X59XX51X34X50X45X33X3224s3t267452418291415530204416116196159140S={s,2,3,4,5,6,7,t}PQ={}XXX44X35X59XX51X34X50X45X33X32s3t267452418291415530204416116196159140S={s,2,3,4,5,6,7,t}PQ={}XXX44X35X59XX51X34X50X45X33X32237184566134105275934682求从1到8的最短路径237184566134105275934682X={1},w1=0min{c12,c14,c16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},p4=1p4=1p1=0237184566134105275934682X={1,4}min{c12,c16,c42,c47}=min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2X={1,2,4},p2=2p1=0p4=1p2=2237184566134105275934682X={1,2,4}min{c13,c23,c25,c47}=min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3X={1,2,4,6},p6=3p2=2p4=1p1=0p6=3237184566134105275934682X={1,2,4,6}min{c23,c25,c47,c67}=min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3X={1,2,4,6,7},p7=3p2=2p4=1p1=0p6=3p7=3237184566134105275934682X={1,2,4,6,7}min{c23,c25,c75,c78}=min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6X={1,2,4,5,6,7},p5=6p2=2p4=1p1=0p6=3p7=3p5=6237184566134105275934682X={1,2,4,6,7}min{c23,c53,c58,c78}=min{2+6,6+9,6+4,3+8}=min{8,15,10,11}=8X={1,2,3,4,5,6,7},p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8237184566134105275934682X={1,2,3,4,6,7}min{c38,c58,c78}=min{8+6,6+4,3+7}=min{14,10,11}=10X={1,2,3,4,5,6,7,8},p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10237184566134105275934682X={1,2,3,4,6,7,8}1到8的最短路径为{1，4，7，5，8}，长度为10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10三、含有负权的最短路的求法83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v8例：求从v1到v8的最短路83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-1-2383-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-71-1583-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-7-3-1-5683-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-7-3-1-56从v1到v8的最短路的长度为：6从v1到v8的最短路线为：v8v6v3v1应用举例设备更新问题。某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用旧的，则需支付一定的维修费用。现在的问题是如何制定一个几年之内的设备更新 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 ，使得总的支付费用最少。我们用一个五年之内要更新某种设备的计划为例，若已知该种设备在各年年初的价格如下表，还知使用不同时间的设备所需要的维修费用如下表。第1年第2年第3年第4年第5年价格1111121213使用年限0-11-22-33-44-5维修费用5681118可供选择的设备更新 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 显然是很多的。例如，每年都购置一台新设备，则其购置费用为11+11+12+12+13=59，而每年支付的维修费用为5，五年合计为25。于是5年的总费用为59+25=84再如，每1，3，5年各购进一台。此时设备购置费用为11+12+13=36，维修费用为5+6+5+6+5=27，5年总费用为36+27=63。如何制定总费用最省的设备更新计划呢？转化为最短路问题。用点代表“第i年年初购进一台新设备”这样上述设备更新问题就变为：在有向赋权图G=(V,E,F)(图解如下)中求v1到v6的最短路问题。由实际问题可知,设备使用三年后应当更新,因此删除该图中v1到v5,v1到v6,v2到v6的连线；又设备使用一年后就更新则不划算,因此再删除该图中v1v2,v2v3,v3v4,v4v5,v5v6五条连线后得到从上图中容易得到v1到v6只有两条路：v1v3v6和v1v4v6.而这两条路都是v1到v6的最短路.五年的总费用为53。例拣货路径问题Pickpath货架分布要拣货物第1步从第1通道到第2通道每条路径代表图中的一条边第2步找出从第2通道到第3通道的每条路径第3步找出从第3通道到第4通道的每条路径第4步找出从第4通道到完成的每条路径FindtheshortestpathoftheassociatedgraphTheshortestpathontheassociatedgraphgivesanefficientpickpathinwarehouse对应图的最短路给出了仓库的有效拣选路径5.4网络的最大流5.4.1网络的最大流的概念网络流一般在有向图上讨论定义网络上支路的容量为其最大通过能力，记为cij，支路上的实际流量记为fij图中规定一个发点s，一个收点t节点没有容量限制，流在节点不会存储容量限制条件：0fijcij平衡条件：viA(vi)B(vi)5.4网络的最大流图中规定一个发点s，一个收点t－节点没有容量限制，流在节点不会存储－容量限制条件：0fijcij－平衡条件：满足上述条件的网络流称为可行流，总存在最大可行流当支路上fij=cij，称为饱和弧；v(f)为可行流的流量最大流问题也是一个线性规划问题viA(vi)B(vi)定义：设f是一个可行流，是vs从vt到的一条链，若满足下列条件，则是可行流的一条增广链：(1)弧(vi,vj)+上，即+中每一条弧是非饱和弧；(2)弧(vi,vj)-上，即-中每一条弧是非零流弧；定义：把网络分割为两个成分的弧的最小集合，其中一个成分包含s点，另一个包含t点。一般包含s点的成分中的节点集合用V表示，包含t点的成分中的节点集合用V表示截量集容量是指截量集中前向弧的容量之和福特-富克森定理：网络的最大流等于最小截量集容量5.4.2确定网络最大流的标号法从任一个初始可行流出发，如0流基本算法：找一条从s到t点的增广链。若在当前可行流下找不到增广链，则已得到最大流增广链中与s到t方向一致的弧称为前向弧，反之后向弧增广过程：前向弧fij=fij+,后向弧fij=fij增广后仍是可行流最大流最小截量的标号法步骤第一步：标号过程，找一条增广链1、给源点s标号[s+,q(s)=]，表示从s点有无限流出潜力2、找出与已标号节点i相邻的所有未标号节点j，若(1)(i,j)是前向弧且饱和，则节点j不标号；(2)(i,j)是前向弧且未饱和，则节点j标号为[i+,q(j)]，表示从节点i正向流出，可增广q(j)=min[q(i),cijfij]；(3)(j,i)是后向弧，若fji=0，则节点j不标号；(4)(j,i)是后向弧，若fji>0，则节点j标号为[i,q(j)]，表示从节点j流向i，可增广q(j)=min[q(i),fji]；最大流最小截量的标号法步骤3、重复步骤2，可能出现两种情况：(1)节点t尚未标号，但无法继续标记，说明网络中已不存在增广链，当前流v(f)就是最大流；所有获标号的节点在V中，未获标号节点在V中，V与V间的弧即为最小截量集；算法结束(2)节点t获得标号，找到一条增广链，由节点t标号回溯可找出该增广链；到第二步最大流最小截量的标号法步骤第二步：增广过程1、对增广链中的前向弧，令f=f+q(t)，q(t)为节点t的标记值2、对增广链中的后向弧，令f=fq(t)3、非增广链上的所有支路流量保持不变第三步：抹除图上所有标号，回到第一步一次只找一条增广链，增广一次换一张图最后一次用广探法，以便找出最小截量集最大流最小截量集的标号法举例(s+,)(s+,6)(2,6)(3+,1)(4+,1)(s+,)(s+,5)(2+,2)(5,2)(4+,2)(s+,)(s+,3)(2,3)最小截量集§5.5最小费用最大流问题在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，还经常要考虑费用的问题。比如一个铁路系统的运输网络流，即要考虑网络流的货运量最大，又要考虑总费用最小。最小费用最大流问题就是要解决这一类问题。我们首先考察，在一个网络D中，当沿可行流f的一条增广链μ，以调整量θ=1改进f，得到的新可行流f'的流量，有v(f)=v(f)+1，而此时总费用b(f)比b(f)增加了设一个网络D=（V，A，C），对于每一个弧(vi,vj)∈A,给定一个单位流量的费用bij0，网络系统的最小费用最大流问题，是指要寻求一个最大流f，并且流的总费用达到最小。结论：如果可行流f在流量为v(f)的所有可行流中的费用最小，并且是关于f的所有增广链中的费用最小的增广链，那么沿增广链μ调整可行流f，得到的我们将叫做这条增广链的费用。新可行流f，也是流量为v(f)的所有可行流中的最小费用流。依次类推，当f是最大流时，就是所要求的最小费用最大流。显然，零流f={0}是流量为0的最小费用流。寻求最小费用流，总可以从零流f={0}开始。下面的问题是：如果已知f是流量为v(f)的最小费用流，那么就要去寻找关于f的最小费用增广链。对此，重新构造一个赋权有向图M(f)，其顶点是原网络D的顶点，而将D中的每一条弧(vi,vj)变成两个相反方向的弧（vi,vj）和(vj,vi)，并且定义M(f)中弧的权wij为：并且将权为+∞的弧从M(f)中略去。这样，在网络D中寻找关于f的最小费用增广链就等于价于在M(f)中寻求从vs到vt的最短路。算法开始，取零流f(0)={0}.一般地，如果在第K-1步得到最小费用流f(K-1),则构造图M(f(k-1))。在图M(f(k-1))中，寻求从vs到vt的最短路。如果存在最短路，则f(k-1)就是最小费用最大流。如果存在最短路，则在原网络D中得到相对应（一一对应）的增广链μ0在增广链μ上对f(k–1)进行调整，取调整量令：得到一个新的可行流f(k)，在对f(k)重复以上的步骤，直到D中找不到相对应的增广链时为止。例求图5.5.1所示网络中的最小费用最大流，弧旁的权是（bij,cij）.(bij,cij)(1,8)(3,10)(2,4)(6,2)(1,7)(4,10)(2,5)v1v2vsv3vt图5.5.1解：（1）取初始可行流为零流f(0)={0},构造赋权有向图M(f(0)),求出从vs到vt的最短路(vs,v2,v1,vt),如图5.5.1a中双箭头所示。(1)(3)(2)(6)(1)(4)(2)M(f(0))v1vsv2v3vt图5.5.1a（2）在原网络D中，与这条最短路相对应的增广链为μ=（vs,v2,v1,vt）。（3）在μ上对f(0)={0}进行调整，取θ=5，得到新可行流f(1)，如图5.5.1b所示。按照以上的算法，依次类推，可以得到f(1)，f(2)，f(3)，f(4)，流量分别为5，7，10，11，并且分别构造相对应的赋权有向图M(f(1)),M(f(2)),M(f(3)),M(f(4))。由于在M(f(4))中已经不存在从vs到vt的最短路，因此，可行流f(4)，v(f(1))=11是最小费用最大流。(8,5)(10,0)(4,0)(2,0)(7,5)(10,0)(5,5)图5.5.1bf(1),v(f(1))=5v1vsv2v2vtM(f(1))图5.5.1cv1(2)(-1)v3(1)(3)(6)(1)(4)(-2)(-1)vsv2vt(2,0)(5,5)(8,5)(4,0)(7,7)(10,2)(10,0)图5.5.1df(2),v(f(2))=7v1vsv2v3vtM(f(2))图5.5.1e(1)(3)(2)(6)(-1)(4)(-2)(-1)(-4)v1vsv3vtv2(8,8)(10,3)(4,3)(2,0)(7,7)(10,2)(5,5)图5.5.1ff(3),v(f(3))=10v1vsv2v3vt(-1)(3)(2)(6)(-1)(4)(-2)(-4)M(f(3))图5.5.1g(-2)(-3)v1vsv2v3vt(8,8)(10,4)(4,4)(2,0)(7,7)(10,3)(5,4)图5.5.1hf(4),v(f(4))=11v1vsv2v3vt(-1)(3)(-2)(6)(-1)(4)(2)(-4)M(f(4))图5.5.1i(-2)(-3)v1vsv2v3vtApplicationsofNetworkOptimization网络最优化模型的应用网络在交通、电子和通讯网络遍及我们日常生活的各个方面，网络规划也广泛用于解决不同领域中的各种问题，如生产、分配、项目计划、厂址选择、资源管理和财务策划等等。网络规划为描述系统各组成部分之间的关系提供了非常有效直观和概念上的帮助，广泛应用于科学、社会和经济活动的每个领域中。Networkrepresentation网络表述这种描述还有其他应用吗？想想看！TypesofNetworkOptimizationProblem网络最优化问题类型MinimumCostNetworkFlowModel最小费用流问题MaximumFlowProblems最大流问题ShortestPathProblem最短路问题MinimumSpanningTreeProblem最小支撑树问题MinimumCostNetworkFlowModel最小费用流问题最小费用流问题的构成：节点(nodes)（供应点、需求点、转运点）弧（arcs）目标:通过网络满足需求提供供应，最小化流的总成本AssumptionsofMinimumCostNetworkFlow最小费用流问题的假设至少一个供应点一个需求点剩下都是转运点通过弧的流只允许沿着箭头方向流动，通过弧的最大流量取决于该弧的容量网络中有足够的弧提供足够容量，使得所有在供应点中产生的流都能够到达需求点在流的单位成本已知前提下，通过每一条弧的流的成本和流量成正比CharacteristicofSolution解的特征具有可行解的特征：在以上的假设下，当且仅当供应点所提供的流量总和等于需求点所需要的流量总和时，最小费用流问题有可行解具有整数解的特征：只要其所有的供应、需求和弧的容量都是整数值，那么任何最小费用流问题的可行解就一定有所有流量都是整数的最优解DistributionUnlimitedCo.无限配送公司无限配送公司的最小成本流问题的电子表格模型实际举例NetworkSimplexMethod网络单纯形法实际运用中解决比较大型问题时需要用不同的方法网络单纯形法可以用来解决那些对于单纯形法来说太大而无法解决的大型问题ExcelSolver软件中没有网络单纯形法，但是其他的线性规划的商业软件包通常都有这种方法SomeApplications一些实际应用国际纸业公司（InternationalPaperCompany）配送网络（Interfaces1988年3/4）世界上最大的纸浆、纸和纸类产品的制造商以及木材和夹板的主要生产者。拥有两千万英亩的林区或其权益。分布在不同地方的林区是它配送网络的供应点,供应流必须经过一系列很长的转运点：林区→木材堆积场→锯木厂→造纸厂→纸制品加工厂→仓库→客户实务经典SomeApplications一些实际应用马尔萨斯公司（Marshalls,Inc.）配送网络（Interfaces1987年7/8）一家折扣连锁零售店，现在和以前是如何使用微型计算机去处理一个最小费用流问题。应用中公司力图使得从供应商到加工中心，再从加工中心到零售店的商流最优。其中的一些网络有超过20,000条弧。实务经典MaximumFlowProblems最大流问题最大流问题也与网络中的流有关，但目标不是使得流的成本最小化，而是寻找一个流的方案，使得通过网络的流量最大这种问题有哪些应用呢？想想看！BMZCaseStudyBMZ案例研究BMZ从德国斯图加特工厂到洛杉矶配送中心的配送网络案例研究BMZCaseStudyBMZ案例研究BMZ案例的网络描述案例研究BMZCaseStudyBMZ案例研究BMZ案例求解案例研究AssumptionsofMaximumFlowProblems最大流问题的假设网络中所有流起源于一个叫做源的节点所有的流终止于一个叫做收点的节点其余所有的节点叫做转运点通过每一个弧的流只允许沿着弧的箭头方向流动目标是使得从源到收点的总流量最大ShortestPathProblem最短路问题最短路问题的最普遍的应用在两个点之间寻找最短路这种问题有哪些应用呢？LittletownFireStation里特城消防站实际举例里特城的消防站和某一农场社区间的道路系统LittletownFireStation里特城消防站实际举例里特城的消防站道路系统的网络表述LittletownFireStation里特城消防站实际举例AssumptionsofshortestPathProblem最短路问题的假设网络中选择一条路,始于某源点终于目标地连接两个节点的连线叫做边（允许任一个方向行进），弧（只允许沿着一个方向行进）和每条边相关的一个非负数，叫做该边的长度目标是为了寻找从源到目标地的最短路MinimumSpanningTreeProblem最小支撑树问题给你网络中的节点，但没有给你边。或者，给你可供选择的边和如果把它插入到网络中后的每条边的正的成本（或者相似的度量）在设计网络时你希望通过插入足够的边，以满足每两个节点之间都存在一条路的需要目标是寻找一种方法，使得在满足要求的同时总成本最小TheSimpleAlgorithm简单的算法选择第一条边：选择成本最低的备选边选择下一条边：在一个已经有一条边连接的节点和另一个还没有边连接的节点之间选择成本最低的备选边重复第二个步骤，直到所有的节点都有一条边（可能会有多于一条边）与其相连此时就得到了最优解（最小支撑树）SomeApplications一些实际应用电信网络（计算机网络、电话专用线网络、有线电视网络等等）的设计低负荷运输网络的设计，使得网络中提供链接的部分（如铁路、公路等等）的总成本最小高压输电线路网络的设计电器设备线路网络（如数字计算机系统）的设计，使得线路总长度最短连接多个场所的管道网络设计实务应用SessionSummary本讲小结网络表示在描绘网络系统中各部之间关联非常有用最大流问题的目标是使得从一个特定的起点（源）到一个特定的终点（收点）的总流量最大最短路问题也有始点（源）和终点（目标地），但是，它的目标是从源点到目标地寻找一条总长度最短的路最小支撑树问题的目标是使得为任意两个节点之间提供路时总成本最小