运筹学第九章网络计划胡运权

1、运筹学运筹学2第九章第九章 网络计划网络计划 网络计划图网络计划图 时间参数的计算时间参数的计算 网络计划优化网络计划优化3 通过重组通过重组, ,打乱打乱, ,优化等手段改变原本的固有办事格式优化等手段改变原本的固有办事格式, ,优化办优化办事效率的一种办事方法。事效率的一种办事方法。 一种安排工作进程的数学方法。一种安排工作进程的数学方法。 它的实用范围极广泛，在企业管理和基本建设中，以及关系复它的实用范围极广泛，在企业管理和基本建设中，以及关系复杂的科研项目的组织与管理中，都可以应用。杂的科研项目的组织与管理中，都可以应用。 我国，是从我国，是从2020世纪世纪6060年代开始运用网络计

2、划的，著名数学家年代开始运用网络计划的，著名数学家华华罗庚罗庚教授结合我国实际，在吸收国外网络计划技术理论的基础教授结合我国实际，在吸收国外网络计划技术理论的基础上，将上，将cpmcpm、pertpert等方法统一定名为统筹法。等方法统一定名为统筹法。 统筹方法包括绘制计划网络图、进度安排、网络优化等环节。统筹方法包括绘制计划网络图、进度安排、网络优化等环节。统筹方法统筹方法4 统筹方法的统筹方法的第一步工作就是绘制计划网络图第一步工作就是绘制计划网络图，也就是将工序，也就是将工序（或称为活动）进度表转换为统筹方法的网络图。（或称为活动）进度表转换为统筹方法的网络图。例例9.1 9.1 某公司

3、研制新产品的部分工序与所需时间以及它们之间的某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如表所示，请画出其网络计划图。相互关系都显示在其工序进度表如表所示，请画出其网络计划图。工序代号工序代号工序内容工序内容所需时间所需时间（天（天)紧前工序紧前工序abcde产品设计与工艺设计产品设计与工艺设计外购配套零件外购配套零件外购生产原料外购生产原料自制主件自制主件主配可靠性试验主配可靠性试验601513388-aacb,d第一节第一节 网络图网络图2021-10-20运筹学-线性规划-线性规划5 解解: :用网络图表示上述的工序进度表用网络图表示上述的工序进度表点点

4、表示一个事件表示一个事件, ,是一个或若干个工序的开始或结束是一个或若干个工序的开始或结束, ,是相邻工是相邻工序在时间上的分界点序在时间上的分界点, ,点用圆圈表示点用圆圈表示, ,圆圈里的数字表示点的编号。圆圈里的数字表示点的编号。弧弧表示一个工序（或活动），弧的方向是从工序开始指向工序表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上是各工序的代号，下面标以完成此工序所需的时间的结束，弧上是各工序的代号，下面标以完成此工序所需的时间（或资源）等数据，即为对此弧所赋的权数（或资源）等数据，即为对此弧所赋的权数6abcde601383815图图17 例例9.29.2 把例把例1

5、 1的工序进度表做一些扩充，如表，请画出的工序进度表做一些扩充，如表，请画出其统筹方法的网络图。其统筹方法的网络图。工序代号工序代号 所需时间（天）所需时间（天） 紧前工序紧前工序工序代号工序代号所需时间所需时间（天）（天）紧前工序紧前工序abcd60151338aacefgh810165b，dde，8解：解：虚工序虚工序是实际上并不存在而虚设的工序，用来表示相邻工是实际上并不存在而虚设的工序，用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。序的衔接关系，不需要人力、物力等资源与时间。152643a60b158e1013dc38f图图29在网络图上添加、工序得网络图在网络图上添加、工

6、序得网络图3 3。 在统筹方法的网络图中在统筹方法的网络图中不允许两个点之间多于一条弧不允许两个点之间多于一条弧，因，因此增加了一个点和虚工序如图此增加了一个点和虚工序如图4 4。b1256734a6015ec13d388h510fg16图图310在绘制统筹方法的网络图时，要注意图中在绘制统筹方法的网络图时，要注意图中不能有缺口和回路不能有缺口和回路。161257834a6015bec13d388h510f6g图图4避免交叉避免交叉节点标号：节点标号：j iij11第二节第二节 时间参数的计算时间参数的计算 在绘制出网络图之后，我们可以由网络图求出：在绘制出网络图之后，我们可以由网络图求出：1

