蔡诗文鲁林霞李强

1、第5章 图论 8推出新型产品完成计划的问题 论文摘要本文根据某公司推出新型产品的作业流程和各作业的计划完成时间、最短完成时间、计划完成时间缩短所用费用，来确定新产品生产时间和产品上市所需费用的最优策略。对于问题一，画出相应的计划网络图，可以清楚的看出作业流程情况；对于问题二，利用递推关系模型计算最早开始时间、最迟开始时间和工序时差，关键路线。利用Lingo 11.0 求解得到关键路线：，完成新产品的最迟时间加上作业的完成时间周是周。作业的最早时间分别是；最迟开始的时间分别是。对于问题三，可以说是对问题二的优化。通过建立递推关系模型计算最早完工时间与计划完成时间缩短时间的关系，利用Lingo 1

2、1.0求解在规定时间内完成的最小费用以及相应的时间。关键词：计划网络图 计划评审方法 关键路线法 期望 概率 问题重述某公司计划推出一种新型产品，需要完成的作业由表1示。表1作业名称计划完成时间（周）紧前作业最短完成时间（周）缩短1周的费用（元）A设计产品6-4800B市场调查5-3600C原材料订货3A1300D原材料收购2C1600E建立产品设计规范3A,D1400F产品广告宣传2B1300G建立产品生产基地4E2200H产品运输倒库2G,F2200（1）画出产品的计划网络图；（2）求完成的最短时间，列出各项作业的最早开始时间、最迟开始时间和计划网络的关键路线；（3）假定公司计划在17 周

3、内推出该产品，各项作业的最短时间和缩短1 周的费用如上表所示，求产品在17 周内上市的最小费用；（4）如果各项作业的完成时间并不能完全确定，而是根据以往的经验估计出来的，估计值如表2所示。试计算出产品在21 周内上市的概率和以95的概率完成新产品上市所需的周数。表2作业ABCDEFGH最乐观的估计24211321最可能的估计65323442最悲观的估计106435564 问题分析由题意可以看出，问题一、二主要考察了计划网络图的绘制与计算以及计划评审方法和关键路径法等相关统筹法的运用，利用计划网络图表示的作业之间的关系，确定出每个作业的最早开始时间、完成作业的时间、作业的最迟开始时间，工序时差的

4、关系从而将问题解答。问题三可以说是问题二的优化，将之前的模型，加上两个因素：一是对任务加上更多的资源，如在作业中加上更多的人力、物力使得产品完成的更快，成为“缩短期”；二是使计划网络模型满足到期完成，必须报入缩短期费用，目标是使缩短期的费用最少。1 模型假设1、每项作业完成的时间都是固定的。2、每一项工作的完成期间不受到任何因素的影响。 符号说明：表示事件的开始时间（）；：表示事件的最迟开始时间（）；：是作业的计划完成时间；：是作业的最短完成时间；：表示以为开始作业，以为完工作业的工序之差； ：是作业缩短一周的费用；：是作业的缩短时间；：要求完成的周数VI模型建立问题一： 根据题意，建立产品的

5、计划网络图如图1所示。C3E3D2B5H2F22G3A 645678123A6 图1问题二：（1）设为最初事件，为最终事件。希望求得完成的最短时间，即极小化，因此对于事件和有不等式：由此得到的相应的数学规划模型为：(其中是所有的事件集合，是所有的作业集合)。利用Lingo 11.0 编写程序（程序见附件一），由运行结果（运行结果见附件二）可以得到所求结果。运行结果给出了各个作业的开工时间，只要每个作业按规定的时间开工，整个项目完成的最短时间为20周。（2）1计算最早开始时间：用表示作业的最早开始时间，它等于到的最长单向链长，由图性质可得如下的递推公式：C3E3D2B5H2F22G3A 6567

6、89234A610图若用表示完工作业，则为作业完成所需要的时间。计算最迟完工时间：他应该等于总工期减去该作业的完工作业到总完工作业最长单向链的长。用表示作业的最迟完工时间，则有以下递推公式： 计算时差：一道工序的时差是指该工序的最迟完成时间与最早开始时间之差再减去它的工序长，凡时差为零的工序，它们的开始时间必须准时，即关键作业：利用Lingo 11.0 编写程序（程序见附件三），由运行结果（运行结果见附件四）可以得到所求结果。从结果中可以看出，关键路线：，完成新产品的最迟时间加上作业的完成时间周是周。作业的最早时间分别是；最迟开始的时间分别是。问题三：1、完成每个作业所用的各个时间的约束，即

