[理学]数模培训_图论模型2012.ppt

* 南京信息工程大学数理学院 费文龙 * 关键路径(最长路径)算法 定理 若有向图G中不存在有向回路,则可以将G 的结点重新编号为u1, u2, …, un,使得对任意的边ui uj∈E(G),都有i＜ j . 各工序最早启动时间算法步骤： ① 根据定理对结点重新编号为u1, u2, …, un . ② 赋初值 ?(u1)= 0. ③ 依次更新 ?(uj ),j = 2, 3, … , n . ?(uj )= max{?(ui )+ ?(ui ,uj )|uiuj∈E(G)}. ④ 结束. 其中?(uj )表示工序 uj 最早启动时间,而?(un)即?(vn)是整个工程完工所需的最短时间. * 南京信息工程大学数理学院 费文龙 * A B 2 2 C 6 D 3 E 2 F 2 G 2 H 2 K 4 N 3 I 8 J 8 4 4 2 L 3 M 8 5 6 此例不必重新编号，只要按字母顺序即可. ?(A)=0, ?(B)=?(C)=2, ?(D)=8, ?(E)=max{2+3,8+2}=10, ?(F)=?(G)=?(H)=?(D)+2=10, ?(I)=max{?(G)+8,?(H)+4}=18, ?(J)=?(G)+8=18, ?(K)=max{?(E)+4,?(H)+4}=14, ?(L)=?(J)+3=21, ?(M)=?(K)+8=22, ?(N)=max{?(F)+3,?(I)+2,?(L)+5,?(M)+6}=28. 关键路径? * 南京信息工程大学数理学院 费文龙 * 通过以上计算表明： 这项工程至少需要28天才能完成. 关键路径(最长路径): A→B→D→E→K→M→N A→B→D→H→K→M→N 工序A,B,D,E,H,K,M不能延误,否则将影响工程的完成. 但是对于不在关键路径上的工序, 是否允许延误？如果允许, 最多能够延误多长时间呢？ 各工序允许延误时间t(uj )等于各工序最晚启动时间?(uj )减去各工序最早启动时间?(uj ). 即 t(uj )=?(uj )-?(uj ). * 南京信息工程大学数理学院 费文龙 * 最晚启动时间算法步骤(已知结点重新编号)： ① 赋初值 ?(un )=?(un). ② 更新 ?(uj ),j = n - 1, n - 2, … , 1. ?(uj )= min{?(ui )- ?(ui ,uj )|uiuj∈E(G)}. ③ 结束. 顺便提一句,根据工序uj允许延误时间t(uj )是否为0,可判断该工序是否在关键路径上. * 南京信息工程大学数理学院 费文龙 * A B 2 2 C 6 D 3 E 2 F 2 G 2 H 2 K 4 N 3 I 8 J 8 4 4 2 L 3 M 8 5 6 ?(N)=28, ?(M)=28-6=22, ?(L)=28-5=23, ?(K)=?(M)-8=14, ?(J)=?(L)-3=20,?(I)=28-2=26, ?(H)=min{?(K)-4,?(I)-4}=10, ?(G)=min{?(J)-8,?(I)-8}=12, ?(F)=28-3=25, ?(E)=?(K)-4=10, ?(D)=min{?(E)-2,?(F)-2,?(G)-2,?(H)-2}=8, ?(C)=?(E)-3=7,?(B)=?(D)-6=2,?(A)=0. * 南京信息工程大学数理学院 费文龙 * 各工序允许延误时间如下： t(A)=t(B)=t(D)=t(E)=t(H)=t(K)=t(M)=0, t(C)=5,t(F)=15,t(G)=2,t(I)=8,t(J)=2, t(L)=2. * 南京信息工程大学数理学院 费文龙 * PERT图 在PERT(Programme evaluation and review technique)图中, 采用有向边表示工序, 其权值表示该工序所需时间. 如果工序ei完成后ej才能开始, 则令vk 是ei的终点, ej 的始点. 根据这种约定, 前例的PERT图如下： A B C E F D D G G H H I J K L M 对于PERT图,一些算法与PT图类似. * 南京信息工程大学数理学院 费文龙 * PT图要比PERT图好一些. PT图的结点数基本上是固定的,这是最重要的一点,容易编程计算. 另外PT图比PERT图更加灵活,它能适应一些额外的约束. 例如下图中 ? (i )/2 vi vj ⑴ ? (i ) + t vi vj ⑵ bj v0 vj ⑶ ⑴ 表示工序vi完成一半之后vj就可以开始. ⑵ 表示工序vi完成后经过t 时刻vj才开