运筹学网络计划

第六章网络计划引例：沏茶1324烧水（10）备茶（3）沏茶（2）以网络图的形式制定计划，求得计划的最优方案。并据以组织和计划生产，达到预定目标的一种科学的管理方法。设：有一项工程，分为若干道工序；已知各工序间的先后关系，以及各工序所需时间t。问：（1）工程完工期T=？（2）工程的关键工序有哪些？1.问题的一般提法关键工序：主矛盾工序，不能延期完工路线：从始点到终点的一条路关键路线：由关键工序组成的路线，是所有路线中时间最长的路线。关键工序的延误将导致整个项目完成时间延误相关概念：1324烧水（10）备茶（3）沏茶（2）两种方法的原理基本一致，都是用网络表示工程项目，以确定关键路线；这两种方法的主要区别是：CPM方法对工程中各工序完工时间的估计是确定的，而PERT方法对时间估计是概率型的；PERT方法主要注重计划中的时间问题，CPM方法在把费用概念引人计划控制过程中，不仅注重时间问题，而且还考虑工程的费用和成本问题，考虑工程时间的均衡问题求解方法：关键路径法(CriticalPathMethd，简称CPM方法)计划评审技术(ProgramEvaluationandReviewTechnique，简称PERT法）2.解法——关键路径法（CPM）分为三步：􀂾绘制工程网络图􀂾标号法求工期T􀂾标号法求关键路线准备工作:将整个工程分解为若干工序确定各工序的前后顺序（紧前、紧后）确定工序完成时间三点估计法：最乐观时间a、最可能时间m、最悲观时间b一点估计法64bmatijp1352）图的结构（1）绘制工程网络图弧(箭线)：表示工序；为工序的起点、终点结点：表示相邻工序的时间分界点，称事项相邻弧：表示工序前后衔接关系，称紧前(后)工序；权：工序的完成时间1）顺序：按工序先后从左至右；1324烧水（10）备茶（3）沏茶（2）只有当事项的所有紧前工序完成后，事项的紧后工序才能开始。连接箭尾的结点称为该工序的紧前事项连接箭头的结点称为该工序的紧后事项。缺口：多个始点或多个终点的现象。（应当只有一个始点和终点）回路：方向一致的闭合链。3）绘图要求：图中不得有缺口、回路和多重边。多重边的处理：（1）绘制工程网络图（续）一项工作只能用唯一的实箭线和唯一的双号表示。处理方法：增加虚工序。12ab12a2bb'虚工序3）绘图要求：（1）绘制工程网络图（续）要尽量避免弧的交叉：12345678910111213141234567891011121314编号由左到右，不能重复(每条弧上起点的编号数小于终点的编号数)P135方法：箭杆删除法给起点一个编号数1，设想将该点为起点的弧都去掉，从而又有新的起点，依次给新的起点编号，反复这样做直到终点已经编号为止。例1：某工厂进行技术改造，需要拆掉旧厂房、建造新厂房和安排设备。这项改建工程可以分解为7道工序，其相关资料如下表：工序代号工序名称紧前工序工序时间（周）A拆迁/2B工程设计/3C土建工程设计B2.5D采购设备B6E厂房土建C、A20F设备安装D、E4G设备调试F2工序代号工序名称紧前工序工序时间（周）A拆迁/2B工程设计/3C土建工程设计B2.5D采购设备B6E厂房土建C、A20F设备安装D、E4G设备调试F2A（2）B(3)C(2.5)D(6)E(20)F(4)G(2)解：123456工序ABCDEFGHIJKLMN紧前工序____DEAFGBHBHIJGCIKL所需天数103127354436347CBAD2E3F4G5H6IJI’KLI’’MN17891011用箭秆删除法标号（保证箭尾号大于箭头号)例2：绘制工程网络图工序代号紧前工序工序时间（周）A/2B/3C/2DA3EA4工序代号紧前工序工序时间（周）FB7GB6HD、E4IB、C10JG、I3续左表解：1A(2)D(3)C(2)2E(4)3F(7)B'(0)G(6)46E'(0)5I(10)7J(3)H(4)8B(3)两种情况需要引入虚工序：①两个工序A、B有相同的始点和终点（两个或两个以上的工序有相同的紧前工序，又同时作为另外一工序的紧前工序）②四个工序A、B、X、Y有如下关系：A是X的紧前工序，A和B同时又是Y的紧前工序P134图6.2P134图6.1123456ABXYA'虚工序工序ABCDEFGH紧前工序------AA、BBD、ED、CG、F工序时间(天)24936242练习：123467895A(2)B(4)C(9)D(3)E(6)G(4)F(2)H(2)（2）用标号法求工期T1）标出各事项的最早开始时间，-给始点标；10jEjj-给任意点标,Ej=Max{以为箭头的各箭之“箭尾+箭长tij”}0263136162)终点的中的T即完工期。nT1A(2)D(3)C(2)2E(4)3F(7)B'(0)G(6)45E'(0)6I(10)7J(3)H(4)8B(3)30028336123313136121616（3）求关键路（用标号法）1）标出各事项的最晚开始时间，iLii-给任意点标,Li=Min{以为箭尾的各箭之“箭头-箭长tij”}nT-给终点标；1A(2)D(3)C(2)2E(4)3F(7)B'(0)G(6)45E'(0)6I(10)7J(3)H(4)8B(3)2）计算各工序的总时差R(i,j)=的-tij-的。ijji3）关键路径：由R(i,j)=0的关键工序组成的由至的路。n1（3）求关键路（用标号法）（不影响总工期条件下，任务可以延迟的最大幅度）00283361233131361216161A(2)D(3)C(2)2E(4)3F(7)B'(0)G(6)45E'(0)6I(10)7J(3)H(4)8B(3)一个工序的总时差为0意味着该工序在不影响工期前提下机动时间为0，及工序的最早开始时间也是最迟开始时间，其开始和结束时间没有一点机动的余地注：关键工序头尾皆有=（反之未必成立）工序ABCDEFGH紧前工序------AA、BBD、ED、CG、F工序时间(天)24936242练习：123467895A(2)B(4)C(9)D(3)E(6)G(4)F(2)H(2)0047224811111013711151517171计算最早开始时间(ES)与最早完工(EF)时间从网络起点开始,用下列公式计算最早开始时间(tES)和最早完工时间(tEF):最早开始时间=(紧前活动的)最早结束时间的最大值=开始结点的最早时间tES(i,j)=maxktEF(k,i)=ETi最早完工时间=最早开始时间+活动持续时间tEF(i,j)=tES(i,j)+t(i,j)工序时间参数的计算：2计算最晚开始时间与最晚结束时间从最后活动开始依次按下式计算每个活动最晚结束时间tLF和最晚开始时间tLS最晚结束时间=(紧后活动的)最晚开始时间的最小值=完成结点的最晚时间tLF(i,j)=minktLS(j,k)=LTj最晚开始时间=最晚结束时间–活动持续时间tLS(i,j)=tLF(i,j)-t(i,j)工序时间参数的计算(续):3总时差总时差:不影响总工期条件下，任务可以延迟的最大幅度，用R(i,j)表示:总时差=最晚开始时间–最早开始时间=最晚结束时间–最早结束时间R(i,j)=tLS(i,j)-tES(i,j)=tLF(i,j)-tEF(i,j)p144工序时间参数的计算(续):作业:工序代号工序紧前工序工序时间A系统提出和研究问题无4B研究选点问题A7C准备调研方案A10D收集资料工作安排B8E挑选、实地训练工作人员B、C12F准备收集资料用表格C7G实地调查D、E、F5H分析准备调查报告G4I任务结束H0工序代号工序紧前工序工序时间A系统提出和研究问题无4B研究选点问题A7C准备调研方案A10D收集资料工作安排B8E挑选、实地训练工作人员B、C12F准备收集资料用表格C7G实地调查D、E、F5H分析准备调查报告G4I任务结束H0关键路线逻辑关系图网络结构图A4(0,1)(4,1)(11,2)(14,2)(14,4)(26,5)(31,6)(35,7)B7C10E12D8F7G5H4124678530411261414313535312614141404[课堂练习]P150习题6.1160234756891011121314abcdefghijklmnopq142030211071225510601015257f'b'工序紧前工序工序时间工序紧前工序工序时间工序紧前工序工序时间a/60gb,c7mj,k5ba14he,f12ni,l15ca20if60on2da30jd,g10pm7ea21kh25qo,p5fa10lj,,k10绘制网络图，关键路线，工期，总时差160234756891011121314abcdefghijklmnopq142030211071225510601015257b'f'152[课堂练习]P150习题6.1练习为筹建某餐馆，需制定计划。将工程分为14道工序，各工序需时及先后关系如下表。试求该工程完工期T及关键路径。工序内容紧前工序所需天数A购买炉灶及材料——10B购买室内设备——3C招集工人——1D选择开业地点——2E申请许可得到执照D7F修理门窗、粉刷墙壁E3G砌炉灶、水池A、F5H接通上下水道G4I安装室内设备B、H4J做好室内装饰B、H3K购进米面及副食品I、J6L张贴开业广告G3M人员训练C、I4N开业前操作试验K、L7工序ABCDEFGHIJKLMN紧前工序____DEAFGBHBHIJGCIKL所需天数1031273544363471CBAD2E3F4G5H6IJ7I’8KL9I’’M10N11（2）求完工期（用标号法）1）标出各事项的最早开始时间，-给始点标；-给任意点标,Ej=Max{以为箭头的各箭之“箭尾+箭长tij”}10jEjj2)终点的中的T即完工期。nT1C(1)B(3)A(10)D(2)2E(7)3F(3)4G(5)5H(4)6I(4)J(3)7I’(0)8K(6)L(3)9I’’(0)M(4)10N(7)110291217212525312538（3）求关键路（用标号法）2）计算各工序的时差R(i,j)=的-tij-的。ijji1）标出各事项的最晚开始时间，-给终点标；-给任意点标,Li=Min{以为箭尾的各箭之“箭头-箭长tij”}niLiiT3）关键路径：由R(i,j)=0的关键工序组成的由至的路。n191C(1)B(3)A(10)D(2)2E(7)3F(3)4G(5)5H(4)6I(4)J(3)7I’(0)8K(6)L(3)I’’(0)M(4)10N(7)11029121721252531253838253425213117129201C(1)B(3)A(10)D(2)2E(7)3F(3)4G(5)5H(4)6I(4)J(3)7I’(0)8K(6)L(3)9I’’(0)M(4)10N(7)1102912172125253125383825342521311712920完工期T=38（天）；关键路：D-E-F-G-H-I-K-N。由本例可见：关键工序头尾皆有=，但反之未必。关键工序时间之和=工期T。二、工程完工期的概率分析（计划评审技术PERT）1、PERT与CPM的区别：工程工期的概率分析是是时间不确定情况下PERT的主要工作CPM工序时间是确定的,ijijijmba，最可能时间为，最悲观时间为设工序最乐观时间为2期望工期TE=关键工序的平均工序时间之和；工期方差=关键工序时间方差之和。由概率论的中心极限定理总工期),(~2ETNT64ijijijijbmat226ijijijab确定平均工序时间的三点估计法：)1,0(~NTTE标准化方法：首先计算1、给定时间T*，求工期T≤T*内完工的概率ETT***2d21*}{*}{2tePTTPt*)(Δ*：阴影面积*)()(1)()(然后查表求。例15、已知某工程网络图，以及各工序的时间参数。求工程在43