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

§2最短路问题例设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购置新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的方案，使得五年内购置费用和维修费用总的支付费用最小。：设备每年年初的价格表设备维修费如下表年份12345年初价格1111121213使用年数0-11-22-33-44-5每年维修费用56811181整理课件§2最短路问题解：将问题转化为最短路问题，如以下图：用vi表示“第i年年初购进一台新设备〞,弧〔vi,vj〕表示第i年年初购进的设备一直使用到第j年年初。把所有弧的权数计算如下表：v1v2v3v4v5v61234561162230415921622304131723314172351862整理课件§2最短路问题(继上页)把权数赋到图中，再用Dijkstra算法求最短路。最终得到以下图，可知，v1到v6的距离是53，最短路径有两条：v1v3v6和v1v4v6v1v2v3v4v5v6162230415916223041312317181723V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723V2（16,1）16(30,1)(53,3)(53,4)3整理课件§3最小生成树问题树是图论中的重要概念，所谓树就是一个无圈的连通图。

图11-11中，(a)就是一个树，而(b)因为图中有圈所以就不是树，(c)因为不连通所以也不是树。图11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)4整理课件§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)5整理课件§3最小生成树问题一、求解最小生成树的破圈算法算法的步骤：1、在给定的赋权的连通图上任找一个圈。2、在所找的圈中去掉一个权数最大的边〔如果有两条或两条以上的边都是权数最大的边，那么任意去掉其中一条〕。3、如果所余下的图已不包含圈，那么计算结束，所余下的图即为最小生成树，否那么返回第1步。6整理课件§3最小生成树问题例4用破圈算法求图〔a〕中的一个最小生成树v1331728541034v7v6v5v4v27v6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31(a)(b)(c)(d)(e)(f)图11-137整理课件§3最小生成树问题例5、某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如以下图，图中v1,…,v7表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。解：此问题实际上是求图11-14的最小生成树，这在例4中已经求得，也即按照图11-13的(f)设计，可使此网络的总的线路长度为最短，为19百米。“管理运筹学软件〞有专门的子程序可以解决最小生成树问题。v1331728541034v7v6v5v4v2v3图11-148整理课件§4最大流问题最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。一、最大流的数学模型例6某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一局部如以下图所示。由于管道的直径的变化，它的各段管道〔vi,vj〕的流量cij〔容量〕也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地v1向销地v7运送石油，问每小时能运送多少加仑石油？v563522241263v1v2v7v4v3v6图11-269整理课件§4最大流问题

我们可以为此例题建立线性规划数学模型：设弧(vi,vj)上流量为fij，网络上的总的流量为F，那么有：10整理课件§4最大流问题

在这个线性规划模型中，其约束条件中的前6个方程表示了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧(vi,vj)的流量fij要满足流量的可行条件，应小于等于弧(vi,vj)的容量cij，并大于等于零，即0≤fij≤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。11整理课件

§4最大流问题二、最大流问题网络图论的解法

对网络上弧的容量的表示作改进。为省去弧的方向，如以下图:(a)和(b)、(c)和(d)的意义相同。

用以上方法对例6的图的容量标号作改进，得以下图vivjvivjcij0〔a〕〔b〕cijcijvivj〔cji〕〔c〕vivjcijcji〔d〕63522241263v1v2v5v7v4v3v60000000000012整理课件

§4最大流问题求最大流的根本算法〔1〕找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，那么已经求得最大流。〔2〕找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络的流量pf。〔3〕在这条路上，减少每一条弧的顺流容量pf，同时增加这些弧的逆流容量pf，返回步骤〔1〕。用此方法对例6求解：第一次迭代：选择路为v1v4v7。弧〔v4,v7〕的顺流容量为2，决定了pf=2，改进的网络流量图如以下图：63522241263v1v2v5v7v4v3v600000000000420213整理课件§4最大流问题第二次迭代：选择路为v1v2v5v7。弧〔v2,v5〕的顺流容量为3，决定了pf=3，改进的网络流量图如以下图：第三次迭代：选择路为v1v4v6v7。弧〔v4,v6〕的顺流容量为1，决定了pf=1，改进的网络流量图如以下图：635222413v1v2v5v7v4v3v60000000042022033303222413v1v2v5v7v4v3v60000004202203333301314整理课件第四次迭代：选择路为v1v4v3v6v7。弧〔v3,v6〕的顺流容量为2，决定了pf=2，改进的网络流量图如以下图：第五次迭代：选择路为v1v2v3v5v7。弧〔v2,v3〕的顺流容量为2，决定了pf=2，改进的网络流量图如以下图：22243v1v2v5v7v4v3v6100001203203335031200231322v1v2v5v7v4v3v61012020333501202313150020205§4最大流问题15整理课件经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为10。最大流量图如以下图：22v1v2v5v7v4v3v6123522355§4最大流问题“管理运筹学软件〞中还有专门的子程序用于解决最大流问题。16整理课件§5最小费用最大流问题最小费用最大流问题：给了一个带收发点的网络，对每一条弧〔vi,vj〕，除了给出容量cij外，还给出了这条弧的单位流量的费用bij，要求一个最大流F，并使得总运送费用最小。一、最小费用最大流的数学模型例7由于输油管道的长短不一，所以在例6中每段管道〔vi,vj〕除了有不同的流量限制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〕v1v2v5v7v4v3v6(6,3)17整理课件§5最小费用最大流问题

