1、数学建模 数学建模竞赛试题及论文 : 原文信息 命题人： 邹祥福 审批人： 试卷分类（A 卷或 B 卷） A 数学建模竞赛试题：C 题：工件加工排序计划排序问题中的车间作业问题，研究 n 个工件在 m 台机器上有序的加工问题，每个工件都有完工的日期（DD，Due date）, 加工的时间（PT，Processing time）和工件的价值（VAL ，Value if job is selected）. 现研究一个工厂生产工序的计划和安排，需要计划与合理安排各个工件在这些机器上加工的先后次序，即拟订加工工序，通过各个工件在各种机器上加工次序的合理安排，使得完成这批工件加工任务所需的总时间最省（注
2、：总时间即为各个零件的加工时间和加工其他零件时它们等待时间之和）或要求整个选择加工的工件价值最大。有一个工厂现在有 12 种工件（编号为工件 1，工件 2，工件 12）需要在车床，钻床，铣床几种不同的设备上加工。考虑下面的工件加工的排序问题：这 12 种工件 都要求在车床上加工，车床一次只能加工一种工件，这 12 种工件加工所需时间，每个工件的完工时间和每个工件的价值如表（1）所示：工件 加工时间（h） 完工时间(h) 工件价值 1 2.8 9 8 2 3.2 7.5 4 3 1.2 15 16 4 4 23 3 5 2.7 10 7 6 0.9 22 20 7 2.5 17 17 8 3.3
3、 33 11 9 1.7 7 7 10 2.5 18 12 11 3.6 25 5 12 4.7 11 18 表（1）不考虑工件的完工时间和工件的价值，为该工厂安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。建立数学模型并给出相应的算法。由于工件必须在它们要求的时间内完工，按照表（1）的数据，为该工厂安排选择加工工件的种类及加工的次序，使得整个选择加工的工件价值最大。建立数学模型并给出相应的算法。如果这 12 种工件都要求先在车床上加工，然后再在钻床上加工（即工件在钻床加工之前必须先在车床上加工过） ，每种机器一次只能加工一种工件，这 12 种工件加工所需时间如表（2）所示：工件
4、 车床加工时间（h） 钻床加工时间(h) 1 2.8 4 2 3.2 1.3 3 1.2 1.8 4 4 2.2 5 2.7 3 6 0.9 4.5 7 2.5 1.7 8 3.3 2.5 9 1.7 4.5 10 2.5 2.5 11 3.6 3.8 12 4.7 1.9 表（2）为该工厂安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。建立数学模型并给出相应的算法。 如果这 12 种工件都要求先在车床上加工，然后再在钻床上加工，最后再在铣床上加工，每种机器一次只能加工一种工件，这 12 种工件加工所需时间如表（三）所示：工件 车床加工时间（h） 钻床加工时间(h) 铣床加工时间
5、(h) 1 2.8 4 3 2 3.2 1.3 1 3 1.2 1.8 2.5 4 4 2.2 1.3 5 2.7 3 1.8 6 0.9 4.5 2 7 2.5 1.7 3.6 8 3.3 2.5 0.8 9 1.7 4.5 1 10 2.5 2.5 1.1 11 3.6 0.9 1.3 12 4.7 1.9 0.7 表（3）为该工厂安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。建立数学模型并给出相应的算法。对于上述问题你做 的数学模型和相应的算法给出评价。并将模型推广到 n 个工件在m 台机器上加工的一般的工件排序问题，给出你的想法和解决问题的思路。解题正文：C 题：工件加
6、工排序（建模小组成员： AP0308306 陈运标 AP0308307 邓风仪 AP0206311 黄深泉）摘要本题根据已知数据，结合问题中的具体要求，我们引入 0/1 变量建立工件排序的数学规划模型。借助 Lingo 软件进行求解运算，得出其中的最优排序方案。使得完成这批工件加工任务所需要的总时间最省。在这里，我们通过对各个工件（排序后）完成某项特定工序所需总时间进行求和得到整个加工任务所需要的总时间。而各工件的总时间包括其机床加工时间和加工其他零件时的等待时间。模型的假设：在后面的模型中，我们都假定了忽略工件在转换工序时的运输时间。即将整个工件加工过程简化为一个连续的过程，只考虑机床在加工
7、 件时其他工件的等待时间。模型的建立：我们的思路是引入 0/1 变量对工件进行动态排序，根据问题要求得出排序后的目标函数（即数学模型） 。根据题目的约束条件，利用 Lingo 软件算出模型的最优解，从而获得工件的最优排序。问题（一）题目要求：12 种工件都要求在车床上加工，车床一次只能加工一种工件。设 i 工件车床加工时间为 A ,规定完工时间为 B ,工件价值为 C 不考虑工件的完工时间和工件的价值，安排工件加工的次序，使得完成这批工件加工任务所需的总时间最省。分析：引入 0/1 变量，利用目标函数最优化工件排序。设 为 i 工件实际完工时间，所以完成这批工件的总时间为 T= ,而 =A +
8、A =A +A +A =A +A + = 因此: 建立问题（1）的目标函数即数学模型为 Min= 定义 x ，x x 为 0/1 变量， ， ， 为原始工件序列下 i 工件的车床加工时间；所以A =x a +x a + .+x a A =x a +x a + .+x a .A =x a +x a + .+x a x +x + .+x =1x +x + .+x =1.x +x + .+x =1x +x +x + +x +x =1x +x +x + +x +x =1.x +x +x +x +x =1Lingo 程序：（附 wenti(1).lg4 文件）model:!不考虑完工时间和工件价值的排序
9、问题;sets:gongjian/g1.g12/:shijian; !属性为原始排序下各个工件的机床加工时间;shunxu/s1.s12/:time,fin_time; !属性为重新排序后各工件的机床加工时间和完成车工序的时间;links(shunxu,gongjian): note;endsets!目标函数：求各个工件的加工总时间和最小;min=sum(shunxu(I):fin_time(I);!重新排序后各工件的机床加工时间;for(shunxu(J):time(J)=sum(gongjian(I):shijian(I)*note(I,J););!排序后各个工件的加工总时间;for(sh
10、unxu(I):fin_time(I)=sum(shunxu(J)|J#le#I:time(J););!每个顺序位只能有一个工件;for(shunxu(I):sum(gongjian(J): note(I,J)=1;);!每个工件只能排在一个顺序位上;for(gongjian(J):sum(shunxu(I): note(I,J )=1;);!定义 0/1 变量;for(links:bin(note);data:!输出数据到 Excel 文档;OLE(D:liebiao.XLS)=time,fin_time;!原始排序下各个工件的机床加工时间;shijian= 2.8,3.2,1.2,4,2.
11、7,0.9,2.5,3.3,1.7,2.5,3.6,4.7;enddataend结果数据：工件 加工时间 完成时间 T 6 0.9 0.9 3 1.2 2.1 9 1.7 3.8 10 2.5 6.3 7 2.5 8.8 5 2.7 11.5 1 2.8 14.3 2 3.2 17.5 8 3.3 20.8 11 3.6 24.4 4 4 28.4 12 4.7 33.1 总计：171.9 表 1-1所以最优排序是 639107512811412完成这批工件加工任务所需的最省总时间为 171.92) 分析：由于工件必须在它们要求的时间内完工，即某工件在任务开始起到该工件加工完毕之间所用的总时间
12、应少于该工件的规定完工时间。所以要使整个加工任务的工件总价值最大，必须合理选择加工工件的种类及其加工的次序。引入 0-1 变量,若选择 i 工件加工,则记 Y =1.否则记 Y =0;工件的排序算法同问题 1） ，但约束条件有所不同。在本题 中，12 种工件不一定都可以入选到最优加工序列中（即目标排序中可能出现工件空缺） ，所以 ( =1, 2, .12)，且 ( =1, 2, .12)， 为 0-1 变量。用 Lingo 进行编程，工件集加入原始排序下车床加工时间，完工时间和工件价值属性；顺序集加入重新排序后车床加工时间，完工时间和工件价值属性；因此该模型为：目标函数: Max= （在排序算
13、法及程序中已隐含有 ）工件选择： ( =1, 2, .12)， ( =1, 2, .12)完工时间约束： ( =1, 2, .12)Lingo 程序：（wenti(2).lg4 文件）model:!考虑完工时间和工件价值的排序问题;sets:gongjian/g1.g12/:shijian,endtime,gj_value; ! 属性为原始排序下各个工件的机床加工时间，完工时间，工件价值;shunxu/s1.s12/:time,overtime,fin_value; ! 属性为重新排序后各个工件的机床加工时间，完工时间，工件价值;links(shunxu,gongjian): note;end
14、sets!目标函数;max=sum(shunxu(I):fin_value(I);!从新 序后各工件的机床加工时间（可能为零，即表示未选中工件）;for(shunxu(I):time(I)=sum(gongjian(J):shijian(J)*note(I,J);!从新排序后各工件的完工时间（可能为零，即表示未选中工件）;for(shunxu(I):overtime(I)=sum(gongjian(J):endtime(J)*note(I,J););!从新排序后各工件的工件价值（可能为零，即表示未选中工件）;for(shunxu(I):fin_value(I)=sum(gongjian(J):
15、gj_value(J)*note(I,J););!每个顺序位只能有一个工件或者没有工件;for(shunxu(I):sum(gongjian(J): note(I,J)=1);!每个工件只能排在一个顺序位上;for(gongjian(J):sum(shunxu(I): note(I,J)=1);!各工件的完工时间约束;for(shunxu(I):sum(shunxu(J)|J#le#I:time(J)=overtime(I););!定义 0/1 变量;for(links:bin(note);data:!原始排序下各个工件的机床加工时间;shijian= 2.8,3.2,1.2,4,2.7,0.
16、9,2.5,3.3,1.7,2.5,3.6,4.7;!原始排序下各个工件的完工时间;endtime=9,7.5,15,23,10,22,17,33,7,18,25,11;!原始排序 各个工件的工件价值 ;gj_value=8,4,16,3,7,20,17,11,7,12,5,18;enddataend模型结果：导出列表：工件顺序 车床加工时间 规定的完工时间 各工件价值 0 0 0 0 0 0 1 2.8 9 8 5 1.7 7 7 12 4.7 11 18 10 2.5 18 12 3 1.2 15 16 6 0.9 22 20 7 2.5 17 17 2 4 23 3 11 3.6 25
17、5 8 3.3 33 11 总价值：117 表 1-2由上表可知，最优方案是选择工件 1512103672118，并按此顺序进行加工。从而获得最大的工件总价值为 117.关于问题（二） ， （三） ， （四）分析：问题（二）要求：如果这 12 种工件都要求先在车床上加工，然后再在钻床上加工（即工件在钻床加工之前必须先在车床上加工过） ，每种机器一次只能加工一种工件，求工件加工的最优排序，使得完成这批工件加工任务所需的总时间最省。根据总时间的定义，某工件从任务开始时刻起到完成钻床工序止所需要的总时间包括该工件完成车工序的时间，等待上 个工件加工完的时间（即从该工件在车床加工完毕时刻起到其上一个工
18、件在钻床上加工完毕这一段时间） ，该工件在钻床上加工的时间。我们假设 工件在车床 加工所需时间为 ，在钻床上 加工所需时间为 ； 工件完成在车床 加工的总时间为 ；（ ）工件完成在钻床 加工的总时间为 ， （ ） 。这里要分两种情况进行分析： 1).当 时，即 工件完成车工序的总时间大于或等于（ ）工件完成钻工序的总时间，此时 工件不需要等待（ ）工件而立即就进入钻工序，因此 工件完成钻床工序的总时间表达式为 + ;2).当 时，即 工件完成车工序的总时间小于或等于（ ）工件完成钻工序的总时间，此时 工件需要等待（ ）工件完成钻床工序才能进入钻床加工。因此 工件完成钻床工序的总时间表达式为 +
19、 。综合以上两种情况，得到 工件完成钻床工序的总时间计算公式为Max（ ， ）+ （ ）同理，对于问题（三） ，我们也可以得到类似的计算公式.，下面是以列表的形式将这一推导公式推广到 工件 个工序的情况：假设 i 工件在车床 加工所需时间为 ；在钻床上 加工所需时间为 ；在铣床 上加工所需要的时间为 ；在后续的各工序（ ）中加工所需要的时间设为 ；下表中内容表示 i 工件从任务开始时刻起到完成 道工序止所需要的总时间 工序顺序 工件顺序 车床 钻床 铣床 加工 1 + + + 2 + Max（ ， ）+ Max（ ， ）+ Max（ ， ）+ 3 Max（ ， ）+ Max（ ， ）+ Max
20、（ ， ）+ i Max（ ， ）+ Max（ ， ）+ Max（ ， ）+ 表 2-1模型的建立：根据表 2-1，问题（二）中要求的完成加工任务的最省总时间即为在最优排序下各工件完成钻床加工工序的总时间之和。即建立问题（二）的数学模型为 Max= + （ ， ）+ ；这里 + ； Lingo 编程：附录 1（went i(3).lg4）文件同理，问题（三）中要求的完成加工任务的最省总时间即为在最优排序下各工件完成铣床加工工序的总时间之和。建立问题（三）的数学模型为 Max= + （ ， ）+ ；这里 + ； Lingo 编程：附录 2（wenti(4).lg4）文件归纳以上算式，推广到 i
21、个工件 j 部机床的工件排序问题，建立问题（四）的数学模型为 Max= + （ ， ）+ ；这里 + ； Lingo 编程：（略） 模型结果：问题（二）运算后导出列表：顺序号 工件号 车床加工时间 钻床加工时间 完成车床工序总时间 完成钻床工序总时间 1 3 1.2 1.8 1.2 3 2 6 0.9 4.5 2.1 7.5 3 7 2.5 1.7 4.6 9.2 4 2 3.2 1.3 7.8 10.5 5 10 2.5 2.5 10.3 13 6 5 2.7 3 13 16 7 9 1.7 4.5 14.7 20.5 8 4 4 2.2 18.7 22.7 9 8 3.3 2.5 22 2
22、5.2 10 1 2.8 4 24.8 29.2 11 11 3.6 3.8 28.4 33 12 12 4.7 1.9 33.1 35 总时间：224.8 表 2-2由上表可知，最优的工件排序为 367210594811112，完成这 工件加工任务所需的最省总时间为 224.8。问题（三）运算后导出列表：顺序号 工件号 车床加工时间 钻床加工时间 铣床加工时间 1 3 1.2 1.8 2.5 2 9 0.9 4.5 2 3 11 3.6 0.9 1.3 4 10 2.5 2.5 1.1 5 7 2.5 1.7 3.6 6 9 1.7 4.5 1 7 2 3.2 1.3 1 8 5 2.7 3
23、 1.8 9 8 3.3 2.5 0.8 10 1 2.8 4 3 11 4 4 2.2 1.3 12 12 4.7 1.9 0.7 表 2-3顺序号 工件号 完成车床工序总时间 完成钻床工序总时间 完成铣床工序总时间 1 3 1.2 3 5.5 2 9 2.1 7.5 9.5 3 11 5.7 8.4 10.8 4 10 8.2 10.9 12 5 7 10.7 12.6 16.2 6 9 12.4 17.1 18.1 7 2 15.6 18.4 19.4 8 5 18.3 21.4 23.2 9 8 21.6 24.1 24.9 10 1 24.4 28.4 31.4 11 4 28.4
24、30.6 32.7 12 12 33.1 35 35.7 总时间：239.4 表 2-4从软件的运行情况可知，最优的工件排序为 391110792581412；完成这批工件加工任务所需的最省总时间为 239.4模型评价，改进方法，推广在本题的解答过程中所建立的数学规划模型中，我们始终围绕一种化整为零的 学思想，将整批工件的加工任务拆分为在最优的排序下每个工件的实际加工情况来分析，根据各工件在加工过程中加工时间和总时间之间的联系，寻求各工件加工总时间的具体算法。再利用 Lingo 软件进行求解模型，得出工件的最优排序。其中逻辑严谨，论证充分，算法简洁准确。有效地提高了软件求解效率。由于在模型求解
25、中利用了 Lingo 软件，大大简化了编程工作，且模型本身结合软件的使用就具有很强的可移植性，便于模型的推广。列如在推广到 m 工件 n 部机床的情况，只需在程序中的工件，顺序集里加入相应的属性；在程序段中加入对应的算法和约束条件就可以完全替换从而解决问题了。参考资料：姜启源 等，数学模型（第三版） ，高等教育出版社，2003。洪文 吴本忠，Lingo4.0 for windows 最优化软件及应用，北京大学出版社， 2001。http:/http:/mcm.csu.edu.c n/Forums/1/268/ShowPost.aspx#268附录一：model:!工件先车后钻的排序问题;set
26、s:gongjian/g1.g12/:che_shijian,zuan_shijian;shunxu/s1.s12/:che_time,zuan_time,che_fintime,zuan_fintime;links(shunxu,gongjian): note;endsets!目标函数;min=sum(shunxu(I):zuan_fintime(I);!从新排序后各工件的车床加工时间;for(shunxu(I):che_time(I)=sum(gongjian(J):che_shijian(J)*note(I,J););!从新排序后各工件的钻床加工时间;for(shunxu(I):zuan
27、_time(I)=sum(gongjian(J):zuan_shijian(J)*note(I,J););!每个顺序位只能有一个工件;for(shunxu(I):sum(gongjian(J): note(I,J)=1;);!每个工件只能排在一个顺序位上;for(gongjian(J):sum(shunxu(I): note(I,J)=1;);!从新排序后各工件在完成车工序的总时间;for(shunxu(I):che_fintime(I)=sum(shunxu(J)|J#le#I:che_time(J););!从新排序后各工件在完成钻工序的总时间;for(shunxu(I)| I#gt#1:z
28、uan_fintime(I)=if(che_fintime(I)#ge#zuan_fintime(I-1),che_fintime(I),zuan_fintime(I-1)+zu an_time(I););!顺序 1 中的工件在完成钻工序的总时间 ;zuan_fintime(1)=che_fintime(1)+zuan_time(1);!定义 0/1 变量;for(links:bin(note);data:!原始排序下各个工件的车床加工时间;che_shijian= 2.8,3.2,1.2,4,2.7,0.9,2.5,3.3,1.7,2.5,3.6,4.7;!原始排序下各个工件的钻床加工时间;
29、zuan_shijian=4,1.3,1.8,2.2,3,4.5,1.7,2.5,4.5,2.5,3.8,1.9;enddataend附录二：model:!工件先车后钻再铣的的排序问题;sets:gongjian/g1.g12/:che_shijian,zuan_shijian,xi_shijian;shunxu/s1.s12/:che_time,zuan_time,xi_time,che_fintime,zuan_fintime,xi_fintime;links(shunxu,gongjian): note;endsets!目标函数;min=sum(shunxu(I):xi_fintime(
30、I);!从新排序后各工件的车床加工时间;for(shunxu(I):che_time(I)=sum(gongjian(J):che_shijian(J)*note(I,J););!从新排序后各工件的钻床加工时间;for(shunxu(I):zuan_time(I)=sum(gongjian(J):zuan_shijian(J)*note(I,J););!从新排序后各工件的铣床加工时间;for(shunxu(I):xi_time(I)=sum(gongjian(J ):xi_shijian(J)*note(I,J););!每个顺序位只能有一个工件;for(shunxu(I):sum(gongji
31、an(J): note(I,J)=1;);!每个工件只能排在一个顺序位上;for(gongjian(J):sum(shunxu(I): note(I,J)=1;);!从新排序后各工件的车完工时间;for(shunxu(I):che_fintime(I)=sum(shunxu(J)|J#le#I:che_time(J););!从新排序后各工件在钻工序的完工时间;for(shunxu(I)| I#gt#1:zuan_fintime(I)=if(che_fintime(I)#ge#zuan_fintime(I-1),che_fintime(I),zuan_fintime(I-1)+zuan_time
32、(I););!顺序 1 中的钻床工序的完工时间 ;zuan_fintime(1)=che_fintime(1)+zuan_time(1);!从新排序后各工件在完成铣工序的时间;for(shunxu(I)| I#gt#1:xi_fintime(I)=if(zuan_fintime(I)#ge#xi_fintime(I-1),zuan_fintime(I),xi_fintime(I-1)+xi_time(I););!顺序 1 中的铣床工序的完工时间 ;xi_fintime(1)=zuan_fintime(1)+xi_time(1);!定义 0/1 变量;for(links:bin(note);da
33、ta:!输出数据到 Excel 文档;OLE(D:liebiao.XLS)=che_time,zuan_time,xi_time,che_fintime,zuan_fintime,xi_ fintime;!原始排序下各个工件的车床加工时间;che_shijian= 2.8,3.2,1.2,4,2.7,0.9,2.5,3.3,1.7,2.5,3.6,4.7;!原始排序下各个工件的钻床加工时间;zuan_shijian=4,1.3,1.8,2.2,3,4.5,1.7,2.5,4.5,2.5,0.9,1.9;!原始排序下各个工件的铣床加工时间;xi_shijian=3,1,2.5,1.3,1.8,2,3.6,0.8,1,1.1,1.3,0.7;enddataend
