浙江大学最牛应用运筹学PPT课件

.,1,浙江大学管理学院杜红duhong,应用运筹学（2008复习版）,.,2,第三章线性规划模型,建立线性规划问题模型模型构建的一般思路：确定该LP问题的目标是什么？实现目标取决于什么因素和条件？确定哪几个因素为决策变量？目标如何用决策变量来加以描述？约束条件如何表达？决策变量本身是否有限制条件？,.,3,第三章线性规划模型,线性规划问题模型的一般形式：目标函数：约束条件：,X0,.,4,第三章线性规划模型,两个变量的线性规划问题的几何解释,Maxz=X1+3X2s.t.X1+X26-X1+2X28X1,X20,z=0,z=3,z=6,z=9,z=12,z=15.3,0123456,-8-7-6-5-4-3-2-1,654321,x1,x2,目标函数等值线Z=X1+3X2,可行域,(4/3,14/3),例：求解以下线性规划问题,.,5,第三章线性规划模型,对偶问题与影子价格定义：设以下线性规划问题MAXZ=CTXs.t.AXbX0为原始问题，则称以下问题MINW=bTYs.t.ATYCY0为原始问题的对偶问题，最优值Y为影子价格,.,6,第三章线性规划模型,对偶问题与原始问题的关系,.,7,对偶问题的性质对偶问题的对偶是原问题。若两个互为对偶问题之一有最优解，则另一个必有最优解，且目标函数值相等(Z*=W*)，最优解满足CX*=Y*b。若X*,Y*分别是原问题和对偶问题的可行解，则X*,Y*为最优解的充分必要条件是Y*XL=0和YSX*=0。,第三章线性规划模型,原问题标准型：MaxZ=CXAX+XL=bX,XL0,对偶问题标准型：MinW=YbYA-YS=CY,YS0,.,8,第三章线性规划模型,原问题和对偶问题的互补松松弛关系：,.,9,第三章线性规划模型,对偶问题解影子价格根据对偶问题的性质有：Z*=W*=biyi*两边对bi求偏导数得到：Z*=yi*(i=1,2,m)bi即yi*表示每增加一个单位bi后Z*的增量,.,10,例3-9:合理下料问题：某工厂生产某一型号的机床，每台机床上分别需用2.9、2.1、1.5米长的轴1跟、2根和1根，这些轴需用同一种园钢制作，圆钢的长度为7.4米。如需要生产100台机床，问应如何安排下料，才能使用料最省？试建立其线性规划模型。,第三章线性规划模型,.,11,第三章线性规划模型,问题分析：对于每一根7.4米长的钢材，可有若干种下料方式把它截取成我们所需要的轴，如可以截取2根2.9米和1根1.5米，合计用料7.3米，余料为0.1米。可以列出全部的下料方式：,.,12,线性规划模型配套问题,思考题：某厂生产一种产品，由两个B1零件和三个B2零件配套组装而成。该厂有A1，A2，A3三种机床可加工上述两种零件，每种机床的台数以及每台机床每个工作日全部用于加工某一种零部件的最大产量（即生产率：件/日）如下表所示。试求该产品产量最大的生产方案。,.,13,该题不是单纯要求两种零件产量越大越好，而是要求每个工作日按2:3的比例生产出来的B1和B2零件的套数达到最大。决策变量：以Xij表示每台Ai(i=1,2,3)机床每个工作日加工Bj(j=1,2)零件的时间。Z为B1,B2零件按2:3比例配套的数量（套/日）。约束条件：工时约束X11+X12=1(A1一天）X21+X22=1(A2一天）X31+X32=1(A3一天）配套约束：Z=MIN(320X11+235X21+410X31)/2,(330X12+245X22+418X32)/3),.,14,Z=MIN(320X11+235X21+410X31)/2,(330X12+245X22+418X32)/3)等价于Z(320X11+235X21+410X31)/2Z(330X12+245X22+418X32)/3非负约束：Z,Xij0,Z为整数目标函数：MAXY=Z求解结果：Y*=Z*=44,X11=0.13,X12=0.87,X21=1,X22=0X31=0.25,X32=0.75,A1B1:8,A1B2:78,A2B1:70,A2B2:0,A3B1:10,A3B2:54B1:88件；B2:132件,.,15,配料问题练习,某化工厂要用三种原料D,P,H混合配置三种不同规格的产品A,B,C。各产品的规格、单价如左表所示，各原料的单价及每天的最大供应量如右表所示，该厂应如何安排生产才能使利润最大？,.,16,配料问题练习答案,变量：产品A中D,P,H含量分别为X11,X12,X13产品B中D,P,H含量分别为X21,X22,X23产品C中D,P,H含量分别为X31,X32,X33令：X11+X12+X13=X1X21+X22+X23=X2X31+X32+X33=X3根据规格条件有：X110.5X1;X120.25X1X210.25X2;X220.5X2,.,17,配料问题答案,得到：-X11+X12+X130-X11+3X12-X130-3X21+X22+X230-X21+X22-X230原材料供应条件：X11+X21+X31100X12+X22+X32100X13+X23+X3360非负约束：Xij0,i,j=1,2,3目标函数：maxz=-15X11+25X12+15X13-30X21+10X22-40X31-10X33,.,18,第四章线性规划的扩展,整数线性规划(IntegerLinearProgramming,ILP)问题定义：决策变量是整数的线性规划所有变量都取整数的规划称为纯整数规划部分变量取整数的规划称为混合整数规划整数规划与线性规划的关系线性规划问题整数规划问题,.,19,第四章线性规划的扩展,整数规划与线性规划解的差异,X2,X1,A,B,线性规划解：A（2.6，3.8）,Z=17.8,整数规划解：B（5，3）,Z=17.0,.,20,第四章线性规划的扩展,0-1规划一些变量的取值被限定为0或1。是整数规划的特例。0-1规划的一般模型：s.t.Xj=0,1j=1,2,n（X=0,1等价于X1,X0且取整数。）0-1规划问题求解：思路与LP、IP问题一致。0-1变量的灵活运用（选与不选或只能选几种等）。,.,21,例4-2厂址选择问题在N个地点中选r个（Nr）建厂，在第i个地点建厂（i=1，2，N）所需投资为Ii万元，占地Li亩，建成以后的生产能力为Pi万吨。现在有总投资I万元，土地L亩，应如何选择厂址，使建成后总生产能力最大。,第四章线性规划的扩展,.,22,设：整数规划（0-1规划）模型为：,投资约束,土地约束,建厂约束,第四章线性规划的扩展,.,23,例4.3考虑固定成本的最小生产费用问题某工厂有三种设备均可生产同一产品，第j种设备运行的固定成本为dj，运行的单位变动成本为cj，则生产成本与产量xj的关系为：j=1,2,3如何使设备运行的总成本最小？,第四章线性规划的扩展,.,24,引入01变量yj，令建立以下模型：这里M是一个很大的正数。当yj=0时，xj=0，即第j种设备不运行，相应的运行成本djyj+cjxj=0当yj1时，0xjM，实际上对xj没有限制，运行成本为dj+cjxj这是一个混合0-1规划问题,第四章线性规划的扩展,.,25,练习题：建立线性规划模型,.,26,练习题：建立线性规划模型,决策变量确定：（是否投资需要决策）X11，X12，X21，X31均为01变量约束条件确定：第一种产品的方案一和方案二最多只能选一：X11+X121第二种产品、第三种产品可选也可不选：X211，X311全部投资额应不超过550万300X11+280X12+260X21+240X31550,第一种产品方案1方案2X11X12,第二种产品X21,第三种产品X31,.,27,练习题：建立线性规划模型,目标函数确定：每年的收益和最大每年的总收益包含两部分：第一部分：项目投资收益，利用投资回收系数第二部分：剩余资金的普通投资收益,.,28,第四章线性规划的扩展,指派问题n项任务（B1,B2,Bn)由n个人(A1,A2,An)去完成，每项任务交给一人，每人只有一项任务。第i个人Ai去做第j项任务Bj的工作效率（如工时、成本或价值等）为Cij。问如何安排人员使总工作效率最好？设Xij表示Ai完成Bj工作，并令1当指派Ai去完成Bj工作Xij=0当不指派Ai去完成Bj工作,.,29,第四章线性规划的扩展,指派问题数学模型的标准型MINZ=（Cij0)（i=1,2,n)(j=1,2,n)Xij皆为0或1由Cij组成的方阵C=(Cij)nn称为效率矩阵,.,30,第四章线性规划的扩展,指派问题标准型的求解匈牙利法指派问题有以下性质：若从效率矩阵C的任何一行（列）各元素中分别减去一个常数K（K可正可负）得到新矩阵D,则以D为效率矩阵的指派问题与原问题有相同的解，但最优值比原问题最优值小K。用匈牙利法求解的条件：MIN、i=j、Cij0,.,31,第四章线性规划的扩展,匈牙利法的主要步骤：第一步：变换效率矩阵，使在各行各列都出现零元素。1、从矩阵C的每行元素减去该行的最小元素；2、再从所得矩阵的每列中减去该列最小元素。第二步：以最少数目的水平线和垂直线划去所有的零元素。如果所用的直线等于行或列数，则结束指派。否则继续。第三步：找到没有被划去的最小的元素，所有没有被划中的元素减去这一最小值。而被划中两次的元素（该元素行列都被划中）则要加上这一最小值。再返回到第一步。第四步：最后根据零元素的位置，确定最优分配方案。,.,32,第四章线性规划的扩展,运输问题从产地到销地之间运送货物的最佳路径。多个产地和多个销地；每个产地的产量不同，每个销地的销量也不同；各产销两地之间的运价不同。如何组织调运，才能既满足各销地的要求，又使总的运输费用（或里程、时间等）最小。,.,33,第四章线性规划的扩展,设有同一种货物从m个出发地1，2，m运往n个到达地1，2，n。第i个出发地的供应量（Supply）为si（si0），第j个到达地的需求量（Demand）为dj（dj0）。每单位货物从产地i运到销地j的运价为Cij。求一个使总运费最小的运输方案。123n供应1c11c1ns12c21成本c2ns2cijmcm1cmnsm需求d1dn,出发地,到达地,.,34,第四章线性规划的扩展,产销平衡的运输问题模型令Xij为从i地运到j地的数量MINZ=（Cij0)（i=1,2,m)供应约束(j=1,2,n)需求约束Xij0由Cij、Si、dj组成的(m+1)(n+1)矩阵称为运输矩阵,.,35,第四章线性规划的扩展,目标规划及有概念关数学模型偏差：实际决策值与目标值之间的差异正偏差：决策值超过目标值的部分负偏差：决策值低于目标值的部分记正偏差量d+，负偏差量d-，则有：d+d-0绝对约束：严格满足的等式或不等式约束目标约束：把约束右端项看成是要追求的目标值，在达到此目标时允许有正负偏差，线性规划问题的目标函数，在给定目标值和加入正、负偏差后可变换为目标约束，也可将绝对约束变换为目标约束。,.,36,第四章线性规划的扩展,优先等级与权系数：要达到的多个目标之间有主次、轻重缓急之分，因此各目标之间有优先等级。凡第一位要达到的目标赋予等级系数P1,次位的赋予等级系数P2，以此类推；并规定PkPk+1,Pk比Pk+1更大的优先权。相同等级的以不同的权系数加以区别。目标规划的目标函数：目标规划的目标函数是按各目标约束的正、负偏差变量和赋予相应的优先因子而构造的。当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值，因此目标规划的目标函数只能是MINZ=f（d+,d-)。要求恰好达到目标值（正负偏差都要尽可能地小），这时MINZ=f（d+d-)要求不超过目标值（允许达不到，正偏差要尽可能地小）MINZ=f（d+)要求不低于目标值：MINZ=f（d-),.,37,运输与目标规划练习：,有三个产地给四个销地供应某产品，产销地之间的供需量和单位运价（Cij）如下：,要求：1）建立此运输问题的线性规划模型(用矩阵的形式简化表示)；2）由于市场情况的变化，B3和B4的销量各增加了50单位（可求得此时最小运费为2950元）。由于生产能力无法再提升，因此有关部门在研究调运方案时需依次考虑以下情况（已规定其优先等级P1P3）：P1:A3向B1提供的产量不少于100；P2:给B1和B3的供应需求率要相等；P3:总运费增加不超过最小调运方案费用的10。试建立求解满意调运方案的目标规划模型（不需要化简整理）。,.,38,运输与目标规划练习：,产销平衡，运输问题模型令Xij为从i地运到j地的数量目标函数：MINZ=（Cij0)约束条件：（i=1,2,3)供应约束(j=1,2,3,4)需求约束Xij0,.,39,运输与目标规划练习：,供应绝对约束：i=1,2,3目标约束条件：j=1,2,3,4需求目标约束目标函数：,.,40,第四章线性规划的扩展,动态规划动态规划解决多阶段决策问题将过程按时间、空间等标志分为若干个阶段；每一个阶段都需要作出决策；阶段决策依赖于当前状态，又影响以后发展。动态规划没有标准模型，没有唯一确定的解法,决策1,决策2,决策3,决策n,1,状态1,2,3,n,状态n,状态4,状态3,状态2,阶段1,阶段2,阶段3,阶段n,.,41,第四章线性规划的扩展,动态规划的基本概念：阶段k：表示决策顺序的离散量，阶段可按时间或空间划分。状态Sk：能确定地表示决策过程当前特征的量。状态可以是数量也可以是字符，数量状态可以是连续的也可以是离散的。状态变量Xk：表示每一状态可以取不同值的变量。决策dk：从某一状态向下一状态过渡时所做的选择。决策是所在状态变量的函数，记为dk(Xk)。决策允许集合Dk(xk)：在状态Xk下，允许采取决策的全体。状态转移方程Xk+1=T(Xk,dk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。,.,42,第四章线性规划的扩展,动态规划的方法将完整的问题划分成若干个阶段；明确最终要达到的目的；从最终结果倒推，逐个阶段地作出决策；回到出发点，作出最后一个决策，再向前推可得到每一阶段的最优决策。,.,43,动态规划作业,.,44,第四章线性规划的扩展,S1=2,S4=0,S3=2,S3=1,S3=0,S2=2,S2=1,S2=0,0.06,0.48,0.30,0.16,0.30,0.50,0.80,0.30,0.50,0.80,0.20,0.40,0.60,0.60,0.40,0.60,0.15,0.20,0.40,第一组,第三组,第二组,剩余人数,.,45,第五章时序和路径规划,工作的时序规划时序顺序时间时序规划多项任务等待同一人或物处理，每项任务的单独完成的时间确定，且没有先后关系（紧前、紧后）。怎样安排各项任务的顺序，使总效率最高？系统时间加工时间排队时间,.,46,第五章时序和路径规划,工作的时序规划平均排队（等待）时间最短问题加工时间最短者优先（相同时间的可任意安排）平均延误时间最短问题最先到期的工作优先,.,47,第五章时序和路径规划,时序规划扩展（约翰逊原则）：两台顺序机器完成一批工作每项工作在机器1和机器2上的加工时间不一样，如何使系统效率最高？,3,2,1,4,机器1,机器2,工作,.,48,第五章时序和路径规划,约翰逊原则找出各台机器上加工时间最短的一项工作，如果在机器1上，这项工作最先做；如果在机器2上，这项工作最后做；不断重复，从两端往内排。相同时间可任选一个，一般先安排机器1上工作。,.,49,第五章时序和路径规划,最小树一个网络中有很多树，其中边的长度（权数）之和为最小的树为最小树。最小树的获取破圈法从图中任取一个圈，去掉该圈的一条最大边，将此圈破去，然后重复破圈，直至无圈为止。,.,50,第五章时序和路径规划,通过一个网络的最短路径问题在一个网络中，给定一个始点Vs，和一个终点Vt，求Vs到Vt的一条路，使路长最短。求解能划分阶段的，可采用动态规划方法。不能分阶段的，采用狄克斯屈方法。,.,51,第五章时序和路径规划,狄克斯屈方法开始节点标永久标记0,S,其余临时T,-找出与开始节点相邻的所有节点，为每一个设标记L,1，其中L值最小的节点标记右上角标上*，使之成为永久标志。从新的永久标志开始，找出从此节点出发可到达的所有节点，计算这些节点的最短距离（现有距离和经新的永久标志到达的距离的小的一个值），保持、新设或更改这些节点的标志为最短距离，最短路径上前一节点标号，比较图中所有没有*的标记（临时性标记），找出距离最短的一个节点，使之成为永久性标记。重复这一步，直到所有的节点都成为永久性标志为止。,.,52,第五章时序和路径规划,k,i,j,Di,m,Lij,Dj,k,从i-j时：如果Di+LijDj,则不改变j的标记；如果Di+LijDj，则改为Di+Lij,i,狄克斯屈方法,.,53,最短路径问题的应用,例56：设备更新问题某厂使用一种设备，每年年初设备科需要对该设备的更新与否作出决策。若购置新设备，就要支付购置费；如果继续使用则需要支付维修费，设备使用的年数越长，每年所需的维修费越多。现若第一年年初购置了一台新设备，问在5年内如何制定设备更新计划，以便使新设备购置费和维修费的总费用最小？已知设备在5年内各年年初的价格及设备使用不同年数的维修费如下：,.,54,最短路径问题的应用,例56：设备更新问题把求总费用最小问题化为最短路径问题。用点i(i=1,2,3,4,5)表示第i年买进一台新设备。增设一点6表示第五年末。从i点到i+1,6各画一条弧，弧（i,j）表示在第i年买进的设备一直使用到第j年年初（第j1年年末）。求1点到6点的最短路径。路径的权数为购买和维修费用。弧（i,j）的权数为第i年的购置费ai从第i年使用至第j-1年末的维修费之和。从第i年使用至第j-1年末的维修费：b1+bj-i（使用寿命为j-i年）如：（24）权数为：a2+b1+b2=1156=22具体权数计算结果如下：,.,55,通过一个网络的最短路径,例56设备更新问题：使用Dijstra算法，上述问题最短路为1-3-6或1-4-6即：第1、3年年初购买设备，或第1、4年年初购买设备五年最佳总费用为53。,1,3,2,5,4,6,16,22,17,18,23,30,59,41,17,30,16,23,41,31,22,.,56,通过一个网络的最大流量,最大流量问题在一定条件下，使网络系统中从开始点到结束点之间的某种物资流的流量达到最大的问题。限制条件是每一条边的最大通过能力（流量）不等。但有多条路最大流量求解线性规划方法福特富尔克逊标号法（“分步流动”）,.,57,最大流量的线性规划模型,例57：有下列石油运输管道图。某公司欲采用这个网络图从1地向销地7运送原油，弧的容量Cij（万升/时）已给定（因管道直径的变化，Cij不完全相同）。问如何安排输送，方能使每小时运送的原油最多？,.,58,最大流量的线性规划模型,设弧（i,j）上的流量为Fij,总流量为F.目标函数：MAXF=F12+F14约束条件：流入流出;FijCij;Fij02点：F12=F23+F25;4点：F14=F43+F46+F473点：F23+F43=F35+F36;5点：F25+F35F576点：F36+F46F67;7点：F47+F57+F67=F12+F14解：F12=5;F14=5;F23=2;F25=3;F43=2;F46=1;F47=2;F35=2F36=2;F57=5;F67=3最大流量F10,.,59,思考题：最小费用最大流,如果弧（i,j）上的单位流量费用为Bij(百元/万升）。图中每一条弧的权数前一位为流量限制Cij，后一位为单位费Bij。怎样运送才能使运送最多的石油并使总的费用最小？提示：先求得最大F值；再求总流量为F时使总费用最小的方案。进一步思考：1）求最小费用问题，如何求每小时运送6万升原油的最小费用？2）Cij为两节点之间的距离时，求节点1到节点7的最短距离？,.,60,第五章时序和路径规划,标记：流入节点的流量，该流量的来源节点，第一个节点标记，S。选取已有标记的一个节点，找出从此节点能直接到达的一个节点，确定到达节点的最大流量，相应地标上标记。重复这一步，尽快到达终点，得到一条从起点到终点的路径，此路径的最大流量为流入终点的流量。将此路径上的每一边的流动能力减去此流量。再从起始节点开始，按新的流动能力，重新进行标号，找出新的一条途径和流量，重复进行下去，直到把所有可能的路径全部找到为止，全部路径的流量和即为通过该网络的最大流量。,福特富尔克逊标号法：,.,61,第五章时序和路径规划,i,j,Fi,K,Fj,i,mij,Fj=min(Fi,mij),福特富尔克逊标号法：,.,62,第七章决策分析,风险决策存在几种自然状态，哪一种状态发生不确定，但每种自然状态发生的可能性可以预计（主观概率值）。决策依据：最大期望收益、最小期望损失标准期望值：不同自然状态下可能得到的值期望值（概率结果值）决策方法：最大期望计算、条件概率、决策树、效用曲线分析,.,63,第七章决策分析,最大期望收益值计算i为备择方案，i=1,2,nj为自然状态，j=1,2,m为为第i个备择方案的期望收益值pj为第j个自然状态出现的概率Oij为第i个备择方案在第j个自然状态下的收益Vi0为第i个备择方案的初始投资值,.,64,第七章决策分析,风险的衡量当备择方案的期望收益值相等时，需计算风险值。风险应尽可能地小。为第i个备择方案的风险,.,65,第七章决策分析,决策树结构,决策节点,状态节点,状态节点,收益,收益,收益,收益,概率枝,方案枝,概率值,概率值,概率值,概率值,.,66,第七章决策分析,利用决策树决策绘出决策树预计各状态概率从右向左计算各个方案的收益期望根据期望值大小选择方案决策树求解多阶段决策问题,.,67,第七章决策分析,贝叶斯决策自然状态出现的概率估计的正确程度直接影响到决策中收益期望值。在条件许可的情况下，往往需要补充新信息。获得补充信息需支付一定的费用。根据获得的新信息修正原先对自然状态出现的概率的估计值，并利用修正的概率重新进行决策。修正概率主要利用贝叶斯定理。,.,68,第七章决策分析,贝叶斯决策过程先验分析根据资料及经验对各自然状态出现的概率作出估计，称为先验概率；根据先验概率可作出决策，得到最优期望值，记为EMV*。预验分析补充信息的成本收益分析后验分析获取条件概率，运用贝叶斯定理对先验概率进行修正，得到后验概率；根据后验概率作出决策，计算补充信息的价值。,.,69,第七章决策分析,预验分析信息的价值在于它能提高决策的最大期望值。但获取信息的费用超过它所能提高的期望收益就不合算了。所有信息中最好、最理想的信息自然是完全可靠、准确的信息，这种信息预报某自然状态出现，则在实际中必定出现这自然状态，这种信息称为完备信息。补充信息费用应远小于完备信息的价值（上限）。当完全信息预报出现第K个自然状态出现时，最优方案由MAXUkjj确定。在完备信息下，决策所能获得的最大期望收益值：ERPI与EMV*之间的差额就是得到完全信息而使期望值增加的部分，即为完备信息价值EVPI。,.,70,第七章决策分析,后验分析补充新信息，通过对X1,X2,XS共S个状态的调查，获得实际出现自然状态i而预报Xj的概率，即：P(Xj|i)。在已知先验概率P(j)(j=1,2,m)及条件概率P(Xj|i)(j=1,2,s;i=1,2,m)的基础上，利用贝叶斯定理计算修正概率，即后验概率：根据后验概率，计算各方案的期望收益值，并依据期望收益值，重新作出决策(最大期望收益)。计算获得补充信息后，最大期望收益的实际增量。,.,71,第七章决策分析,后验分析计算的表格形式,.,72,风险型决策,贝叶斯决策作业：假定天气是影响某工程项目能否按期完工的决定因素，如果天气好，工程能按期完工，施工单位能获利5万元；如果天气不好，不能按期完工，则要罚款1万元；但如不施工则要损失人工费0.2万元。根据过去的经验，在计划期内天气好的可能性为30。为更好地掌握天气情况，可请气象部门作进一步的预报，需支付信息费0.08万元。从所提供的预报信息可知，气象部门对好天气的预测准确性为80，对坏天气的预报准确性为90。问该如何进行决策？,.,73,贝叶斯决策作业,先验分析：好天气1（0.3)坏天气2（0.7)EMV施工510.8不施工0.20.20.2EMV*=0.8施工有利，期望收益0.8万元预验分析：完备信息最大期望收益ERPI=0.3*50.7*(-0.2)=1.36(万元）完备信息价值EVPI=1.36-0.8=0.56(万元)EVPI远大于收集信息成本(0.08),初步认为合算。,.,74,贝叶斯决策作业,后验分析：气象中心提供预报两种天气状态：好(X1),坏(X2)(补充信息的自然状态与原自然状态一致)补充信息概率好天气预报准确性为80，坏天气预报准确性为90P(X1|1)=0.8实际是好天气预报也是好天气P(X2|1)=0.2实际是好天气预报且是坏天气P(X1|2)=0.1实际是坏天气预报且是好天气P(X2|2)=0.9实际是坏天气预报也是坏天气,.,75,贝叶斯决策作业,后验分析概率计算的表格形式：后验决策：预报天气好（X1），每个方案的最大期望收益EMV好天气1|X1（0.77)坏天气2|X1（0.23)EMV施工513.62*不施工0.20.20.2,.,76,贝叶斯决策作业,后验决策：预报天气坏（X2），每个方案的最大期望收益EMV好天气1|X2（0.09)坏天气2|X2（0.91)EMV施工510.46不施工0.20.20.2*补充信息价值：后验决策最大期望收益EMV*=0.313.62+0.69(0.2)=0.9842补充信息价值：补充信息带来期望收益增量0.9842-0.80=0.1842补充信息价值大于预报信息成本（0.08)，因此的确是合算的。后验决策结果：预报好天气时施工，预报坏天气时不施工。,.,77,贝叶斯决策的决策树,1,2,6,7,8,11,10,5,4,9,不预报,预报,预报好0.31,预报差0.69,施工,施工,不施工,不施工,施工,不施工,天气好0.3,天气差0.7,天气差0.91,天气好0.09,天气差0.23,天气好0.77,5,5,5,-0.2,-0.2,-0.2,-1,-1,-1,0.8,3.62,-0.2,-0.46,-0.2,-0.2,-0.2,3.62,0.90,0.8,0.9,3,成本0.08,.,78,第八章项目管理,绘制网络图的准备工作确定目标：以时间要求还是资源费用要求为主工程分解：列出全部分解后的工序及代号清单工序关系：确定每一道工序的紧前工序是哪些工序时间：确定每一道工序的完成所需的时间一时估计法：仅估计一个完成工序的最大时间D三时估计法：乐观时间a、悲观时间b、最可能时间m,.,79,第八章项目管理,网络图绘制规则方向、时序与结点编号网络图是有向图，按流程的顺序，规定工序从左向右排列。网络图中的各个结点都有一个时间（某一个或若干个工序开始或结束时间），一般按结点的时间顺序编号（从左到右，从上到下），箭尾结点编号应小于箭头结点编号。始结点编号为1。网络图中不能出现缺口和回路二个结点之间只能有一个直接的工序两条箭线不能有同样的始末结点，若二个事项之间有几个平行进行的工序，不许直接连接，而需要引入虚工序。,.,80,第八章项目管理,网络图绘制规则平行作业有几个工序平行作业结束后转入下一个工序的情况下，考虑到计算网络时间的方便，选择在平行作业的几个工序中所需时间最长的一个工序，直接与其紧后工序衔接，而其它工序则通过虚工序与其紧后工序衔接。交叉作业对需要较长时间才能完成的一些工序，在工艺流程与生产组织条件允许的情况下，可以不必等待工序全部结束后再转入其紧后工序，而是分期分批的转入。分批转入时需增加虚工序。,.,81,第八章项目管理,网络图绘制规则始点和终点为表示工程的开始和结束，在网络图中只能有一个始点和一个终点。当工程开始时有几个平行工序或结束时有几个平行工序，而又不能用一个始结点或一个终结点表示时，需用虚工序把它们与始结点或终结点连接。网络图布局尽可能将关键线路布置在中心位置，尽量将联系紧密的工作布置在相近的位置；尽量用水平线或具有一段水平线的折线。,.,82,第八章项目管理,时间参数计算的符号约定,i,E(i),L(i),S(i),j,E(j),L(j),S(j),K,D(i,j),LFij,EFij,LSij,ESij,E(1)=0,L(j),E(j),.,83,第八章项目管理,结点（事项）时间结点本身不占用时间，它只表示某项工作应在某一时刻开始或结束，因此，结点参数主要只有两个：最早实现时间（最早时间）和最迟实现时间（最迟时间）。最早时间：以该结点结束的工作最早可能结束的时间，或以该结点开始的工作最早可能开始的时间。E(1)=0,计算时从左往右算。最迟时间：允许所有后续工序都能及时开始的最晚时间。L(n)=E(n),计算时需从右往左算。,.,84,第八章项目管理,结点（事项）时间计算结点最早时间E(j)的计算E(1)=0E(j)=maxE(i)+D(i,j),j=2,3,4,9,8,7,6,7,E(7)=5,E(8)=6,E(9)=MAXE(7)+6,E(8)+7)=13,.,85,第八章项目管理,结点（事项）时间计算结点最迟时间L(i)的计算L(n)=E(n)L(i)=MINL(j)-D(i,j),i=n-1,n-2,9,11,10,20,12,L(10)=70,L(11)=89,L(9)=MIML(10)-20,L(11)-12)=50,.,86,第八章项目管理,工序时间参数计算一个工序可以从箭尾结点的最早时间开始作业，也可以适当推迟开始，但须在箭头结点的最迟时间内完工才不至于延误后续工序，因此工序时间就包括最早开始时间和最迟开始时间，加上或减去该工序的作业时间，相应地还有最早结束时间和最迟结束时间。最早开始时间:ESij=E(i)最早结束时间：EFij=ESij+D(i,j)最迟结束时间：LFij=L(j)最迟开始时间：LSij=LFij-D(i,j),.,87,第八章项目管理,时差及计算结点时差：最迟与最早时间差S(i)=L(i)E(i)工序总时差：不影响工期(最早结束时间）的该工序可松动的时间（可以推迟开始的时间）.Sij=LSijESij=LFijEFij=L(j)E(i)D(i,j)工序单时差：不影响紧后工序最早可能开始条件下，工序最早可能完工时间可以推迟的时间.Rij=E(j)EFij,.,88,第八章项目管理,关键线路关键线路的长度决定了工程周期，关键线路可以有多条，计划安排得越紧凑，关键线路越多。关键线路的确定线性规划方法破圈法：在圈中去掉最短的一个工序。图上作业法：标注结点时间，结点时差为0的结点组成关键线路。表上作业法：计算工序时间，总时差为0的工序组成关键线路。,.,89,线性规划方法求关键线路,画出网络图决策变量：各节点活动的发生时间（项目起始时刻为0）；目标函数：最后一个节点的发生（完成）时间最早；约束条件：各个活动的实际持续时间应不小于完成活动所需时间；某活动实际持续时间某活动结束时间开始时间建立活动节点矩阵，对任一节点，箭头进入为+1，箭头流出为-1。利用该矩阵元素与相应变量之间的乘积和计算各工序的时间。关键线路判断：影子价格为1的工序（为什么？）或实际持续时间与完成活动所需时间相等的工序为关键线路上的工序。,.,90,第八章项目管理,图上标注法,0,60,70,80,100,110,135,170,170,135,110,120,80,117,60,0,.,91,第八章项目管理,费用与完工时间的关系,工程费用,极限时间,间接费用,直接费用,总费用,正常时间,T,.,92,第八章项目管理,时间-费用优化分析方法：最低成本日程：费用最低的工程完工时间T直接费用变动率：缩短单位时间增加的直接费用T计算程序按正常时间画出网络图，找到关键线路计算成本时间在关键线路上找出g最小的工序，压缩活动时间重复上一步，直到总费用上升为止,.,93,第八章项目管理,时间资源优化尽量合理地利用现有资源，并缩短周期时间资源优化方法优先安排关键工序所需要的资源；利用非关键工序的总时差，错开工序开工时间，拉平资源需要量的高峰；在确实受到资源限制，或者在综合考虑经济效益的条件下，也可适当地推迟完工时间,.,94,作业：画网络图并调整时间,.,95,作业：画网络图并调整时间,1,5,6,4,3,2,7,A,X,Y,B,E,D,F,H,C,4,G,8,7,5,3,3,6,4,0,0,4,5,11,12,12,12,15,15,8,8,8,8,关键线路：15467或BXGH，长度：15天,.,96,练习：画网络图并调整时间,正常进度完工费用=直接费用间接费用15315(天)5(百元/天)=228百元关键线路B,G,H中g最小的是G(g=3)，缩短G一天（为什么只缩短一天？）的工程费用变为（间接费用减少）：2281315226调整后有三条关键线路，并且所有节点的时差均为0，因此已无法再压缩工程时间。15467；12367；157,.,97,如何用线性规划求解,在既定的时间T前完工的前提下，问各活动（工序）的完成时间为多少（各项活动如何加速或缩短多少时间），才使因缩短工期而增加的费用最少。设工序（i,j）提前完工时间为Yij，i接点的实际发生时间为Xi，Tij，Tij分别为工序正常完工时间与最快完工时间（极限时间）,gij为直接费用变动率。目标函数：minF=gijYij约束条件：Xj-XiTijYij对一切可以压缩工序YijTijTij对一切可以压缩工序XnT；Xi，Yij0,.,98,如何用线性规划求解,各活动（工序）的完成时间为多少（各项活动如何加速或缩短多少时间），才使时间费用（