运筹学网络计划.ppt

运筹学教程第九章第九章 网络计划网络计划用于项目管理用于项目管理运筹学教程•用网络分析的方法编制的计划称为网络计划它是五十年代末发展起来的一种编制大型工程进度计划的有效方法1956年，美国杜邦公司在制定企业不同业务部门的系统规划时，制定了第一套网络计划这种计划借助于网络表示各项工作与所需要的时间，以及计划执行过程中的关键路线 运筹学教程•这种方法称为关键路线法（缩写为CPM）1958年美国海军武器部，在制定研制“北极星”导弹计划时，同样也应用了网络分析方法与网络计划但它注重于对各项工作安排的评价和审查这种计划称为计划评审方法（缩写为PERT）鉴于这两种方法的差别，CPM主要应用于以往在类似工程中已取得一定经验的承包工程；PERT更多地应用于研究与开发项目 运筹学教程•在这两种方法得到应用推广之后，又陆续地出现了类似的最低成本和估算计划法，产品分析控制法，人员分配法，物资分配和多种项目计划制定法等等虽然方法很多，各自侧重的目标有所不同但它们都应用的是CPM和PERT的基本原理和基本方法 运筹学教程•六十年代我国开始应用CPM与PERT，并根据其基本原理与计划的表达形式，称它们为网络技术和网络方法，又按照网络计划的主要特点――统筹安排，把这些方法称为统筹法。

运筹学教程•国内外应用网络计划的实路表明，它具有一系列优点，特别适用于生产技术复杂，工作项目繁多、且联系紧密的一些跨部门的工作计划例如新产品研制开发，大型工程项目，生产技术准备，设备大修等计划还可以应用在人力、物力、财务等资源的安排，合理组织报表、文件流程等方面 运筹学教程•编制网络计划包括绘制网络图，计算时间参数，确定关键路线及网络优化等环节下面分别讨论这些内容运筹学教程•网络计划的性质及特点网络计划的性质及特点•优点：优点： ①①能全面而明确地反映出各项工作之间的相互依赖、能全面而明确地反映出各项工作之间的相互依赖、相互制约的关系相互制约的关系 ②②反映出整个工程和任务的全貌，指出对全局性有反映出整个工程和任务的全貌，指出对全局性有影响的关键线路和关键工作影响的关键线路和关键工作 ③③显示了机动时间，以便更好地使用人力、设备显示了机动时间，以便更好地使用人力、设备 ④④可利用计算机，编制程序上机可利用计算机，编制程序上机 ⑤⑤便于优化和调整便于优化和调整•缺点：缺点： 流水作业的情况很难在计划上反映出来流水作业的情况很难在计划上反映出来运筹学教程 第一节第一节 网络图网络图例例1：某一设备维修网络图：某一设备维修网络图4225DCBA12453A：设备拆卸； 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运筹学教程二二 事项（事件、结点）事项（事件、结点）•定义：工程（计划）的始点、终点（完成点） 或其各项作业的连接点（交接瞬间）•表示方法：ii（结点编号）： ①表示事项时间大致顺序 自左向右自上向下排列 ②一般以正整数表示 ③一个结点只有一个编号 ④各结点不允许重复使用 一个编号运筹学教程三三路线路线 定义定义：从网络图始点开始，顺着箭头方向前进，连续不断地到达终点的一条通道称为网络图的一条路线。

