《[高等教育]运筹学 第七章 网络计划技术》由会员分享，可在线阅读，更多相关《[高等教育]运筹学 第七章 网络计划技术（49页珍藏版）》请在金锄头文库上搜索。
1、运筹学方法与模型（II）,主讲人：丁小兵 13816953018 ,考勤 1.每节课抽点名（提问的形式） 2.上课内容为考试内容（上课内容的子集） 3.考试形式：平时占30%，期末占70%，不排除太差的会挂科(几乎每年都有)。 4.考题形式：选择题、填空、名词解释、计算题、简答题,本学期主要内容,第七章：网络计划技术* 第八章：动态规划* 第九章：排队论* 第十章：存储论 第十一章：博弈论* 第十二章：决策分析,第七章 网络计划技术,建造一座汽车库及引道的工程项目，从施工开始到全部结束需要多少时间？,把整个工程分解成若干个环节工序； 估算出每个环节所需要的时间工时； 确定各个环节之间的相互联系
2、，先做什么，后做什么，哪些可以同时施工紧前、紧后、平行关系； 汇总上述各点予以具体分析，计算，得总工期。,将工序及所需要时间、各工序之间的关系整理成表工序清单。,这是应用网络技术的第一步。,引例,网络计划图示例,第七章 网络计划技术,1、网络图：,网络图是由结点、弧、权所构成的有向图，即有向赋权图。,2、关键路线： 完成各个工序需要时间最长的路线,7.1基本概念,3、绘制网络图应遵循的原则,（1）方向、时序与结点编号 网络图是有向图，按照流程的顺序，规定工序从左至右排列，网络图中的各个结点都有个时间。一般按各个结点的时间顺序编号。 （2）紧前工序与紧后工序 如果只有在a工序结束后，b工序才能开
3、始，则a工序是b工序是紧前工序，a工序是b工序的紧后工序。 （3）虚工序 为了用来表达相邻工序之间的衔接关系，实际上并不存在的工序。不消耗人力，物力等资源和时间。（） （4）相邻两个结点只能出现一条弧（无平行边） （5）不能有缺口和回路,4、主要网络计划技术概念,工程计划的网络图 网络图的时间参数 网络图的分析,工序 工程的组成部分称为工序。 工时 完成工序所需要的持续时间。,双代号法（箭杆式）：,或,i j,工序需要人力、物力投入，经过一定时间才能完成。 实工序：需要时间的工序。,可能不需要人力、物力。,7.2 网络计划,虚工序：工时为0 的工序。,不需要人力、物力，不存在。,表明工序间的逻
4、辑关系。,2. 事项 工序都有两个事项-开工事项、完工事项。,工序（i , j）的开工事项,工序（i , j）的完工事项,任一工序有且仅有两个事项；直接连结两个事项的箭杆只能有一根。,虚工序,7.2 网络计划,7.2 网络计划,（2）工序a有紧后工序c与d，工序d有紧前工序b与a。,（3）工序a有紧后工序b与c，工序d有紧前工序b与c。,（4）工序a有紧后工序b与d，工序c有紧后工序d与e。,7.2 网络计划,工序间的基本逻辑关系 对工序（i, j）：紧前工序、紧后工序、平行工序。,4 . 举例,7.2 网络计划,利用公式,期望时间=,5. 工时确定,单一时间确定法：以前多次执行过的、有可靠的
5、生产定额值的，可以一个确定的时间作为它的工时。,三种时间确定法：初次执行，无资料可循。,a=最乐观时间、b=最保守时间、m=最可能时间,估计,7.2 网络计划,7.2 网络计划,对承担的工程经过工序分解、工时确定，根据生产工艺、生产组织的制约确定出各工序间的逻辑关系后，可以用一张网络图把上述各点统一反映出来，借以形象地表达工程计划方案的编制。,绘制网络图：前进法、后退法、任意法。,草图,逐步调整,（尽量消除箭杆的交叉）,（正确运用虚工序）,排列整齐、完整准确反映工程计划编制的网络图。,注意：1. 总开工、总完工事项都是唯一的； 2. 编号：总开工事项1，各事项编号不重复，任一工序完工事项编号大
6、于开工事项编号，总完工事项为n.,7.3 网络图的时间参数,1 事项的参数,1) 事项的最早（可能）开始时刻E,事项 i 的最早（可能）开始时刻：在此之前，事项i 不可能开始。从顶点1到顶点K的最长路径长度,总开工事项，最早可能开始时刻=0，即E1=0。,计算：从总开工事项起。从左至右地对其余事项予以计算。,22,18,15,8,0,事项时间,最早开始时间Te(j)：通常按箭头事项计算事项最早时间，它等于从始点事项起到本事项最长路线的时间长度： Te(1)=0 Te(j)=max Te(i)+T(i,j),(j=1,2,n) (若有2条或2条以上路径) 式中，Te(j)和Te(i)分别为箭头和
7、箭尾事项 的最早时间。,最迟时间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=总工期,7.3 网络图的时间参数,7.3 网络图的时间参数,计算各事项的最迟开始时间,重要结论和概念,最早开始时间=最晚开始时间的事项为项目的关键事
8、项,关键工序：总时差为0的工序。 关键路线：由关键工序组成的从总开工总完工事项的一条路线。 非关键工序：总时差大于0 的工序。,1.关键工序与关键线路,例题 1,例题 2,例题 3,已知下列资料：,要求： （1）绘制网络图（2）各事项的最早开始时间与最迟结束时间（3）确定关键路径,例题 4,如下图所示网络图，求出各结点的最早与最晚开始时间，关键路径等参数。,请画出前表网络图：,7.2 网络计划,注意紧前工序、紧后工序和虚工序的位置顺序,例题 4,Te(1)=0 Te(2)=8 Te(3)= 4 Te(4)= 8 Te(5)=11 Te(6)=12 Te(7)= 15,Tl(7)=15 Tl(6
9、)=12 Tl(5)= 12 Tl(4)=8 Tl(3)=5 Tl(2)=8 Tl(1)= 0,7.4 网络图优化分析,1.网络图优化的原则,1) 向非关键工序要资源； 2) 向关键工序要时间。,总工期-成本优化问题,（1）直接成本： 如人工、原材料、燃料和机械设备租用等直接与工序工作有关的费用，直接成本要分摊到每道工序上。 （2）间接成本： 如管理人员工资、行政办公费、采购费、劳保福利等，间接成本不分摊到每道工序上而作为整个工程的成本。显然，整个TE短，间接成本就低。,（1）直接成本： 如人工、原材料、燃料和机械设备租用等直接与工序工作有关的费用，直接成本要分摊到每道工序上。 （2）间接成本
10、： 如管理人员工资、行政办公费、采购费、劳保福利等，间接成本不分摊到每道工序上而作为整个工程的成本。显然，整个工程时间最短，间接成本就低。 (3)赶工成本 增加了人力物力等资源以后,使工期得以缩短而需要的费用,2.直接成本、间接成本、赶工成本,3、基本概念:,正常时间赶工时间正常成本赶工成本赶工成本斜率,赶工成本斜率： 工序（I,j）缩短一个单位时间所增加的直接成本称为该工序赶工成本斜率，记为：cij,C:表示成本 W：工作时间,5、优化分类：,一、缩短工程进度优化 二、时间成本优化 三、资源优化,例5-1,例题5-1 某工程的有关资料如下表所示，每天可以安排只有10人，要求工程在15天里完成
11、，应如何安排工程进度可以在现有人力资源下按期完成任务？,解题方法：,1、绘制网络图 看关键路线时间，人力资源是否满足要求？ 2、画出每天对人员的需要量的直方图 3、计划调整,二、时间成本优化,工程总费用=直接费用+间接费用+赶工费用 例5-5 某工程由4项工作组成，其资料如表5-9,该工程的间接成本为每天4500元，试求最低成本日,解：画出网络图，标上时间参数 工程直接费用=45000元 总费用=45000+4500*12+0=99000 求关键线路：,另外，一条线路了 1-2- 4 为时间富裕线，有2天机动时间。 改进方案1：,缩短关键工作时间，从成本斜率最低的关键工作着手,分析关键工作AC
12、D，工作D的赶工成本斜率最低，所以对D赶工，但是赶工多少？ 对D赶工2天后，出现两条关键路线1-2-3-4，1-2-4，工期为10天，总费用为：45000+450010+20002=94000,改进方案2：进一步缩短工期？ 要缩短工期就需要考虑两条路线,工程可选择的赶工方案,由上表可以知道，方案3的赶工费用最低，所以选择B，D各赶工1天，这样工期变为9天。 总费用=45000+45009+20003+10001 =92500 改进方案三 继续赶工，对A或者B,C赶工，但是发现B,C赶工费用为5000，大于工程每天的间接费，赶工已经不合算，所以对A赶工2天： 总费用：45000+45007+20
13、003+10001+40002=91500 答：该工程总工期为7天，总费用为91500,课后作业,1.计算各结点的最早与最迟时间，各工序的最早开工、完工时间。,2.计算各结点的最早与最迟时间，各工序的最早开工、完工时间。,所有工序路线： 1- 2- 7- 10- 11=18 1- 2- 5- 6- 7 -10- 11=19 1 -2- 5- 6 -9 -10- 11=16 1 -2 -4 -5- 6 -7 -10 -11=18 1- 2- 4- 5- 6- 9- 10- 11=16 1 -2- 4- 8 -9 -10 -11=17 1 -3- 4- 5- 6- 7- 10- 11=20（关键路
14、线） 1 -3- 4- 5- 6- 9 -10 -11=17 1 -3- 4- 8- 9- 10- 11=19 1- 3- 4- 8- 11=19,习题,（1）绘制网络图 （2）计算各结点的最早和最晚开始时间 （3）求关键路线,肯定型网络：采用单一时间估计法估计各道工序作业时间的PERT网络为肯定型网络。,非肯定型网络：工序时间是随机变量的PERT网络称为非肯定的PERT网络。,u=,采用三种时间估计法来估算非肯定型网络个工序的工序时间，即对每道工序估计有3种时间：,a=最乐观时间、b=最保守时间、m=最可能时间,假设工序时间这个随机变量服从取值范围从a到b的B分布，随机变量的期望值u和方差a2分别为：,a2=,7.5 肯定型与非肯定型网络,
