运筹学第九章-网络计划课件

1、运筹学赵明霞山西大学经济与管理学院运筹学赵明霞第九章 网络计划 网络计划图 时间参数的计算 网络计划优化2第九章 网络计划 网络计划图2通过重组,打乱,优化等手段改变原本的固有办事格式,优化办事效率的一种办事方法。 一种安排工作进程的数学方法。它的实用范围极广泛，在企业管理和基本建设中，以及关系复杂的科研项目的组织与管理中，都可以应用。我国，是从20世纪60年代开始运用网络计划的，著名数学家华罗庚教授结合我国实际，在吸收国外网络计划技术理论的基础上，将CPM、PERT等方法统一定名为统筹法。统筹方法包括绘制计划网络图、进度安排、网络优化等环节。统筹方法3通过重组,打乱,优化等手段改变原本的固有

2、办事格式,优化办事效 统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为活动）进度表转换为统筹方法的网络图。例9.1 某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如表所示，请画出其网络计划图。工序代号工序内容所需时间（天)紧前工序abcde产品设计与工艺设计外购配套零件外购生产原料自制主件主配可靠性试验601513388-aacb,d第一节 网络图4 统筹方法的第一步工作就是绘制计划网络图，也就是将工序解:用网络图表示上述的工序进度表点表示一个事件,是一个或若干个工序的开始或结束,是相邻工序在时间上的分界点,点用圆圈表示,圆圈里的数字表示点的编号。弧

3、表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上是各工序的代号，下面标以完成此工序所需的时间（或资源）等数据，即为对此弧所赋的权数2022/10/155-线性规划-线性规划解:用网络图表示上述的工序进度表2022/10/115-abcde601383815图16abcde601383815图16 例9.2 把例1的工序进度表做一些扩充，如表，请画出其统筹方法的网络图。工序代号所需时间（天）紧前工序工序代号所需时间（天）紧前工序abcd60151338aacefgh810165b，dde，7 例9.2 把例1的工序进度表做一些扩充，如表，请画出其统解：虚工序是实际上并不存在而虚设

4、的工序，用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。152643a60b158e1013dc38f图28解：虚工序是实际上并不存在而虚设的工序，用来表示相邻工序的衔在网络图上添加、工序得网络图3。 在统筹方法的网络图中不允许两个点之间多于一条弧，因此增加了一个点和虚工序如图4。b1256734a6015ec13d388h510fg16图39在网络图上添加、工序得网络图3。b1256734a601在绘制统筹方法的网络图时，要注意图中不能有缺口和回路。161257834a6015bec13d388h510f6g图4避免交叉节点标号：j iij10在绘制统筹方法的网络图时，要注意图中不

5、能有缺口和回路。161第二节 时间参数的计算 在绘制出网络图之后，我们可以由网络图求出：1、完成此工程项目所需的最少时间。2、每个工序的开始时间与结束时间。3、关键路线及其应用的关键工序。4、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时间可以推迟多久。11第二节 时间参数的计算11一、工作时间 t (i, j )确定型概率型缺乏统计来确定完成每个活动所需时间，但对所需时间做了三种估计：1.乐观时间。指所需最少时间，用a表示。2.最可能时间。指正常时间，用m表示。3.悲观时间。指不顺利情况下，最多时间，用b表示。2022/10/1512一、工作时间 t (i, j )确定型202

6、2/10/111活动 乐观时间最可能时间悲观时间 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.3 2022/10/1513活动 乐观时间最可能时间悲观时间 a1. 显然这三种完成活动所需时间都具有一定概率，由经验，我们可以可以假定这些时间的概率分布近似服从 分布。我们可以用如下公式计算出完成活动所需的：方差平均时间例如：完成工作g所需平均时间：同时求出方差为14 显然这三种完成活动所需时间都具有一定概率，由经验，我 同样可以求出每个活动的完成所需平均时间

