第五章时序和路径规划ppt课件

1、 浙江大学管理学院浙江大学管理学院 杜红杜红 博士博士 副教授副教授时序规划最小树问题经过一个网络的最短途径经过一个网络的最大流量n时序顺序时间时序顺序时间n时序规划时序规划n 多项义务等待同一人或物处置，每多项义务等待同一人或物处置，每项义务的单独完成的时间确定，且没有项义务的单独完成的时间确定，且没有先后关系紧前、紧后。怎样安排各先后关系紧前、紧后。怎样安排各项义务的顺序，使总效率最高？项义务的顺序，使总效率最高？n系统时间加工时间排队时间系统时间加工时间排队时间n时序规划原那么目的时序规划原那么目的n 到达时间先进先出到达时间先进先出n 最小富有时间到期时间加工最小富有时间到期时间加工时

2、间时间n 最接近完成者优先最接近完成者优先n 在完成之前最少的机器开关次数在完成之前最少的机器开关次数n 下一任务最短的排队下一任务最短的排队n 关键比例最低关键比例最低n 最重要的优先最重要的优先n 加工工序之间的转换本钱最低加工工序之间的转换本钱最低n 加工时间最短者优先加工时间最短者优先n 最先到期的任务优先最先到期的任务优先 n平均排队等待时间最短问题平均排队等待时间最短问题n 加工时间最短者优先加工时间最短者优先n 一样时间的可恣意安排一样时间的可恣意安排n平均延误时间最短问题平均延误时间最短问题n 最先到期的任务优先最先到期的任务优先n例例51：教材：教材 P105 实例实例5.3

3、n例例5 52 2：教材：教材 P106 P106 实例实例5.45.4n 平均排队时间最短：加工时间短者优先平均排队时间最短：加工时间短者优先n A G C H E B F A G C H E B F D Dn加工时间加工时间 2 2 3 3 4 5 7 2 2 3 3 4 5 7 8 8n等待时间等待时间 0 2 4 7 10 14 19 0 2 4 7 10 14 19 2626n总等待时间：总等待时间：82 82 平均等待时间：平均等待时间：10.2510.25 平均延误时间最短：最先到期者优先平均延误时间最短：最先到期者优先 G B C A E F D H G B C A E F D

4、 H到期时间到期时间 2 7 8 13 14 20 30 36 2 7 8 13 14 20 30 36加工时间加工时间 2 5 3 2 4 7 8 3 2 5 3 2 4 7 8 3开场时间开场时间 0 2 7 10 12 16 23 31 0 2 7 10 12 16 23 31完工时间完工时间 2 7 10 12 16 23 31 34 2 7 10 12 16 23 31 34延误时间延误时间 0 0 2 0 2 3 1 0 0 0 2 0 2 3 1 0 总延误时间：总延误时间：8 8 平均延误时间：平均延误时间：1 1n延误的任务项数最少延误的任务项数最少n 先按先到期者优先的原那

5、么排初次次先按先到期者优先的原那么排初次次序序 n 假设没有延误的任务，那么是最优假设没有延误的任务，那么是最优解。解。n 假设有延误的任务，那么找出其中假设有延误的任务，那么找出其中的一项，找出到此项任务之前包括该的一项，找出到此项任务之前包括该项加工时间最长的一项，并将之抽去，项加工时间最长的一项，并将之抽去，重新安排时间，假设已没有延误的任务，重新安排时间，假设已没有延误的任务，那么将被抽取的这一项放置最后；如仍那么将被抽取的这一项放置最后；如仍有被延误的任务，那么再反复这一步。有被延误的任务，那么再反复这一步。按先到期者优先原那么安排的初次次序为：按先到期者优先原那么安排的初次次序为：

