《运筹学第九章网络计划 胡运权.ppt》由会员分享，可在线阅读，更多相关《运筹学第九章网络计划 胡运权.ppt（58页珍藏版）》请在三一文库上搜索。
1、运筹学,2,第九章 网络计划,网络计划图 时间参数的计算 网络计划优化,3,通过重组,打乱,优化等手段改变原本的固有办事格式,优化办事效率的一种办事方法。 一种安排工作进程的数学方法。 它的实用范围极广泛，在企业管理和基本建设中，以及关系复杂的科研项目的组织与管理中，都可以应用。 我国，是从20世纪60年代开始运用网络计划的，著名数学家华罗庚教授结合我国实际，在吸收国外网络计划技术理论的基础上，将CPM、PERT等方法统一定名为统筹法。 统筹方法包括绘制计划网络图、进度安排、网络优化等环节。,统筹方法,4,统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为活动）进度表转换为统筹方法的
2、网络图。 例9.1 某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如表所示，请画出其网络计划图。,第一节 网络图,2020/7/25,运筹学-线性规划-线性规划,5,解:用网络图表示上述的工序进度表 点表示一个事件,是一个或若干个工序的开始或结束,是相邻工序在时间上的分界点,点用圆圈表示,圆圈里的数字表示点的编号。 弧表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上是各工序的代号，下面标以完成此工序所需的时间（或资源）等数据，即为对此弧所赋的权数,6,图1,7,例9.2 把例1的工序进度表做一些扩充，如表，请画出其统筹方法的网络图。,8,解：虚工
3、序是实际上并不存在而虚设的工序，用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。,9,在网络图上添加、工序得网络图3。 在统筹方法的网络图中不允许两个点之间多于一条弧，因此增加了一个点和虚工序如图4。,b,10,在绘制统筹方法的网络图时，要注意图中不能有缺口和回路。,16,图4,避免交叉 节点标号：j i,11,第二节 时间参数的计算 在绘制出网络图之后，我们可以由网络图求出： 1、完成此工程项目所需的最少时间。 2、每个工序的开始时间与结束时间。 3、关键路线及其应用的关键工序。 4、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时间可以推迟多久。,2020/7/25,
4、12,一、工作时间 t (i, j ),确定型 概率型 缺乏统计来确定完成每个活动所需时间，但对所需时间做了三种估计： 1.乐观时间。指所需最少时间，用a表示。 2.最可能时间。指正常时间，用m表示。 3.悲观时间。指不顺利情况下，最多时间，用b表示。,2020/7/25,13,例9.3,14,显然这三种完成活动所需时间都具有一定概率，由经验，我们可以可以假定这些时间的概率分布近似服从 分布。我们可以用如下公式计算出完成活动所需的：,方差,平均时间,例如：完成工作g所需平均时间：,同时求出方差为,15,同样可以求出每个活动的完成所需平均时间及方差,16,1、最早时间 从网络的发点开始，按顺序计
5、算出每个工序的最早开始时间 （ES )和最早结束时间（EF),二、时间参数,2020/7/25,17,例9.4,2020/7/25,18,2、最晚时间,从网络的收点开始计算，在不影响整个工程最早结束时间的情 况下，各个工序的最晚结束时间（LF)和最晚开始时间(LS),19,2020/7/25,20,1、总时差 在不影响工程最早结束时间的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序的总时差R,三、时差,2020/7/25,21,2、单时差 在不影响紧后工序最早开始时间的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序的单时差r,2020/7/25,运筹学-线性规划
6、-线性规划,22,四、关键工序，关键路线,网络中最长的路线就决定了完成整个工程所需的最少时间，这条路线称为关键路线。 总时差为0的工序为关键工序。,2020/7/25,23,例9-1,2020/7/25,运筹学-线性规划-线性规划,24,2020/7/25,运筹学-线性规划-线性规划,25,26,例9.4 某公司装配一条新的生产线，具体过程如表1,求：完成此工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间和非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以推迟多久？,27,28,29,30,31,最后将各工序的时差，以及其他信息构成工序时间表如表所示。 这样就找到了
7、一条由关键工序a,d,g,i和j依次连接成的从发点到收点的关键路线。,2020/7/25,32,完成工序所需时间不确定,例9-2,2020/7/25,33,2020/7/25,运筹学-线性规划-线性规划,34,2020/7/25,35,关键线路,2020/7/25,36,第三节 网络计划优化,把串联工作改为平行工作或平行交叉工作,2020/7/25,37,利用时差 总时差不影响最短工期，但影响后续工序的自由时间。 单时差不影响后续工序。,2020/7/25,38,3.时间-资源优化,做法： 1）优先安排关键工序所需的资源。 2）利用非关键工序的时差，错开各工序的开始时间。 3）适当延长时差大的
8、工序时间，或切断非关键工序进程。,2020/7/25,39,2020/7/25,40,2020/7/25,41,2020/7/25,运筹学-线性规划-线性规划,42,4.工期成本优化,直接费用：为了加快工程进度，需要增加人力、设备和工作班次，这需要增加一笔费用，成为直接费用。 间接费用：由于工程早日完工，减少了管理人员的工资办公费等费用称为间接费用。一般说工序越短，直接费用越多，间接费用越少。,43,工序的最快完成时间：指完成时间的最高限度。 我们设完成工序j的正常所需时间为Tj;直接费用为cj;完成工序j的最快完成时间为Tj,直接费用为cj。这样我们可以计算出缩短工序j的一天工期所增加的直接
9、费用，用kj表示，称为直接费用变动率（成本斜率）。有,44,模型一，在既定的时间T完工的前提下，问各工序的完成时间为多少才使因缩短工期而增加的直接费用最少。 设工序（i ,j)的提前完工时间为yij,我们用Tij,Tij分别表示正常完工时间与最快完工的时间，则有工序（i ,j)的实际完工时间为：Tij- yij 。我们用Cij,Cij表示用正常完工时间和最快完成时间完成工序所需要的费用，kij为工序（i ,j)的直接费用变动率（成本斜率）。,45,方法一：线性规划法 S.t. xj-xi Tij-yij, 对一切弧（i, j) yij Tij-Tij, 对一切弧（i, j) xn-x1 T,
10、xi 0， yij 0。,46,例9.5 例4所提供的信息都作为本例的信息，另外还给出了在装配过程中各道工序所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需的直接费用和每缩短一天工期所需增加的直接费用，如表所示。,2020/7/25,运筹学-线性规划-线性规划,47,48,该工程要求在150天内完工，问每个工序应比正常完工时间提前多少天完成，才能使整个工程因缩短工期而增加的直接费用为最少。 如果工期要求在140天完工呢？,b,49,解：设此网络图上第i点发生的时间为xi，工序提前完工的时间为yij。 minf=120y27+300y23+400y24+500y25+23
11、0y37+350y46+400y57+290y67. s.t. x2-x1 60-y12, x7- x2 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。,50,方法二：统筹法 从关键工序中找成本斜率最小的工序，压缩工期； 重新计算关键路线和关
12、键工序； 再重复循环1和2，直至达到压缩工期要求； 计算增加的总直接费用,51,模型二，我们知道直接费用是随着完成时间的缩短而增加，而间接费用却会随着完成时间的缩短而减少，设单位时间的间接费用为d,计划期的间接费用与总工期成正比，即为d(xn-x1)。 那么求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间T和各个工序最优完成时间的模型为： s. t. xj - xi Tij - yij，对一切弧（i ,j) yij Tij - Tij ，对一切弧（i ,j) xi 0， yij 0。,52,例9.6 如果在例5中，每天的间接费用为330元，求使包括间接费用与直接费用在内的总费用
13、最少的整个工程最优完成时间T和各个工序最优完成时间。 解： min f=330(x8-x1) +120y27+300 y23 +400y24+500y25+230y37+350y46+290y67,s.t. x2-x1 60-y12, x7- x2 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,y120 y2715 y23 5 y24 10 y25 5 y37 8 y46 10 y57 5 y78 0 xi 0，yij 0.（对一切可
14、能的ij),53,f=55700. x1=0, y12=0, y67 =10, x2=60, y27 =0, y78=0. x3 =125, y23 =0, x4 =107, y24 =0, x5 =110, y25 =0, x6 =110, y37 =0, x7 =125, y46 =0, x8 =160, y57 =0, 也就是说整个工程工期为160天时总费用最少为124600元，各个工序开始时间如解所示，工序 i 要提前10天完工，其余的工序按正常时间完工。,54,例9-3,55,2020/7/25,56,2020/7/25,运筹学-线性规划-线性规划,57,58,习 题,9.4（1） 9.5 9.7 9.8,