运筹学图与网络模型精选课件.ppt

《运筹学图与网络模型精选课件.ppt》由会员分享，可在线阅读，更多相关《运筹学图与网络模型精选课件.ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、关于运筹学图与网络模型第一页，本课件共有56页图论图论 Graph Theory哥尼斯堡七桥问题哥尼斯堡七桥问题 (K Knigsberg Bridge Problemnigsberg Bridge Problem)Leonhard Euler(1707-1783)Leonhard Euler(1707-1783)在在17361736年发表第一篇图论年发表第一篇图论方面的论文，奠基了图论中的一些基本定理方面的论文，奠基了图论中的一些基本定理很多问题都可以用点和线来表示，一般点表示实体，线表很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联示实体间的关联BACD第二页，本课件共有5

2、6页11 图与网络的基本概念图与网络的基本概念 1.1 图与网络图与网络节点节点(Vertex)物理实体、事物、概念物理实体、事物、概念一般一般用用 vi 表示表示边边(Edge)节点间的连线，表示有关系节点间的连线，表示有关系一般一般用用 eij 表示表示图图(Graph)节点和边的集合，节点和边的集合，一般用一般用 G(V,E)表示表示点集点集 V=v1,v2,vn边集边集E=eij网络网络(Network)边上具有表示连接强度的边上具有表示连接强度的权值，如权值，如 wij又称又称加权图加权图(Weighted graph)第三页，本课件共有56页1.2 无向图与有向图无向图与有向图边都

3、没有方向的图称为无向图，如图边都没有方向的图称为无向图，如图1在无向图中在无向图中 eij=eji，或，或(vi,vj)=(vj,vi)当边都有方向时，称为有向图，用当边都有方向时，称为有向图，用G(V,A)表示表示在有向图中，有向边又称为在有向图中，有向边又称为弧弧，用，用 aij表示，表示，i,j 的顺序是的顺序是不能颠倒的，图中弧的方向用箭头标识不能颠倒的，图中弧的方向用箭头标识图中既有边又有弧，称为混合图图中既有边又有弧，称为混合图第四页，本课件共有56页 1.3 端点，关联边，相邻，次端点，关联边，相邻，次图中可以只有点，而没有边；而有边必有点图中可以只有点，而没有边；而有边必有点若

4、节点若节点vi,vj 之间有一条边之间有一条边 eij，则称，则称 vi,vj 是是 eij 的的端点端点(end vertex)，而，而 eij 是节点是节点 vi,vj 的的关联边关联边(incid%nt edge)同一条边的两个端点称为同一条边的两个端点称为相邻相邻(adjacent)节点节点，具有共同端点，具有共同端点的边称为的边称为相邻边相邻边一条边的两个端点相同，称为一条边的两个端点相同，称为自环自环(self-loop)；具有两个共；具有两个共同端点的两条边称为同端点的两条边称为平行边平行边(parallel edges)既没有自环也没有平行边的图称为既没有自环也没有平行边的图称

5、为简单图简单图(simple graph)在无向图中，与节点相关联边的数目，称为该节点的在无向图中，与节点相关联边的数目，称为该节点的“次次”(degree)，记为记为 d；次数为奇数的点称为；次数为奇数的点称为奇点奇点(odd),次数为偶次数为偶数的点称为数的点称为偶点偶点(even)；图中都是偶点的图称为偶图；图中都是偶点的图称为偶图(even graph)第五页，本课件共有56页 1.3 端点，关联边，相邻，次端点，关联边，相邻，次有向图中，由节点指向外的弧的数目称为正次数，记为有向图中，由节点指向外的弧的数目称为正次数，记为 d+，指向该节点的弧的数目称为负次数，记为指向该节点的弧的数

6、目称为负次数，记为 d次数为次数为 0 的点称为的点称为孤立点孤立点(isolated vertex)，次数为，次数为 1 的点的点称为称为悬挂点悬挂点(pendant vertex)定理定理 1：图中奇点的个数总是偶数个：图中奇点的个数总是偶数个 1.4 链，圈，路径，回路，欧拉回路链，圈，路径，回路，欧拉回路相邻节点的序列相邻节点的序列 v1 ,v2 ,vn 构成一条构成一条链链(link)，又称为，又称为行行走走(walk)；首尾相连的链称为；首尾相连的链称为圈圈(loop)，或，或闭行走闭行走在无向图中，节点不重复出现的链称为在无向图中，节点不重复出现的链称为路径路径(path)；在有