6、 G B C A E F D HG B C A E F D H到期时间到期时间 2 7 8 13 14 20 30 362 7 8 13 14 20 30 36加工时间加工时间 2 5 3 2 4 7 8 32 5 3 2 4 7 8 3完工时间完工时间 2 7 10 12 16 23 31 342 7 10 12 16 23 31 34延误时间延误时间 0 0 2 0 2 3 1 00 0 2 0 2 3 1 0找出一项延误的任务是找出一项延误的任务是 C C ；C C 之前包括之前包括 C C加工时间最长的是加工时间最长的是 B, B, 抽去抽去 B B 后，重新安排后，重新安排时间：时间

7、： 抽去任务抽去任务 B B 后的次序安排：后的次序安排： G C A E F D H G C A E F D H到期时间到期时间 2 8 13 14 20 30 36 2 8 13 14 20 30 36加工时间加工时间 2 3 2 4 7 8 3 2 3 2 4 7 8 3开场时间开场时间 0 2 5 7 11 18 26 0 2 5 7 11 18 26完工时间完工时间 2 5 7 11 18 26 29 2 5 7 11 18 26 29延误时间延误时间 0 0 0 0 0 0 0 0 0 0 0 0 0 0B B7 75 5292934342727n时序规划扩展：时序规划扩展：n 两

8、台顺序机器完成一批任务两台顺序机器完成一批任务n n每项任务在机器每项任务在机器1和机器和机器2上的上的加工时间不一样，如何使系统效加工时间不一样，如何使系统效率最高？率最高？ 3214机器机器1机器机器2任务任务n约翰逊原那么约翰逊原那么n 找出各台机器上加工时间最短的一项任务，找出各台机器上加工时间最短的一项任务， n 假设在机器假设在机器1上，这项任务最先做；上，这项任务最先做；n 假设在机器假设在机器2上，这项任务最后做；上，这项任务最后做；n 不断反复，从两端往内排。一样时间可任不断反复，从两端往内排。一样时间可任选一个，普通先安排机器选一个，普通先安排机器1上任务。上任务。例例53

9、：教材：教材P110 实例实例5.6任务：任务： A B C D E F G机器机器1： 2 5 10 8 4 12 9机器机器2： 14 7 3 10 5 6 6顺序：顺序：1开场：开场： 0 2 6 11 19 31 40 1完成：完成： 2 6 11 19 31 40 502开场：开场： 2 16 21 28 38 44 502完成：完成： 16 21 28 38 44 50 53 ACEBDGF最小树问题最小树问题n图及相关的概念n图：点及点与点之间的连线箭线：有向图构成n边与弧：两点之间连线为边或弧箭线如： 1-2，4-6n链与路：恣意两点之间的点与边弧组成了一条链路。n 如：1-2

10、-4-6n圈与回路：链路的两端为同一点那么构成一个圈回路。n 如：1-2-3n连通图：恣意两点之间至少有一条链，没有孤立点。n网络：一个有向图的弧有某种“流转物流动时的图称为网络n权：边或弧的权数，表示边或弧性质或数量。453427987737298544最小树问题最小树问题n树的概念n 连通图，但没有圈为树。由一切节点(N)和相应的边(N-1)组成。总经理消费经理人力经理销售经理车间主任销售代表招聘经理最小树问题最小树问题n最小树最小树n 一个网络中有很多树，其中边的长度一个网络中有很多树，其中边的长度权数之和为最小的树为最小树。权数之和为最小的树为最小树。n最小树的获取破圈法最小树的获取破

11、圈法n 从图中任取一个圈，去掉该圈的一条从图中任取一个圈，去掉该圈的一条最大边，将此圈破去，然后反复破圈，最大边，将此圈破去，然后反复破圈，直至无圈为止。直至无圈为止。n 最小树问题最小树问题4323245172674例例54：求以以下图的最小树：求以以下图的最小树经过一个网络的最短途径经过一个网络的最短途径n问题问题n 在一个网络中，给定一个始点在一个网络中，给定一个始点Vs，和，和一个终点一个终点Vt，求，求Vs 到到Vt的一条路，使路的一条路，使路长最短。长最短。n求解求解n 能划分阶段的，可采用动态规划方法。能划分阶段的，可采用动态规划方法。n 不能分阶段的，采用狄克斯屈方法。不能分阶