7、及方差活动T（平均时间）方差活动T方差a 20.028f20.111b30.445g40.445c20.111h40.111d20.028i20.028e10.02815 同样可以求出每个活动的完成所需平均时间及方差活动T（平均时1、最早时间从网络的发点开始，按顺序计算出每个工序的最早开始时间（ES )和最早结束时间（EF)工序a的最早开始时间工序a的最早完成时间ija0，6060二、时间参数161、最早时间工序a的最早工序a的最早ija0，6060二1236785a0,6060b60,10545e60.100c60,70h100,115j135,17035i110.135g80,11030d

8、60.80204025f70,881841015例9.42022/100,6060b60,10545e62、最晚时间从网络的收点开始计算，在不影响整个工程最早结束时间的情况下，各个工序的最晚结束时间（LF)和最晚开始时间(LS)工序a的最晚开始时间工序a的最晚完成时间ij0，60a2022/10/15182、最晚时间从网络的收点开始计算，在不影响整个工程最早结束时 1236785a0,60600,60b60,1054590,135e60.100c60,70h100,115j135,17035135,170i110.135g80,1103080,110d60.80206

9、0,804080,12025110,135f70,8818117,135410107,11715120,13519 1236785a0,60600,60b60,101、总时差在不影响工程最早结束时间的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序的总时差R三、时差2022/10/15201、总时差三、时差2022/10/11202、单时差在不影响紧后工序最早开始时间的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序的单时差r2022/10/15212、单时差2022/10/1121四、关键工序，关键路线网络中最长的路线就决定了完成整个工程所需的最少时间，这条路线称

10、为关键路线。总时差为0的工序为关键工序。2022/10/1522-线性规划-线性规划四、关键工序，关键路线网络中最长的路线就决定了完成整个工程所例9-12022/10/1523例9-12022/10/11232022/10/1524-线性规划-线性规划2022/10/1124-线性规划-线性规划2022/10/1525-线性规划-线性规划2022/10/1125-线性规划-线性规划例9.4 某公司装配一条新的生产线，具体过程如表1,求：完成此工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间和非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以推迟多久？26例9.4 某

11、公司装配一条新的生产线，具体过程如表1,求：完工序代号工序内容所需时间（天）紧前工序abcdefghij生产线设计外购零配件下料、锻件工装制造1木模、铸件机械加工1工装制造2机械加工2机械加工3装配调试60451020401830152535/aaaacdd, egb, i, f, h27工序代号工序内容所需时间（天）紧前工序a生产线设计60/2712346785a60b45echj35ig1030d204025f18152812346785a60b45echj35ig1030d204 1236785a0,6060b60,10545e60.100c60,70h100,115j135,17035

12、i110.135g80,11030d60.80204025f70,88184101529 1236785a0,6060b60,10545e 1236785a0,60600,60b60,1054590,135e60.100c60,70h100,115j135,17035135,170i110.135g80,1103080,110d60.802060,804080,12025110,135f70,8818117,135410107,11715120,13530 1236785a0,60600,60b60,10 最后将各工序的时差，以及其他信息构成工序时间表如表所示。这样就找到了一条由关键工序a,d

13、,g,i和j依次连接成的从发点到收点的关键路线。31 最后将各工序的时差，以及其他信息构成工序时间表如表所示完成工序所需时间不确定例9-22022/10/1532完成工序所需时间不确定例9-22022/10/11322022/10/15332022/10/11332022/10/1534-线性规划-线性规划2022/10/1134-线性规划-线性规划关键线路2022/10/1535关键线路2022/10/1135第三节 网络计划优化把串联工作改为平行工作或平行交叉工作2022/10/1536第三节 网络计划优化把串联工作改为平行工作或平行交叉工作2利用时差 总时差不影响最短工期，但影响后续工序

14、的自由时间。 单时差不影响后续工序。2022/10/1537利用时差2022/10/11373.时间-资源优化做法： 1）优先安排关键工序所需的资源。 2）利用非关键工序的时差，错开各工序的开始时间。 3）适当延长时差大的工序时间，或切断非关键工序进程。2022/10/15383.时间-资源优化做法：2022/10/11382022/10/15392022/10/11392022/10/15402022/10/11402022/10/15412022/10/11414.工期成本优化直接费用：为了加快工程进度，需要增加人力、设备和工作班次，这需要增加一笔费用，成为直接费用。间接费用：由于工程早日

