15013080蔡诗文-鲁林霞-李强

第5章图论8推出新型产品完成计划的问题Ⅰ论文摘要本文根据某公司推出新型产品的作业流程和各作业的计划完成时间、最短完成时间、计划完成时间缩短所用费用，来确定新产品生产时间和产品上市所需费用的最优策略。对于问题一，画出相应的计划网络图，可以清楚的看出作业流程情况；对于问题二，利用递推关系模型计算最早开始时间、最迟开始时间和工序时差，关键路线。利用Lingo11.0求解得到关键路线：12356789，完成新产品的最迟时间8y加上作业H的完成时间2周是22周。作业,,,,,,,ABCDEFGH的最早时间分别是0,0,6,6,11,13,15,18；最迟开始的时间分别是0,0,6,15,11,13,15,18。对于问题三，可以说是对问题二的优化。通过建立递推关系模型计算最早完工时间与计划完成时间缩短时间的关系，利用Lingo11.0求解在规定时间内完成的最小费用以及相应的时间。。关键词：计划网络图计划评审方法关键路线法期望概率Ⅱ问题重述某公司计划推出一种新型产品，需要完成的作业由表1示。表1作业名称计划完成时间（周）紧前作业最短完成时间（周）缩短1周的费用（元）A设计产品6-4800B市场调查5-3600C原材料订货3A1300D原材料收购2C1600E建立产品设计规范3A,D1400F产品广告宣传2B1300G建立产品生产基地4E2200H产品运输倒库2G,F2200（1）画出产品的计划网络图；（2）求完成的最短时间，列出各项作业的最早开始时间、最迟开始时间和计划网络的关键路线；（3）假定公司计划在17周内推出该产品，各项作业的最短时间和缩短1周的费用如上表所示，求产品在17周内上市的最小费用；（4）如果各项作业的完成时间并不能完全确定，而是根据以往的经验估计出来的，估计值如表2所示。试计算出产品在21周内上市的概率和以95％的概率完成新产品上市所需的周数。表2作业ABCDEFGH最乐观的估计24211321最可能的估计65323442最悲观的估计106435564Ⅲ问题分析由题意可以看出，问题一、二主要考察了计划网络图的绘制与计算以及计划评审方法和关键路径法等相关统筹法的运用，利用计划网络图表示的作业之间的关系，确定出每个作业的最早开始时间、完成作业的时间、作业的最迟开始时间，工序时差的关系从而将问题解答。问题三可以说是问题二的优化，将之前的模型，加上两个因素：一是对任务加上更多的资源，如在作业中加上更多的人力、物力使得产品完成的更快，成为“缩短期”；二是使计划网络模型满足到期完成，必须报入缩短期费用，目标是使缩短期的费用最少。[1]Ⅳ模型假设1、每项作业完成的时间都是固定的。2、每一项工作的完成期间不受到任何因素的影响。Ⅴ符号说明ix：表示事件i的开始时间（1..8i）；iy：表示事件i的最迟开始时间（1..8i）；ijt：是作业(,)ij的计划完成时间；,tsij：是作业(,)ij的最短完成时间；ijs：表示以i为开始作业，以j为完工作业的工序之差；ijc：是作业(,)ij缩短一周的费用；ijh：是作业(,)ij的缩短时间；d：要求完成的周数VI模型建立问题一：根据题意，建立产品的计划网络图如图1所示。图1问题二：（1）设1为最初事件，n为最终事件。希望求得完成的最短时间，即极小化1nxx，因此对于事件和有不等式：jiijxxtC3E3D2B5H2F22G3A645678123A6由此得到的相应的数学规划模型为：1min,(,),,..0,njiijixxxxtijAijVstxiV(其中V是所有的事件集合，A是所有的作业集合)。利用Lingo11.0编写程序（程序见附件一），由运行结果（运行结果见附件二）可以得到所求结果。运行结果给出了各个作业的开工时间，只要每个作业按规定的时间开工，整个项目完成的最短时间为20周。（2）[1]计算最早开始时间：用ix表示作业i的最早开始时间，它等于1到i的最长单向链长，由图2性质可得如下的递推公式：图2max|jiijxxtij若用n表示完工作业，则nx为作业完成所需要的时间。计算最迟完工时间：他应该等于总工期减去该作业的完工作业到总完工作业最长单向链的长。用表示作业的最迟完工时间，则有以下递推公式：min|jijiyxtij计算时差：一道工序的时差是指该工序的最迟完成时间与最早开始时间之差再减去它的工序长，凡时差为零的工序，它们的开始时间必须准时，即关键作业i：ijjiijsyxt利用Lingo11.0编写程序（程序见附件三），由运行结果（运行结果见附件四）可以得到所求结果。从结果中可以看出，关键路线：12356789，完成新产品的最迟时间8y加上作业H的完成时间2周是22周。作业,,,,,,,ABCDEFGH的最早时间分别是0,0,6,6,11,13,15,18；最迟开始的时间分别是0,0,6,15,11,13,15,18。问题三：1、完成每个作业所用的各个时间的约束，即jiijijxxtstC3E3D2B5H2F22G3A656789234A6100ijijijhtts,,ijA,ijV2、完成任务所用的时间不超过要求完成的时间，即1nxxd3、要使产品额外增加的费用最少，即,minijijijAch即所建立的模型为,minijijijAch1..0jiijijijijijnxxtststhttsxxd利用Lingo11.0编写程序（程序见附件五），由运行结果（运行结果见附件六）可以得到所求结果。最小费用为零，都没有缩短。问题四：VII参考文献[1]附件一：model:sets:events/1..8/:x;operate(events,events)/12,13,15,24,37,45,56,67,78/:t;endsetsdata:t=6,5,0,3,2,2,3,4,2;enddatamin=x(8)-x(1);@for(operate(i,j):x(j)x(i)+t(i,j));End附件二：Globaloptimalsolutionfound.Objectivevalue:20.00000Infeasibilities:0.000000Totalsolveriterations:0VariableValueReducedCostX(1)0.0000000.000000X(2)6.0000000.000000X(3)5.0000000.000000X(4)9.0000000.000000X(5)11.000000.000000X(6)14.000000.000000X(7)18.000000.000000X(8)20.000000.000000T(1,2)6.0000000.000000T(1,3)5.0000000.000000T(1,5)0.0000000.000000T(2,4)3.0000000.000000T(3,7)2.0000000.000000T(4,5)2.0000000.000000T(5,6)3.0000000.000000T(6,7)4.0000000.000000T(7,8)2.0000000.000000RowSlackorSurplusDualPrice120.00000-1.00000020.000000-1.00000030.0000000.000000411.000000.00000050.000000-1.000000611.000000.00000070.000000-1.00000080.000000-1.00000090.000000-1.000000100.000000-1.000000附件三：model:sets:events/1..9/:t,x,y,s;operate(events,events)/12,23,24,26,35,48,56,67,78,89/;endsetsdata:t=0,6,5,3,2,2,3,4,2;enddatax(1)=0;@for(events(j)|j#gt#1:x(j)=@max(operate(i,j):x(i)+t(i)));levents=@size(events);y(levents)=x(levents);s(levents)=0;@for(events(i)|i#lt#levents:y(i)=@min(operate(i,j):y(j)-t(i));s(i)=y(i)-x(i));End附件四：Feasiblesolutionfound.Totalsolveriterations:0VariableValueLEVENTS9.000000T(1)0.000000T(2)6.000000T(3)5.000000T(4)3.000000T(5)2.000000T(6)2.000000T(7)3.000000T(8)4.000000T(9)2.000000X(1)0.000000X(2)0.000000X(3)6.000000X(4)6.000000X(5)11.00000X(6)13.00000X(7)15.00000X(8)18.00000X(9)22.00000Y(1)0.000000Y(2)0.000000Y(3)6.000000Y(4)15.00000Y(5)11.00000Y(6)13.00000Y(7)15.00000Y(8)18.00000Y(9)22.00000S(1)0.000000S(2)0.000000S(3)0.000000S(4)9.000000S(5)0.000000S(6)0.000000S(7)0.000000S(8)0.000000S(9)0.000000RowSlackorSurplus10.00000020.00000030.00000040.00000050.00000060.00000070.00000080.00000090.000000100.000000110.000000120.000000130.000000140.000000150.000000160.000000170.000000180.000000190.000000200.000000210.000000220.000000230.000000240.000000250.000000260.000000270.000000280.000000附件五：sets:events/1..8/:x;operate(events,events)/12,13,15,24,37,45,56,67,78/:t,ts,c,h;endsetsdata:t=6,5,0,3,2,2,3,4,2;ts=4,3,0,1,1,1,1,2,2;c=800,600,0,300,600,400,300,200,200;d=17;enddatamin=@sum(operate:c*h);@for(operate(i,j):x(j)-x(i)+ts(i,j)=t(i,j));n=@size(events);x(n)-x(1)=d;@for(operate:@bnd(0,h,t-ts));@for(operate:h=t-ts);end附件六：Globaloptimalsolutionfound.Objectivevalue:0.000000Infeasibilities:0.000000Totalsolveriterations:0VariableValueReducedCostD17.000000.000000N8.0000000.000000X(1)0.0000000.000000X(2)2.0000000.000000X(3)2.0000000.000000X(4)4.0000000.000000X(5)5.0000000.000000X(6)7.0000000.00