教学材料《运筹学》-第7章

7.1网络图的种类与绘制相邻工序的分界点称为结点或事件，一般用圆圈来表示，每个结点编上顺序号，如i,j,k,结点既不消耗人力、物力，也不占用时间。由工序、事件及时间参数所构成的有向图即为网络图。若箭线表示工序，结点为工序间相互关系的网络图，称箭线式网络，如图7-2所示。在后续内容中，均以确定型箭线式网络图为研究对象。若用结点表示工序、用箭线表示工序间相互关系的网络图，称结点式网络，如图7-3(a)所示，结点中的i,N,t分别表示工序的序号、名称和时间，由于工序序号和名称通常是一一对应的，因此也可省略工序名称，如图7-3(b)所示。对于图7-2，可以用结点式网络图表示，如图7-4所示。上一页下一页返回7.1网络图的种类与绘制7.1.2箭线式网络图的绘制规则箭线式网络图绘制的主要规则如下:(1)一条箭线和它的相关结点(事项)只能代表一道工序，不能代表多道工序，两个结点之间只能有一条箭线相连。图7-5所示的箭线表示方法是错误的。(2)不允许出现缺口与回路。网络图中只能有一个始点和一个终点，即不能出现缺口，从网络图的始结点经由任何路径都可以到达终结点。出现缺口的错误画法如图7-6所示，即工程的开始和结束均没有表达清楚。如图7-7所示，结点2,3和4构成闭合回路，即工序发生循环。上一页下一页返回7.1网络图的种类与绘制(3)在网络图中不允许出现没有箭尾结点和没有箭头结点的箭线，错例如图7-8所示。(4)在网络图中不允许出现带有双向箭头或无箭头的箭线，错例如图7-9所示。(5)画图时应尽量避免箭线交叉。当交叉不可避免时，可采用过桥法、断线法、指向法进行处理，如图7-10所示。(6)当网络图的始结点有多条外向箭线或终结点有多条内向箭线时，为使图形简洁，可用母线法绘制，如图7-11所示。(7)虚工序。虚工序是为了表达相邻工序之间的逻辑关系而虚设的工序。上一页下一页返回7.1网络图的种类与绘制由于虚工序不消耗时间、费用和资源，一般用虚箭线表示。要求c、工序必须在a工序和b工序完成后才能开始，若如图7-12(a)所示，则违反了规则(1)。这时可引入虚工序，正确表示a,b,c、三道工序之间的逻辑关系，如图7-12(b)所示。

(8)方向与编号的规定。网络图是有方向的，工序应按工艺流程顺序或工作逻辑关系从左向右排列。编号应从始结点开始，按照时序依次从小到大对结点编号，直到终结点，规定箭尾编号小于箭头编号。在实际应用中，为了便于调整工序(如增加工序)，编号往往不是连续的(如1，5，8，12)。上一页返回7.2关键路线法关键路线法(CriticalPathMethod,CPM)，是一种计划管理方法，即通过分析项目过程中各个活动序列进度安排的总时差来优化项目工期的网络分析方法，在一定工期、成本、资源条件下获得最佳的计划安排，以达到缩短工期、提高工效、降低成本的目的。关键路线法的步骤:(1)计算结点的时间参数;(2)计算工序的时间参数;(3)计算总时差和单时差;(4)确定关键路线;(5)网络计划优化。下一页返回7.2关键路线法7.2.1结点的时间参数m)最早时间。某一结点的最早时间tE(j)是以该结点开始的工序的最早开始时间。①计算步骤。tE(j)等于从起点开始到本结点的最长线路上各道工序时间之和。从始点开始，自左向右按箭线方向逐个计算，公式为②计算技巧。首先找出与该结点相关联的箭头，有m个箭头说明有m条线路，然后计算出工序时间最长的线路。上一页下一页返回7.2关键路线法(2)最迟时间。结点的最迟时间tL(j)是指以该结点结束的工序的最迟必须完工时间。①计算步骤。从终点开始，从右向左逆箭线方向逐个计算，公式为对于终结点来说，最迟时间和最早时间相等。②计算技巧。首先找出与该结点相关联的箭尾，有p个箭尾说明有p条线路，然后计算工序时间最短的线路。上一页下一页返回7.2关键路线法7.2.2工序的时间参数(1)最早可能开工时间。最早可能开工时间tES(j)是指该工序的所有紧前工序都结束的最早时间，即以某一结点为开始的工序的最早可能开工时间，是与该工序箭尾相连的结点的最早时间，计算公式为(2)最迟必须完工时间。上一页下一页返回7.2关键路线法最迟必须完工时间tLF(j)是指在不影响其紧后各个工序的按时开始或工程如期完工的前提下，该工序必须完工的时刻，即以某一结点为结束的工序的最迟必须完工时间，是与该工序箭头相连的结点的最迟时间，计算公式为(3)最早可能完工时间。最早可能完工时间tLS(j)是指该工序结束的最早时间，即最早可能开工时间加上本下序的作业时间，计算公式为上一页下一页返回7.2关键路线法(4)最早必须开工时间。最早必须开工时间tEF(i,j)是指在不影响其紧后工序按期开工或工程如期完工的前提下，该工序必须开工的最迟时刻，即最迟必须完工时间减去该工序的作业时间，计算公式为7.2.3总时差与单时差时差又称机动时间或宽裕时间，是指在不影响如期完成任务的条件下，各道工序可以机动使用的一段时间。关于总时差和单时差的示意图详见图7-19，其中工序(j,k)是工序(i,j)的紧后工序。上一页下一页返回7.2关键路线法总时差R(i,j)是指不影响其紧后工序最迟必须开工的前提下，本工序最早可能完工时间可以推迟的时间，计算公式为单时差二(i,j)又称自由时差，是指在不影响其紧后工序最早可能开工的前提下，本工序最早可能完工时间可以推迟的时间，计算公式为计算结点和工序的时间参数的目的是确定时差，而时差是进行网络计划优化的基础，因此必须熟练掌握。以下几点技巧可供学习时参考:计算结点时间参数时，最早时间(对应箭尾)应按从左至右的顺序计算;最迟时间(对应箭头)应按从右至左的顺序计算，应注意某一结点对应的箭尾或箭头的数量，而且终结点的最早时间等于最迟时间。上一页下一页返回7.2关键路线法计算工序时间参数时，应先计算最早可能开工时间(对应结点最早时间)和最迟必须完工时间(对应结点最迟时间)，然后使用工序作业时间计算最早可能完工时间和最迟必须开工时间。总时差的计算有两种方法:用最迟必须开工时间减去最早可能开工时间，或者用最迟必须完工时间减去最早可能完工时间。在计算某工序的单时差时，要考虑其紧后工序，用紧后工序的最早可能开工时间减去本工序的最早可能完工时间。注意:若某工序无紧后工序，则单时差为零;对于某一工序，总时差为零，单时差一定为零。根据结点时间参数或工序时间参数的计算结果确定关键线路。上一页返回7.3网络计划优化通过绘制网络图，计算网络时间参数，以及确定关键路线，得到的仅是一个初步计划方案。为了得到一个从各方面都较好的方案，往往要根据项目的要求综合考虑进度、资源利用和降低费用等目标，进行调整和改善，确定最优的方案。7.3.1工期优化工期优化是指在满足既定约束条件下，延长或缩短工期以达到要求工期的目标。计算工期TC≤计划工期TP≤要求工期TR，即计算工期TC≤要求工期TR。优化方法:压缩关键线路中关键工序的持续时间。下一页返回7.3网络计划优化优化步骤:①计算并找出初始网络计划的关键线路和关键工序;②求出应压缩的时间“TC—TP”；③确定各关键工序能压缩的时间;④选择关键工序，压缩其作业时间，并重新计算工期T′C;⑤当，重复以上步骤，直到T′C<TR;⑥当所有关键工作的持续时间都已达到能缩短的极限，工期仍不能满足要求时，应对网络计划的技术、组织方案进行调整或标工期重新进行审定。7.3.2工期—费用优化工期费用优化，即工期成本优化，是指寻求工程总成本最低时的工期或按要求工期寻求最低成本的计划安排。