15、完工，减少了管理人员的工资办公费等费用称为间接费用。一般说工序越短，直接费用越多，间接费用越少。2022/10/1542-线性规划-线性规划4.工期成本优化直接费用：为了加快工程进度，需要增加人力、 工序的最快完成时间：指完成时间的最高限度。 我们设完成工序j的正常所需时间为Tj;直接费用为cj;完成工序j的最快完成时间为Tj,直接费用为cj。这样我们可以计算出缩短工序j的一天工期所增加的直接费用，用kj表示，称为直接费用变动率（成本斜率）。有43 工序的最快完成时间：指完成时间的最高限度。43模型一，在既定的时间T完工的前提下，问各工序的完成时间为多少才使因缩短工期而增加的直接费用最少。 设

16、工序（i ,j)的提前完工时间为yij,我们用Tij,Tij分别表示正常完工时间与最快完工的时间，则有工序（i ,j)的实际完工时间为：Tij- yij 。我们用Cij,Cij表示用正常完工时间和最快完成时间完成工序所需要的费用，kij为工序（i ,j)的直接费用变动率（成本斜率）。44模型一，在既定的时间T完工的前提下，问各工序的完成时间为多少方法一：线性规划法S.t. xj-xi Tij-yij, 对一切弧（i, j) yij Tij-Tij, 对一切弧（i, j) xn-x1 T, xi 0， yij 0。45方法一：线性规划法45例9.5 例4所提供的信息都作为本例的信息，另外还给出了

17、在装配过程中各道工序所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需的直接费用和每缩短一天工期所需增加的直接费用，如表所示。46例9.5 例4所提供的信息都作为本例的信息，另外还给出了在工序Tij正常完工Cij直接费用Tij最快完工Cij直接费用直接费用变动率a60100006010000-b454500306300120c10280054300300d2070001011000400e40100003512500500f183600105440230g3090002012500350h153750105750400i256250159150290j3512000351

18、2000-2022/10/1547-线性规划-线性规划工序Tij正常完工Cij直接费用Tij最快完工Cij直接该工程要求在150天内完工，问每个工序应比正常完工时间提前多少天完成，才能使整个工程因缩短工期而增加的直接费用为最少。如果工期要求在140天完工呢？b12345678afechgijd48该工程要求在150天内完工，问每个工序应比正常完工时间提前多解：设此网络图上第i点发生的时间为xi，工序提前完工的时间为yij。minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y67.s.t. x2-x1 60-y12, x7- x2

19、45-y27 x3-x210-y23 x4-x220-y24 x5-x240-y25 x7-x318-y37 x6-x430-y46 x5-x40 x7-x515-y57 x7-x625-y67 x1 =0 x8 150 y120 y2715 y23 5 y24 10 y25 5 y37 8 y46 10 y57 5 y78 0 xi 0，yij 0.（对一切可能的ij)运算得到结果：f=6400。49解：设此网络图上第i点发生的时间为xi，工序提前完工的时间为方法二：统筹法从关键工序中找成本斜率最小的工序，压缩工期；重新计算关键路线和关键工序；再重复循环1和2，直至达到压缩工期要求；计算增加

20、的总直接费用50方法二：统筹法50模型二，我们知道直接费用是随着完成时间的缩短而增加，而间接费用却会随着完成时间的缩短而减少，设单位时间的间接费用为d,计划期的间接费用与总工期成正比，即为d(xn-x1)。 那么求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间T和各个工序最优完成时间的模型为： s. t. xj - xi Tij - yij，对一切弧（i ,j) yij Tij - Tij ，对一切弧（i ,j) xi 0， yij 0。51模型二，我们知道直接费用是随着完成时间的缩短而增加，而间接费 例9.6 如果在例5中，每天的间接费用为330元，求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间T和各个工序