《管理运筹学 第7章最短路实例.ppt》由会员分享，可在线阅读，更多相关《管理运筹学 第7章最短路实例.ppt（30页珍藏版）》请在三一文库上搜索。
1、1,2最短路问题,例 设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。 已知：设备每年年初的价格表 设备维修费如下表,2,2最短路问题,解： 将问题转化为最短路问题，如下图： 用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。 把所有弧的权数计算如下表：,3,2最短路问题,(继上页) 把权数赋到图中，再
2、用Dijkstra算法求最短路。 最终得到下图，可知，v1到v6的距离是53，最短路径有两条： v1 v3 v6和 v1 v4 v6,4,3最小生成树问题,树是图论中的重要概念，所谓树就是一个无圈的连通图。,图11-11中，(a)就是一个树，而(b)因为图中有圈所以就不是树， (c)因为不连通所以也不是树。,5,3最小生成树问题,给了一个无向图G=(V,E)，我们保留G的所有点，而删掉部分G的边或者说保留一部分G的边，所获得的图G，称之为G的生成子图。在图11-12中，(b)和(c)都是(a)的生成子图。 如果图G的一个生成子图还是一个树，则称这个生成子图为生成树，在图11-12中，(c)就是
3、(a)的生成树。 最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。,(a),(b),(c),6,3最小生成树问题,一、求解最小生成树的破圈算法 算法的步骤： 1、在给定的赋权的连通图上任找一个圈。 2、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。 3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。,7,3最小生成树问题,例4 用破圈算法求图（a）中的一个最小生成树,图11-13,8,3最小生成树问题,例5、某大学准备对其所属的7个学院办公室计算机联网
4、，这个网络的可能联通的途径如下图，图中v1,v7 表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。,解：此问题实际上是求图11-14的最小生成树，这在例4中已经求得，也即按照图11-13的(f)设计，可使此网络的总的线路长度为最短，为19百米。 “管理运筹学软件”有专门的子程序可以解决最小生成树问题。,9,4最大流问题,最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。 一、最大流的数学模型 例6 某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所
5、示。由于管道的直径的变化，它的各段管道（vi,vj）的流量cij（容量）也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地 v1向销地 v7运送石油，问每小时能运送多少加仑石油？,v5,10,4最大流问题,我们可以为此例题建立线性规划数学模型： 设弧(vi,vj)上流量为fij，网络上的总的流量为F，则有：,11,4最大流问题,在这个线性规划模型中，其约束条件中的前6个方程表示了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧(vi,vj)的流量fij要满足流量的可行条件，应
6、小于等于弧(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。,12,4最大流问题,二、最大流问题网络图论的解法 对网络上弧的容量的表示作改进。为省去弧的方向，如下图: (a)
7、和 (b)、(c)和(d)的意义相同。 用以上方法对例6的图的容量标号作改进，得下图,vi,vj,vi,vj,cij,0,（a）,（b）,cij,cij,vi,vj,（cji）,（c）,vi,vj,cij,cji,（d）,13,4最大流问题,求最大流的基本算法 （1）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。 （2）找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络的流量pf。 （3）在这条路上，减少每一条弧的顺流容量pf ，同时增加这些弧的逆流容量pf，返回步骤（1）。 用此方法对例6求解： 第一次迭代：选择路为v1
8、 v4 v7 。弧（ v4 , v7 ）的顺流容量为2， 决定了pf=2，改进的网络流量图如下图：,14,4最大流问题,第二次迭代：选择路为v1 v2 v5 v7 。弧（ v2 , v5 ）的顺流容量为 3，决定了pf=3，改进的网络流量图如下图： 第三次迭代：选择路为v1 v4 v6 v7 。弧（ v4 , v6 ）的顺流容量为 1，决定了pf=1，改进的网络流量图如下图：,15,第四次迭代：选择路为v1 v4 v3 v6 v7 。弧（ v3 , v6 ）的顺流容 量为2，决定了pf=2，改进的网络流量图如下图： 第五次迭代：选择路为v1 v2 v3 v5 v7 。弧（ v2 , v3 ）的
9、顺流容 量为2，决定了pf=2，改进的网络流量图如下图：,4最大流问题,16,经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为10。 最大流量图如下图：,4最大流问题,“管理运筹学软件”中还有专门的子程序用于解决最大流问题。,17,5最小费用最大流问题,最小费用最大流问题：给了一个带收发点的网络，对每一条弧 （vi,vj），除了给出容量cij外，还给出了这条弧的单位流量的费用bij，要 求一个最大流F，并使得总运送费用最小。 一、最小费用最大流的数学模型 例7 由于输油管道的长短不一，所以在例6中每段管道（ vi,vj ）除 了有不
10、同的流量限制cij外，还有不同的单位流量的费用bij ，cij的单位为万 加仑/小时， bij的单位为百元/万加仑。如图。从采地 v1向销地 v7运送石 油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流 量和最小费用。,(6,6),(3,4),(5,7),(2,5),(2,4),（2,3）,(4,4),(1,3),(2,8),（3,2）,v1,v2,v5,v7,v4,v3,v6,(6,3),18,5最小费用最大流问题,这个最小费用最大流问题也是一个线性规划的问题。 解：我们用线性规划来求解此题，可以分两步走。 第一步，先求出此网络图中的最大流量F，这已在例6中建立了线性规划的模
11、型，通过管理运筹学软件已经获得结果。 第二步，在最大流量F的所有解中，找出一个最小费用的解，我们来建立第二步中的线性规划模型如下： 仍然设弧（vi,vj）上的流量为fij，这时已知网络中最大流量为F，只要在例6的约束条件上，再加上总流量必须等于F的约束条件：f12=f14=F,即得此线性规划的约束条件，此线性规划的目标函数显然是求其流量的最小费用 。 由此得到线性规划模型如下：,19,5最小费用最大流问题,20,5最小费用最大流问题,用管理运筹学软件，可求得如下结果：f12=4,f14=6, f25=3,f23=1,f43=3,F57=5,f36=2,f46=1,f47=2,f67=3,f35
12、=2。其最优值(最小费用)=145。对照前面例6的结果，可对最小费用最大流的概念有一个深刻的理解。 如果我们把例7的问题改为：每小时运送6万加仑的石油从采地v1到销地v7最小费用是多少？应怎样运送？这就变成了一个最小费用流的问题。一般来说，所谓最小费用流的问题就是：在给定了收点和发点并对每条弧(vi,vj)赋权以容量cij及单位费用bij的网络中，求一个给定值f的流量的最小费用，这个给定值f的流量应小于等于最大流量F，否则无解。求最小费用流的问题的线性规划的模型只要把最小费用最大流模型中的约束条件中的发点流量F改为f即可。在例6中只要把f12+f14=F改为f12+f14=f=6得到了最小费用
13、流的线性规划的模型了。,21,5最小费用最大流问题,二、最小费用最大流的网络图论解法 对网络上弧（vi,vj）的（cij,bij）的表示作如下改动，用(b)来表示(a)。 用上述方法对例7中的图形进行改进，得图如下页：,vi,vj,vi,vj,（cij,bij ）,（0,-bij ）,（a）,（b）,（cij,bij ）,（cij,bij ）,vi,vj,（cji,bji ）,（cij,bij ）,vi,vj,（cji,bji ）,（0,-bji),（0,-bji),（c）,（d）,22,5最小费用最大流问题,求最小费用最大流的基本算法 在对弧的标号作了改进的网络图上求最小费用最大流的基本算法
14、与求 最大流的基本算法完全一样，不同的只是在步骤（1）中要选择一条总的 单位费用最小的路，而不是包含边数最小的路。,23,5最小费用最大流问题,用上述方法对例7求解： 第一次迭代：找到最短路v1 v4 v6 v7。第一次迭代后总流量为1，总 费用10。,v5,24,5最小费用最大流问题,第二次迭代：找到最短路v1 v4 v7。第二次迭代后总流量为3，总费用 32。,25,5最小费用最大流问题,第三次迭代：找到最短路v1 v4 v3 v6 v7 。第三次迭代后总流量为 5，总费用56。,26,5最小费用最大流问题,第四次迭代：找到最短路v1 v4 v3 v5 v7 。第四次迭代后总流量为 6，总
15、费用72。,27,5最小费用最大流问题,第五次迭代：找到最短路v1 v2 v5 v7 。第五次迭代后总流量为9，总 费用123。,28,5最小费用最大流问题,第六次迭代：找到最短路v1 v2 v3 v5 v7 。第六次迭代后总流量为 10，总费用145。已经找不到从v1到v7的每条弧容量都大于零的路了，故 已求得最小费用最大流了。,29,5最小费用最大流问题,如果对例7求一个最小费用流的问题：每小时运送6万加仑石油从v1到v7的最小费用是多少，或者每小时运送7万加仑呢？我们可以从第四次迭代及图11-32即可得到运送6万加仑最小费用72百元，其运送方式通过比较图11-28及图11-32即得图11-36所示。 至于每小时运送7万加仑，我们可以在图11-36的基础上，再按第五次迭代所选的最短路运送1万加仑即得最小费用：72+1*17=89百元，其运送方式如图11-37所示。,30,5最小费用最大流问题,注：“管理运筹学软件”有专门的子程序用于解决这类问题。,