7-网络计划(运筹学)

1补充：网络计划技术(统筹法)基本概念确定性网络计划网络图的优化不确定性网络计划2020/2/272一.什么是网络计划技术/统筹法对于任何一项生产制造、科学实验、工程实施、军事作战等项目活动，为了充分利用有限的时间、空间与资源（人力、物力、财力），都必须编制一个科学的工作组织计划来有效地组织、调度与控制该项活动的进程，以实现最佳的效应和效益。而这种为编制科学的组织计划的有效方法统称为统筹方法。例1甲、乙两工程师从早上六时起床到上班前有一系列活动要做。对于同样的活动过程，有人忙乱不堪，甚至迟到，有人则又快又好，关键在于一个科学的活动实施计划。穿衣刷牙洗脸做稀饭热馒头吃早饭收拾房间整理出门上班甲出门上班穿衣洗脸刷牙收拾房间整理吃早饭做稀饭热馒头乙例2大型工程项目（三峡工程、南水北调工程、人造卫星工程、宇航工程等）有如下活动：产品设计、仿真、试制、中试原材料设备定货、采购、运输、入库厂房、设备施工建筑、安装产品计划、生产、销售、安装、调试、维护参与单位涉及国家各部门、各行业、事业单位，为高速度、低成本、高质量，并在规定期限内完成该工程项目，其关键在：抓好科学技术抓好项目管理，组织协调好各单位、各任务、各工序的完成。例3三军联合作战演习空军夺取制空权，对敌实施地面攻击，运送空降兵海军舰艇护卫，运送陆军、海军陆战队登陆夺取滩头阵地登陆完成后的巩固阵地与纵深发展电子对抗部队实施情报收集分析与电子对抗参与兵种：海军航空兵、海军陆战队、水面舰艇部队、空军歼击机、攻击机、轰炸机、电子对抗机各团、大队，坦克、炮兵、步兵、防化兵、通讯兵、侦察兵、导弹部队等。需迅速订好科学的作战演习计划，以便对作战演习过程演习过程进行有效的管理与控制。6网络计划作为一个管理者，常常面临着一些复杂、大型的工程项目，这些工程项目涉及到众多部门和单位的大量的独立的工作或活动，如何来编制计划、安排进度并进行有力的控制，这是管理的重要内容。统筹方法是解决这些问题的强有力的工具关键路线法（CPM，CriticalPathMethod），美国杜邦公司提出，用于协调公司不同部门计划评审法（PERT，ProgramEvaluationandReviewTechnique），美国海军武装部提出，用于导弹项目的管理和计划目前统称为PERT/CPM方法统筹方法可以应用在各种不同的项目计划上，特别适用于一些跨部门的工作计划，例如，新产品的研制开发，大型工程项目的建设，大型复杂设备的维修以及新系统的设计与安装等计划．网络计划技术（统筹法）的功能完成工程需做哪些工序，各工序需多长时间完成？总工期预计多长时间？完成工程的各工序采用什么样的逻辑顺序关系？关键工作是什么？如何加快工程的完成。环境发生变化时，该工程的风险分析。计划网络图（PERT图）计划网络图反映一个工程项目中各项作业（工序）的内在逻辑关系的一种有向图称为计划网络图，又称统筹图，工序流线图，PERT图等，以符号G表示。此中“内在逻辑关系”是指由于工程本身的工艺与组织性要求，而对各工序提出的在时间上和空间上所要求的先后处理关系。10PERT网络图PERT网络图的一些基本概念定义1（工序）指任何消耗时间或资源的行动、人、财、物、工时，用表示。紧前工序表示的是在另一项工序开始前，必须完成该工序紧后工序表示的是在一项工序结束后，立即开始的工序定义2（事项或事件）标志工序的开始或结束。不需消耗时间和资源。用表示。定义3（路线）指PERT网络图中，从最初事项到最终事项的由各项工序连贯组成的一条路。路线的时间是路线上各工序时间的总和。其中，各项工序累计时间最长的那条路线，决定完成网络图上所有工序需要的最短时间，称为关键路线。总的持续时间短于关键路线，却长于其他诸路线的路线称为次关键路线。其余路线称为非关键路线。123初步设计技术设计11确定型网络图例：建筑项目管理建筑工程项目的工序一览表工序工序说明紧前工序工序时间ABCDEFG挖掘－2打地基A4承重墙施工B10封顶C6安装外部管道C4安装内部管道D，E5外墙施工D7121，某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如下表所示，请画出其统筹方法的网络图．1314例2：我们把例1的进度表作一些扩充，如下表所示，请画出其统筹方法的网络图。6f??是否正确由于d是f的紧前工序，所以d的结束应该是f的开始，所以代表f的弧的起点应该是④，但是，b工序的结束也是④，所以b工序也成了f工序的紧前工序，这和题意不符合。15为此引入虚工序。虚工序是实际上并不存在而虚设的工序。仅用来表示相邻工序之间的衔接关系，虚工序不需要人力、物力等资源与时间，在图中用虚线表示。本例中虚工序所需时间为0。f6d38f10616在网络图上添上g，h工序就得网络图如图如下：上图中④、⑤两点间有2条弧。但是在计算机上，两点之间不管有多少弧，都认为是一条。因此再增加一个节点和引入虚工序。17PERT网络图的绘制绘制PERT网络图时，一般从左到右，从上到下。事项的编号，箭头处必须大于箭尾处。工序关系的表达方式：（a）工序a结束后才开始b和c（b)c在a和b结束后才开始（c）a和b均结束后才可以开始c和d（d）c在a结束后开始，d在a和b结束后才开始18网络时间和关键路线在绘制出网络图之后，我们可以用网络图求出：(1)完成此工程项目所需的最少时间．(2)每个工序的开始时间与结束时间．(3)关键路线及其相应的关键工序．(4)非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时间间可以推迟多久．19例：某公司装配一条新的生产线，其装配过程中的各个工序与其所需时间以及它们之间的相互衔接关系如下表所示，求：完成此工程所需最少时间，关键路线及相应关键工序，各工序的最早开始时间及结束时间和非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以推迟多久．20绘制网络图，如下：21首先从网络的始点开始，按顺序计算出每个工序的最早开始时间(ES)和最早结束时间(EF)。我们设一个工序所需时间为t，则对同一个工序来说，有EF＝ES十t．由于工序a最早开始时间ES＝0，所需时间t＝60，可知工序a的最早结束时间EF＝0+60=60。我们在网络的弧a的上面，字母a的右边标上这对数据下图。由于任一工序只有当其所有的紧前工序结束之后才能开始，所以任一工序的最早开始时间应该等于其所有紧前工序最早结束时间中的最后的时间。上述的等量关系我们称之为最早开始时间法则，运用这个法则以及EF＝ES＋t的关系，我们可以依次算出此网络图中的各弧的最早开始时间与最早完成时间。最早开始时间和最早结束时间的计算22[ES,EF]在上图中，例如工序h的最早开始时间应取工序d和e的最早结束时间中的最后时间，即在80与100中取最大者100．而其最早结束时间EF＝ES＋t＝100十15＝115．故在弧h上标以[100，115]．最早开始时间和最早结束时间的计算23其次，我们从网络图的终点开始计算出在不影响整个工程最早结束时间的情况下各个工序的最晚开始时间(缩写为LS)和最晚结束时间(缩写为LF)，显然对同一工序来说，有LS=LF-t。对工序j可知其LF=170，t=35，可计算出LS=170-35=135．我们把这两个数据标在网络图弧j的下面t右边的方括号内。由于任一工序必须在其所有的紧后工序开始之前结束，这样我们得到了最晚时间法则：在不影响整个工程最早结束时间的情况下，任一工序的最晚结束时间等于其所有紧后工序的最晚开始时间中的最早时间。运用这个法则和LS＝LF-t的关系式，我们可以从收点开始计算出每个工序的LF与LS如下图所示．最晚开始时间和最晚结束时间的计算24例如在图中，工序b的LF的值是从其紧后工序j的LS值得到，即工序b的LF＝135，而工序b的LS的值为LF-t=135-45＝90。故在弧b下面标以[90，135]。[LS,LF]最晚开始时间和最晚结束时间的计算25接着，我们可以计算出每一个工序的时差，我们把在不影响工程最早结束的条件下，工序最早开始(或结束)的时间可以推迟的时间，称为该工序的时差，对每一个工序来说其时差记为TS，有TS＝LS-ES＝LF-EF例如，对工序b来说，其时差TS＝LS－ES＝90－60＝30。这就是说工序b至多可以推迟30天开始，不至于影响整个工程的最早结束时间。我们称工序b是非关键工序。而对工序g来说，其时差TS＝LS－ES＝80－80＝0。这也就是说工序g的提前与推迟开始(或结束)都会使整个工程最早结束时间提前与推迟。我们称工序g是关键工序。由所有关键工序组成的线路称为关键线路（关键路径）。最后将各工序的时差，以及其他信息构成工序时间表，如下表所示。时差的计算2627关键路径28用WinQSB来求解关键路线采用PERT-CPM模块29网络图的优化1，时间－资源优化在编制网络图计划安排工程进度时，我们要合理地利用现有资源，并缩短工程周期．为了使工程进度与资源利用都得到比较合理安排，我们采取以下的做法：(1)优先安排关键工序所需要的资源。(2)利用非关键工序的时差，错开各工序的开始时间，拉平资源需要量的高峰。(3)要统筹兼顾工程进度的要求和现有资源的限制，往往要经过多次综合平衡，才能得到比较合理的计划方案。30下面列举一个拉平资源需要量高峰的实例．在前例中，若完成工序d，f，g，h，i的机械加工工人人数为65人，并假定这些工人可以完成这五个工序中的任一个工序，下面我们来寻求一个时间－资源优化方案．有关d，f，g，h，i工序所需的工人人数及上述工序开始时间，所需时间及时差如下表所示．31若上述各工序都按最早开始时间安排，那么从第60天至第135天的75天里，所需的机械加工工人的人数如下图所示．从图可见，在第70－80天和第100－110天这两段时间，需要工人数达到80与81人，远超过了现有工人人数。另一方面在第90－100天和第115－135天所需工人数仅有42人和26人，远远少于现有工人数这种安排的资源负荷是不均匀的，不妥当的。32我们应该优先安排关键工序所需的工人，再利用非关键工序的时差，错开各工序的开始时间，从而拉平工人需要量的高峰．经过调整，我们让非关键工序f从第80天开始，工序h从第110天开始．找到了时间-资源优化的方案.如下图所示，在不增加工人的情况下保证了工程按期完成．开始时间7080开始时间100100332，时间－费用优化问题在编制网络计划时，我们要考虑这样一些时间与费用的问题：在既定的时间前工程完工的前提下，使得所需要的费用最少，或者在不超过工程预算的条件下，使得工程最早完工．这些就是时间—费用优化要研究和解决的问题．加快工程进度的一个关键概念是应急处理。应急完成工序是指通过某些高费用的途径（如加班，雇佣临时工，使用特殊设备或材料等），把工序的完成时间减少到正常水平之下。应急正常34时间－费用的优化问题可以化为线性模型来求解规划问题：若考虑工程项目的成本，包括应急费用，那么问题是在项目工期小于或等于项目管理者期望水平的限制条件下，使得总成本最小化。决策：（1）每项工序的开始时间（2）进行应急处理后每项工序的工期减少量（3）项目的期望完成时间。35设xi为工序i的最早完成时间，yi为工序i的应急时间。假定工程开始时间为0，则对于工序1，有x1t1-y1，即x1+y1t1，其中t1为工序1的正常完成时间。对其他紧相邻工序i和j，有xj-xitj-yj，即xj+yj-xitj。其中tj为工序j的正常完成时间则线性规划模型为其中si为工序i的成本斜率，Ci为工序i说允许的最大应急时间，T为工程要求的完成时间。36举例：继续前面的例子，下表给出了在装配过程中各道工序所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需的直接费用和每缩短一天工期所需增加的直接费用。该工程要求在150天内完工，问每个工序应比正常完工时间提前多少天完成，才能使整个工程因缩短工期而增加的直接费用为最少。3738设此网络图上第i点发生的时间为xi，工序