各条路线所需的周期为对应的作业时间之和 关键路线和关键工序关键路线和关键工序： 概念概念：网络图中所需工时最长的路线称为关键路线 关键路线上的工序称为关键工序 表示方法表示方法：关键路线及工序常用双线表示 注意注意：（1）关键路线的完成时间决定整个工程的完工时间； （2）关键路线可能不只一条关键路线越多，组织工作 越好，安排越紧凑； （3）关键路线与非关键路线可以转化运筹学教程一一 网络图必须只有一个网络始点和一个终点网络图必须只有一个网络始点和一个终点二二 网络图是有方向的，不允许出现回路网络图是有方向的，不允许出现回路三三 直接连接两个相邻结点之间的活动只能有一个直接连接两个相邻结点之间的活动只能有一个四四 逻辑关系正确，箭线两端必须必须有节点逻辑关系正确，箭线两端必须必须有节点五五 正确运用虚工作正确运用虚工作一、一、 网络图的绘制原则网络图的绘制原则运筹学教程一一网络图必须只有一个网络始点和网络图必须只有一个网络始点和一个终点一个终点 23543’145321错错错错对对对对运筹学教程二二 网络图是有方向的，不允许出现回路网络图是有方向的，不允许出现回路 12345B BA AC CD DE E错错运筹学教程三三 直接连接两个相邻结点之间的活动只能有一个直接连接两个相邻结点之间的活动只能有一个3543453’’ 3’D 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)任务分解二、实例工作工作内容紧前工作工时（周）ABCDEFGHIJKL市场调查资金筹备需求分析产品设计产品研制制定成本计划制定生产计划筹备设备筹备原材料安装设备调集人员准备开工投产／／AADC,EFB,GB,GHGI,J,K4103682328521运筹学教程(2)绘制网络图（尽量用水平和竖直线）12345678910AFECDAKIHJLB4103682328251运筹学教程(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天完工的概率T＝ΣTi=58.98查表0.597工序Tσ2cdfgh 10.5010.1620.335.16 12.831.360.254.00 2514.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）工作单时差 不影响紧后工作的最早开工时间运筹学教程•例118972310654468322382510041018202323253132323126232320181040044101820232323232531010041513182029232324263110tEStLSRr001100000013611001100006130100运筹学教程五、时间参数的图上计算法六、表上计算法见下表 原则：工作的排列应严格按照箭尾事项编号由小到大的顺序排列，箭尾事项相同的工作，按其箭头事项有小到大排列工作工作工时t(i,j)最早开工tES(i,j)最早完工tEF(i,j)最迟开工tLS(i,j)最迟完工tLF(i,j)总时差R(i,j)单时差r(i,j)关键工作箭尾i箭头j12345678910①①②②③④⑤⑥⑥⑦⑦⑧⑨②⑦③④④⑤⑥⑦⑨⑧⑨⑨⑩41063823022851040104104 71018 18 20 2023 23 23 23 25 23 25 23 3125 3031323231312631232624312923232320201818101815104231340013011000061010013011000060010********运筹学教程七、概率型网络图的时间参数计算例2 已知网络计划见下表，求25月完工概率工作ambtσ ①-②①-③②-⑥③-④③-⑤③-⑥④-⑤⑤-⑥⑤-⑦⑥-⑦756471034738794813459109812410196711886.833948.16713.54.1675.16794.50.3330.5100.51.50.50.50.6670.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人数5102015181920951运筹学教程 1 2 3 4 5 6 7 8 9 10 01114235642234395763134时标网络图0人数5102015919201851运筹学教程 1 2 3 4 5 6 7 8 9 10 01114235642234395763134时标网络图0人数51020159102018141运筹学教程 1 2 3 4 5 6 7 8 9 10 01114235642234395763134时标网络图0人数51020159107910运筹学教程四、工期费用优化•直接费用： 指人工、材料、能源等与各项活动直接有关的费用；活动作业时间越短，直接费用就越大。

•间接费用： 指管理费用，销售费用等费用；它与各项活动时间无直接关系，而与工程周期长短直接相关运筹学教程工程费用与工期关系图 0直接费用间接费用总费用费用时间1.直接费用的计算直接费用的计算•假定直接费用与工期为线性关系，如图： MdMijmij Dij费用时间BA dijmij为极限费用；Mij为正常费用； dij为极限工期；Dij为正常工期；d为压缩后的作业时间；M为压缩后的直接费用运筹学教程•几个概念•Mij指当工期延长到—定程度，直接费用不能再随之下降时的费用；•Dij指对应正常费用（ Mij ）的工期；•mij指当工期缩短到一定程度，再增加直接费用，工期也不能再缩短时的费用； dij指对应极限费用（ mij ）的工期 运筹学教程•直接费用变动率•指活动作业时间每缩短或延长一个单位时间所需增加或减少的费用结论：•直接费用变动率越大，则缩短工期而增加的直接费用越多•时间——费用优化时，首先应缩短关键线路上cij值最小的活动作业时间 运筹学教程2.间接费用的计算间接费用的计算•设单位时间间接费用额为Cj 则工期Tx对应的间接费用CJ 为：CJ =CjTx 运筹学教程（三）时间（三）时间—费用优化的原则费用优化的原则 ① 关键线路上的活动优先；② 直接费用变化率小的活动优先；③ 逐次压缩活动的作业时间以不超过赶工时间为限； 运筹学教程•具体步骤： 1)用正常作业时间计算网络时间参数、活动直接费用变化率及工程周期。

2)计算正常时间条件下的工程总费用3)逐步压缩关键线路的延续时间，找出最低费用及最佳工期注意： 每次优化以后，会引起关键线路的变化，因而要重新绘制网络图，寻找出关键线路 运筹学教程例3 工作 正常工时 特急工时成本斜率cij(元／d)时间(d)费用(元)时间(d)费用(元)①－②②－③ ②－④ ③－④③－⑤④－⑥⑤－⑥243022262418185000900040001000080005400640016181824201810700010200480010300900054006800250100200150250－50运筹学教程 Mij=47800元 正常情况下，总间接费用18000，缩短一天减少330元求最低成本日程12345624302226241818T=74250,8100,12200,4150,2250,4－,050,8运筹学教程12345624302226241818T=74250,8100,12200,4150,2250,4－,050,812345624182226241818T=6412?20运筹学教程12345624202226241818T=64250,8100, 2200,4150,2250,4－,050.812345624182026241818T=62250,8100, 0200,2150,2250,4－,050.8运筹学教程不能继续缩短工期以降低成本。

总工期62天，总成本63440元 关键线路多条，必须同时缩短寻求费用最小的缩短边可以化为寻求最小割集问题运筹学教程二、甘特图（Gantt Chart）1、对各项活动进行计划调度与控制2、简单、醒目、便于编制3、横向表示时间，纵向表示活动4、各种图形符号x活动开始时间结束时间工作量目前进度分析设计实施验收与评价甘特图的例子。