运筹学课件：6网络计划a

1、第6章 网络计划引例：沏茶1324烧水（10）备茶（3）沏茶（2）洗碗（2）第6章 网络计划网络计划方法一般由两个阶段组成：初始计划阶段和计划方案调整阶段。初始计划阶段将工程项目划分为多个相互衔接的工序，估计工序的完工时间，然后用网络图表示，按计划时间参数确定完成项目的个关键工序及由其组成的关键线路，拟定一初始计划方案。该阶段包括网络图绘制和关键线路确定两个环节。计划方案调整阶段根据要求，综合考虑时间、费用、资源等目标，对初始计划方案进行调整改善，直至得出一满意的计划方案。一、工序时间确定的工程计划网络问题 问题的一般提法 设：有一项工程，包括许多彼此关联的独立活动组成，这些活动称为工序；已知

2、各工序间的先后关系，以及各工序所需时间t。 问：（1）工程完工期T=？ （2）工程的关键工序有哪些？第6章 网络计划求解方法关键路径法（CPM）分为三步： 绘制工程网络图 标号法求工期 T 标号法求关键路线双代号网络图示例ij工序名称(工序持续时间)单代号网络图示例工作代号工作名称持续时间1.1 构成网络图的三要素：（双代号）（1）箭线（工序，工作）在网络图中，带箭头的线段，称箭线。箭线表示的具体内容取决于网络图的祥略程度。箭线代表整个工序的全过程，要消耗时间及各种资源，一般在网络图上表注的是消耗时间的数量。 实箭线表示具体工序，虚箭线表示虚工序，仅表示工序与工序之间的关联，不需要消耗时间、费

3、用和资源。（2）结点（事项）前后两工序的交点，表示工序的开始、结束和连接关系。是瞬间概念，不消耗时间和资源。用 表示。第一个节点，称始结点；最后一个结点称终结点；其它节点称中间结点。节点沿箭线由左到右从小到大。i前后两工序的交点，表示工序的开始、结束和连接关系。是瞬间概念，不消耗时间和资源。用 表示。第一个节点，称始结点；最后一个结点称终结点；其它节点称中间结点。节点沿箭线由左到右从小到大。i一项工序中与箭尾衔接的结点，称工序的紧前事项。 一项工序中与箭头衔接的结点，称工序的紧后事项。工序的紧前工序：A工序的箭头与B工序的紧前事项衔接，则A为B的紧前工序。工序的紧后工序：B工序的箭尾与A工序的

4、紧后事项衔接，则B为A的紧后工序。 事项的紧前工序：用箭头与事项连接的工序。事项的紧后工序：用箭尾与事项连接的工序。（3）线路 指网络图中从始节点到终节点之间可连通的线路。1324烧水（10）备茶（3）沏茶（2）洗碗（2）1）顺序：按工序先后从左至右；2）要求：图中不得有缺口、回路和多重边。缺口：多个始点或多个终点的现象。 （应当只有一个始点和终点）1.2 网络图的绘制：（双代号）多重边：两点间有多于一条的边。AB处理方法：增加虚工序。AAB回路：方向一致的闭合链。处理方法：增加虚工序。多个始点或多个终点：例 P134 表6.123674589A B C D E G F H 1工作ABCDEF

5、GH紧前工作-AA,BB D,ED,CG,F工序代号紧前工序工序时间（周）A/2B/3C/2DA3EA4工序代号紧前工序工序时间（周）FB7GB6HD 、 E4IB 、 C10JG、I3例：绘制工程网络图续左表解：1A (2)D (3)C (2)2E (4)3F(7)B (0)G(6)45E(0)6I (10)7J(3)H (4)8B (3)练习 为筹建某餐馆，需制定计划。将工程分为14道工序，各工序需时及先后关系如下表。试绘制工程网络图。工序内容紧前工序所需天数A购买炉灶及材料10B购买室内设备3C招集工人1D选择开业地点2E申请许可得到执照D7F修理门窗、粉刷墙壁E3G砌炉灶、水池A、F5

6、H接通上下水道G4I安装室内设备B、H4J做好室内装饰B、H3K购进米面及副食品I、J6L张贴开业广告G3M人员训练C、I4N开业前操作试验K、L7工序ABCDEFGHIJKLMN紧前工序_DEAFGBHBHIJGCIKL所需天数1031273544363471CBAD2E3F4G5H6IJ7I8KL9IM10N111234569781011网络图编号方法 箭杆删除法：首先给起点（总开工事项）以编号1，接着设想从起点流出的箭线删除，得到一个或几个不为任何有向边终点的结点（不为任何箭线箭头的结点），对它们逐一顺序编号（这些结点之间的编号大小的顺序是无关紧要的），然后把这些新编号结点流出的箭线删除

7、，又得一些不为任何箭线终点的结点，同样逐一编号，如此继续进行，直到最后一个结点（即总完工事项）被编上号为止。练习 P150习题6.1160234756891011121314abcdefghijklmnopq142030211071225510601015257f b 1.3时间参数计算与关键路线确定工序（i，j）的时间参数：最早开始时间 ESi-j （Earliest Start Time）最早完成时间 EFi-j （Earliest Finish Time）最迟完成时间 LFi-j （Latest Finish Time）最迟开始时间 LSi-j （Latest Start Time）总时

