运筹学教程第九章 网络计划用于项目管理运筹学教程 用网络分析的方法编制的计划称为网络计划 。它是五十年代末发展起来的一种编制大型 工程进度计划的有效方法。1956年，美国杜 邦公司在制定企业不同业务部门的系统规划 时，制定了第一套网络计划。这种计划借助 于网络表示各项工作与所需要的时间，以及 计划执行过程中的关键路线。 运筹学教程 这种方法称为关键路线法（缩写为CPM）。 1958年美国海军武器部，在制定研制“北极星 ”导弹计划时，同样也应用了网络分析方法与 网络计划。但它注重于对各项工作安排的评 价和审查。这种计划称为计划评审方法（缩 写为PERT）。鉴于这两种方法的差别，CPM 主要应用于以往在类似工程中已取得一定经 验的承包工程；PERT更多地应用于研究与开 发项目。 运筹学教程 在这两种方法得到应用推广之后，又陆续地 出现了类似的最低成本和估算计划法，产品 分析控制法，人员分配法，物资分配和多种 项目计划制定法等等。虽然方法很多，各自 侧重的目标有所不同。但它们都应用的是 CPM和PERT的基本原理和基本方法。 运筹学教程 六十年代我国开始应用CPM与PERT，并根据 其基本原理与计划的表达形式，称它们为网 络技术和网络方法，又按照网络计划的主要 特点统筹安排，把这些方法称为统筹法 。运筹学教程 国内外应用网络计划的实路表明，它具有一 系列优点，特别适用于生产技术复杂，工作 项目繁多、且联系紧密的一些跨部门的工作 计划。例如新产品研制开发，大型工程项目 ，生产技术准备，设备大修等计划。还可以 应用在人力、物力、财务等资源的安排，合 理组织报表、文件流程等方面。 运筹学教程 编制网络计划包括绘制网络图，计算时间参 数，确定关键路线及网络优化等环节。下面 分别讨论这些内容。运筹学教程 网络计划的性质及特点 优点：能全面而明确地反映出各项工作之间的相互依 赖、相互制约的关系反映出整个工程和任务的全貌，指出对全局性 有影响的关键线路和关键工作显示了机动时间，以便更好地使用人力、设备可利用计算机，编制程序上机便于优化和调整 缺点：流水作业的情况很难在计划上反映出来运筹学教程第一节 网络图例1：某一设备维修网络图4225DCB A12453A：设备拆卸； B：电器部分修理 ； C：机械部分修理； D：设备安装调试 。网络图的组成：节点箭线（包 括虚线）工作代号消耗时间运筹学教程一 工作或工序（作业、 活动） 定义：指一项有具体内容的、需要人力、物力、财力、占用一 定空间和时间才能完成的活动过程。 虚活动（作业）：只表示作业之间相互依存、相互制约、相互 衔接的关系，但不需人力、物力、空间和时间的虚设的活动。 示例1： 示例2： 先行活动、后续活动和并行活动B B12121 14 46 63 35 52 2产品设计产品设计A A自制零部件自制零部件B B1 1外购零部件外购零部件B B2 2装配装配C C样品鉴定样品鉴定D DA AD DC CB B455035155运筹学教程二 事项（事件、结点） 定义：工程（计划）的始点、终点（完成点）或其各项作业的连接点（交接瞬间）。 表示方法：i i（结点编号）： 表示事项时间大致顺序自左向右自上向下排列一般以正整数表示一个结点只有一个编号各结点不允许重复使用一个编号运筹学教程三路线定义：从网络图始点开始，顺着箭头方向前进，连续不断地到达终点的 一条通道称为网络图的一条路线。各条路线所需的周期为对应的作业时间 之和。关键路线和关键工序：概念：网络图中所需工时最长的路线称为关键路线。关键路线上的工序称为关键工序表示方法：关键路线及工序常用双线表示注意：（1）关键路线的完成时间决定整个工程的完工时间；（2）关键路线可能不只一条。关键路线越多，组织工作越好，安排越紧凑；（3）关键路线与非关键路线可以转化。运筹学教程一 网络图必须只有一个网络始点和一个终点 二 网络图是有方向的，不允许出现回路 三 直接连接两个相邻结点之间的活动只能有一 个 四 逻辑关系正确，箭线两端必须必须有节点 五 正确运用虚工作一、 网络图的绘制原则运筹学教程 网络图必须只有一个网络始点和一 个终点23543145321错错对对运筹学教程二 网络图是有方向的，不允许出现回路12345B BA AC C D DE E错错运筹学教程三 直接连接两个相邻结点之间的活动只能有一 个35434533D DC CB BA AD DC CB BA A错错对对运筹学教程 箭线首尾必有结点，不能从箭线中间引 出另一条箭线14131211131211配砂配砂造型造型造型造型配砂配砂2 2配砂配砂1 1对对错错运筹学教程五 虚作业的运用不消耗资源，表示逻辑关系。必要时加虚节点 。运筹学教程作业名称和内容作业 代号后续作 业代号作业长 度（月 ）设计AB、C1基本建设BD8订购设备CD3安装设备DE6试车E结束1运筹学教程124563ABDEC18613运筹学教程ABACD另一例：关系如下，如何合在一起 ？运筹学教程ABCDABCDB和C没有 前后关系 ，用虚工 作表示A 和D的前 后关系。运筹学教程ABCDACEABCDEABCDE另一例：如何处理 ？ ？OK运筹学教程网络图的绘制步骤一 定义各项作业（工作）恰当地确定各项工作范围，以使网络图复杂程度适中二 编制工作表（示例）（1）列出各项作业清单 （2） 确定或估计各项作业时间（3）表明各项作业之间的逻辑关系三 画网络图 （1）确定各项作业层次：无紧前作业的层次为1；其它各作业层次数 = 紧前作业层次中最大者 + 1（2）画草图 （3） 画正图 （4） 进行结点编号运筹学教程(1)任务分解二、实例工作工作内容紧前工作 工时（周 ） A B C D E F G H I J K L市场调查 资金筹备 需求分析 产品设计 产品研制 制定成本计划 制定生产计 划 筹备设备 筹备原材料 安装设备 调集人员 准备开工投产 A A D C,E F B,G B,G H G I,J,K4 10 3 6 8 2 3 2 8 5 2 1运筹学教程(2)绘制网络图（尽量用水平和竖直线）12345678910AFECDAKIHJLB410368 2328251运筹学教程(3)节点编号箭尾编号小于箭头编号。进入节点的所有箭头的箭尾都必须编号， 该节点才能编号运筹学教程 三、网络计划的分类 （一）按性质分类1.肯定型网络计划2.非肯定型网络计划 （二）按表示方法分类1.单代号2.双代号 （三）按目标分类1.单目标网络计划2.多目标网络计划运筹学教程 （四）按有无时间坐标分类1.时标网络计划2.非时标网络计划 （五）按层次分类1.总网络计划2.局部网络计划 （六）按工作衔接特点分类1.普通网络计划2.搭接网络计划3.流水网络计划运筹学教程第二节 时间参数计算 例9-3 四条路线 1-2-3-5-8：13 1-2-4-6-7-8：17 1-2-6-7-8：12 1-2-3-4-6-7-8：21 关键线路决定工期，各项工作有轻重缓急之分 。158236474523421342运筹学教程一、作业时间t(i,j)的确定完成某一工序所需要的时间 （1）确定型资源确定，时间可确定计算 （2）概率型（三点时间估计） 乐观时间：在顺利情况下，完成工序所需要 的最少时间，常用符号a表示； 最可能时间：在正常情况下，完成工序所需 要的时间，常用符号m表示； 悲观时间：在不顺利情况下，完成工序所需 要的最多时间，常用符合b表示。运筹学教程运筹学教程例：60天完工的概率TTi=58.98 查表0.597工序T2c d f g h 10.50 10.16 20.33 5.16 12.831.36 0.25 4.0025 14.67运筹学教程二、事项时间参数 (1)事项最早时间(后面工作的最早可能开工时间 )tE(n)=总最早完工期从前向后计算，取大值运筹学教程（2）事项最迟时间(后面工作的最迟必须开工时间 )确定工期，从右向左计算取小值。tL(t)三、工作的时间参数 1.最早可能开工时间与最早可能完工时间。tES(i,j)（i事项最早时间）， tEF(i,j) 2.最迟必须开工时间与最迟必须完工时间。tLS(i,j)， tLF(i,j)(j事项最迟时间)运筹学教程四、时差 （1）工作总时差不影响总工期的最多机动时间。（2）工作单时差不影响紧后工作的最早开工时间。运筹学教程 例118972310654468322382510041018202323253132 323126232320181040044101820232323 2325310100415131820292323 242631 10tES tLSR r001100000013611001100006130100运筹学教程五、时间参数的图上计算法六、表上计算法 见下表原则：工作的排列应严格按照箭尾事项编号 由小到大的顺序排列，箭尾事项相同的工作 ，按其箭头事项有小到大排列。工作工作工时 t(i,j)最早开工 tES(i,j)最早完工 tEF(i,j)最迟开工 tLS(i,j)最迟完工 tLF(i,j)总时 差 R(i,j)单时 差 r(i,j)关键工作 箭尾i箭头j12345678910 4 10 6 3 8 2 3 0 2 2 8 5 104 010 410 4 7 101818 20202323 2323 2523 2523 31 25 30 313232313126312326243129232323202018181018151042313400 13 0 11 0 0 0 0 6 1 0 1 00 13 0 11 0 0 0 0 6 0 0 1 0* * * *运筹学教程七、概率型网络图的时间参数计算 例2 已知网络计划见下表，求25月完工概率工作ambt - - - - - - - - - - 7 5 6 4 7 10 3 4 7 38 7 9 4 8 13 4 5 9 109 8 12 4 10 19 6 7 11 88 6.833 9 4 8.167 13.5 4.167 5.167 9 4.50.333 0.5 1 0 0.5 1.5 0.5 0.5 0.667 0.833运筹学教程1235746(8,0.333)(6.833,0.5 )(9,1)(4,0)(8.167,0.5)(13.5,1.5 )(4.167,0.5 )(5.167,0.5 )(9,0.667)(4.5,0.833 )运筹学教程第三节 网络计划的优化应从工期、成本、资源消耗等方面综合评价。一、把串联工作改为平行工作或平行交叉工作 。124444运筹学教程二、利用时差尽量利用单时差，其次总时差。三、资源配置优化12354642234395763134时间人数运筹学教程1 2 3 4 5 6 7 8 9 10 01114235642234395763134时 标 网 络 图0人数51020 151819209 5 1运筹学教程1 2 3 4 5 6 7 8 9 10 01114235642234395763134时 标 网 络 图0人数51020 15 91920185 1运筹学教程1 2