华东交通大学：《数学模型》课程教学资源（PPT讲稿）图论与网络模型（五）

图论与网络模型(五)

图论与网络模型(五)

关键路径分析技术与 计划评审技术 1关键路径分析 项工程包括若干工序,完成每道工 序需要一定的时间,工序之间存在先后顺 序关系,那么如果安排各工序的开工时间 和顺序,才能使工程尽可能早完成? 关键路径分析就是借助图的技术来求解此 问题的一个方法。它告诉我们哪些工序是 影响工程的关键,它们的提前或推后完工, 都必然影响工程的完工

一、关键路径分析技术与 计划评审技术 一项工程包括若干工序，完成每道工 序需要一定的时间，工序之间存在先后顺 序关系，那么如果安排各工序的开工时间 和顺序，才能使工程尽可能早完成？ 关键路径分析就是借助图的技术来求解此 问题的一个方法。它告诉我们哪些工序是 影响工程的关键，它们的提前或推后完工， 都必然影响工程的完工。 1.关键路径分析

例题:设某项工程的各个工序与所需时 间以及它们之间的相互关系如下表所示: 工序工序代号所需时间(天)紧后工序 产品设计 60 b、c、d、e 外购配套件 45 下料、锻件 10 工装制造1 20 9、h 木模 机械加工1 abcdefg 40 18 工装制造2 30 机械加工2 h 15 机械加工3 25 kII 装配调试 35

例题：设某项工程的各个工序与所需时 间以及它们之间的相互关系如下表所示： 工 序 工序代号 所需时间（天） 紧后工序 产品设计 a 60 b、c、d、e 外购配套件 b 45 l 下料、锻件 c 10 f 工装制造1 d 20 g、h 木模 e 40 h 机械加工1 f 18 l 工装制造2 g 30 k 机械加工2 h 15 l 机械加工3 k 25 l 装配调试 l 35 /

现在我们要编制该工程的网络计划,确定 各工序的开工时间等,特别是确定关键工序 首先根据上面表所给出的内容,绘制网络图。 所谓网络图是由点(结点)、弧及权所构 成的有向图。即有向赋权图 在这里,一个点表示一个事项(或事件), 它是一个或若干个工序的开始或结束,是相邻 工序在时间上的分界点。点用圆圈和其里面的 数字表示,数字表示点的编号,如 ①②③④⑤⑥⑦⑧. 弧表示一个工序,用箭线“→”表示。权表示 完成某工序所需的时间,用T(表示

现在我们要编制该工程的网络计划，确定 各工序的开工时间等，特别是确定关键工序。 首先根据上面表所给出的内容，绘制网络图。 所谓网络图是由点（结点）、弧及权所构 成的有向图。即有向赋权图。 在这里，一个点表示一个事项（或事件）， 它是一个或若干个工序的开始或结束，是相邻 工序在时间上的分界点。 点用圆圈和其里面的 数字表示，数字表示点的编号，如 … 弧表示一个工序，用箭线“”表示。权表示 完成某工序所需的时间,用T(i,j)表示

上述问题对应的网络图: 45 10 18 g ① ⑧ 60 20 30 35 2⑤ 15

上述问题对应的网络图：         a 60 b 45 c 10 d 20 e 40 f 18 g 30 h 15 k 25 l 35

箭尾事项 箭头事项 紧前 紧后 工序 工序 有关网络图的构造请进一步参考有关书籍

i j 箭尾事项 箭头事项 紧前 i 工序 紧后 工序 有关网络图的构造请进一步参考有关书籍

事项的时间: (1)事项最早时间TE(j): 若事项为某些工序的箭尾事项,事项最 早时间为各工序的最早可能的开始时间; 若事项为某些工序的箭头事项,事项最 早时间为各工序的最早可能的结束时间 工序 工序 事项

事项的时间： （1）事项最早时间TE(j)： 若事项为某些工序的箭尾事项，事项最 早时间为各工序的最早可能的开始时间； 若事项为某些工序的箭头事项，事项最 早时间为各工序的最早可能的结束时间 j 事项 工序 工序

工序i j 事项 TE()的计算: TE(1)=0 TEG=Max TE(+T(iJ)) j=2,3,,n 计算结果写入事项左下方的口内。如下:

j 事项 工序i TE(j)的计算： TE(1)=0 TE(j)=max{ TE(i) + T(i,j) } j=2,3,…,n 计算结果写入事项左下方的内。如下：

45 C 1070 18 g k 6060208030102513535170 e 100 15

        a 60 b 45 c 10 d 20 e 40 f 18 g 30 h 15 k 25 l 0 60 80 35 70 100 110 135 170

事项的时间: (2)事项最迟时间T(i) 箭头事项各工序的最迟必须结束的时间; 或箭尾事项各工序的最迟必须开始的时间 工序 工序 事项

事项的时间： （2）事项最迟时间TL(i)： 箭头事项各工序的最迟必须结束的时间； 或 箭尾事项各工序的最迟必须开始的时间。 i 事项 工序 工序