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

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