7、向；在有向图中，节点不重复出现且链中所有弧的方向一致，则称为有图中，节点不重复出现且链中所有弧的方向一致，则称为有向路径向路径(directed path)首尾相连的路径称为首尾相连的路径称为回路回路(circuit)；第六页，本课件共有56页 1.4 链，圈，路径，回路，连通图链，圈，路径，回路，连通图走过图中所有边且每条边仅走一次的闭行走称为走过图中所有边且每条边仅走一次的闭行走称为欧拉回路欧拉回路定理定理 2：偶图一定存在欧拉回路：偶图一定存在欧拉回路(一笔画定理一笔画定理)1.4 连通图，子图，成分连通图，子图，成分设有两个图设有两个图 G1(V1,E1),G2(V2,E2),若若V2

8、 V1,E2 E1，则则 G2 是是 G1 的子图的子图无向图中，若任意两点间至少存在一条路径，则称为无向图中，若任意两点间至少存在一条路径，则称为连通图连通图(connected graph)，否则为，否则为非连通图非连通图(discon-nected graph)；非连通图中的每个非连通图中的每个连通子图连通子图称为称为成分成分(component)链，圈，路径链，圈，路径(简称路简称路)，回路都是原图的子图，回路都是原图的子图平面图平面图(planar graph)，若在平面上可以画出该图而没有任，若在平面上可以画出该图而没有任何边相交何边相交第七页，本课件共有56页2 树树图与最小生成

9、树图与最小生成树一般研究无向图一般研究无向图树图：倒置的树，根树图：倒置的树，根(root)在上，树叶在上，树叶(leaf)在下在下多级辐射制的电信网络、管理的指标体系、家谱、分类学、组多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图织结构等都是典型的树图第八页，本课件共有56页 2.1 树的定义及其性质树的定义及其性质任两点之间有且只有一条路径的图称为任两点之间有且只有一条路径的图称为树树(tree)，记为，记为T 树的性质：树的性质：最少边的连通子图，树中必不存在回路最少边的连通子图，树中必不存在回路任何树必存在次数为任何树必存在次数为 1 的点的点具有具有 n

10、 个节点的树个节点的树 T 的边恰好为的边恰好为 n 1 条，反之，任何有条，反之，任何有n 个节点，个节点，n 1 条边的连通图必是一棵树条边的连通图必是一棵树 2.2 图的生成树图的生成树树树 T 是连通图是连通图 G 的的生成树生成树(spanning tree)，若，若 T 是是 G的的子图且包含图子图且包含图 G 的所有的节点；包含图的所有的节点；包含图 G 中部分指定节中部分指定节点的树称为点的树称为 steiner tree第九页，本课件共有56页 2.3 最小生成树最小生成树有有n 个乡村，各村间道路的长度是已知的，如何个乡村，各村间道路的长度是已知的，如何铺设光缆线路使铺设光

11、缆线路使 n 个乡村连通且总长度最短个乡村连通且总长度最短显然，这要求在已知边长度的网路图中找最小显然，这要求在已知边长度的网路图中找最小生成树生成树 第十页，本课件共有56页2.4 求解最小生成树的破圈算法求解最小生成树的破圈算法所谓的最小生成树问题就是在一个赋权的连通的无向图所谓的最小生成树问题就是在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。为最小。算法的具体步骤如下：1.1.在给定的赋权的连通图上任找一个圈；在给定的赋权的连通图上任找一个圈；2.2.在所找的圈中去掉一条权数最大的边（如果有两条在

12、所找的圈中去掉一条权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其或两条以上的边都是权数最大的边，则任意去掉其中一条。中一条。3.3.如果所余下的图中已不含圈，则计算结束，所余下的图即为如果所余下的图中已不含圈，则计算结束，所余下的图即为最小生成数，否则返回第最小生成数，否则返回第1 1步。步。第十一页，本课件共有56页应用举例：应用举例：某大学准备对其所属的某大学准备对其所属的7 7个学院办公室计算机个学院办公室计算机 联网，这个网络的可能连通的路径如图联网，这个网络的可能连通的路径如图G G所示，图中所示，图中v v1 1,v,v7 7表示表示7 7个学院办公室，图中的