7、 1、完成此工程项目所需的最少时间。、完成此工程项目所需的最少时间。2 2、每个工序的开始时间与结束时间。、每个工序的开始时间与结束时间。3 3、关键路线及其应用的关键工序。、关键路线及其应用的关键工序。4 4、非关键工序在不影响工程的完成时间的前提下，其开始时、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时间可以推迟多久。间与结束时间可以推迟多久。2021-10-2012一、工作时间一、工作时间 t (i, j )u确定型确定型u概率型概率型缺乏统计来确定完成每个活动所需时间，但对所需时缺乏统计来确定完成每个活动所需时间，但对所需时间做了三种估计：间做了三种估计：1.1.乐观时

8、间。指所需最少时间，用乐观时间。指所需最少时间，用a a表示。表示。2.2.最可能时间。指正常时间，用最可能时间。指正常时间，用m m表示。表示。3.3.悲观时间。指不顺利情况下，最多时间，用悲观时间。指不顺利情况下，最多时间，用b b表示。表示。2021-10-2013活动活动 乐观时间乐观时间最可能时间最可能时间悲观时间悲观时间 abcdefghi1.52.01.01.50.51.03.03.01.52.02.52.02.01.02.03.54.02.02.56.03.02.51.53.07.05.02.5例例9.39.3 14 显然这三种完成活动所需时间都具有一定概率，由经验，我显然这三

