运筹学——网络计划课件

单击此处编辑母版标题样式,OR3,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,OPERATIONS RESE,运 筹 学,提醒：五月27、28日（即下周二、周三）的下午2：30到,系机房上实验课，不得缺席。,OR3,1,OPERATIONS RESE运 筹 学提醒：五,第五节 网络计划,引言：,国外实践证明：应用网络计划技术组织与管理生产和项目，一般能缩短工期20左右，降低成本10左右。,上海宝钢炼铁厂1号高炉土建工程施工中，应用网络法，缩短工期21，降低成本9.8。,OR3,2,第五节 网络计划引言：OR3,1、基本概念,网络图（有向赋权图）的构成：节点和箭线,节点：每个节点称为事件，是箭线两端的连接点。表示工序的开始或结束。,剪线：代表工序。剪尾表示该工序的开始，箭头表示该工序的结束。,工序：是组成整个任务的局部任务，需要消耗一定资源或占用一定时间。,注意：与工序相比，节点不需要时间或所需要时间少到可以忽略不计。,OR3,3,1、基本概念网络图（有向赋权图）的构成：节点和箭线OR3,例:,景泰蓝的制作工序：制胎、掐丝、点蓝、烧蓝、打磨、镀金。,i,j,工作名称或代号,持续时间,注意：,网络计划图是有向、有序的赋权图，应按项目的工作,流程从左向右编制。在时序上反应各项工作的先后顺序。,节点编号必须是,箭尾编号小于箭头编号,。,1,2,3,4,5,6,7,制胎,掐丝,点蓝,烧蓝,打磨,镀金,0.5,1,1,2,2,2,OR3,4,例:景泰蓝的制作工序：制胎、掐丝、点蓝、烧蓝、打磨,2、画网络图的基本规则,1）网络图中只能有,一个,总起点节点和,一个,总终点节点。总起点节点和总终点节点分别表示计划的开始和结束。,紧前工序：紧排在本工作之前的工作。,紧后工序：指紧排在本工作之后的工序。,1,3,4,2,5,6,7,A,B,C,D,E,F,OR3,5,2、画网络图的基本规则1）网络图中只能有一个总起点节点和一个,2）网络图不允许出现循环回路。,3)节点i,j之间不允许有两道或两道以上的工序。,2,1,3,1,2,A,B,OR3,6,2）网络图不允许出现循环回路。21312ABOR3,4)需正确表示工序之间的前行后继关系，工序之间的逻辑关系的分解图归纳如下：,（1）A完成后进行B和C。,A,B,C,OR3,7,4)需正确表示工序之间的前行后继关系，工序之间的逻辑关系的分,(2)A,B均完成后进行C。,A,B,C,OR3,8,(2)A,B均完成后进行C。ABCOR3,（3）A，B均完成后进行C和D。,A,B,C,D,OR3,9,（3）A，B均完成后进行C和D。ABCDOR3,(4)A完成后进行C，A,B完成后进行D。,虚工序：只表示相邻工作之间的逻辑关系，不占用资源的虚设工序。,A,C,B,D,OR3,10,(4)A完成后进行C，A,B完成后进行D。ACBDOR3,（5）A，B均完成后进行C；B,D均完成后进行E。,A,C,B,D,E,OR3,11,（5）A，B均完成后进行C；B,D均完成后进行E。ACBDE,5)虚工序的运用：可以用于正确表示平行工序与交叉工序。,平行工序：一道工序分为几道工作同时进行，称为平行工序。,交叉工序：两件或两件以上的工序交叉进行，称为交叉工序。,OR3,12,5)虚工序的运用：可以用于正确表示平行工序与交叉工序。OR3,举例,挖沟：,挖沟，埋钢管。挖一段埋一段。,24,挖沟,挖沟,8,挖沟,8,挖沟,8,a,1,a,2,a,3,b,1,b,2,b,3,十八岗,拖拉机厂,十五里河,姚公庙,OR3,13,举例挖沟：24挖沟挖沟8挖沟8挖沟8a1a2a3b1b2b3,工 序,A,B,C,D,E,F,G,H,I,紧前工序,-,-,A,B,B,C、D,C、D,E、F,G,工序时间,4,6,6,7,5,9,7,4,8,例题1：请按照下表编制该项目的网络计划图,A,B,C,D,E,G,H,4,6,7,6,7,5,F,9,4,I,8,OR3,14,工 序ABCDEFGHI紧前工序-ABB,课堂练习：请编制下表的网络计划图P,287,工序,紧后工序,工序时间,A,B,C,D,E,60,B,L,45,C,F,10,D,G,H,20,E,H,40,F,L,18,G,K,30,H,L,15,K,L,25,L,/,35,OR3,15,课堂练习：请编制下表的网络计划图P287工序紧后工序工序时间,线路：网络图中，从起点节点沿箭线方向顺序通过一系列箭线与节点，最后到达终点节点的通路。,关键路线：即持续时间最长的路线。关键路线上的各工作叫做关键工作。,A,B,C,D,E,G,H,4,6,7,6,7,5,F,9,4,I,8,OR3,16,线路：网络图中，从起点节点沿箭线方向顺序通过一系列箭线与节点,A,B,C,D,E,G,H,4,6,7,6,7,5,F,9,4,I,8,网络计划图的布局要求：尽可能将关键路线布置在网络图的中心位置，按工作的先后顺序将联系紧密的工作布置在临近的位置；箭线应是水平或具有水平线的折线。,A,4,C,6,B,6,D,7,G,7,I,8,F,9,E,5,H,4,OR3,17,A BCDEGH467675F94I8网络计,3、网络计划图的时间参数计算,1）工作持续时间的计算方法：,（1）单时估计法。,D工作的持续时间,Q工作的工作量。,R可投入人力和设备的数量,S每人或每台设备每工作班能完成的工作量。,n-每天正常工作班次。,OR3,18,3、网络计划图的时间参数计算1）工作持续时间的计算方法：OR,（2）三时估计法。先估计三种时间值，然后求其平均数。,乐观时间，记为a,最可能时间，记为m,悲观时间，记为b,工作持续时间：,OR3,19,（2）三时估计法。先估计三种时间值，然后求其平均数。OR3,2）其它时间的计算公式,（1）工作最早开始时间（ES)；工作最早完成时间（EF）,从网络图的起点开始进行计算。,第一项工作的最早开始时间为0，记为：ES,1j,0；,最早完成时间为：EF,1j,=ES,1j,+D,1j,注意：前一项工序完成以后，其紧后的工序才能开始。前一项工作的最早完成时间是其紧后工序的最早开始时间。所以有：,EF,ij,=ES,ij,+D,ij,OR3,20,2）其它时间的计算公式EFij=ESij+D ijO,(2)工作最迟开始时间（LS）；工作最迟完成时间（LF）,从网络图的终点开始采用逆序法进行计算。,网络图中最后一项工序的最迟完成时间应为工程的计划工期。若未给定计划工期，则取其为最早完成时间。即LF,i-n,=EF,i-n.，,LS,i-n,=LF,i-n,-D,i-n,其它工序：LS,i-j,=LF,i-j,-D,i-j,即LF=min(紧后工作的LS).,OR3,21,(2)工作最迟开始时间（LS）；工作最迟完成时间（LF）OR,（3）工作时差,时差又叫机动时间或富余时间。常用的时差有两种：,a)工作总时差TF,i-j。,指在不影响,工期,的前提下，工作所具有的机动时间。,计算公式：TF,i-j,=EF,i-j,-ES,i-j,-D,i-j,=LS,i-j,-ES,i-j,或者为：TF,i-j,=LF,i-j,-EF,i-j,b)工作自由时差FF。在不影响其,紧后工作,最早开始的前提下，工作所具有的机动时间。,计算公式：FF,i-j,=ES,j-k,-ES,i-j,-D,i-j,或：FF,i-j,=ES,j-k,-EF,i-j,注意：关键路线上无机动时间，工作总时差为零。,最后一道工序的FF为总工期将该工序的最早结束时间。,.,.,OR3,22,（3）工作时差OR3,.,例,计算上例工序时间参数,工序,i,j,D(i,j),ES,EF,LS,LF,TF,FF,A,4,0,4,3,7,3,0,B,6,0,6,0,6,0,0,C,6,4,10,7,13,3,3,D,7,6,13,6,13,0,0,E,5,6,11,19,24,13,11,F,9,13,22,15,24,2,0,G,7,13,20,13,20,0,0,H,4,22,26,24,28,2,2,I,8,20,28,20,28,0,0,OR3,23,.例 计算上例工序时间参数 工序ijD(i,j)ESEFL,4 网络优化,(1)工期优化：,使用技术措施，缩短关键路线。,采取组织措施，合理调配人力，物力，资金等资源。,(2)资源优化：,优先安排关键工作所需的资源；,利用非关键工作的总时差，错开各工作的开始时间。,的确受到资源约束时，考虑推迟工期,1,2,1,2,3,网络优化在上述基础上，寻求时间更短、资源,更省、成本更低的方案。,OR3,24,4 网络优化(1)工期优化：12123网络优化在上述基础上,(3)时间费用优化,时间和费用双目标优化，一般来讲二者是矛盾的。通过仔细分析，寻找既省时又省钱的方案，即最低成本日程。,费用：直接费用和间接费用,直接费用：建造工程本身所需材料、人工,间接费用：工程所需管理费用、设备租赁费用等。,c,t,间接费用,总费用,直接费用,赶工：直接费用增加，间接费用减少。,OR3,25,(3)时间费用优化ct间接费用总费用直接费用赶工：直接费用,费用优化的步骤,(1)计算工作费用增加率；,(2)在网络图中找出费用率最低的一项关键工作或一组关键工作作为缩短持续时间的对象。,(3)计算相应的增加的总费用，然后考虑由于工期的缩短间接费用的变化，在这个基础上计算项目的总费用。,重复上述步骤，直至获得满意的方案为止。,赶工直接费用率,费用差,时间差,OR3,26,费用优化的步骤(1)计算工作费用增加率；赶工直接费用率费用,前面内容总复习：,第一章：绪论。（了解）,第二章：线性规划与单纯形法,1，掌握线性规划的建模方法。,2，掌握将非标准型LP模型转变为标准型。,3，掌握LP问题的解法：图解法，单纯形解法。,（图解法：什么情况下会出现唯一最优解，无穷多最优解，无界解，无可行解。）,（单纯形法：会运用单纯形法求解LP问题；会根据单纯形表中出现的特征判断出该问题是否有唯一最优解，无穷多最优解，无界解以及无可行解P,24,。,OR3,27,前面内容总复习：第一章：绪论。（了解）OR3,4，掌握大M法以及两阶段法。,5，理解书P3637页的表19，110，图19。,第三章：对偶理论与灵敏度分析,1，掌握原问题与对偶问题数学模型的转化。书P56，表24。,2，对偶问题的基本性质P,57,。特别是性质3、5、6、7,3，理解影子价格，影子价格的应用。,OR3,28,4，掌握大M法以及两阶段法。OR3,影子价格：,对偶解,y,i,*,的经济意义,：其它条件不变的情况下，第i种资源改变一个单位所引起的目标函数最优解的变化。,情况 某资源对偶解,0,，该资源有利可图，可增加此种资源量；某资源对偶解为0，则不增加此种资源量。,情况 直接用影子价格与市场价格相比较，进行决策，决定是否买入该资源。,即：,影子价格所含有的信息：1、资源紧缺状况；2、确定资源转让基价；3、取得紧缺资源的代价。,OR3,29,影子价格：对偶解yi*的经济意义：其它条件不变的情况下，第,Cj,C,1,C,2,C,n,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,j,0,0,0,X,3,X,4,X,5,360,200,300,9 4 1 0 0,4 5 0 1 0,3 10 0 0 1,90,40,30,j,0,70 120 0 0 0,0,0 120,X,3,X,4,X,2,240,50,30,7.8 0 1 0 -0.4,2.5 0 0 1 -0.5,0.3 1 0 0 0.1,30.76,20,100,j,3600,34 0 0 0 -12,70,1200,X,3,X,1,X,2,84,20,24,0 0 1 -3.12 1.16,1 0 0 0.4 -0.2,0 1 0 -0.12 0.16,j,4280,0 0 0 -13.6 -5.2,OR3,30,CjC1 C2 CnCBXBb,OR3,31,OR3 31,OR3