管理运筹学 第7章最短路实例

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管 理 运 筹 学,1,2,最短路问题,例 设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。,已知：设备每年年初的价格表,设备维修费如下表,年份,1,2,3,4,5,年初价格,11,11,12,12,13,使用年数,0-1,1-2,2-3,3-4,4-5,每年维修费用,5,6,8,11,18,2,2,最短路问题,解：,将问题转化为最短路问题，如下图：,用,v,i,表示“第,i,年年初购进一台新设备”,弧（,v,i,v,j,）表示第,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,3,2,最短路问题,(,继上页,),把权数赋到图中，再用,Dijkstra,算法求最短路。,最终得到下图，可知，,v,1,到,v,6,的距离是,53,，最短路径有两条：,v,1,v,3,v,6,和,v,1,v,4,v,6,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),4,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),5,3,最小生成树问题,给了一个无向图,G=(V,E),，我们保留,G,的所有点，而删掉部分,G,的边或者说保留一部分,G,的边，所获得的图,G,，称之为,G,的生成子图。在图,11-12,中，,(b),和,(c),都是,(a),的生成子图。,如果图,G,的一个生成子图还是一个树，则称这个生成子图为生成树，在图,11-12,中，,(c),就是,(a),的生成树。,最小生成树问题就是指在一个赋权的连通的无向图,G,中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。,图,11-12,(a),(b),(c),6,3,最小生成树问题,一、求解最小生成树的破圈算法,算法的步骤：,1,、在给定的赋权的连通图上任找一个圈。,2,、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。,3,、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第,1,步。,7,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,8,3,最小生成树问题,例,5,、某大学准备对其所属的,7,个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中,v,1,v,7,表示,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,9,4,最大流问题,最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。,一、最大流的数学模型,例,6,某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（,v,i,v,j,）的流量,c,ij,（容量）也是不一样的。,c,ij,的单位为万加仑,/,小时。如果使用这个网络系统从采地,v,1,向销地,v,7,运送石油，问每小时能运送多少加仑石油？,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,10,4,最大流问题,我们可以为此例题建立线性规划数学模型：,设弧,(v,i,v,j,),上流量为,f,ij,，网络上的总的流量为,F,，则有：,11,4,最大流问题,在这个线性规划模型中，其约束条件中的前,6,个方程表示了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧,(v,i,v,j,),的流量,f,ij,要满足流量的可行条件，应小于等于弧,(v,i,v,j,),的容量,c,ij,，并大于等于零，即,0,f,ij,c,ij,。我们把满足守恒条件及流量可行条件的一组网络流,f,ij,称之为可行流，（即线性规划的可行解），可行流中一组流量最大（也即发出点总流出量最大）的称之为最大流（即线性规划的最优解）。,我们把例,6,的数据代入以上线性规划模型，用,“,管理运筹学软件,”,，马上得到以下的结果：,f,12,=5,，,f,14,=5,，,f,23,=2,，,f,25,=3,，,f,43,=2,，,f,46,=1,，,f,47,=2,，,f,35,=2,，,f,36,=2,，,f,57,=5,，,f,67,=3,。最优值（最大流量）,=10,。,12,4,最大流问题,二、最大流问题网络图论的解法 对网络上弧的容量的表示作改进。为省去弧的方向，如下图,:(a),和,(b),、,(c),和,(d),的意义相同。,用以上方法对例,6,的图的容量标号作改进，得下图,v,i,v,j,v,i,v,j,c,ij,0,（,a,）,（,b,）,c,ij,c,ij,v,i,v,j,（,c,ji,）,（,c,）,v,i,v,j,c,ij,c,ji,（,d,）,6,3,5,2,2,2,4,1,2,6,3,v,1,v,2,v,5,v,7,v,4,v,3,v,6,0,0,0,0,0,0,0,0,0,0,0,13,4,最大流问题,求最大流的基本算法,（,1,）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。,（,2,）找出这条路上各条弧的最小的顺流的容量,p,f,，通过这条路增加网络的流量,p,f,。,（,3,）在这条路上，减少每一条弧的顺流容量,p,f,，同时增加这些弧的逆流容量,p,f,，返回步骤（,1,）。,用此方法对例,6,求解：,第一次迭代：选择路为,v,1,v,4,v,7,。弧（,v,4,v,7,）的顺流容量为,2,，,决定了,p,f,=2,，改进的网络流量图如下图：,6,3,5,2,2,2,4,1,2,6,3,v,1,v,2,v,5,v,7,v,4,v,3,v,6,0,0,0,0,0,0,0,0,0,0,0,4,2,0,2,14,4,最大流问题,第二次迭代：选择路为,v,1,v,2,v,5,v,7,。弧（,v,2,v,5,）的顺流容量为,3,，决定了,p,f,=3,，改进的网络流量图如下图：,第三次迭代：选择路为,v,1,v,4,v,6,v,7,。弧（,v,4,v,6,）的顺流容量为,1,，决定了,p,f,=1,，改进的网络流量图如下图：,6,3,5,2,2,2,4,1,3,v,1,v,2,v,5,v,7,v,4,v,3,v,6,0,0,0,0,0,0,0,0,4,2,0,2,2,0,3,3,3,0,3,2,2,2,4,1,3,v,1,v,2,v,5,v,7,v,4,v,3,v,6,0,0,0,0,0,0,4,2,0,2,2,0,3,3,3,3,3,0,1,3,15,第四次迭代：选择路为,v,1,v,4,v,3,v,6,v,7,。弧（,v,3,v,6,）的顺流容,量为,2,，决定了,p,f,=2,，改进的网络流量图如下图：,第五次迭代：选择路为,v,1,v,2,v,3,v,5,v,7,。弧（,v,2,v,3,）的顺流容,量为,2,，决定了,p,f,=2,，改进的网络流量图如下图：,2,2,2,4,3,v,1,v,2,v,5,v,7,v,4,v,3,v,6,1,0,0,0,0,1,2,0,3,2,0,3,3,3,5,0,3,1,2,0,0,2,3,1,3,2,2,v,1,v,2,v,5,v,7,v,4,v,3,v,6,1,0,1,2,0,2,0,3,3,3,5,0,1,2,0,2,3,1,3,1,5,0,0,2,0,2,0,5,4,最大流问题,16,经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为,10,。,最大流量图如下图：,2,2,v,1,v,2,v,5,v,7,v,4,v,3,v,6,1,2,3,5,2,2,3,5,5,4,最大流问题,“,管理运筹学软件”中还有专门的子程序用于解决最大流问题。,17,5,最小费用最大流问题,最小费用最大流问题：给了一个带收发点的网络，对每一条弧,（,v,i,v,j,），除了给出容量,c,ij,外，还给出了这条弧的单位流量的费用,b,ij,，要,求一个最大流,F,，并使得总运送费用最小。,一、最小费用最大流的数学模型,例,7,由于输油管道的长短不一，所以在例,6,中每段管道（,v,i,v,j,）除,了有不同的流量限制,c,ij,外，还有不同的单位流量的费用,b,ij,，,c,ij,的单位为万,加仑,/,小时，,b,ij,的单位为百元,/,万加仑。如图。从采地,v,1,向销地,v,7,运送石,油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流,量和最小费用。,(6,6),(3,4),(5,7),(2,5),(2,4),（,2,3,）,(4,4),(1,3),(2,8),（,3,2,）,v,1,v,2,v,5,v,7,v,4,v,3,v,6,(6,3),18,5,最小费用最大流问题,这个最小费用最大流问题也是一个线性规划的问题。,解：我们用线性规划来求解此题，可以分两步走。,第一步，先求出此网络图中的最大流量,F,，这已在例,6,中建立了线性规划的模型，通过管理运筹学软件已经获得结果。,第二步，在最大流量,F,的所有解中，找出一个最小费用的解，我们来建立第二步中的线性规划模型如下：,仍然设弧（,v,i,v,j,）上的流量为,f,ij,，这时已知网络中最大流量为,F,，只要在例,6,的约束条