9、种完成活动所需时间都具有一定概率，由经验，我们可以可以假定这些时间的概率分布近似服从们可以可以假定这些时间的概率分布近似服从 分布。我们可以分布。我们可以用如下公式计算出完成活动所需的：用如下公式计算出完成活动所需的：64bmat262)(ab460.75.340.364bmatg94方差方差平均时间平均时间例如：完成工作例如：完成工作g g所需平均时间：所需平均时间：同时求出方差为同时求出方差为15 同样可以求出每个活动的完成所需平均时间及方差同样可以求出每个活动的完成所需平均时间及方差活动活动 t（平均时间）（平均时间）方差方差活动活动t方差方差a 20.028f20.111b30.445

10、g40.445c20.111h40.111d20.028i20.028e10.02816 1 1、最早时间、最早时间 从网络的从网络的发点开始发点开始，按顺序计算出每个工序的，按顺序计算出每个工序的最早开始时间最早开始时间（es )es )和最早结束时间（和最早结束时间（ef)ef)工序工序a的最早的最早开始时间开始时间工序工序a的最早的最早完成时间完成时间ija0，6060二、时间二、时间参数参数),(),(),(),(max),(0), 1 (jitjitjitiktjitjtesefefkeses2021-10-20171236785a0,6060b60,10545e60.100c60,

11、70h100,115j135,17035i110.135g80,11030d60.80204025f70,881841015例例9.49.42021-10-20182 2、最晚时间、最晚时间从网络的从网络的收点开始收点开始计算，在不影响整个工程最早结束时间的情计算，在不影响整个工程最早结束时间的情况下，各个工序的况下，各个工序的最晚结束时间（最晚结束时间（lf)lf)和和最晚开始时间最晚开始时间(ls)(ls),(),(),(),(min),(),(),(jitjitjitkjtjitnitnitlflslsklfeflf工序工序a的最晚的最晚开始时间开始时间工序工序a的最晚的最晚完成时间完成

12、时间ij0，60a19 1236785a0,60600,60b60,1054590,135e60.100c60,70h100,115j135,17035135,170i110.135g80,1103080,110d60.802060,804080,12025110,135f70,8818117,135410107,11715120,1352021-10-2020 1 1、总时差、总时差 在不影响工程最早结束时间的条件下，工序最早开始（或结束）在不影响工程最早结束时间的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序的总时差的时间可以推迟的时间，成为该工序的总时差r r三、时差三、

13、时差),(),(),(),(),(jitjitjitjitjireslseflf2021-10-2021 2 2、单时差、单时差 在不影响紧后工序最早开始时间的条件下，工序最早开始（或在不影响紧后工序最早开始时间的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序的单时差结束）的时间可以推迟的时间，成为该工序的单时差r r),(),(),(jitkjtjirefes2021-10-20运筹学-线性规划-线性规划22四、关键工序，关键路线四、关键工序，关键路线网络中最长的路线就决定了完成整个工程所需的最少网络中最长的路线就决定了完成整个工程所需的最少时间，这条路线称为时间，这条路线称

14、为关键路线关键路线。总时差为总时差为0 0的工序为的工序为关键工序关键工序。2021-10-2023例例9-19-12021-10-20运筹学-线性规划-线性规划242021-10-20运筹学-线性规划-线性规划2526例例9.49.4 某公司装配一条新的生产线，具体过程如表某公司装配一条新的生产线，具体过程如表1,1,求：完成求：完成此工程的最少时间，关键路线及相应的关键工序，各工序的最此工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间和非关键工序在不影响工程完成时间的前提下，其早开始时间和非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以推迟多久？开始时间与结束

15、时间可以推迟多久？27工序代号工序代号工序内容工序内容所需时间（天）所需时间（天）紧前工序紧前工序abcdefghij生产线设计生产线设计外购零配件外购零配件下料、锻件下料、锻件工装制造工装制造1木模、铸件木模、铸件机械加工机械加工1工装制造工装制造2机械加工机械加工2机械加工机械加工3装配调试装配调试60451020401830152535/aaaacdd, egb, i, f, h2812346785a60b45echj35ig1030d204025f181529 1236785a0,6060b60,10545e60.100c60,70h100,115j135,17035i110.135g

16、80,11030d60.80204025f70,88184101530 1236785a0,60600,60b60,1054590,135e60.100c60,70h100,115j135,17035135,170i110.135g80,1103080,110d60.802060,804080,12025110,135f70,8818117,135410107,11715120,13531 最后将各工序的时差，以及其他信息构成工序时间表如表所示。最后将各工序的时差，以及其他信息构成工序时间表如表所示。这样就找到了一条由关键工序这样就找到了一条由关键工序a,d,g,ia,d,g,i和和j j依次

17、连接成的从发点到收依次连接成的从发点到收点的点的关键路线关键路线。2021-10-2032完成工序所需时间不确定完成工序所需时间不确定 例例9-29-22021-10-20332021-10-20运筹学-线性规划-线性规划342021-10-203576312)()()(ititittpess%98.53)099. 0() 10()25(787. 1833.2425dtntp?787. 1833. 05 . 15 . 02222关键线路关键线路2021-10-2036第三节第三节 网络计划优化网络计划优化 把串联工作改为平行工作或平行交叉工作把串联工作改为平行工作或平行交叉工作2021-10-

18、2037 利用时差利用时差 总时差不影响最短工期，但影响后续工序的自由时间。总时差不影响最短工期，但影响后续工序的自由时间。 单时差不影响后续工序。单时差不影响后续工序。2021-10-20383 3. .时间时间- -资源优化资源优化做法：做法： 1 1）优先安排关键工序所需的资源。）优先安排关键工序所需的资源。 2 2）利用非关键工序的时差，错开各工序的开始时间。）利用非关键工序的时差，错开各工序的开始时间。 3 3）适当延长时差大的工序时间，或切断非关键工序进程。）适当延长时差大的工序时间，或切断非关键工序进程。2021-10-20392021-10-20402021-10-204120

19、21-10-20运筹学-线性规划-线性规划424 4. .工期工期成本优化成本优化直接费用直接费用：为了加快工程进度，需要增加人力、设备和工作：为了加快工程进度，需要增加人力、设备和工作班次，这需要增加一笔费用，成为直接费用。班次，这需要增加一笔费用，成为直接费用。间接费用间接费用：由于工程早日完工，减少了管理人员的工资办公：由于工程早日完工，减少了管理人员的工资办公费等费用称为间接费用。一般说工序越短，直接费用越多，费等费用称为间接费用。一般说工序越短，直接费用越多，间接费用越少。间接费用越少。43 工序的工序的最快完成时间最快完成时间：指完成时间的最高限度。：指完成时间的最高限度。 我们设

20、完成工序我们设完成工序j的正常所需时间为的正常所需时间为tj;直接费用为直接费用为cj;完成工完成工序序j的最快完成时间为的最快完成时间为tj,直接费用为直接费用为cj。这样我们可以计算出。这样我们可以计算出缩短工序缩短工序j的一天工期所增加的直接费用，用的一天工期所增加的直接费用，用kj表示，称为表示，称为直接直接费用变动率（成本斜率）费用变动率（成本斜率）。有。有jjjjjttcck44模型一模型一，在既定的时间，在既定的时间t完工的前提下，问各工序的完成时间为完工的前提下，问各工序的完成时间为多少才使多少才使因缩短工期而增加的直接费用最少因缩短工期而增加的直接费用最少。 设工序设工序（i

21、 ,j)的提前完工时间为的提前完工时间为yij,我们用我们用tij,tij分别表示正分别表示正常完工时间与最快完工的时间，则有工序（常完工时间与最快完工的时间，则有工序（i ,j)的实际完工时的实际完工时间为：间为：tij- yij 。我们用。我们用cij,cij表示用正常完工时间和最快完成时表示用正常完工时间和最快完成时间完成工序所需要的费用，间完成工序所需要的费用，kij为工序为工序（i ,j)的直接费用变动率的直接费用变动率（成本斜率）。（成本斜率）。ijijijijijttcck45方法一：线性规划法方法一：线性规划法s.t. xj-xi tij-yij, 对一切弧（对一切弧（i, j