13、边为可能联网的路径，边上所赋的个学院办公室，图中的边为可能联网的路径，边上所赋的权数为这条路线的长度，单位为百米。请设计一个网络能连通权数为这条路线的长度，单位为百米。请设计一个网络能连通7 7个学院办公室，并使总的线路长度最短。个学院办公室，并使总的线路长度最短。v1v2v3v4v6v5v7103343278541G第十二页，本课件共有56页v1v2v3v4v6v5v7103343278541G1 1.在在G中找到一个圈中找到一个圈（v1,v7,v6,v1），并知在此圈上边，并知在此圈上边v1,v6的权数的权数1010为最大，在为最大，在G中去掉边中去掉边v1,v6得图得图G1。第十三页，本

14、课件共有56页v1v2v3v4v6v5v7334327541G2 2.在在G1中找到一个圈中找到一个圈（v3,v4,v5,v7,v3），并知在此圈上边，并知在此圈上边v4,v5的权数的权数8 8为最大，在为最大，在G1中去掉边中去掉边v4,v5得图得图G2。8第十四页，本课件共有56页v1v2v3v4v6v5v733432741G3 3.在在G2中找到一个圈中找到一个圈（v2,v3,v5,v7,v2），并知在此圈上边，并知在此圈上边v5,v7的权数的权数5 5为最大，在为最大，在G2中去掉边中去掉边v5,v7得图得图G3。5第十五页，本课件共有56页v1v2v3v4v6v5v733432741

15、G4 4.在在G3中找到一个圈中找到一个圈（v3,v5,v6,v7,v3），并知在此圈上边，并知在此圈上边v5,v6和和v3,v7的权数的权数4 4为最大，在为最大，在G3中去掉边中去掉边v5,v6得图得图G4。第十六页，本课件共有56页v1v2v3v4v6v5v73343271G5 5.在在G4中找到一个圈中找到一个圈（v2,v3,v7,v2），并知在此圈上边，并知在此圈上边v3,v7的权数的权数5 5为最大，在为最大，在G2中去掉边中去掉边v5,v7得图得图G3。第十七页，本课件共有56页v1v2v3v4v6v5v7333271G5 6.在在G5中已找不到任何一个圈了，可知中已找不到任何一

16、个圈了，可知G5即为图即为图G的的最小生成树。这个最小生成树的所有边的总权数为最小生成树。这个最小生成树的所有边的总权数为3+3+3+1+2+7=193+3+3+1+2+7=19。第十八页，本课件共有56页3 3 最短路问题最短路问题最短路问题是对一个赋权的有向图最短路问题是对一个赋权的有向图G（权数可能是路程的长度、（权数可能是路程的长度、花费的成本等等）中的指定的两个点花费的成本等等）中的指定的两个点Vs和和Vt找到一条从找到一条从Vs到到Vt的路，使得这条路上所有弧的权数的总和最小，这条的路，使得这条路上所有弧的权数的总和最小，这条路被称为从路被称为从Vs到到Vt的最短路，这条路上所有弧

17、的权数的总和的最短路，这条路上所有弧的权数的总和被称之为从被称之为从Vs到到Vt的距离。的距离。第十九页，本课件共有56页3.1 求解最短路的求解最短路的Dijkstra算法算法（Dijkstra algorithm,1959）Dijkstra算法也称为双标号算法。所谓双标号，也就是对图中的点算法也称为双标号算法。所谓双标号，也就是对图中的点vj赋予两个标赋予两个标号号(lj,kj)，第一个标号第一个标号lj表示从起点表示从起点vs到到vj的最短路的长度，第二个标号的最短路的长度，第二个标号kj表示在表示在vs到到vj的最短路上的最短路上vj前面一个邻点的下标。前面一个邻点的下标。1.给起点给

