运筹学图与网络模型.ppt

《运筹学图与网络模型.ppt》由会员分享，可在线阅读，更多相关《运筹学图与网络模型.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、与有向图边都没有方向的图称为无向图，如图边都没有方向的图称为无向图，如图1在无向图中在无向图中 eij=eji，或，或(vi,vj)=(vj,vi)当边都有方向时，称为有向图，用当边都有方向时，称为有向图，用G(V,A)表示表示在有向图中，有向边又称为在有向图中，有向边又称为弧弧，用，用 aij表示，表示，i,j 的顺序是不能的顺序是不能颠倒的，图中弧的方向用箭头标识颠倒的，图中弧的方向用箭头标识图中既有边又有弧，称为混合图图中既有边又有弧，称为混合图现在学习的是第4页，共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)现在学习的是第5页，共56页 1.3 端点，关联边，相邻，次端点，关联边，相邻，次有向图中，由节点指向外的弧的数目称为正次数，记为有向图中，由节点指向外的弧的数目称为正次数，记为 d+，指向该节点的弧的数目称为负次数，记

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

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

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

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

10、次数为 1 的点的点具有具有 n 个节点的树个节点的树 T 的边恰好为的边恰好为 n 1 条，反之，任何有条，反之，任何有n 个节点，个节点，n 1 条边的连通图必是一棵树条边的连通图必是一棵树 2.2 图的生成树图的生成树树树 T 是连通图是连通图 G 的的生成树生成树(spanning tree)，若，若 T 是是 G的子的子图且包含图图且包含图 G 的所有的节点；包含图的所有的节点；包含图 G 中部分指定节点中部分指定节点的树称为的树称为 steiner tree现在学习的是第9页，共56页 2.3 最小生成树最小生成树有有n 个乡村，各村间道路的长度是已知的，如何个乡村，各村间道路的长

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

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

13、v,v7 7表示表示7 7个学院办公室，图中的边为可能联网的路径，边上所赋的权数为个学院办公室，图中的边为可能联网的路径，边上所赋的权数为这条路线的长度，单位为百米。请设计一个网络能连通这条路线的长度，单位为百米。请设计一个网络能连通7 7个学院个学院办公室，并使总的线路长度最短。办公室，并使总的线路长度最短。v1v2v3v4v6v5v7103343278541G现在学习的是第12页，共56页v1v2v3v4v6v5v7103343278541G1 1.在在G中找到一个圈中找到一个圈（v1,v7,v6,v1），并知在此圈上边，并知在此圈上边v1,v6的权数的权数1010为最大，在为最大，在G中

14、去掉边中去掉边v1,v6得图得图G1。现在学习的是第13页，共56页v1v2v3v4v6v5v7334327541G2 2.在在G1中找到一个圈中找到一个圈（v3,v4,v5,v7,v3），并知在此圈上边，并知在此圈上边v4,v5的权数的权数8 8为最大，在为最大，在G1中去掉边中去掉边v4,v5得图得图G2。8现在学习的是第14页，共56页v1v2v3v4v6v5v733432741G3 3.在在G2中找到一个圈中找到一个圈（v2,v3,v5,v7,v2），并知在此圈上边，并知在此圈上边v5,v7的权数的权数5 5为最大，在为最大，在G2中去掉边中去掉边v5,v7得图得图G3。5现在学习的是

15、第15页，共56页v1v2v3v4v6v5v733432741G4 4.在在G3中找到一个圈中找到一个圈（v3,v5,v6,v7,v3），并知在此圈上边，并知在此圈上边v5,v6和和v3,v7的权数的权数4 4为最大，在为最大，在G3中去掉边中去掉边v5,v6得图得图G4。现在学习的是第16页，共56页v1v2v3v4v6v5v73343271G5 5.在在G4中找到一个圈中找到一个圈（v2,v3,v7,v2），并知在此圈上边，并知在此圈上边v3,v7的权数的权数5 5为最大，在为最大，在G2中去掉边中去掉边v5,v7得图得图G3。现在学习的是第17页，共56页v1v2v3v4v6v5v733

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

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