(1)费用和工期的关系。工程总费用=直接费用+间接费用，如图7-27所示。上一页下一页返回7.3网络计划优化

(2)方法与步骤。①按工作正常持续时间画出网络计划，找出关键线路、工期、总费用;②计算各工作的直接费用率△Ci-j;③压缩工期;④计算压缩后的总费用为:一间接费用率△Ti-j;⑤重复③、④步，直到总费用最低。压缩工期时应注意:压缩关键工作的持续时间;不能把关键工序压缩成非关键工序;选择直接费用率或直接费用率组合(同时压缩几项关键工序时)最低的关键工序进行压缩，且其值应不超过间接费率。7.3.3工期一资源优化完成一项工作需要的资源基本不变，资源优化是通过改变工序的开始时间和完成时间使资源使用均衡。上一页下一页返回7.3网络计划优化资源优化包括两个方面:资源有限，工期最短;工期固定，资源均衡。这里只介绍第二个方面，优化的方法和步骤:①绘制早时标网络计划图，计算每个单位时间的资源需要量;②从计划开始之日起，逐个检查每个时间段的资源需要量是否超过资源限量;③分析超过资源限量的时段，以降低时段的资源需要量;④绘制调整后的网络计划，重新计算每个时间单位的资源需要量;⑤重复步骤②一④，直至满足要求为止。调整时应注意:不改变原网络计划中各工作之间的逻辑关系;不改变各工作的持续时间;除规定中断的工作之外，一般不允许中断工作;选择将哪一项工序安排在另一项工序之后开始，标准是使工期延长最短;调整的次序为:优先调整时间长、资源小的工序。上一页返回7.4非确定型统筹问题以上所考虑的工序时间是确定的，实际上很多工程并不是这样，解决非确定型统筹问题，需要把不确定的工序时间化为确定的工序时间，再编制工程进度计划和绘制统筹图，这就是计划评审技术(PERT)。对于非确定型问题的工序时间，一般采用“三时估计法”，而对于非确定型统筹问题而言，重要的是这种估计的可靠性如何。(1)三时估计法。在影响工序因素较多，工序持续时间难以准确估计时，可以采用三时估计法来确定作业时间。假设:u一最快可能完成的时间;m一最可能完成的时间;b一最慢可能完成的时间。在一般情况下，可按下列公式近似估算工序时间:下一页返回7.4非确定型统筹问题在工序时间确定后，其他时间参数的计算与确定型网络图基本相同。(2)估计的可靠性。在工序时间的不确定性条件下，如果已对各工序作了三时估计，得到工序估计值E[t(i,j)]，并根据公式算出方差。将估计值E[t(i,j)]当作实际工序时间看待，就可绘制出网络图，找出关键路线。工程的总工期，是由所有关键工序的工序时间之和求得的，但这里的工序时间都是随机变量，因此，总工期也是随机变量，也存在总工期的期望值E(Te)与方差D(Te)。