7、2、完成任务所用的时间不超过要求完成的时间，即 3、要使产品额外增加的费用最少，即 即所建立的模型为 利用Lingo 11.0 编写程序（程序见附件五），由运行结果（运行结果见附件六）可以得到所求结果。最小费用为零，都没有缩短。问题四：VII参考文献1 附件一：model:sets:events/1.8/:x;operate(events,events)/1 2,1 3,1 5,2 4,3 7,4 5,5 6,6 7,7 8/: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

8、)+t(i,j);End附件二： Global optimal solution found. Objective value: 20.00000 Infeasibilities: 0.000000 Total solver iterations: 0 Variable Value Reduced Cost X( 1) 0.000000 0.000000 X( 2) 6.000000 0.000000 X( 3) 5.000000 0.000000 X( 4) 9.000000 0.000000 X( 5) 11.00000 0.000000 X( 6) 14.00000 0.000000 X

9、( 7) 18.00000 0.000000 X( 8) 20.00000 0.000000 T( 1, 2) 6.000000 0.000000 T( 1, 3) 5.000000 0.000000 T( 1, 5) 0.000000 0.000000 T( 2, 4) 3.000000 0.000000 T( 3, 7) 2.000000 0.000000 T( 4, 5) 2.000000 0.000000 T( 5, 6) 3.000000 0.000000 T( 6, 7) 4.000000 0.000000 T( 7, 8) 2.000000 0.000000 Row Slack

10、or Surplus Dual Price 1 20.00000 -1.000000 2 0.000000 -1.000000 3 0.000000 0.000000 4 11.00000 0.000000 5 0.000000 -1.000000 6 11.00000 0.000000 7 0.000000 -1.000000 8 0.000000 -1.000000 9 0.000000 -1.000000 10 0.000000 -1.000000附件三：model:sets:events/1.9/:t,x,y,s;operate(events,events)/1 2,2 3,2 4,2

11、 6,3 5,4 8,5 6,6 7,7 8,8 9/;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附件四：Feasible solution found. Total solve

12、r iterations: 0 Variable Value LEVENTS 9.000000 T( 1) 0.000000 T( 2) 6.000000 T( 3) 5.000000 T( 4) 3.000000 T( 5) 2.000000 T( 6) 2.000000 T( 7) 3.000000 T( 8) 4.000000 T( 9) 2.000000 X( 1) 0.000000 X( 2) 0.000000 X( 3) 6.000000 X( 4) 6.000000 X( 5) 11.00000 X( 6) 13.00000 X( 7) 15.00000 X( 8) 18.000

13、00 X( 9) 22.00000 Y( 1) 0.000000 Y( 2) 0.000000 Y( 3) 6.000000 Y( 4) 15.00000 Y( 5) 11.00000 Y( 6) 13.00000 Y( 7) 15.00000 Y( 8) 18.00000 Y( 9) 22.00000 S( 1) 0.000000 S( 2) 0.000000 S( 3) 0.000000 S( 4) 9.000000 S( 5) 0.000000 S( 6) 0.000000 S( 7) 0.000000 S( 8) 0.000000 S( 9) 0.000000 Row Slack or

14、 Surplus 1 0.000000 2 0.000000 3 0.000000 4 0.000000 5 0.000000 6 0.000000 7 0.000000 8 0.000000 9 0.000000 10 0.000000 11 0.000000 12 0.000000 13 0.000000 14 0.000000 15 0.000000 16 0.000000 17 0.000000 18 0.000000 19 0.000000 20 0.000000 21 0.000000 22 0.000000 23 0.000000 24 0.000000 25 0.000000

15、26 0.000000 27 0.000000 28 0.000000附件五：sets:events/1.8/:x;operate(events,events)/1 2,1 3,1 5,2 4,3 7,4 5,5 6,6 7,7 8/: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=siz