12、段的，采用狄克斯屈方法。经过一个网络的最短途径经过一个网络的最短途径狄克斯屈狄克斯屈Dijstra方法方法开场节点标永久标志开场节点标永久标志0,S,其他为暂时其他为暂时标志标志T,-找出与开场节点相邻的一切节点，为找出与开场节点相邻的一切节点，为每一个设标志每一个设标志L,1，其中，其中L值最小的值最小的节点标志右上角标上节点标志右上角标上*，使之成为永，使之成为永久标志。久标志。L为两节点间间隔，为两节点间间隔，1表示始表示始于第一节点于第一节点重新的永久标志开场，找出从此节点重新的永久标志开场，找出从此节点出发可到达的一切节点，计算这些节出发可到达的一切节点，计算这些节点的最短间隔现有间

13、隔和经新的永点的最短间隔现有间隔和经新的永久标志到达的间隔的小的一个值，久标志到达的间隔的小的一个值，坚持、新设或更改这些节点的标志为坚持、新设或更改这些节点的标志为 最短间隔，最短途径上前一节点标最短间隔，最短途径上前一节点标号号，比较图中一切没有，比较图中一切没有*的标志暂的标志暂时性标志，找出间隔最短的一个节时性标志，找出间隔最短的一个节点，使之成为永久性标志。反复这一点，使之成为永久性标志。反复这一步，直到一切的节点都成为永久性标步，直到一切的节点都成为永久性标志为止。志为止。经过一个网络的最短途径经过一个网络的最短途径kijDi ,mLijDj,k从从i-j时：时： 假设假设Di+L

14、ijDj,那么不改动那么不改动j的标志；的标志； 假设假设Di+LijDj，那么改为，那么改为Di+Lij,i经过一个网络的最短途径经过一个网络的最短途径n例例55 狄克斯屈方法狄克斯屈方法 ：教材：教材P131 实例实例5.1235,41432657201510682410820110,S21,325,344,2T,-T,-T,-T,-T,-T,-20,115,141,6*经过一个网络的最短途径经过一个网络的最短途径从起始点到每一点的最短间隔为：从起始点到每一点的最短间隔为： 节点节点 最短间隔最短间隔 途径途径 2 20 12 3 15 13 4 25 134 5 35 1345 6 21

15、 136 7 41 1367最短途径问题的运用最短途径问题的运用n例56：设备更新问题 n 某厂运用一种设备，每年年初设备科需求对该设备的更新与否作出决策。假设购置新设备，就要支付购置费；假设继续运用那么需求支付维修费，设备运用的年数越长，每年所需的维修费越多。现假设第一年年初购置了一台新设备，问在5年内如何制定设备更新方案，以便使新设备购置费和维修费的总费用最小？知设备在5年内各年年初的价钱及设备运用不同年数的维修费如下：最短途径问题的运用最短途径问题的运用n例56：设备更新问题 n 把求总费用最小问题化为最短途径问题。用点 i (i=1,2,3,4,5)表示第 i 年买进一台新设备。增设一

16、点 6 表示第五年末。从i点到i+1, 6 各画一条弧，弧i , j表示在第 i 年买进的设备不断运用到第 j 年年初第 j 1年年末。求1点到6点的最短途径。途径的权数为购买和维修费用。n 弧i , j的权数为第i年的购置费ai从第i年运用至第j-1年末的维修费之和。n 从第i年运用至第j-1年末的维修费：b1+bj-i 运用寿命为j-i年 n 如：24权数为：a2+b1+b2=1156=22 详细权数计算结果如下：经过一个网络的最短途径经过一个网络的最短途径n例例56 设备更新问题设备更新问题 ：n运用运用Dijstra算法，上述问题最短路为算法，上述问题最短路为1-3-6或或1-4-6n