18、j的最短路上的最短路上vj前面一个邻点的下标。前面一个邻点的下标。1.给起点给起点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 v

19、s s到到v vt t的距离即为的距离即为l lt t，而从，而从v vs 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)，

20、则给此弧的终点以双标号，则给此弧的终点以双标号(s(scdcd,c),c),返回第返回第2 2步。步。现在学习的是第20页，共56页例例1.求下图中求下图中v1到到v6的最短路。的最短路。v1v4v3v2v5v62531255173现在学习的是第21页，共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)

21、，并有，并有s s1212=l=l1 1+c+c1212=0+3=3,s=0+3=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=

22、(v1 1,v,v2 2),),(v(v1 1,v,v4 4),(v),(v3 3,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

23、iI,vI,vj jJ=(vJ=(v2 2,v,v6 6),),(v(v4 4,v,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

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

25、点，其中个地点，其中v1表示甲地，表示甲地，v7表示乙地，表示乙地，点之间的联线（点之间的联线（边边）表示两地之间的公路，边所赋的权数表示）表示两地之间的公路，边所赋的权数表示两地间的公路长度。两地间的公路长度。v1甲地甲地v7乙地乙地v3v4v6v2v51510173465642现在学习的是第24页，共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

26、)=s13=10，边，边v1,v3中未标号点中未标号点v3标以标以(10,1).3.I=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,s

27、27)=s35=14.边边v3,v5中未标号的点中未标号的点v5标以标以(14,3).5.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).现在学习的是第25页，共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=

28、22,min(s24,s27,s54,s67)=s54=18.边边v5,v4中未标号的点中未标号的点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,其最短路径为其

29、最短路径为v1 v3 v5 v6 v7.现在学习的是第26页，共56页例例2 2的各点标号如下：的各点标号如下：v1甲地甲地v7乙地乙地v3v4v6v2v51510173465642(0,s)(18,5)(10,1)(16,5)(14,3)(13,3)(22,6)现在学习的是第27页，共56页例例3.设备更新问题设备更新问题设备更新问题设备更新问题。某公司试用一台设备，在每年年初，公司就。某公司试用一台设备，在每年年初，公司就要决定是购买新设备还是继续使用旧设备。如果购置新设备，要决定是购买新设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果就要支付一

30、定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。现继续使用旧设备，可以省去购置费，但维修费用就高了。现在需要我们制定一个五年之内的更新设备计划，使得五年内在需要我们制定一个五年之内的更新设备计划，使得五年内购置费和维修总的支付费用最小。这种设备每年年初的价格购置费和维修总的支付费用最小。这种设备每年年初的价格以及使用不同时间的设备所需要的维修费如下表所示。以及使用不同时间的设备所需要的维修费如下表所示。年份年份12345年初价格年初价格1111121213使用年数使用年数0-11-22-33-44-5每年维修每年维修费用费用5681118现在学习的是

31、第28页，共56页 将该问题转化成求最短路问题，将该问题转化成求最短路问题，vi表示表示“第第i年年初购进一台年年初购进一台新设备新设备”，对于弧，对于弧(vi,vj)，它的权数定义为从第，它的权数定义为从第i年年初购进设备年年初购进设备使用到第使用到第j-1年年底所花费的购置费及维修费的总和，计算结果年年底所花费的购置费及维修费的总和，计算结果如下：如下：ji123456116223041592162230413172331417235186现在学习的是第29页，共56页v1v2v3v4v5v6161817171623312322304159413022现在学习的是第30页，共56页1.起始

32、点起始点v1标以标以(0,s).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),(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+

33、41=41,s=0+41=41,s1616=l=l1 1+c+c1616=0+59=59,min(s=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,

34、v3 3),(v),(v2 2,v,v4 4),(v),(v2 2,v,v5 5),(v),(v2 2,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)=

35、s)=s1313=22.=22.给弧给弧(v(v1 1,v,v3 3)的终点的终点v v3 3标以标以(22,1).(22,1).现在学习的是第31页，共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 s343

36、4=l=l3 3+c+c3434=22+17=39,s=22+17=39,s3535=l=l3 3+c+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)|v

