《运筹学清华大学》PPT课件

《《运筹学清华大学》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十一章网络计划章节大纲工程计划网络图的绘制网络时间的计算关键路线与网络优化一、工程计划网络问题（关键路径法）问题的一般提法设：有一项工程，分为若干道工序；已知各工序间的先后关系，以及各工序所需时间t。问：（1）工程完工期T=？（2）工程的关键工序有哪些？2.解法——关键路径法（CPM）（1）绘制工程网络图（2）求完工期（用标号法）（3）求关键路（用标号法）1.1网络计划图网络计划图的基本思想是：首先应用网络计划图来表示工程项目中计划要完成的各项工作，完成各项工作必然存在先后顺序及其相互依赖的逻辑关系；这些关系用节点、箭线来构成网络图。网络图是由左向右绘

2、制，表示工作进程。并标注工作名称、代号和工作持续时间等必要信息。通过对网络计划图进行时间参数的计算，找出计划中的关键工作和关键线路；通过不断改进网络计划，寻求最优方案，以求在计划执行过程中对计划进行有效的控制与监督，保证合理地使用人力、物力和财力，以最小的消耗取得最大的经济效果。网络计划图是在网络图上标注时标和时间参数的进度计划图，实质上是有时序的有向赋权图。表述关键路线法（CPM）和计划评审技术（PERT）的网络计划图没有本质的区别，它们的结构和术语是一样的。仅前者的时间参数是确定型的，而后者的时间参数是不确定型的。1.1网络计划图工序在网络计划图中，

3、用箭线表示工作，箭尾的节点表示工作的开始点，箭头的节点表示工作的完成点。用（i-j）两个代号及箭线表示一项工作。在箭线上标记必须的信息，如下图：箭尾事项箭头事项工序之间的关系紧前工序：紧排在本工作之前的工作；且开始或完成后，才能开始本工作。紧后工序：紧排在本工作之后的工作；本工作开始或结束后，才能开始或结束的工作。虚工序：不占用时间和不消耗人力，资金等的虚设的工作。虚工序只表示相邻工序之间的逻辑关系。网络图的要求相邻节点只能是一个工序的相关事项；网络图中不能有缺口和回路应改正为TS1234ABC123456DABCE1）顺序：按工序先后从左至右；2）图中

4、弧（箭线）：表示工序；顶点（结点）：表示相邻工序的时间分界点，称事项，用表示。相邻弧：表示工序前后衔接关系，称紧前（后）工序；3）要求：图中不得有缺口、回路和多重边。i缺口：多个始点或多个终点的现象。（应当只有一个始点和终点）绘制工程网络图处理方法：增加虚工序。多重边：两点间有多于一条的边。AB处理方法：增加虚工序。AA’B例1为筹建某餐馆，需制定计划。将工程分为14道工序，各工序需时及先后关系如下表。试求该工程完工期T及关键路径。回路：方向一致的闭合链。工序内容紧前工序所需天数A购买炉灶及材料——10B购买室内设备——3C招集工人——1D选择开业地点—

5、—2E申请许可得到执照D7F修理门窗、粉刷墙壁E3G砌炉灶、水池A、F5H接通上下水道G4I安装室内设备B、H4J做好室内装饰B、H3K购进米面及副食品I、J6L张贴开业广告G3M人员训练C、I4N开业前操作试验K、L7工序ABCDEFGHIJKLMN紧前工序____DEAFGBHBHIJGCIKL所需天数1031273544363471CBAD2E3F4G5H6IJ7I’8KL9I’’M10N11网络计划图的时间参数计算网络图中工作的时间参数。它们是：工作持续时间(D)；工作最早开始时间（ES）；工作最早完成时间（EF）；工作最迟开始时间（LS）；工作

6、最迟完成时间（LF）；工作总时差（TF）；工作自由时差（FF）。工作持续时间(D)——作业时间Ti-j⑴单时估计法（定额法）每项工作只估计或规定一个确定的持续时间值的方法。一般具有工作的工作量，劳动定额资料以及投入人力的多少等，计算各工作的持续时间；工作持续时间Q—工作的工作量。以时间单位表示,如小时;或以体积，重量，长度等单位表示；R—可投入人力和设备的数量；S—每人或每台设备每工作班能完成的工作量；n—每天正常工作班数。或具有类似工作的持续时间的历史统计资料时，可以根据这些资料，采用分析对比的方法确定所需工作的持续时间。⑵三时估计法在不具备有关工作的

7、持续时间的历史资料时，在较难估计出工作持续时间时，可对工作进行估计三个时间值，然后计算其平均值。这三个时间值是：乐观时间。在一切都顺利时，完成工作需要的最少时间，记作a。最可能时间。在正常条件下，完成工作所需要时间。记作m。悲观时间。在不顺利条件下，完成工作需要最多时间，记作b。显然上述三种时间发生都具有一定的概率，根据经验，这些时间的概率分布认为是正态分布。一般情况下，通过专家估计法，给出三时估计的数据。可以认为：工作进行时出现最顺利和最不顺利的情况比较少。较多是出现正常的情况。按平均意义可用以下公式计算工作持续时间值：工作最早开始时间ES和工作最早完

8、成时间EF工作的最早开始时间ES是紧前工序最早结束时间。ES=TE（i）EF=E