16、e(events);x(n)-x(1)<=d;for(operate:bnd(0,h,t-ts);for(operate:h<=t-ts);end附件六：Global optimal solution found. Objective value: 0.000000 Infeasibilities: 0.000000 Total solver iterations: 0 Variable Value Reduced Cost D 17.00000 0.000000 N 8.000000 0.000000 X( 1) 0.000000 0.000000 X( 2) 2.000000

17、0.000000 X( 3) 2.000000 0.000000 X( 4) 4.000000 0.000000 X( 5) 5.000000 0.000000 X( 6) 7.000000 0.000000 X( 7) 17.00000 0.000000 X( 8) 17.00000 0.000000 T( 1, 2) 6.000000 0.000000 T( 1, 3) 5.000000 0.000000 T( 1, 5) 0.000000 0.000000 T( 2, 4) 3.000000 0.000000 T( 3, 7) 2.000000 0.000000 T( 4, 5) 2.0

18、00000 0.000000 T( 5, 6) 3.000000 0.000000 T( 6, 7) 4.000000 0.000000 T( 7, 8) 2.000000 0.000000 TS( 1, 2) 4.000000 0.000000 TS( 1, 3) 3.000000 0.000000 TS( 1, 5) 0.000000 0.000000 TS( 2, 4) 1.000000 0.000000 TS( 3, 7) 1.000000 0.000000 TS( 4, 5) 1.000000 0.000000 TS( 5, 6) 1.000000 0.000000 TS( 6, 7

19、) 2.000000 0.000000 TS( 7, 8) 2.000000 0.000000 C( 1, 2) 800.0000 0.000000 C( 1, 3) 600.0000 0.000000 C( 1, 5) 0.000000 0.000000 C( 2, 4) 300.0000 0.000000 C( 3, 7) 600.0000 0.000000 C( 4, 5) 400.0000 0.000000 C( 5, 6) 300.0000 0.000000 C( 6, 7) 200.0000 0.000000 C( 7, 8) 200.0000 0.000000 H( 1, 2)

20、0.000000 800.0000 H( 1, 3) 0.000000 600.0000 H( 1, 5) 0.000000 0.000000 H( 2, 4) 0.000000 300.0000 H( 3, 7) 0.000000 600.0000 H( 4, 5) 0.000000 400.0000 H( 5, 6) 0.000000 300.0000 H( 6, 7) 0.000000 200.0000 H( 7, 8) 0.000000 200.0000 Row Slack or Surplus Dual Price 1 0.000000 -1.000000 2 0.000000 0.

21、000000 3 0.000000 0.000000 4 5.000000 0.000000 5 0.000000 0.000000 6 14.00000 0.000000 7 0.000000 0.000000 8 0.000000 0.000000 9 8.000000 0.000000 10 0.000000 0.000000 11 0.000000 0.000000 12 2.000000 0.000000 13 2.000000 0.000000 14 0.000000 0.000000 15 2.000000 0.000000 16 1.000000 0.000000 17 1.0

22、00000 0.000000 18 2.000000 0.000000 19 2.000000 0.000000 20 0.000000 0.000000 21 0.000000 0.000000第二十六章 1 问题重述通过表49中1999年中国省、自治区的城市规模结构特征的一些数据，利用聚类分析的方法将这些省、自治区来进行分类。 问题分析我们要用数量化的方法描述事物之间的相似程度来对事物进行分类。在数据标准化之后，利用欧式距离计算27个样本点两两之间的距离，利用最短距离法来测量类与类之间的距离。最后画出聚类图然后按照要求进行分类。 模型假设1、 每个省、自治区的规模不会变化。 符号说明 模型建立1、 数据标准化： ；2、 构造距离矩阵来计算27个样本点两两之间的距离，利用欧几里得得距离：用最短距离法来测量类之间的距离：；3、 构造27个类，每一类只包含一个样本点，每一类平台高度为零；4、 合并距离最近的两类为一新类，并以这两类距离值作为聚类图的平台高度；5、 若类的个数为1，进入步骤6，若类数不为1，则回到步骤4；6、 绘制聚类图，根据需要决定类的个数和种类。 模型求解 模型评价与改进参考文献编号 作者，书名，出版地：出版社，出版年。编号 作者，论文名，杂志名，卷期号：起止页码，出版年。编号 作者，资源标题，网址