17、 即：第即：第1、3年年初购买设备，或第年年初购买设备，或第1、4年年年年初购买设备初购买设备n 五年最正确总费用为五年最正确总费用为53。132546162217182330594117301623413122作业题：作业题：n某地某地7个村镇之间现有交通间隔如图个村镇之间现有交通间隔如图n求：求：1)从村从村1到其他各村的最短间隔？到其他各村的最短间隔？ n 2)如要沿路架设线，如何使总长度最小同如要沿路架设线，如何使总长度最小同时又使每个村都能安装上？时又使每个村都能安装上？1211101512102516171526724经过一个网络的最大流量经过一个网络的最大流量n最大流量问题最大流

18、量问题n 在一定条件下，使网络系统中从开场在一定条件下，使网络系统中从开场点到终了点之间的某种物资流的流量到点到终了点之间的某种物资流的流量到达最大的问题。限制条件是每一条边的达最大的问题。限制条件是每一条边的最大经过才干流量不等。但有多条最大经过才干流量不等。但有多条路路n最大流量求解最大流量求解n线性规划方法线性规划方法n福特富尔克逊标号法福特富尔克逊标号法“分步流动分步流动 最大流量的线性规划模型最大流量的线性规划模型n例例57：有以下石油运输管道图。某公司：有以下石油运输管道图。某公司欲采用这个网络图从欲采用这个网络图从1地向销地地向销地7运送原油，运送原油，弧的容量弧的容量Cij万升

19、万升/时已给定因管道直时已给定因管道直径的变化，径的变化，Cij不完全一样。问如何安排不完全一样。问如何安排保送，方能使每小时运送的原油最多？保送，方能使每小时运送的原油最多？62321256432最大流量的线性规划模型最大流量的线性规划模型n设弧设弧i,j上的流量为上的流量为Fij, 总流量为总流量为F.n目的函数：目的函数：MAX F=F12+F14n约束条件：约束条件： 流入流出流入流出; FijCij; Fij0n 2点：点：F12=F23+F25; 4点：点：F14=F43+F46+F47n 3点：点：F23+F43=F35+F36; 5点点 ：F25+F35F57 n 6点：点：F

20、36+F46F67 ; 7点：点：F47+F57+F67=F12+F14n解：解：F12=5;F14=5;F23=2;F25=3;F43=2;F46=1;F47=2;F35=2n F36=2;F57=5;F67=3 最大流量最大流量F1062321256432思索题：最小费用最大流思索题：最小费用最大流n假设弧假设弧i,j上的单位流量费用为上的单位流量费用为Bij (百元百元/万升。万升。n 图中每一条弧的权数前一位为流量限制图中每一条弧的权数前一位为流量限制Cij，后一位为，后一位为单位费单位费Bij。n怎样运送才干使运送最多的石油并使总的费用最小？怎样运送才干使运送最多的石油并使总的费用最

21、小？n提示：先求得最大提示：先求得最大F值；再求总流量为值；再求总流量为F时使总费用最小时使总费用最小的方案。的方案。n进一步思索：求最小费用问题。进一步思索：求最小费用问题。n 如何求每小时运送如何求每小时运送6万升原油的最小费用？万升原油的最小费用？ 6,32,53,22,31,32,85,76,64,43,42,4最大流量的标注法最大流量的标注法n标志：标志：流入节点的流量，该流量的来源节点流入节点的流量，该流量的来源节点，第一个节点标志第一个节点标志，S。n选取已有标志的一个节点，找出从此节点能直选取已有标志的一个节点，找出从此节点能直接到达的一个节点，确定到达节点的最大流量，接到达的一个节点，确定到达节点的最大流量，相应地标上标志。反复这一步，尽快到达终点，相应地标上标志。反复这一步，尽快到达终点，得到一条从起点到终点的途径，此途径的最大得到一条从起点到终点的途径，此途径的最大流量为流入终点的流量。将此途径上的每一边流量为流入终点的流量。将此途径上的每一边的流动才干减去此流量。再从起始节点开场，的流动才干减去此流量。再从起始节点开场，按新的流动才干，重新进展标号，找出新的一按新的流动