18、起点v1以标号以标号(0,s)表示从表示从v1到到v1的距离为的距离为0，v1为起点。为起点。2.找出已标号的点的集合找出已标号的点的集合I，没标号的点的集合，没标号的点的集合J以及弧的集合以及弧的集合(vi,vj)|viI,vI,vj jJJ，这里这个弧的集合是指所有从已标号的点到，这里这个弧的集合是指所有从已标号的点到未标号的点的弧的集合。未标号的点的弧的集合。3.3.如果上述弧的集合是空集，则计算结束。如果如果上述弧的集合是空集，则计算结束。如果v vt t已标号已标号(l(lt t,k,kt t)，则，则v vs s到到v vt t的距离即为的距离即为l lt t，而从，而从v vs

19、s到到v vt t的最短路径，则的最短路径，则可以从可以从k kt t反向追踪到起点反向追踪到起点v vs s而得到。如果而得到。如果v vt t未标号，则可以断未标号，则可以断言不存在从言不存在从v vs s到到v vt t的有向路。否则转下一步。的有向路。否则转下一步。4.4.对上述弧的集合中的每一条弧，计算对上述弧的集合中的每一条弧，计算s sijij=l=li i+c+cijij在所有的在所有的s sijij中，中，找到其值为最小的弧，不妨设此弧为找到其值为最小的弧，不妨设此弧为(v(vc c,v,vd d)，则给此弧的终点，则给此弧的终点以双标号以双标号(s(scdcd,c),c),

20、返回第返回第2 2步。步。第二十页，本课件共有56页例例1.求下图中求下图中v1到到v6的最短路。的最短路。v1v4v3v2v5v62531255173第二十一页，本课件共有56页1.给起始点给起始点v1标以标以(0,s)，表示从，表示从v1到到v1的距离为的距离为0。2.已标号点集已标号点集I=v1，未标号点集，未标号点集J=v2,v3,v4,v5,v6，弧集，弧集(vi,vj)|viI,vI,vj jJ=(vJ=(v1 1,v,v2 2),(v),(v1 1,v,v3 3),(v),(v1 1,v,v4 4)，并有，并有s s1212=l=l1 1+c+c1212=0+3=3,s=0+3=

21、3,s1313=l=l1 1+c+c1313=0+2=2,s=0+2=2,s1414=l=l1 1+c+c1414=0+5,min(s=0+5,min(s1212,s,s1313,s,s1414)=s)=s1313=2.=2.我们给弧我们给弧(v(v1 1,v,v3 3)的终点的终点v v3 3标以标以(2,1).(2,1).3.3.I=vI=v1 1,v,v3 3,J=v,J=v2 2,v,v4 4,v,v5 5,v,v6 6,弧集弧集(v(vi i,v,vj j)|v)|vi iI,vI,vj jJ=(vJ=(v1 1,v,v2 2),(v),(v1 1,v,v4 4),(v),(v3 3

22、,v,v4 4)且且s s3434=l=l3 3+c+c3434=2+1=3,min(s=2+1=3,min(s1212,s,s1414,s,s3434)=s)=s1212=s=s3434=3.=3.给弧给弧(v(v1 1,v,v2 2)的终的终点标以点标以(3,1),(3,1),弧弧(v(v3 3,v,v4 4)的终点标以的终点标以(3,3).(3,3).4.4.I=vI=v1 1,v,v2 2,v,v3 3,v,v4 4,J=v,J=v5 5,v,v6 6,弧集弧集(v(vi i,v,vj j)|v)|vi iI,vI,vj jJ=(vJ=(v2 2,v,v6 6),(v),(v4 4,v

23、,v6 6),),并有并有s s2626=l=l2 2+c+c2626=3+7=10,s=3+7=10,s4646=l=l4 4+c+c4646=3+5=8,min(s=3+5=8,min(s2626,s,s4646)=s)=s4646=8.=8.5.5.I=vI=v1 1,v,v2 2,v,v3 3,v,v4 4,v,v6 6,J=v,J=v5 5,弧集为弧集为，计算结束。，计算结束。v v5 5没有标号没有标号表明从表明从v v1 1到到v v5 5没有有向路。没有有向路。6.6.最短路径为最短路径为v v1 1 v v3 3 v v4 4 v v6 6.第二十二页，本课件共有56页例例1

24、 1的各点的标号如下的各点的标号如下(v(v1 1到到v v5 5没有有向路）没有有向路）v1v4v3v2v5v62531255173(0,s)(3,3)(8,4)(3,1)(2,1)第二十三页，本课件共有56页3.2 最短路问题的应用最短路问题的应用例例2.电信公司准备在甲、乙两地沿路架设一条光缆线，问如电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给了甲、乙两地间的交何架设使其光缆线路最短？下图给了甲、乙两地间的交通图，图中的点通图，图中的点v1,v2,.,v7表示表示7个地点，其中个地点，其中v1表示甲地，表示甲地，v7表示乙地，点之间的联线（表示乙地，点之

25、间的联线（边边）表示两地之间的公路，）表示两地之间的公路，边所赋的权数表示两地间的公路长度。边所赋的权数表示两地间的公路长度。v1甲地甲地v7乙地乙地v3v4v6v2v51510173465642第二十四页，本课件共有56页1.起始点起始点v1标号为标号为(0,s).2.I=v1,J=v2,v3,v4,v5,v6,v7,边集边集vi,vj|vi,vj中一个中一个I,另一另一个个J=v1,v2,v1,v3，且，且s12=l1+c12=0+15=15，s13=l1+c13=0+10=10，min(s12,s13)=s13=10，边，边v1,v3中未标中未标号点号点v3标以标以(10,1).3.I=

26、v1,v3,J=v2,v4,v5,v6,v7,边集边集vi,vj=v1,v2,v3,v2,v3,v5,且且s32=l3+c32=10+3=13，s35=l3+c35=10+4=14，min(s12,s32,s35)=s32=13.边边v3,v2中未中未标号的点标号的点v2标以标以(13,3).4.I=v1,v3,v2,J=v4,v5,v6,v7,边集边集vi,vj=v3,v5,v2,v4,v2,v7,且且s24=l2+c24=13+6=19,s27=l2+c27=13+17=30,min(s35,s24,s27)=s35=14.边边v3,v5中未标号的点中未标号的点v5标以标以(14,3).5

27、.I=v1,v2,v3,v5,J=v4,v6,v7,边集边集vi,vj=v2,v4,v5,v4,v2,v7,v5,v6,并有并有s54=l5+c54=14+4=18,s56=l5+c56=14+2=16,min(s24,s54,s27,s56)=s56=16.边边v5,v6中未标号的点中未标号的点v6标以标以(16,5).第二十五页，本课件共有56页6.I=v1,v2,v3,v5,v6,J=v4,v7.边集边集vi,vj=v2,v4,v2,v7,v5,v4,v6,v7,且且s67=l6+c67=16+6=22,min(s24,s27,s54,s67)=s54=18.边边v5,v4中未标号的点中

28、未标号的点v4标以标以(18,5).7.I=v1,v2,v3,v4,v5,v6,J=v7.边集边集vi,vj=v2,v7,v4,v7,v6,v7,且且s47=l4+c47=18+8=23,min(s27,s47,s67)=s67=22.边边v6,v7中未标号的点中未标号的点v7标以标以(22,6).8.此时此时I=v1,v2,v3,v4,v5,v6,v7,J=.边集合边集合vvi i,v,vj j为空集，为空集，计算结束。计算结束。9.9.从从v1到到v7的最短距离为的最短距离为22,22,其最短路径为其最短路径为v1 v3 v5 v6 v7.第二十六页，本课件共有56页例例2 2的各点标号如

29、下：的各点标号如下：v1甲地甲地v7乙地乙地v3v4v6v2v51510173465642(0,s)(18,5)(10,1)(16,5)(14,3)(13,3)(22,6)第二十七页，本课件共有56页例例3.设备更新问题设备更新问题设备更新问题设备更新问题。某公司试用一台设备，在每年年初，公司。某公司试用一台设备，在每年年初，公司就要决定是购买新设备还是继续使用旧设备。如果购置新设就要决定是购买新设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。如果继

30、续使用旧设备，可以省去购置费，但维修费用就高了。现在需要我们制定一个五年之内的更新设备计划，使得五年现在需要我们制定一个五年之内的更新设备计划，使得五年内购置费和维修总的支付费用最小。这种设备每年年初的价内购置费和维修总的支付费用最小。这种设备每年年初的价格以及使用不同时间的设备所需要的维修费如下表所示。格以及使用不同时间的设备所需要的维修费如下表所示。年份年份12345年初价格年初价格1111121213使用年数使用年数0-11-22-33-44-5每年维修每年维修费用费用5681118第二十八页，本课件共有56页 将该问题转化成求最短路问题，将该问题转化成求最短路问题，vi表示表示“第第i

31、年年初购年年初购进一台新设备进一台新设备”，对于弧，对于弧(vi,vj)，它的权数定义为从第，它的权数定义为从第i年年年年初购进设备使用到第初购进设备使用到第j-1年年底所花费的购置费及维修费的年年底所花费的购置费及维修费的总和，计算结果如下：总和，计算结果如下：ji123456116223041592162230413172331417235186第二十九页，本课件共有56页v1v2v3v4v5v6161817171623312322304159413022第三十页，本课件共有56页1.起始点起始点v1标以标以(0,s).2.I=v1,J=v2,v3,v4,v5,v6.弧集弧集(vi,vj)

32、|viI,vI,vj jJ=(vJ=(v1 1,v,v2 2),(v),(v1 1,v,v3 3),(v),(v1 1,v,v4 4),(v),(v1 1,v,v5 5),(v),(v1 1,v,v6 6)并有并有s s1212=l=l1 1+c+c1212=0+16=16,s=0+16=16,s1313=l=l1 1+c+c1313=0+22=22,s=0+22=22,s1414=l=l1 1+c+c1414=0+30=30,s=0+30=30,s1515=l=l1 1+c+c1515=0+41=41,s=0+41=41,s1616=l=l1 1+c+c1616=0+59=59,min(s=

33、0+59=59,min(s1212,s,s1313,s,s1414,s,s1515,s,s1616)=s)=s1212=16.=16.给弧给弧(v(v1 1,v,v2 2)的终点的终点v v2 2标以标以(16,1).(16,1).3.I=v1,v2,J=v3,v4,v5,v6.弧集弧集(vi,vj)|viI,vI,vj jJ=(vJ=(v1 1,v,v3 3),(v),(v1 1,v,v4 4),(v),(v1 1,v,v5 5),(v),(v1 1,v,v6 6),(v),(v2 2,v,v3 3),(v),(v2 2,v,v4 4),(v),(v2 2,v,v5 5),(v),(v2 2

34、,v,v6 6)并有并有s s2323=l=l2 2+c+c2323=16+16=32,s=16+16=32,s2424=l=l2 2+c+c2424=16+22=38,s=16+22=38,s2525=l=l2 2+c+c2525=16+30=46,s=16+30=46,s2626=l=l2 2+c+c2626=16+41=57,min(s=16+41=57,min(s1313,s,s1414,s,s1515,s,s1616,s,s2323,s,s2424,s,s2525,s,s2626)=s)=s1313=22.=22.给弧给弧(v(v1 1,v,v3 3)的终点的终点v v3 3标以标以

35、(22,1).(22,1).第三十一页，本课件共有56页4.I=v1,v2,v3,J=v4,v5,v6.弧集弧集(vi,vj)|viI,vI,vj jJ=(vJ=(v1 1,v,v4 4),),(v(v1 1,v,v5 5),(v),(v1 1,v,v6 6),(v),(v2 2,v,v4 4),(v),(v2 2,v,v5 5),(v),(v2 2,v,v6 6),(v),(v3 3,v,v4 4),(v),(v3 3,v,v5 5),(v),(v3 3,v,v6 6)并有并有s s3434=l=l3 3+c+c3434=22+17=39,s=22+17=39,s3535=l=l3 3+c+

36、c3535=22+23=45,s=22+23=45,s3636=l=l3 3+c+c3636=22+31=53,=22+31=53,min(smin(s1414,s,s1515,s,s1616,s,s2424,s,s2525,s,s2626,s,s3434,s,s3535,s,s3636)=s)=s1414=30.=30.给弧给弧(v(v1 1,v,v4 4)的终点的终点v v4 4标以标以(30,1).(30,1).5.I=v1,v2,v3,v4,J=v5,v6.弧集弧集(vi,vj)|viI,vI,vj jJ=(vJ=(v1 1,v,v5 5),),(v(v1 1,v,v6 6),(v),

37、(v2 2,v,v5 5),(v),(v2 2,v,v6 6),(v),(v3 3,v,v5 5),(v),(v3 3,v,v6 6),(v),(v4 4,v,v5 5),(v4,v),(v4,v6 6)并有并有s s4545=l=l4 4+c+c4545=30+17=47,s=30+17=47,s4646=l=l4 4+c+c4646=30+23=53,=30+23=53,min(smin(s1515,s,s1616,s,s2525,s,s2626,s,s3535,s,s3636,s,s4545,s,s4646)=s)=s1515=41.=41.给弧给弧(v(v1 1,v,v5 5)的的终点

38、终点v v5 5标以标以(41,1).(41,1).6.I=v1,v2,v3,v4,v5,J=v6.弧集弧集(vi,vj)|viI,vI,vj jJ=(vJ=(v1 1,v,v6 6),),(v(v2 2,v,v6 6),(v),(v3 3,v,v6 6),(v),(v4 4,v,v6 6),(v),(v5 5,v,v6 6)并有并有s s5656=l=l5 5+c+c5656=41+18=59,=41+18=59,min(smin(s1616,s,s2626,s,s3636,s,s4646,s,s5656)=s)=s3636=s=s4646=53.=53.给弧给弧(v(v3 3,v,v6 6

39、)和和(v(v4 4,v,v6 6)的终点的终点v v6 6标以标以(53,3)(53,3)和和(53,4).(53,4).第三十二页，本课件共有56页v1v2v3v4v5v6161817171623312322304159413022(0,s)(16,1)(30,1)(41,1)(53,4)(53,3)(22,1)第三十三页，本课件共有56页4 4 最大流问题最大流问题最大流问题：最大流问题：给了一个带收发点的网络，其每条弧的赋权称之为给了一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。收

40、点的最大流量。第三十四页，本课件共有56页4.1 最大流的数学模型最大流的数学模型例：某石油公司拥有一个管道网络，使用这个网络可例：某石油公司拥有一个管道网络，使用这个网络可以把石油从开采地运送到一些销售点。由于管道的直以把石油从开采地运送到一些销售点。由于管道的直径的变化，他的各段管道径的变化，他的各段管道(vi,vj)的流量的流量cij也不一样，如下也不一样，如下图所示。图所示。cij的单位为万加仑的单位为万加仑/小时。如果使用这个网络系统从小时。如果使用这个网络系统从开采地开采地v1向销地向销地v7运送石油，问每小时能运送多少加仑石运送石油，问每小时能运送多少加仑石油？油？v1v6v3v

41、4v5v2v761223236542第三十五页，本课件共有56页 设弧设弧(vi,vj)上的流量为上的流量为fij，网络上的总的流量为，网络上的总的流量为F，则上述，则上述问题的线性规划模型为：问题的线性规划模型为：目标函数：目标函数：max F=f12+f14约束条件：约束条件：f12=f23+f25 f14=f43+f46+f47 f23+f43=f35+f36 f25+f35=f57 f36+f46=f67 f57+f67+f47=f12+f14 fij cij,(i=1,2,.,6;j=2,.,7)fij 0,(i=1,2,.,6;j=2,.,7)第三十六页，本课件共有56页4.2 最

42、大流问题网络图论的解法最大流问题网络图论的解法1.对一条弧对一条弧(vi,vj)的容量用一对数的容量用一对数(cij,0)标在弧标在弧(vi,vj)上，上，cij表示从表示从vi到到vj容许通过的容量，容许通过的容量，0表示从表示从vj到到vi容许通过的容许通过的容量。容量。vivjvivjvivjcijvivj0cjicijcijcjicij第三十七页，本课件共有56页2.求最大流的基本算法求最大流的基本算法找出一条从发点到收点的路，在这条路上的每一条弧顺找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于流方向的容量都大于0。如果不存在这样的路，则已求。如果不存在这样的路，则

43、已求得最大流。得最大流。找出这条路上各条弧的最小的顺流的容量找出这条路上各条弧的最小的顺流的容量pf，通过这，通过这条路增加网络的流量条路增加网络的流量pf。在这条路上，减少每一条弧的顺流容量在这条路上，减少每一条弧的顺流容量pf，同时增加这些，同时增加这些弧的逆流容量弧的逆流容量pf，返回步骤，返回步骤。注意：注意：在步骤在步骤中尽量选择中尽量选择包含弧数最少包含弧数最少的路。的路。第三十八页，本课件共有56页引例的引例的Ford-Fulkerson标号算法：标号算法：(贝尔曼贝尔曼-福特算法福特算法 )第一次迭代：第一次迭代：选择路为：选择路为：v1v4 v7.弧弧(v4,v7)的顺流容量

44、为的顺流容量为2，决定了，决定了pf=2，改进的网络流量如图所示：，改进的网络流量如图所示：v1v6v3v4v5v7612232365422000000000042020v2第三十九页，本课件共有56页第二次迭代：第二次迭代：选择路为：选择路为：v1v2 v5 v7.弧弧(v2,v5)的顺流容量为的顺流容量为c25=3，决定了，决定了pf=3，改进的网络流量如图所示：，改进的网络流量如图所示：v1v6v3v4v5v7612323542200000000420233230350v2第四十页，本课件共有56页第三次迭代：第三次迭代：选择路为：选择路为：v1v4 v6 v7.弧弧(v4,v6)的顺流

45、容量为的顺流容量为c46=1，决定了决定了pf=1，改进的网络流量如图所示：，改进的网络流量如图所示：v1v6v3v4v5v7122342500000420233230363301310v2第四十一页，本课件共有56页第四次迭代：第四次迭代：选择路为：选择路为：v1v4 v3 v6 v7.弧弧(v3,v6)的顺流容量为的顺流容量为c36=2，决定了，决定了pf=2，改进的网络流量如图所示：，改进的网络流量如图所示：v1v6v3v4v5v702234261000033023323038151321020v2第四十二页，本课件共有56页第五次迭代：第五次迭代：选择路为：选择路为：v1v2 v3 v

46、5 v7.弧弧(v2,v3)的顺流容量为的顺流容量为c23=2，决定了，决定了pf=2，改进的网络流量如图所示：，改进的网络流量如图所示：v1v6v3v4v5v7022110812032150233230310105022005v2第四十三页，本课件共有56页最大流最大流如图所示：如图所示：v1v6v3v4v5v72101223252355v2第四十四页，本课件共有56页5 5 最小费用最大流问题最小费用最大流问题最小费用最大流问题：最小费用最大流问题：给了一个带收发点的网络，对每一条弧给了一个带收发点的网络，对每一条弧(vi,vj),除了给出了除了给出了容量容量cij外，还给出了这条弧的单位

47、流量的费用外，还给出了这条弧的单位流量的费用bij，要求一，要求一个最大流个最大流F,并使总运送费用最小。并使总运送费用最小。第四十五页，本课件共有56页5.1 最小费用最大流的数学模型最小费用最大流的数学模型例：在上例中，假设不同的单位流量的费用为例：在上例中，假设不同的单位流量的费用为bij，对每段管，对每段管道道(vi,vj)用用(cij,bij)表示流量和费用，如图所示。如果使用这表示流量和费用，如图所示。如果使用这个网络系统从开采地个网络系统从开采地v1向销地向销地v7运送石油，怎样运送才能运送运送石油，怎样运送才能运送最多的石油并使得总的运送费用最少？求出每小时的最大流量及最多的石

48、油并使得总的运送费用最少？求出每小时的最大流量及相应的最小费用。相应的最小费用。v1v6v3v4v5v2v7(6,6)(6,3)(3,4)(2,3)(2,4)(1,3)(3,2)(2,8)(2,5)(4,4)(5,7)第四十六页，本课件共有56页 设弧设弧(vi,vj)上的流量为上的流量为fij，网络上的总的流量为，网络上的总的流量为F，则上述，则上述问题的线性规划模型为：问题的线性规划模型为：目标函数：目标函数：min z=fij bij=6f12+3f14+4f25+5f23+2f43+4f35+7f57+3f36+3f46+8f47+4f67约束条件：约束条件：f12+f14=F=10

49、f12=f23+f25 f14=f43+f46+f47 f23+f43=f35+f36 f25+f35=f57 f36+f46=f67 f57+f67+f47=f12+f14 fij cij,(i=1,2,.,6;j=2,.,7)fij 0,(i=1,2,.,6;j=2,.,7)第四十七页，本课件共有56页5.2 最小费用最大流问题网络图论的解法最小费用最大流问题网络图论的解法1.对一条弧对一条弧(vi,vj)的容量用一对数的容量用一对数(cij,0)标在弧标在弧(vi,vj)上，上，cij表示从表示从vi到到vj容许通过的容量，容许通过的容量，0表示从表示从vj到到vi容许通过容许通过的容量

50、。的容量。vivjvivjvivj(cij,bij)(cij,bij)(0,-bij)(0,-bji)(0,-bij)(cji,bji)(cij,bij)vjvi(cji,bji)(cij,bij)第四十八页，本课件共有56页2.求最小费用最大流的基本算法求最小费用最大流的基本算法找出一条从发点到收点的路，在这条路上的每一条找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于弧顺流方向的容量都大于0。如果不存在这样的路，则已。如果不存在这样的路，则已求得最大流。求得最大流。找出这条路上各条弧的最小的顺流的容量找出这条路上各条弧的最小的顺流的容量pf，通过这条路，通过这条路增加网络