37、iI,vI,vj jJ=(vJ=(v1 1,v,v5 5),),(v(v1 1,v,v6 6),(v),(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,s4

38、545,s,s4646)=s)=s1515=41.=41.给弧给弧(v(v1 1,v,v5 5)的终的终点点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,min(s=41+18=59,min(s1616,s,s2626,s,s3636,s,s4646

39、,s,s5656)=s)=s3636=s=s4646=53.=53.给弧给弧(v(v3 3,v,v6 6)和和(v(v4 4,v,v6 6)的终点的终点v v6 6标以标以(53,3)(53,3)和和(53,4).(53,4).现在学习的是第32页，共56页v1v2v3v4v5v6161817171623312322304159413022(0,s)(16,1)(30,1)(41,1)(53,4)(53,3)(22,1)现在学习的是第33页，共56页4 4 最大流问题最大流问题最大流问题：最大流问题：给了一个带收发点的网络，其每条弧的赋权称之为给了一个带收发点的网络，其每条弧的赋权称之为容量，

40、在不超过每条弧的容量的前提下，求出从发点到容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。收点的最大流量。现在学习的是第34页，共56页4.1 最大流的数学模型最大流的数学模型例：某石油公司拥有一个管道网络，使用这个网络可以把石油从例：某石油公司拥有一个管道网络，使用这个网络可以把石油从开采地运送到一些销售点。由于管道的直径的变化，他的各段管开采地运送到一些销售点。由于管道的直径的变化，他的各段管道道(vi,vj)的流量的流量cij也不一样，如下图所示。也不一样，如下图所示。cij的单位为万加仑的单位为万加仑/小时。如果使用这个网络系统从开采地小时。如果使用这个网络系统从开采地

41、v1向销地向销地v7运送石运送石油，问每小时能运送多少加仑石油？油，问每小时能运送多少加仑石油？v1v6v3v4v5v2v761223236542现在学习的是第35页，共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,

42、.,6;j=2,.,7)fij 0,(i=1,2,.,6;j=2,.,7)现在学习的是第36页，共56页4.2 最大流问题网络图论的解法最大流问题网络图论的解法1.对一条弧对一条弧(vi,vj)的容量用一对数的容量用一对数(cij,0)标在弧标在弧(vi,vj)上，上，cij表表示从示从vi到到vj容许通过的容量，容许通过的容量，0表示从表示从vj到到vi容许通过的容量。容许通过的容量。vivjvivjvivjcijvivj0cjicijcijcjicij现在学习的是第37页，共56页2.求最大流的基本算法求最大流的基本算法找出一条从发点到收点的路，在这条路上的每一条弧顺流方找出一条从发点到收

43、点的路，在这条路上的每一条弧顺流方向的容量都大于向的容量都大于0。如果不存在这样的路，则已求得最大流。如果不存在这样的路，则已求得最大流。找出这条路上各条弧的最小的顺流的容量找出这条路上各条弧的最小的顺流的容量pf，通过这条，通过这条路增加网络的流量路增加网络的流量pf。在这条路上，减少每一条弧的顺流容量在这条路上，减少每一条弧的顺流容量pf，同时增加这些弧的，同时增加这些弧的逆流容量逆流容量pf，返回步骤，返回步骤。注意：注意：在步骤在步骤中尽量选择中尽量选择包含弧数最少包含弧数最少的路。的路。现在学习的是第38页，共56页引例的引例的Ford-Fulkerson标号算法：标号算法：(贝尔曼

44、贝尔曼-福特算法福特算法 )第一次迭代：第一次迭代：选择路为：选择路为：v1v4 v7.弧弧(v4,v7)的顺流容量为的顺流容量为2，决定了，决定了pf=2，改进的网络流量如图所示：，改进的网络流量如图所示：v1v6v3v4v5v7612232365422000000000042020v2现在学习的是第39页，共56页第二次迭代：第二次迭代：选择路为：选择路为：v1v2 v5 v7.弧弧(v2,v5)的顺流容量为的顺流容量为c25=3，决，决定了定了pf=3，改进的网络流量如图所示：，改进的网络流量如图所示：v1v6v3v4v5v7612323542200000000420233230350v

45、2现在学习的是第40页，共56页第三次迭代：第三次迭代：选择路为：选择路为：v1v4 v6 v7.弧弧(v4,v6)的顺流容量为的顺流容量为c46=1，决定，决定了了pf=1，改进的网络流量如图所示：，改进的网络流量如图所示：v1v6v3v4v5v7122342500000420233230363301310v2现在学习的是第41页，共56页第四次迭代：第四次迭代：选择路为：选择路为：v1v4 v3 v6 v7.弧弧(v3,v6)的顺流容量为的顺流容量为c36=2，决定了决定了pf=2，改进的网络流量如图所示：，改进的网络流量如图所示：v1v6v3v4v5v702234261000033023

46、323038151321020v2现在学习的是第42页，共56页第五次迭代：第五次迭代：选择路为：选择路为：v1v2 v3 v5 v7.弧弧(v2,v3)的顺流容量为的顺流容量为c23=2，决定了，决定了pf=2，改进的网络流量如图所示：，改进的网络流量如图所示：v1v6v3v4v5v7022110812032150233230310105022005v2现在学习的是第43页，共56页最大流最大流如图所示：如图所示：v1v6v3v4v5v72101223252355v2现在学习的是第44页，共56页5 5 最小费用最大流问题最小费用最大流问题最小费用最大流问题：最小费用最大流问题：给了一个带收

47、发点的网络，对每一条弧给了一个带收发点的网络，对每一条弧(vi,vj),除了给出了容除了给出了容量量cij外，还给出了这条弧的单位流量的费用外，还给出了这条弧的单位流量的费用bij，要求一个，要求一个最大流最大流F,并使总运送费用最小。并使总运送费用最小。现在学习的是第45页，共56页5.1 最小费用最大流的数学模型最小费用最大流的数学模型例：在上例中，假设不同的单位流量的费用为例：在上例中，假设不同的单位流量的费用为bij，对每段管道，对每段管道(vi,vj)用用(cij,bij)表示流量和费用，如图所示。如果使用这个网络系表示流量和费用，如图所示。如果使用这个网络系统从开采地统从开采地v1

48、向销地向销地v7运送石油，怎样运送才能运送最多的石油运送石油，怎样运送才能运送最多的石油并使得总的运送费用最少？求出每小时的最大流量及相应的最小并使得总的运送费用最少？求出每小时的最大流量及相应的最小费用。费用。v1v6v3v4v5v2v7(6,6)(6,3)(3,4)(2,3)(2,4)(1,3)(3,2)(2,8)(2,5)(4,4)(5,7)现在学习的是第46页，共56页 设弧设弧(vi,vj)上的流量为上的流量为fij，网络上的总的流量为，网络上的总的流量为F，则上述问，则上述问题的线性规划模型为：题的线性规划模型为：目标函数：目标函数：min z=fij bij=6f12+3f14+

49、4f25+5f23+2f43+4f35+7f57+3f36+3f46+8f47+4f67约束条件：约束条件：f12+f14=F=10 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)现在学习的是第47页，共56页5.2 最小费用最大流问题网络图论的解法最小费用最大流问题网络图论的解法1.对一条弧对一条弧(vi,vj)的容量用一对数的容量用一对数(cij,0)标在弧标

50、在弧(vi,vj)上，上，cij表表示从示从vi到到vj容许通过的容量，容许通过的容量，0表示从表示从vj到到vi容许通过的容量。容许通过的容量。vivjvivjvivj(cij,bij)(cij,bij)(0,-bij)(0,-bji)(0,-bij)(cji,bji)(cij,bij)vjvi(cji,bji)(cij,bij)现在学习的是第48页，共56页2.求最小费用最大流的基本算法求最小费用最大流的基本算法找出一条从发点到收点的路，在这条路上的每一条弧顺流方找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于向的容量都大于0。如果不存在这样的路，则已求得最大。如果不存在