《管理运筹学网络规划课件.ppt》由会员分享，可在线阅读，更多相关《管理运筹学网络规划课件.ppt（48页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第七章网络规划第七章网络规划第七章网络规划第七章网络规划第一节：现实中的网络规划问题第一节：现实中的网络规划问题第二节：图的基本概念第二节：图的基本概念 第三节：树第三节：树 第四节：最大流问题第四节：最大流问题 第五节：最短路径问题第五节：最短路径问题 第六节：最小费用最大流问题第六节：最小费用最大流问题第七节：网络计划技术第七节：网络计划技术第八节：网络规划的应用第八节：网络规划的应用7.77.7网络计划技术当系统决策之后，面临的问题就是制定计划和组织实施。网络计划技术就是在制定计划和组织实施过程中采用的一种科学方法。本节主要对目前管理中常用的网络计划方法做一系统的介绍。网络计划技术利用网
2、络图对计划任务的进度、费用及其组成部分之间的相互关系进行计划、检查和控制，以使系统协调运转的科学方法。由于这种方法的主要特点是统筹安排，为了突出这一特点，我国把各种不同的网络计划方法统称为统筹法。一、系统管理的网络计划技术一、系统管理的网络计划技术（一）甘特图法该方法是科学管理的奠基人泰勒的学生、美国福兰克兵工厂顾问甘特于 20 世纪40 年代开发的一种计划与管理技术。它以时间为横坐标，以工序为纵坐标，以线条的长短表示一项工作或作业的开始和完成时刻以及工作的进展情况。由于它以条形图进行系统计划与管理，故又称横道图、条形图等，图7-28即是一份简化的现场准备作业的条形图。甘特图平整场地建休息室建
3、材料库设备安装材料进场施工一、系统管理的网络计划技术一、系统管理的网络计划技术（二）关键线路法关键线路法（Critical Path Method，CPM）是美国杜邦公司为建造新工厂从事计划与管理的研究而提出的，并在 1958 年的建厂工作中发挥了很大作用，使工程工期提前两个月，初步显示出其优越性。而后，杜邦公司不仅把 CPM 法应用于大型工程，而且也应用于小型工程和维修工程，都同样收到了良好的效果。美国加泰迪克公司在 47项工程中使用 CPM 法，平均节约时间 22%，节约资金 15%，其效果是显著的。一、系统管理的网络计划技术一、系统管理的网络计划技术（三）计划评审技术计划评审技术（Pro
4、gram Evaluation and Review Teacnique，PERT，也称计划协调技术）是由美国海军特种计划局和洛克希德公司、汉米尔顿公司于 1958 年 1 月联合开发的一种新的计划管理方法。它的首次应用使美国“北极星”导弹潜艇工程的工期由原计划的十年缩短为八年。由于它的成功，自 1962 年起美国政府规定一切新开发的工程项目必须采用这种方法。我国的很多大型开发性工程也都应用了这种方法，收到了良好的效果。一、系统管理的网络计划技术一、系统管理的网络计划技术（四）决策关键线路法任何一项工作都可用多种方案进行计划和管理，因此需要在多种方案的比较中进行决策。然而 CPM 和 PERT
5、 二种方法虽然先进，但却只能考虑完成任务的一种方案，对不同方案必须画出不同的网络图，不仅增大绘制网络图的工作量，而且，在比较和分析时也不能一目了然。为了克服这种局限性，又开发了决策关键线路法（Decision CriticalPath Method，DCPM）。一、系统管理的网络计划技术一、系统管理的网络计划技术（五）图解评审技术上述各种方法中各工序均属确定型工序，但实践中存在随机工序，如检验工序后的返修工序，这类工序应用上述各种方法很难解决，图解评审技术（Graphical evaluationand Review Technique，GERT）是一种广义网络计划法，是解决这类问题的一种方法
6、。二、二、网络计划技术应用的程序网络计划技术应用的程序（一）、网络计划技术应用的一般程序阶阶 段段步步 骤骤准备阶段确定网络计划目标调查研究工作方案设计绘制网络图项目分解逻辑关系分析绘制网络图时间参数计算与确定关键线路计算工作持续时间计算其他时间参数确定关键线路编制可行的网络计划检查与调整编制可行的网络计划优化并确定正式网络计划优化编制正式网络计划实施、调整与控制网络计划的贯彻检查和数据采集调整、控制结束阶段总结分析二、二、网络计划技术应用的程序网络计划技术应用的程序（一）、网络计划技术应用的一般程序阶阶 段段步步 骤骤准备阶段确定网络计划目标调查研究工作方案设计绘制网络图项目分解逻辑关系分析
7、绘制网络图时间参数计算与确定关键线路计算工作持续时间计算其他时间参数确定关键线路编制可行的网络计划检查与调整编制可行的网络计划优化并确定正式网络计划优化编制正式网络计划实施、调整与控制网络计划的贯彻检查和数据采集调整、控制结束阶段总结分析（二）、网络图的绘制1、网络图的组成任务任务工作工作线路线路起点开始沿箭线方向连续通过一系列箭线和节点最后到达终点所经过的路线指一项有目的、有开始和结束标志的许多相互关联且有不同指标要求的工作所组成为完成某项任务在工艺和组织管理上相互独立的活动（子任务）紧前工作紧前工作紧后工作紧后工作（二）、网络图的绘制2、网络图的绘制（1）任务的分解和分析）任务的分解和分析
8、序号编码工序名称紧后工序工期调整期（二）、网络图的绘制2、网络图的绘制（2）画网络图画网络图 单代号网络图工作代号持续时间工作名称工作代号持续时间工作名称（二）、网络图的绘制2、网络图的绘制（2）画网络图画网络图 双代号网络图FEDCBA12图7-30双代号网络图3456双代号（AOA）网络图（activityonarrow network）是用有向箭线及其两端的两个节点编号表示工作的网络图。在双代号网络图中，每一项工作都用一根有向箭线和箭线两端的两个节点来表示，每个节点都编以号码，箭线两端的两个节点的号码即代表该箭线所表示的工作三、双代号网络图的绘制1.双代号网络图的组成FEDCBA1234
9、56持续时间工作名称iijj由工作、节点（事件）和线路三部分组成。节点线路352364虚工作关键线路关键线路2.双代号网络图的绘制（1）双代号网络图各种逻辑关系的正确表示方法该工作必须在哪些工作之前进行？该工作必须在哪些工作之后进行？该工作可以与哪些工作平行进行？ij的平行工作ij工作ij的紧后工作ij的紧前工作ijhijkm图7-35双代号网络图中工作之间的关系hmk虚工作一般起联系、区分和断开三个作用详见P231的表7-82.双代号网络图的绘制（2）双代号网络图的绘制规则必须正确表达已定的工作间的逻辑关系。网络图中，严禁出现循环回路。严禁出现双向箭头箭线和无箭头连线。严禁出现没有箭头节点的
10、箭线或没有箭尾节点的箭线当某节点有多条外向箭线或有多条内向箭线时，可采用母线法绘图，允许多条箭线经一条共用母线引出或引入节点应尽量避免箭线交叉，当箭线交叉不可避免时，可采用过桥法或指向法。只能有一个起点节点；在不分期完成任务的网络图中，应只有和一个终点节点；其他所有节点均为中间节点。任意两个节点之间只能有一条唯一的箭线，不得有两个或两个以上的箭线从同一节点出发且同时指向同一节点。详见P234、5的图2.双代号网络图的绘制（3）双代号网络图的节点编号箭尾节点的号编码应小于箭头节点的号码。在一个网络图中，所有的节点不能出现重复的编号。（4）双代号网络图的绘制步骤分解任务，划分施工工作，制定完成任务
11、的全部工作结构分解表。确定全部工作的逻辑关系，绘制工作逻辑关系表（矩阵表）确定每一工作的持续时间，制定最终的工程分析表根据工程分析表绘制并修改网络图。2.双代号网络图的绘制（5）双代号网络图的绘制方法绘制没有紧前工作的工作箭线，使他们具有相同的开始节点，以保证网络图只有一个起点节点。依次绘制其他工作箭线。当各项工作箭线都绘制出来以后，应合并那些没有紧后工作的工作箭线的箭头节点，以保证网络图只有一个终点节点。无紧前工作的工作（即双代号网络图开始的第一项工作），其开始节点位置号为零；有紧前工作的工作，其开始节点位置号等于其紧前工作的开始节点位置号的最大值加1；有紧后工作的工作，其结束节点位置号等于
12、其紧后工作的开始节点位置号的最小值；无紧后工作的工作（即双代号网络图开始的最后一项工作），其结束节点位置号等于网络图中各工作的结束节点位置号的最大值加1。节点编号：第7章 网络规划21例7-9已知某任务的工作构成及其逻辑关系如表7-6所示，试绘制双代号网络图。工作代号ABCDEGH紧前工作A、BB、C、DC、D工作紧前工作ABCDEGHABCDEGH解：用矩阵表确定紧后（前）工作确定各工作的开始节点位置号和结束节点位置号工作代号ABCDEGH紧前工作A、BB、C、DC、D紧后工作EE、GG、HG、H开始节点位置号00000+110+110+11结束节点位置号Max11Max1，11Max1，1
13、1Max1，111+121+121+12第7章 网络规划22EDCBA120图7-46-aDCBA120HEDCBA120图7-46-c图7-46-bEA120图7-46-e网络图绘图过程120HEDCBAGHDCB51234G67图7-46-d网络图绘图过程第7章 网络规划23例7-10已知某项目的工作构成及其逻辑关系如表7-9所示，试绘制双代号网络图。序号工作代号紧前工作持续时间1A12B53CA34DA25EB、C66FB、C57GD、E58HD、E、F3根据工序之间的关系初步绘制如图7-47。GFEDCBA4325H6187933556251GFEDCBA2H31546简化为图7-48
14、。四、双代号网络图的时间参数计算（一）、时间参数的概念1、工作持续时间（1）定额计算法（确定型）：Di j工作ij的持续时间Qi j工作ij的工程量S产量定额（m3/工日、m2/工日、T/工日、m3/台班）R工人数（机械台班数）H时间定额(H1S)四、双代号网络图的时间参数计算（一）、时间参数的概念1、工作持续时间（2）三时估算法：Di j工作ij的持续时间 a工作ij的乐观持续时间估计值(Optimistic time)b工作ij的悲观持续时间估计值(Pessimistic time)；m工作ij的最可能持续时间估计值(Most Likely time)。四、双代号网络图的时间参数计算（一）
15、、时间参数的概念2、工期（1）计算工期计算工期：根据网络计划的时间参数计算出来的工期，用Tc表示。（2）要求工期要求工期：任务委托人提出的所要求的工期，用Tr表示。（3）计划工期计划工期：在要求工期和计算工期的基础上综合考虑需要和可能而确定的工期，用Tp表示。3、工作最早时间最早开始时间最早开始时间：是指在紧前工作的约束条件下，本工作可能开始的最早时刻，用ESESi-ji-j 表示。最早完成时间最早完成时间：是指在紧前工作的约束条件下，本工作可能完成的最早时刻，用EFEFi-ji-j 表示。四、双代号网络图的时间参数计算（一）、时间参数的概念4、工作最迟时间最迟开始时间最迟开始时间：是指在不影
16、响整个任务按期完成的前提下，本工作最迟必须开始的时刻，用LSLSi-ji-j 表示。最迟完成时间最迟完成时间：是指在不影响整个任务按期完成的前提下，本工作最迟必须完成的时刻，用LFLFi-ji-j 表示。5、工作的时差总时差总时差(TotalFloatTime)：在不影响总工期的前提下，本工作可以利用的机动时间，用TFTFi-ji-j 表示。自由时差自由时差(FreeFloatTime)：在不影响紧后工作最早开始时间的前提下，本工作可以利用的机动时间，用FFFFi-ji-j 表示。四、双代号网络图的时间参数计算（三）、时间参数的计算（图上计算法）1、按工作计算法计算时间参数（1 1）工作的最早
17、开始时间和最早完成时间）工作的最早开始时间和最早完成时间没有紧前工作的工作ij（以起点节点为箭尾节点的工作)ESij=0TFi jLSi jESi j持续时间工作名称ijEFi jLFi jFFi j有紧前工作的工作ij，当工作ij只有一项紧前工作hi时ESijEShiDhi当工作ij有多项紧前工作时ESijMaxEShiDhi工作ij的最早完成时间应按下式计算：EFijESijDij四、双代号网络图的时间参数计算（三）、时间参数的计算（图上计算法）1、按工作计算法计算时间参数（2 2）网络计划工期的计算）网络计划工期的计算网络计划的计算工期当终点节点为n时，箭头指向终点节点的所有工作的最早完
18、成时间的最大值即为网络计划的计算工期Tc，其计算公式为：Tc=MaxEFmn网络计划的计划工期网络计划的计划工期Tp的确定应按下述规定：当已规定了要求工期Tr时：TpTr当未规定要求工期时，可令计划工期等于计算工期：TpTc 四、双代号网络图的时间参数计算（三）、时间参数的计算（图上计算法）1、按工作计算法计算时间参数（3 3）工作的最迟完成时间和最迟开始时间）工作的最迟完成时间和最迟开始时间工作ij的最迟完成时间LFi j应从网络计划的终点节点开始，逆着箭线方向逐项计算，并符合下列规定：没有紧后工作的工作m n（以终点节点为箭头节点的工作），其最迟必须完成时间LFm n应按网络计划的计划工期
19、Tp确定，即：LFm n=Tp 有紧后工作的工作，当工作ij只有一项紧后工作jk时，其最迟必须完成时间LFi j为：LFi j LFjkDjk 当工作ij有多项紧后工作jk时，其最迟必须完成时间LFi j应为：LFi j=MinLFjkDjk 工作ij的最迟必须开始时间LSi j应按下式计算：LSi j LFi jDi j 四、双代号网络图的时间参数计算（三）、时间参数的计算（图上计算法）1、按工作计算法计算时间参数（4 4）工作的总时差）工作的总时差根据总时差TFi j的定义 TF i jLSi jESi jTF i jLFi jEFi jDi jDi ji j工作的工作时间范围TFi jL
20、Fi jEFi jESi jTFi jijijLSi ji j工作的工作时间范围Di jDjkEFi jESi jijEFj kESj kjkFFi j（5 5）工作的自由时差）工作的自由时差FFi jESjkEFi jFFm nTpEFm n（6）按工作计算法计算时间参数示例工作名称ABCDEFHI紧前工作AAB、CB、CD、ED、E、F持续时间15326553例7-11 已知某项目的有关资料如下表所示:01111123456ABCDEFHI53625531021001611161100511500505083111983105138121411161322111113130141521TP
21、=16关键路线关键路线四、双代号网络图的时间参数计算（三）、时间参数的计算（图上计算法）2、按节点计算法计算时间参数节点最早时间：是指双代号网络计划中，以该节点为开始节点的各项工作的最早能够开始的时间，用ETi表示。节点最迟时间：是指双代号网络计划中，以该节点为完成节点的各项工作的最迟必须完成的时间，用LTi表示。LTiETi持续时间工作名称ijLTjETj2、按节点计算法计算时间参数（1 1）节点最早时间的计算）节点最早时间的计算当起点节点i未规定其最早开始时间时，ETi其值应等于0，即：ETi0 当节点j只有一条内向箭线时，其最早时间ETj为：ETjETiDi j 当节点j有多条内向箭线时
22、，其最早时间ETj为：ETjMaxETiDi j （2 2）网络计划工期的计算）网络计划工期的计算TcETn（3 3）节点最迟时间的计算）节点最迟时间的计算终点节点n的最迟时间LT n应按网络计划的计划工期Tp确定：LTn=Tp 当节点i只有一条外向箭线时，其最迟时间LTi为：LTiLT jDi j 当节点i有多条外向箭线时，其最迟时间LTi为：LTiMinLT jDi j 2、按节点计算法计算时间参数（4 4）工作时间参数的计算）工作时间参数的计算ESi jETiEFi jETiDi j LFi jLT j LSi jLT jDi j TF i jLT jETiDi j FFi jETjET
23、iDi j 例7-13按工作计算法计算时间参数示例工作名称ABCDEFGHIJ紧后工作BCDEFGHHIIJJ-持续时间10102030202030305010123456ABCDEFHI305020301089G101010202030J1002030405050701201301301207090704050701007例7-13按工作计算法计算时间参数示例90504020701020123456D30I50E20H30A10789B10J1010F20C20G30010010005010706002050307050020301050300013012013012004050509090
24、01204080509040400401010070070404001200120707002050507070200010 10207030504040507050907070120120130130（四）、表上计算法紧前工作数工序编号持续时间Di-j最早开始ESi-j最早结束EFi-j最迟开始LSi-j最迟结束LFi-j总时差TFi-j自由时差FFi-j(1)(2)(3)(4)(5)=(4)+(3)(6)=(7)-(3)(7)(8)=(6)-(4)(9)=(4)*-(5)1-2 2 0 2 0 2 0 0 1 2-3 3 2 5 2 5 0 0 1 2-4 2 2 4 3 5 1 0 1
25、3-5 0 5 5 5 5 0 0 1 3-7 2 5 7 6 8 1 1 1 4-5 0 4 4 5 5 1 1 1 4-8 1 4 5 8 9 4 3 2 5-6 3 5 8 5 8 0 0 1 6-7 0 8 8 8 8 0 0 1 6-8 0 8 8 9 9 1 0 2 7-9 2 8 10 8 10 0 0 2 8-9 1 8 9 9 10 1 1 2 9-10 1 10 11 10 11 0 0 五、网络图的优化（一）、工期优化（一）、工期优化工期优化也称时间优化，就是当初始网络计划的计算工期大于要求工期时，通过压缩关键线路上工作的持续时间或调整工作关系，以满足工期要求的过程。压缩
26、关键线路方法调整工作关系的方法（二）、资源优（二）、资源优化化资源(人力、材料、机具设备、资金等)的优化，就是要解决网络计划实施中的资源供求矛盾或实现资源的均衡利用，以保证工程的顺利完成，并取得良好的技术经济效果。通常，资源优化有两种不同的目标：资资源有限，工期最短；源有限，工期最短；工期一定，工期一定，实现资实现资源的需求均衡。源的需求均衡。资源有限使工期最短的优化是指在资源供应有限的前提下，保持各个工作的每日资源需求量(强度)是常数，合理地安排资源分配，寻找最短计划工期的过程。（三）、最优工期（三）、最优工期工期-成本优化的目的在于：(1)寻求直接费与间接费总和即成本最低的最优工期TS，以
27、及与此相对应的网络计划中各工作的进度安排。(2)在工期规定(Ti)的条件下，寻求与此相对应的最低成本，以及网络中各工作的进度安排。优化的思路优化的思路缩短工期缩短关键工作的时间缩短费用率最小的关键工作的时间(1)当关键线路只有一条时，首先将这条线。路上费用率ei-j最小的工作的持续时间缩短t。此时，应满足(3)步骤(1)或步骤(2)的工作应进行多次，以逐步缩短工期，使计划工期满足规定的要求，并计算出相应的直接费总和及各工作的时间参数。且保持被缩短持续时间的工作i-j仍为关键工作（即其压缩幅度小于或等于工作的总时差）。(2)如果关键线路有两条以上时，那么每条线路都需要缩短持续时间t，才能使计划工
28、期也相应缩短t。为此，必须找出费用率总和e i-j为最小的工作组合，我们把这种工作组合称为“最小切割”。优化示例优化示例例7-15 某网络计划中各工作的工期成本数据列于表，给出了各工作的正常持续时间D，加快的持续时间d，及与其相应的直接费用M和，计算后所得的费用率e也列在表中。假定每周的间接费用为1.5万元。试进行工期-成本优化工作-周周万元万元万元周1-26415202.501-33020901001.002-3181050601.252-412840451.253-436221201401.433-5301885920.584-63016951030.575-6241645500.63合计
29、540610 1325466，630，024，1218，630，1236，030，012，48960.571325466，630，024，018，630，036，018，012，48844-6缩短12天总费用减少：-1.5X12+0.57X12=-11.161-3缩短6天1325466，024，024，018，030，036，018，012，42784-6与3-5同时缩短2天总费用减少：-1.5X6+1X6=-31325466，024，024，018，036，016，012，427628，0总费用减少：-1.5X2+1.15X6=-0.70工期周直接费万元间接费万元成本万元96540.0014
30、4684.0084546.84126672.8478552.84117669.8476555.14114669.147.87.8网络规划的应用网络规划的应用 某公司有一个管道网络如图7-29所示，使用这个网络可以把石油从v1运到v7。由于输油管道长短不一，每段管道除了有不同的流量限制cij外，还有不同的单位流量的费用bij。图中每边上的数值表示（cij，bij）。如果使用这个网络运送石油，怎样运送才能运送最多的石油，并使运送的费用最小？v1v3v4v6v5v2v7(6,6)(6,3)(2,5)(3,2)(2,4)(2,3)(1,3)(2,8)(4,4)(5,7)图7-24.应用问题图示 线性规
31、划法求解线性规划法求解 第一步：先求出网络的最大流令（vi，vj）上的流量fij，则最大流的数学模型为：MaxF=f12+f14s.t.(f23+f25)-f12=0(f35+f36)-(f23+f43)=0(f43+f46+f47)-f14=0f57-(f25+f35)=0f67-(f36+f46)=0fijcijfij0图7-25.应用问题电子表格求解图示（1）用电子表格求解，可得最大流量为10，如图7-25所示。线性规划法求解线性规划法求解第二步：在最大流量的所有解中，找出一个最小费用的解。数学模型为：Minz=6f12+3f14+4f25+5f23+4f35+3f36+2f43+3f46+8f47+7f57+4f67s.t.f12+f14=10(f23+f25)-f12=0(f35+f36)-(f23+f43)=0(f43+f46+f47)-f14=0f57-(f25+f35)=0f67-(f36+f46)=00-(f47+f57+f67)=-10fijcijfij0图7-26.应用问题电子表格求解图示（2）用电子表格求解，可得最大流量为10，总费用为145。如图7-26所示