单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管 理 运 筹 学,第十一章图与网络模型,1图与网络的根本概念,2最短路问题,3最小生成树问题,4最大流问题,5最小费用最大流问题,1,1图与网络的根本概念,一、图的概念,一图的定义,图论中图是由点和边构成，可以反映一些对象之间的关系。,例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图11-1就是一个表示这种关系的图。,(v,1,),赵,(v,2,)钱,(v,3,)孙,(v,4,)李,(v,5,),周,(v,6,)吴,(v,7,)陈,e,2,e,1,e,3,e,4,e,5,图11-1,2,1图与网络的根本概念,当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况以下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用图11-2来表示，可见图论中的图与几何图、工程图是不一样的。,(v,1,),赵,(v,2,)钱,孙(v,3,),李(v,4,),周(v,5,),吴(v,6,),陈(v,7,),e,2,e,1,e,3,e,4,e,5,图11-2,3,1图与网络的根本概念,a,1,a,2,a,3,a,4,a,14,a,7,a,8,a,9,a,6,a,5,a,10,a,12,a,11,a,13,a,15,(v,1,),赵,(v,2,)钱,(v,3,)孙,(v,4,)李,(v,5,),周,(v,6,)吴,(v,7,)陈,图11-3,如果我们把上面例子中的“相互认识关系改为“认识 的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图11-3就是一个反映这七人“认识关系的图。相互认识用两条反向的弧表示。,4,1图与网络的根本概念,二无向图：,由点和边构成的图，记作G=V，E。,三有向图：,由点和弧构成的图，记作D=V，A。,四连通图：,对无向图G，假设任何两个不同的点之间，至少存在一条链，那么G为连通图。,五回路：,假设路的第一个点和最后一个点相同，那么该路为回路。,六赋权图：,对一个无向图G的每一条边(vi,vj)，相应地有一个数wij，那么称图G为赋权图，wij称为边(vi,vj)上的权。,七网络：,在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。,5,2最短路问题,一、最短路问题,对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条从 Vs 到 Vt 的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。,二、求解最短路的Dijkstra算法(双标号法的步骤,1.给出点V1以标号(0,s),2.找出已标号的点的集合I，没标号的点的集合J以及弧的集合,(Vi,Vj)ViI,Vj J,3.如果上述弧的集合是空集，那么计算结束。如果vt已标号lt,kt，那么 vs到vt的距离为lt，而从 vs到vt的最短路径，那么可以从kt 反向追踪到起点vs 而得到。如果vt 未标号，那么可以断言不存在从 vs到vt的有向路。如果上述的弧的集合不是空集，那么转下一步。,4.对上述弧的集合中的每一条弧，计算 sij=li+cij。在所有的 sij中，找到其值为最小的弧。不妨设此弧为Vc,Vd，那么给此弧的终点以双标号scd,c,返回步骤2。,6,2最短路问题,例1 求以下图中v1到v6的最短路,v,2,3,5,2,7,5,3,1,5,1,2,v,1,v,6,v,5,v,3,v,4,(3,1),v,2,3,5,2,7,5,3,1,5,1,2,V,1,（0,s),v,5,(8,4),v,6,(2,1),v,3,(3,3),v,4,解：采用Dijkstra算法，各点的标号图如下：,由左图可知最短路径为v1v3,v4,v6，最短路径的长度为8。,7,2最短路问题,例2 电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？以下图给出了甲乙两地间的交通图。权数表示两地间公路的长度单位：公里。,V,1,（甲地）,15,17,6,2,4,4,4,3,10,6,5,v,2,V,7,（乙地）,v,3,v,4,v,5,v,6,8,2最短路问题,解：这是一个求无向图的最短路的问题。可以把无向图的每一边vi,vj都用方向相反的两条弧vi,vj和vj,vi代替，就化为有向图，即可用Dijkstra算法来求解。也可直接在无向图中用Dijkstra算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。,9,2最短路问题,每点的标号见以下图：,0,s,V1,甲地,15,17,6,2,4,4,3,10,6,5,(13,3),v,2,(22,6),V7 乙地,V,5,(14,3),V,6,(16,5),V,3,(10,1),V,4,(18,5),例2最终解得：最短路径v,1,v,3,v,5,v,6,v,7,，最短光缆需要22公里。,10,2最短路问题,例3 设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购置新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的方案，使得五年内购置费用和维修费用总的支付费用最小。,：设备每年年初的价格表如下：,年份,1,2,3,4,5,年初价格,11,11,12,12,13,使用年数,第1年,第2年,第3年,第4年,第5年,每年维修费用,5,6,8,11,18,设备维修费如下表：,11,2最短路问题,解：用vi表示“第i年年初购进一台新设备,弧vi,vj表示第i年年初购进的设备一直使用到第j年年初。将问题转化为最短路问题，如以下图：,v,1,v,2,v,3,v,4,v,5,v,6,1,2,3,4,5,6,1,16,22,30,41,59,2,16,22,30,41,3,17,23,31,4,17,23,5,18,6,把所有弧的权数计算如下表：,12,2最短路问题,(继上页)把权数赋到图中，再用Dijkstra算法求最短路。,v,1,v,2,v,3,v,4,v,5,v,6,16,22,30,41,59,16,22,30,41,31,23,17,18,17,23,V,1,（0,s）,v,3,v,4,(41,1),v,5,v,6,22,30,41,59,16,(22,1),30,41,31,23,17,18,17,23,V,2,（16,1）,16,(30,1),(53,3),(53,4),可知，v,1,到v,6,的距离是53，最短路径有两条：v,1,v,3,v,6,和 v,1,v,4,v,6,，即最少费用为53。,各点的标号如以下图所示：,13,3最小生成树问题,一、树的概念,一树的定义,树是图论中的重要概念，所谓树就是一个无圈的连通图。,图11-11中，(a)就是一个树，而(b)因为图中有圈所以就不是树，(c)因为不连通所以也不是树。,图11-11,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,9,v,1,v,2,v,3,v,5,v,8,v,7,v,6,v,4,v,1,v,2,v,3,v,4,v,5,v,7,v,6,v,8,v,9,(a),(b),(c),14,3最小生成树问题,二生成子图,给了一个无向图G=(V,E)，我们保存G的所有点，而删掉局部G的边或者说保存一局部G的边，所获得的图，称之为G的生成子图。在图11-12中，(b)和(c)都是(a)的生成子图。,三生成树,如果图G的一个生成子图还是一个树，那么称这个生成子图为生成树，在图11-12中，(c)就是(a)的生成树。,图11-12,(a),(b),(c),15,3最小生成树问题,二、最小生成树问题,最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。,三、求解最小生成树的破圈算法,算法的步骤：,一在给定的赋权的连通图上找一个含有最大边的圈。,二在所找的圈中去掉一个权数最大的边如果有两条或两条以上的边都是权数最大的边，那么任意去掉其中一条。,三如果所余下的图已不包含圈，那么计算结束，所余下的图即为最小生成树，否那么返回第1步。,16,3最小生成树问题,例4 用破圈算法求图a中的一个最小生成树,v,1,3,3,1,7,2,8,5,4,10,3,4,v,7,v,6,v,5,v,4,v,2,v,1,3,3,1,7,2,8,5,4,3,4,v,7,v,6,v,5,v,4,v,2,v,1,3,3,7,2,5,4,3,4,v,7,v,6,v,5,v,4,v,2,v,3,v,3,v,3,1,v,1,3,3,7,2,4,3,4,v,7,v,6,v,5,v,4,v,2,v,3,1,v,1,3,3,7,2,3,4,v,7,v,6,v,5,v,4,v,2,v,3,1,v,1,3,3,7,2,3,v,7,v,6,v,5,v,4,v,2,v,3,1,(a),(b),(c),(d),(e),(f),图11-13,17,3最小生成树问题,例5、某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如以下图，图中v1,v7 表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。,解：此问题实际上是求图11-14的最小生成树，这在例4中已经求得，也即按照图11-13的(f)设计，可使此网络的总的线路长度为最短，为19百米。,“管理运筹学软件有专门的子程序可以解决最小生成树问题。,v,1,3,3,1,7,2,8,5,4,10,3,4,v,7,v,6,v,5,v,4,v,2,v,3,图11-14,18,4最大流问题,一、最大流问题,给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。,二、最大流的数学模型,例6 某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一局部如以下图所示。由于管道的直径的变化，它的各段管道vi,vj的流量cij容量也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地 v1向销地 v7运送石油，问每小时能运送多少加仑石油？,v,5,6,3,5,2,2,2,4,1,2,6,3,v,1,v,2,v,7,v,4,v,3,v,6,图11-26,v,5,19,4最大流问题,我们可以为此例题建立线性规划数学模型：,设弧(vi,vj)上流量为fij，网络上的总的流量为F，那么有：,20,4最大流问题,在这个线性规划模型中，其约束条件中的前6个方程表示了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧(vi,vj)的流量fij要满足流量的可行条件，应小于等于弧(vi,vj)的容量cij，并大于等于零，即0fij cij。我们把满足守恒条件及流量可行条件的一组网络流 fij称之为可行流，即线性规划的可行解，可行流中一组流量最大也即发出点总流出量最大的称之为最大流即线性规划的最优解。,我们把例6的数据代入以上线性规划模型，用“管理运筹学软件，马上得到以下的结果：f12=5，f14=5，f23=2，f25=3，f43=2，f46=1，f47=2，f35=2，f36=2，f57=5，f67=3。最优值最大流量=10。,21,4最大流问题,三、最大流问题网络图论的解法一 对网络上弧的容量的表示作改进。,为省去弧的方向，如以下图:(a)和(b)、(c)和(d)的意义相同。,v,i,v,j,v,i,v,j,c,ij,0,a,b,c,ij,c,ij,v,i,v,j,cji,c,v,i,v,j,c,ij,c,ji,d,6,3,