这个最小费用最大流问题也是一个线性规划的问题。解：我们用线性规划来求解此题，可以分两步走。第一步，先求出此网络图中的最大流量F，这已在例6中建立了线性规划的模型，通过管理运筹学软件已经获得结果。第二步，在最大流量F的所有解中，找出一个最小费用的解，我们来建立第二步中的线性规划模型如下：仍然设弧〔vi,vj〕上的流量为fij，这时网络中最大流量为F，只要在例6的约束条件上，再加上总流量必须等于F的约束条件：f12=f14=F,即得此线性规划的约束条件，此线性规划的目标函数显然是求其流量的最小费用。由此得到线性规划模型如下：18整理课件§5最小费用最大流问题

19整理课件§5最小费用最大流问题

用管理运筹学软件，可求得如下结果：f12=4,f14=6,f25=3,f23=1,f43=3,F57=5,f36=2,f46=1,f47=2,f67=3,f35=2。其最优值(最小费用)=145。对照前面例6的结果，可对最小费用最大流的概念有一个深刻的理解。如果我们把例7的问题改为：每小时运送6万加仑的石油从采地v1到销地v7最小费用是多少？应怎样运送？这就变成了一个最小费用流的问题。一般来说，所谓最小费用流的问题就是：在给定了收点和发点并对每条弧(vi,vj)赋权以容量cij及单位费用bij的网络中，求一个给定值f的流量的最小费用，这个给定值f的流量应小于等于最大流量F，否那么无解。求最小费用流的问题的线性规划的模型只要把最小费用最大流模型中的约束条件中的发点流量F改为f即可。在例6中只要把f12+f14=F改为f12+f14=f=6得到了最小费用流的线性规划的模型了。20整理课件§5最小费用最大流问题二、最小费用最大流的网络图论解法对网络上弧〔vi,vj〕的〔cij,bij〕的表示作如下改动，用(b)来表示(a)。用上述方法对例7中的图形进行改进，得图如下页：vivjvivj〔cij,bij〕〔0,-bij〕〔a〕〔b〕〔cij,bij〕〔cij,bij〕vivj〔cji,bji〕〔cij,bij〕vivj〔cji,bji〕〔0,-bji)〔0,-bji)〔c〕〔d〕21整理课件§5最小费用最大流问题求最小费用最大流的根本算法在对弧的标号作了改进的网络图上求最小费用最大流的根本算法与求最大流的根本算法完全一样，不同的只是在步骤〔1〕中要选择一条总的单位费用最小的路，而不是包含边数最小的路。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)(0,-3)(0,-8)(0,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(0,-4)（0,-3）图11-2822整理课件§5最小费用最大流问题用上述方法对例7求解：第一次迭代：找到最短路v1v4v6v7。第一次迭代后总流量为1，总费用10。v5(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(2,8)（3,2）v1v2v7v4v3v6(5,3)(1,-3)(0,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）图11-2923整理课件§5最小费用最大流问题第二次迭代：找到最短路v1v4v7。第二次迭代后总流量为3，总费用32。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(0,8)（3,2）v1v2v5v7v4v3v6(3,3)(3,-3)(2,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）图11-3024整理课件§5最小费用最大流问题第三次迭代：找到最短路v1v4v3v6v7。第三次迭代后总流量为5，总费用56。(6,6)(3,4)(5,7)(2,5)(0,-4)（0,3）(1,4)(0,3)(0,8)（1,2）v1v2v5v7v4v3v6(1,3)(5,-3)(2,-8)(1,-3)（2,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(3,-4)（2,-3）图11-3125整理课件§5最小费用最大流问题第四次迭代：找到最短路v1v4v3v5v7。第四次迭代后总流量为6，总费用72。(6,6)(3,4)(4,7)(2,5)(1,-4)（0,3）(1,4)(0,3)(0,8)（0,2）v1v2v5v7v4v3v6(1,3)(6,-3)(2,-8)(1,-3)（3,-2）(0,-6)(0,-4)(0,-5)（1,4）(1,-7)(3,-4)（2,-3）图11-3226整理课件§5最小费用最大流问题

第五次迭代：找到最短路v1v2v5v7。第五次迭代后总流量为9，总费用123。(3,6)(0,4)(1,7)(2,5)(1,-4)（0,3）(1,4)(0,3)(0,8)（0,2）v1v2v5v7v4v3v6(0,3)(6,-3)(2,-8)(1,-3)（3,-2）(3,-6)(3,-4)(0,-5)（1,4）(4,-7)(3,-4)（