8、差 TFi-j （Total Floating Time）自由时差 FFi-j （Free Floating Time）最早开始时间 ESi-j （Earliest Start Time） 工序（i，j）在其所有的紧前工序都完成而可以开始的最早时间最早完成时间 EFi-j （Earliest Finish Time） 工序（i，j）在其所有的紧前工序都完成而可以完成的最早时间EFi-j =ESi-j+Di-j例:计算23674589A2B4C9D3E6G4F2H2100244111015ES练习：P137图6.8例:计算23674589A2B4C9D3E6G4F2H21241171015121

9、7最后结束工序的最早完成时间称为计算工期，记Tc。还可以利用公式：EFi-j =ESi-j+Di-jTc=17EF练习：P137图6.8最迟完成时间 LFi-j （Latest Finish Time） 在不影响工期的前提下，工序（i，j）最迟必须完成的时间最迟开始时间 LSi-j （Latest Start Time） 在不影响工期的前提下，工序（i，j）最迟必须开始的时间LSi-j =LFi-j-Di-j例:计算23674589A2B4C9D3E6G4F2H2117Tc=17151513111127LF练习：P137图6.8例:计算23674589A2B4C9D3E6G4F2H2115Tc

10、S练习：P137图6.8总时差 TFi-j （Total Floating Time） 在不影响工期的前提下，工序（i，j）所具有的机动时间TFi-j = LFi-j - ESi-j-Di-j = LFi-j -EFi-j自由时差 FFi-j （Free Floating Time） 在不影响紧后工序最早开始的前提下，工序（i，j）所具有的机动时间FFi-j =（紧后工序最早开始时间的最小值）-ESi-j-Di-j = （紧后工序最早开始时间的最小值）-EFi-j例:计算23674589A2B4C9D3E6G4F2H21171515131111270024411101

11、523674589A2B4C9D3E6G4F2H21LFES00304303TFTFi-j=LFi-j-ESi-j-Di-j例如：工序D的最早开始时间是第4天，最迟完成时间是第11天，D需要3天完成，因此D具有11-4-3天的机动时间。练习：P137图6.8例:计算23674589A2B4C9D3E6G4F2H2100244111015241171015121723674589A2B4C9D3E6G4F2H21ESEF0003003FF0FFi-j =（紧后工序最早开始时间的最小值）-EFi-j例如：工序D的后续工序有G和F，其最早开始时间分别问第11天和第10天，因此在不影响工序F最早开始的

12、前提下，D的机动时间为10-7=3天。练习：P137图6.8结点i的时间参数：最早时间 ETi 结点i所代表的事项最早可能发生的时间 最迟时间 LTi 结点i所代表的事项在不影响工期的前提下最迟必须发生的时间。求出工期后反推得到。结点i表示工序A和B完成而工序C和D开始结点i的最早时间ETi等于以结点i为起始点的工序C和D的最早开始时间，也等于以结点i为完成结点的工序A和B最早都完成时间（即A与B最早完成时间的最大值）iABCD结点i的最迟时间 LTi等于以结点i为完成结点的工序A和B的最迟完成时间；也等于以结点i为开始结点的工序C和D的最迟开始时间的最小值例计算最早时间 ET23674589

13、A2B4C9D3E6G4F2H210244111071517练习：P137图6.8例 计算最迟时间 LT23674589A2B4C9D3E6G4F2H2117151111132780练习：P137图6.8 工序（i，j）的最早开始时间等于该工序开始结点的最早时间，即ESi-j = ETi 工序（i，j）的最早完成时间等于该工序开始结点的最早时间加上工序时间，即EFi-j = ETi + Di-j 工序（i，j）的最迟完成时间等于该工序完成结点的最迟时间，即LFi-j = LTj 工序（i，j）的最迟开始时间等于该工序完成结点的最迟时间减去工序时间，即LSi-j = LTj - Di-j 工序（

14、i，j）的总时差等于该工序完成结点的最迟时间减去开始结点的最早时间再减去工序时间，即 TFi-j = LTj - ETi - Di-j关键工序一个工序的总时差为0意味着该工序在不影响工期前提下机动时间为0，即该工序的最早开始时间也是最迟开始时间，其开始和结束时间没有一点机动的余地，它的工序时间的任何延长都会引起工期的延后，这样的工序称为关键工序。关键线路由关键工序构成的由网络计划始点到终点的线路称为关键线路。关键线路也是从始点到终点时间最长的线路，其长度就是计算工期。2、用标号法求工期 T步骤：（1）标出各事项的最早时间（2）终点即为工期的标号T1A (2)D (3)C (2)2E (4)3F

15、(7)B (0)G(6)45E(0)6I (10)7J(3)H (4)8B (3)0233ETj 、给任意事项标， ETj =max以”为箭头的各箭之“箭尾+箭长Di-j661316、给始点标03、用标号法求关键路线步骤：1A (2)D (3)C (2)2E (4)3F(7)B (0)G(6)45E(0)6I (10)7J(3)H (4)8B (3)0233661316（1）标出各事项的最迟时间T、给终点标1612813330LTi=min以”为箭尾的各箭之“箭头 箭长 、给任意事项标， 12LTiDi-j注：关键工序头尾皆有=（反之未必成立）TFi-j =的的（2）计算各工序的总时差TFi-j ：则关键工序为TFi-