B题 机床加工.doc

B题 机床加工摘 要本文讨论了如何排列工件加工顺序分别使工件加工时间总和最小、机床加工总时间最小和加工工件总补偿费用最小这三个问题。运用线性规划的方法解决了工件加工时间总和最小的问题，建立了模型，结合多个约束条件，使用lingo软件做线性规划得出工件加工顺序为，加工时间最小和为2588。运用哈米尔顿图原理解决了机床加工总时间最小的问题，使用lingo软件做非线性规划得出加工顺序为机床最小总加工时间为459。运用线性规划原理解决了加工工件总补偿费用最小问题，建立了模型，结合约束条件，使用lingo软件做线性规划处理得出工件加工顺序为最小补偿费14242。文章运用穷举法分别检验建立的三个模型及算出的数据，得出了结论是模型是正确的，数据十分精准。关键字：线性规划 哈密尔顿图 一、问题重述现有14件工件等待在一台机床上加工，某些工件的加工必须安排在另一些工件完工以后才能开始。第号工件的加工时间及先期完工的工件号用下表给出：工件号12345678910111213142028251642123210242040243616前期工号3,45,7,85,9-10,113,8,943,5,74-4,76,7,145,121,2,6 （1）若给出一个加工顺序，则确定了每个工件的完工时间（包括等待与加工两个阶段）。 试设计一个满足条件的加工顺序，使各个工件的完工时间之和达到最小。 （2）假若第号工件紧接着第号工件后开工，机床需要花费的准备时间是， 试设计一个满足条件的加工顺序，使机床花费的总时间最小。 （3）假定工件的完工时间（包括等待与加工两个阶段）超过一确定时限,则需支付一定的补偿费用，其数值等于超过时间与费率之乘积（各个工件补偿率, 见下表）。 1234567891011121314121015161011108541010812试在=100，=0，安排一个加工顺序，使的总补偿费用最小。二、符号说明为第号工件加工顺序编号；为各个工件的完工时间之和；为机床需要花费的总时间；为补偿费；为第号工件的完工时间；其中以上3、 模型假设1、 机床在加工工件时不会出现问题。2、 每个工件可以反复使用。3、 加工各个工件之间的时间是连续的。4、 模型的建立与求解问题一：根据题意可以设各个工件的完工时间之和为约束条件为： ， 利用可以得出最佳的方案和结果为：的最优解为： 问题二：根据题意要求我们可以绘得如下机床准备时间的有向图：1468312411152071049141623884122513122图 11212471110495341821202101413164219141161217图 2从图中可以看出此图为半哈密尔顿图，起点为，终点为，可以将首尾相接，得到H-圈。根据以上图可以画出邻接矩阵如下表：表 1252410143081204120120810127804110469110131416024141719021820210041516200通过编程得到可以得到满足条件的加工顺序，即：机床花费的最小准备时间为：114加工14个工件的总时间为 花费总时间为： 问题三：目标函数约束条件： ， 得到： 最小补偿费为： 142425、 模型检验由题意可得一个包括10个工件的不等式其中没有、，可以得到、的条件为 分析不等式得，、可放在这条链中的某些节点中，经过排列组合共有19种排法，先对进行排序见下表表 2排列序号排列的方法加工这7个工件的完工时间之和加工这7个工件，机床花费的总准备时间加工这7个工件，机床总补偿费用17836523872763872435377586243547796724355765452465676964286577456524658757542465976157246510745732613117177025651272964256513733832565147536124731571363254516709542545177137225451872571254519745562473、可放在这条链中的某些节点中，经过排列组合共有8种排法，对进行排序如下表表 3排列序号排列的方法加工这7个工件的完工时间之和加工这7个工件，机床花费的总准备时间加工这7个工件，机床总补偿费用11887691199121879731185531911 8112255419058512179518838511931619018512119718977011971818958212159根据以上两个表可得各个工件完工时间之和最小的顺序为：即 各个工件的完工时间最小之和为：2588机床花费的总时间最小顺序为： 即 机床花费的最小准备时间为：114加工14个工件的总时间为：345机床花费的总时间最小为：使补偿费用最小顺序为： 即最小补偿费为：经检验所得结果均一致。6、 参考文献1 谢金星，薛毅，优化建模与软件，北京：清华大学出版社，20072 孙惠泉，图论及其应用，北京：科学出版社，20063 邦詹森，.古庭，有向图的理论算法及其应用，北京：科学出版社，2009附录第一问算法：min=20*(14-y1)+28*(14-y2)+25*(14-y3)+16*(14-y4)+42*(14-y5)+12*(14-y6)+32*(14-y7)+10*(14-y8)+24*(14-y9)+20*(14-y10)+40*(14-y11)+24*(14-y12)+36*(14-y13)+16*(14-y14);x1=y1+1;x2=y2+1;x3=y3+1;x4=y4+1;x5=y5+1;x6=y6+1;x7=y7+1;x8=y8+1;x9=y9+1;x10=y10+1;x11=y11+1;x12=y12+1;x13=y13+1;x14=y14+1;y1y3+0.00001; y1y4+0.00001;y2y5+0.00001; y2y7+0.00001;y2y8+0.00001; y3y5+0.00001;y3y9+0.00001; y5y10+0.00001;y5y11+0.00001; y6y3+0.00001;y6y8+0.00001; y6y9+0.00001;y7y4+0.00001; y8y3+0.00001;y8y5+0.00001; y8y7+0.00001;y9y4+0.00001; y11y4+0.00001;y11y7+0.00001; y12y6+0.00001;y12y7+0.00001; y12y14+0.00001;y13y5+0.00001; y13y12+0.00001;y14y1+0.00001; y14y2+0.00001;y14y6+0.00001;y1+y2+y3+y4+y5+y6+y7+y8+y9+y10+y11+y12+y13+y14=91;gin(y1);gin(y2);gin(y3);gin(y4);gin(y5);gin(y6);gin(y7);gin(y8);gin(y9);gin(y10);gin(y11);gin(y12);gin(y13);gin(y14);y113;y213;y313;y413;y513;y613;y713;y813;y913;y1013;y1113;y1213;y1313;y1410(-1); sqrt(y1-y6)2)10(-1);sqrt(y1-y2)2)10(-1); sqrt(y1-y8)2)10(-1);sqrt(y5-y9)2)10(-1); sqrt(y11-y9)2)10(-1);sqrt(y7-y9)2)10(-1); sqrt(y11-y10)2)10(-1);sqrt(y7-y10)2)10(-1); sqrt(y4-y10)2)10(-1);sqrt(y9-y10)2)10(-1);第二问算法：MODEL:SETS:C / 1. 14/: U; LINK( C, C):DIST, X; ENDSETSDATA: DIST =0100000010000001000000100000010000001000000 1000000 100000010000001000000100000025100000010000000241000000100000010100000014100000010000001000000100000010000001000000301000000100000010000008100000012100000010000001000000100000010000001000000100000010000000100000041000000100000010000001210000001000000100000010000000 100000010000001000000010000001000000100000010000001000000121000000100000010000001000000100000010000001000000100000001000000100000010000008101210000001000000100000078100000010000001000000010000004100000010000001000000100000010000001000000100000010000001000000111000000100000001000000461000000100000010000001000000910000001110000001000000100000010000000100000010000001000000100000010000001000000100000010000001000000131410000001610000000241000000100000010000001000000100000010000001410000001000000171000000190210000001000000100000010000001000000100000010000001000000100000018100000020210100000010000001000000100000010000001000000100000010000001000000100000010000001000000100000010000000410000001516100000010000001000000201000000100000010000001000000100000010000000;ENDDATAN = SIZE( C);MIN = SUM( LINK: DIST * X);FOR( C( K):SUM( C( I)| I #NE# K