运筹学 第七章 网络计划技术

运筹学方法与模型（II）主讲人：丁小兵[e-mail]•考勤1.每节课抽点名（提问的形式）2.上课内容为考试内容（上课内容的子集）3.考试形式：平时占30%，期末占70%，不排除太差的会挂科(几乎每年都有)。4.考题形式：选择题、填空、名词解释、计算题、简答题本学期主要内容第七章：网络计划技术*第八章：动态规划*第九章：排队论*第十章：存储论第十一章：博弈论*第十二章：决策分析•第七章网络计划技术建造一座汽车库及引道的工程项目，从施工开始到全部结束需要多少时间？1.把整个工程分解成若干个环节——工序；2.估算出每个环节所需要的时间——工时；3.确定各个环节之间的相互联系，先做什么，后做什么，哪些可以同时施工——紧前、紧后、平行关系；4.汇总上述各点予以具体分析，计算，得总工期。将工序及所需要时间、各工序之间的关系整理成表——工序清单。这是应用网络技术的第一步。引例代号工序名称工时（天）紧前工序a清理现场8——b备料10——c车库地面施工6a,bd预制墙及房顶的桁架16be车库混凝土地面保养24cf立墙架4d,eg立房顶桁架4fh装窗及边墙10fi装门4fj装天花板12gk油漆16h,i,jl引道混凝土施工8cm引道混凝土保养24ln清理现场，交工验收4k,m网络计划图示例adcbeflgijkmnh101044424824166832141612654798101112第七章网络计划技术1、网络图：网络图是由结点、弧、权所构成的有向图，即有向赋权图。2、关键路线：完成各个工序需要时间最长的路线7.1基本概念3、绘制网络图应遵循的原则•（1）方向、时序与结点编号网络图是有向图，按照流程的顺序，规定工序从左至右排列，网络图中的各个结点都有个时间。一般按各个结点的时间顺序编号。•（2）紧前工序与紧后工序如果只有在a工序结束后，b工序才能开始，则a工序是b工序是紧前工序，a工序是b工序的紧后工序。•（3）虚工序为了用来表达相邻工序之间的衔接关系，实际上并不存在的工序。不消耗人力，物力等资源和时间。（……）•（4）相邻两个结点只能出现一条弧（无平行边）•（5）不能有缺口和回路4、主要网络计划技术概念•工程计划的网络图•网络图的时间参数•网络图的分析工序与事项网络图事项的参数工序的参数关键工序与关键路线网络分析1.工序工程的组成部分称为工序。工时完成工序所需要的持续时间。双代号法（箭杆式）：清理现场8（天）a8（天）或（i,j）tijiji＜j工序需要人力、物力投入，经过一定时间才能完成。实工序：需要时间的工序。可能不需要人力、物力。7.2网络计划虚工序：工时为0的工序。⑴不需要人力、物力，不存在。⑵表明工序间的逻辑关系。2.事项工序都有两个事项----开工事项、完工事项。（i,j）tijij工序（i,j）的开工事项工序（i,j）的完工事项任一工序有且仅有两个事项；直接连结两个事项的箭杆只能有一根。jbai×aiji’b虚工序7.2网络计划7.2网络计划（2）工序a有紧后工序c与d，工序d有紧前工序b与a。abdc（3）工序a有紧后工序b与c，工序d有紧前工序b与c。adcb（4）工序a有紧后工序b与d，工序c有紧后工序d与e。adcbe7.2网络计划3.工序间的基本逻辑关系对工序（i,j）：紧前工序、紧后工序、平行工序。ij平行紧前紧后4.举例（1）工序c，d，e是平行工序，它们的紧前工序都是a与b。abedc7.2网络计划利用公式期望时间=64bma5.工时确定单一时间确定法：以前多次执行过的、有可靠的生产定额值的，可以一个确定的时间作为它的工时。三种时间确定法：初次执行，无资料可循。a=最乐观时间、b=最保守时间、m=最可能时间估计7.2网络计划7.2网络计划对承担的工程经过工序分解、工时确定，根据生产工艺、生产组织的制约确定出各工序间的逻辑关系后，可以用一张网络图把上述各点统一反映出来，借以形象地表达工程计划方案的编制。绘制网络图：前进法、后退法、任意法。草图→逐步调整（尽量消除箭杆的交叉）（正确运用虚工序）→排列整齐、完整准确反映工程计划编制的网络图。注意：1.总开工、总完工事项都是唯一的；2.编号：总开工事项1，各事项编号不重复，任一工序完工事项编号大于开工事项编号，总完工事项为n.7.3网络图的时间参数1事项的参数1)事项的最早（可能）开始时刻——E事项i的最早（可能）开始时刻：在此之前，事项i不可能开始。从顶点1到顶点K的最长路径长度总开工事项，最早可能开始时刻=0，即E1=0。EiL计算：从总开工事项起。从左至右地对其余事项予以计算。adcb810745432122181580事项时间最早开始时间Te(j)：通常按箭头事项计算事项最早时间，它等于从始点事项起到本事项最长路线的时间长度：Te(1)=0Te(j)=max{Te(i)+T(i,j)},(j=1,2……,n)(若有2条或2条以上路径)式中，Te(j)和Te(i)分别为箭头和箭尾事项的最早时间。•最迟时间Tl(i)：即为箭头事项各工序的最迟必须结束时间，或箭尾事项各工序的最迟必须开始时间，即：•Tl(n)=Te(n)•Tl(i)=min{Tl(j)-T(i,j)},(i=n-1,n-2……,2,1)•式中，n为终点事项，Tl(i)和Tl(j)分别为箭头和箭尾事项的最迟时间。2)最迟（必须）结束时刻——L事项j的最迟（必须）结束时刻：在此之后，事项j不结束，就会造成工程拖期。总完工事项，最迟（必须）结束时刻Ln=En=总工期EiL7.3网络图的时间参数7.3网络图的时间参数adcb8107454321计算各事项的最迟开始时间重要结论和概念最早开始时间=最晚开始时间的事项为项目的关键事项关键工序：总时差为0的工序。关键路线：由关键工序组成的从总开工总完工事项的一条路线。非关键工序：总时差大于0的工序。1.关键工序与关键线路例题1工作ABCDEF紧前工作---A、BBC、D、E工作ABCDEF紧前工作-AAAB、C、DD例题2例题3工序紧前工序工序时间工序紧前工序时间A-3GC2BA4HF,G5CA7MH2DB,C3EA5FD,E5已知下列资料：要求：（1）绘制网络图（2）各事项的最早开始时间与最迟结束时间（3）确定关键路径例题4如下图所示网络图，求出各结点的最早与最晚开始时间，关键路径等参数。代号工序名称工时（天）紧前工序a清理现场8——b备料10——c车库地面施工6a,bd预制墙及房顶的桁架16be车库混凝土地面保养24cf立墙架4d,eg立房顶桁架4fh装窗及边墙10fi装门4fj装天花板12gk油漆16h,i,jl引道混凝土施工8cm引道混凝土保养24ln清理现场，交工验收4k,m请画出前表网络图：adcbeflgijkmnh1010444248241668321416126547981011127.2网络计划注意紧前工序、紧后工序和虚工序的位置顺序例题4Te(1)=0Te(2)=8Te(3)=4Te(4)=8Te(5)=11Te(6)=12Te(7)=15Tl(7)=15Tl(6)=12Tl(5)=12Tl(4)=8Tl(3)=5Tl(2)=8Tl(1)=07.4网络图优化分析1.网络图优化的原则1)向非关键工序要资源；2)向关键工序要时间。总工期-成本优化问题•（1）直接成本：如人工、原材料、燃料和机械设备租用等直接与工序工作有关的费用，直接成本要分摊到每道工序上。•（2）间接成本：如管理人员工资、行政办公费、采购费、劳保福利等，间接成本不分摊到每道工序上而作为整个工程的成本。显然，整个TE短，间接成本就低。（1）直接成本：如人工、原材料、燃料和机械设备租用等直接与工序工作有关的费用，直接成本要分摊到每道工序上。（2）间接成本：如管理人员工资、行政办公费、采购费、劳保福利等，间接成本不分摊到每道工序上而作为整个工程的成本。显然，整个工程时间最短，间接成本就低。(3)赶工成本增加了人力物力等资源以后,使工期得以缩短而需要的费用2.直接成本、间接成本、赶工成本3、基本概念:•正常时间\赶工时间\正常成本\赶工成本\赶工成本斜率•赶工成本斜率：•工序（I,j）缩短一个单位时间所增加的直接成本称为该工序赶工成本斜率，记为：cijbijgijgijbijijwwcccC:表示成本W：工作时间5、优化分类：•一、缩短工程进度优化•二、时间成本优化•三、资源优化例5-1•例题5-1某工程的有关资料如下表所示，每天可以安排只有10人，要求工程在15天里完成，应如何安排工程进度可以在现有人力资源下按期完成任务？工作名称紧前工作工作时间（天）每天需要的人数（人）A-44B-54C-83DB54EADC97FC13解题方法：•1、绘制网络图看关键路线时间，人力资源是否满足要求？•2、画出每天对人员的需要量的直方图•3、计划调整二、时间成本优化•工程总费用=直接费用+间接费用+赶工费用•例5-5某工程由4项工作组成，其资料如表5-9,该工程的间接成本为每天4500元，试求最低成本日工作名称紧前工作工作时间（天）工作费用（千元）成本斜率正常时间赶工时间正常费用赶工费用A-3110184BA7315191CA4212204DC528142•解：画出网络图，标上时间参数•工程直接费用=45000元•总费用=45000+4500*12+0=99000•求关键线路：•另外，一条线路了1-2-4为时间富裕线，有2天机动时间。•改进方案1：缩短关键工作时间，从成本斜率最低的关键工作着手分析关键工作ACD，工作D的赶工成本斜率最低，所以对D赶工，但是赶工多少？对D赶工2天后，出现两条关键路线1-2-3-4，1-2-4，工期为10天，总费用为：45000+4500×10+2000×2=94000改进方案2：进一步缩短工期？要缩短工期就需要考虑两条路线工程可选择的赶工方案赶工方式成本斜率（元/天）1、A赶工1天2、B、C赶工1天3、B、D赶工1天•由上表可以知道，方案3的赶工费用最低，所以选择B，D各赶工1天，这样工期变为9天。•总费用=45000+4500×9+2000×3+1000×1•=92500•改进方案三•继续赶工，对A或者B,C赶工，但是发现B,C赶工费用为5000，大于工程每天的间接费，赶工已经不合算，所以对A赶工2天：•总费用：45000+4500×7+2000×3+1000×1+4000×2=91500•答：该工程总工期为7天，总费用为91500课后作业1.计算各结点的最早与最迟时间，各工序的最早开工、完工时间。2.计算各结点的最早与最迟时间，各工序的最早开工、完工时间。所有工序路线：1-2-7-10-11=181-2-5-6-7-10-11=191-2-5-6-9-10-11=161-2-4-5-6-7-10-11=181-2-4-5-6-9-10-11=161-2-4-8-9-10-11=171-3-4-5-6-7-10-11=20（关键路线）1-3-4-5-6-9-10-11=171-3-4-8-9-10-11=191-3-4-8-11=19习题工序abcdefg紧前工序--a，ba，bbcd，e时间4234312（1）绘制网络图（2）计算各结点的最早和最晚开始时间（3）求关键路线肯定型网络：采用单一时间估计法估计各道工序作业时间的PERT网络为肯定型网络。非肯定型网络：工序时间是随机变量的PERT网络称为非肯定的PERT网络。u=64bma采用三种时间估计法来估算非肯定型网络个工序的工序时间，即对每道工序估计有3种时间：a=最乐观时间、b=最保守时间、m=最可能时间假设工序时间这个随机变量服从取值范围从a到b的B分布，随机变量的期望值u和方差a2分别为：a2=26ab7.5肯定型与非肯定型网络