22、) yij tij-tij, 对一切弧（对一切弧（i, j) xn-x1 t, xi 0， yij 0。jiijijykf,min46例例9.5 9.5 例例4 4所提供的信息都作为本例的信息，另外还给出所提供的信息都作为本例的信息，另外还给出了在装配过程中各道工序所需正常完工时间与最快完工时了在装配过程中各道工序所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需的直接间，以及对应正常完工时间与最快完工时间的所需的直接费用和每缩短一天工期所需增加的直接费用，如表所示。费用和每缩短一天工期所需增加的直接费用，如表所示。2021-10-20运筹学-线性规划-线性规划47工序工

23、序tij正常完工正常完工cij直接费用直接费用tij最快完工最快完工cij直接费用直接费用直接费用变动直接费用变动率率a60100006010000-b454500306300120c10280054300300d2070001011000400e40100003512500500f183600105440230g3090002012500350h153750105750400i256250159150290j35120003512000-48 该工程要求在该工程要求在150150天内完工，问每个工序应比正常完工天内完工，问每个工序应比正常完工时间提前多少天完成，才能使整个工程因缩短工期而时间

24、提前多少天完成，才能使整个工程因缩短工期而增加的直接费用为最少。增加的直接费用为最少。 如果工期要求在如果工期要求在140140天完工呢？天完工呢？b12345678afechgijd49解：设此网络图上第解：设此网络图上第i点发生的时间为点发生的时间为xi，工序提前完工的时间为，工序提前完工的时间为yij。minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y67.s.t. x2-x1 60-y12, x7- x2 45-y27 x3-x2 10-y23 x4-x2 20-y24 x5-x2 40-y25 x7-x3 18-y37

25、 x6-x4 30-y46 x5-x4 0 x7-x5 15-y57 x7-x6 25-y67 x1 =0 x8 150 y12 0 y27 15 y23 5 y24 10 y25 5 y37 8 y46 10 y57 5 y78 0 xi 0，yij 0.（对一切可能的（对一切可能的ij)运算得到结果：运算得到结果：f=6400。50 方法二：统筹法方法二：统筹法 从关键工序中找成本斜率最小的工序，压缩工期；从关键工序中找成本斜率最小的工序，压缩工期； 重新计算关键路线和关键工序；重新计算关键路线和关键工序； 再重复循环再重复循环1 1和和2 2，直至达到压缩工期要求；，直至达到压缩工期要求

26、；1.1. 计算增加的总直接费用计算增加的总直接费用51模型二模型二，我们知道，我们知道直接费用直接费用是随着完成时间的缩短而增加，而是随着完成时间的缩短而增加，而间间接费用接费用却会随着完成时间的缩短而减少，设单位时间的间接费却会随着完成时间的缩短而减少，设单位时间的间接费用为用为d,计划期的间接费用与总工期成正比，即为计划期的间接费用与总工期成正比，即为d(xn-x1)。 那么那么求求使包括间接费用与直接费用在内的总费用最少的整个工使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间程最优完成时间t和各个工序最优完成时间的模型为：和各个工序最优完成时间的模型为： s. t. xj - xi tij - yij，对一切弧对一切弧（i ,j) yij tij