工件的安装与排序15.doc

工件的安装与排序问题 摘要工件在安装时需要按工艺要求进行排序，在实践中具有一定的意义。本文讨论的是工件在安装时按重量排序、按重量和，以及在工件不满足要求时，怎样更换工件及求出新工件的重量和体积值范围。问题一要求按重量排序，而且相邻区域的4个工件总重量之差不允许超过一定值。对于该问题，我们采用0-1规划来选择满足分配到各扇形区的4个工件。问题二是在问题一的基础上多加了一个要求，即排序还得按体积排序。我们在问题一得到按重量排序的放法，但由于4个工件的顺序并没有确定，所以按重量排序的放法可能不满足按体积排序的放法。所以在问题二中，我们将圆盘分成24块区域，用0-1规划选择第i个工件放在第j块区域，且第i个工件只能放在1块区域里，1块区域只能放一个工件；再根据重量和体积排序算法确定24个工件的具体放法。问题三是在不满足前两个问题的情况下对个别工件进行调整，当工件不满足要求时，允许更换少量的数据。根据前面解决问题的算法可以得出两种修改策略：一是按重量排序；二是按重量和体积排序。如果只考虑重量，分析了两种相临扇区总重量差最大的情况，通过数学分析得出工件调整幅度，如果综合考虑重量和体积因素，则不断修正工件重量和体积，筛选出满足条件的工件组合。关键词：按重量排序、按体积排序、0-1规划、区域一、问题重述某设备由24个工件组成，安装时需要按工艺要求重新排序。 设备的24个工件均匀分布在等分成六个扇形区域的一圆盘的边缘上，放在每个扇形区域的4个工件总重量与相邻区域的4个工件总重量之差不允许超过一定值（如4g）。 工件的排序不仅要对重量差有一定的要求，还要满足体积的要求，即两相邻工件的体积差应尽量大，使得相邻工件体积差不小于一定值（如3 ）； 当工件确实不满足上述要求时，允许更换少量工件。 问题1按重量排序算法； 问题2按重量和体积排序算法； 问题3当工件不满足要求时，指出所更换工件及新工件的重量和体积值范围，并输出排序结果。 请按下面两组工件数据（重量单位：g ，体积单位： ），进行实时计算： 序号重量体积序号重量体积1348101.51358.510323521022357.5103334710533551034349105.54351103.55347.51065355.510363471046357102733094734196832998834296.59329100.5934095.510327.598.51034497113299811342.595.112331.59912343.596.513348.5104.513357.5102.5143471051435510315346.5107.515353.5103.516348104.516356.5103.517347.510417356103.518348104.518352.5104193339719342.59820330972034496.521332.59921339.59822331.59822341.59623331.596.523341962433294.52434597二、问题假设1、所给的24 个工件的重量在某范围内，相差不大，不会出现很重或很轻的工件2、圆盘足够大，每个扇形区域内的工件重量无论多大，均能放在扇形区域内，不会影响其他区域的重量3、存在重量相同但体积不同的工件和体积相同但重量不同的工件供我们更换三、变量说明1、gi第i个工件的重量2、wj第j个扇形区工件的总重量3、vi未经过排序的第i个工件的体积4、Vj已经过排序的第j个工件的体积5、相邻扇区质量和之差的要求范围6、相邻工件体积之差的要求范围四、问题分析分析问题一：我们通过0-1规划来选择哪个工件应该分配在哪个区，并且每个区分配4个工件，每个工件只能选一次，不能重复选。题意要求相邻区域的4个工件总重量之差不允许超过一定值，我们假设这个值为m，我们可以知道（4个最重工件的重量之和 4个最轻工件的重量之和），即。而且我们通过数据表格分析可知，所以数据都是0.5的倍数，所以m最小不能小于0.5g,即。为了得出最佳分配方案，我们以求m的最小值为目标函数建立模型。分析问题二：在问题一中按重量排序可以求得每个扇形区域所含的4个工件，但4个工件的顺序并没有确定，可能不满足按体积的排序。所以为了解决问题二，我们将圆盘分成24块区域，并且使相邻的4块构成一个扇形区域。用0-1规划选择第i个工件放在第j块区域，且第i个工件只能放在1块区域里，1块区域只能放一个工件；同时默认第1块区域到第4块区域构成第一个扇形区域，依次可得到第二、三、四、五、六块扇形区域。再根据重量和体积排序算法确定24个工件的具体放法。分析问题三：明确不满足的情况有两大种：（1）只考虑重量时，不满足重量的要求（2）综合考虑重量和体积时，分为以下3 种：五、模型建立与求解问题一为解决问题一，我们引入：建立模型目标函数:min=m约束条件： 有4个在同一扇区 6个扇区 ？运用数学软件Lingo对模型求解（运用数学软件Lingo所编的程序在附表一），得到结果：第一组工件：第一个扇形区：第6、8、18、19个工件第二个扇形区：第2、10、15、23个工件第三个扇形区：第11、13、14、21个工件第四个扇形区：第4、9、12、16个工件第五个扇形区：第5、7、17、24个工件第六个扇形区：第6、3、20、22个工件第二组工件：第一个扇形区：第1、9、14、22个工件第二个扇形区：第3、7、12、17个工件第三个扇形区：第11、13、16、21个工件第四个扇形区：第6、8、10、18个工件第五个扇形区：第5、15、23、24个工件第六个扇形区：第2、4、19、20个工件问题二我们假设相邻两个工件的体积之差不小于h建立模型目标函数:min=h/m约束条件：运用数学软件Lingo对模型求解（运用数学软件Lingo所编的程序在附表一），得到结果：第一组工件：第一个扇形区：第7、23、1、6第个工件第二个扇形区：第21、17、20、3个工件第三个扇形区：第12、15、16、22个工件第四个扇形区：第2、11、14、9个工件第五个扇形区：第8、5、24、4、个工件第六个扇形区：第19、13、10、18个工件第二组工件：第一个扇形区：第2、11、6、9个工件第二个扇形区：第1、20、4、12个工件第三个扇形区：第5、23、13、21个工件第四个扇形区：第18、8、14、10个工件第五个扇形区：第15、7、16、19个工件第六个扇形区：第17、22、3、24个工件问题三(一)只考虑重量时，不满足条件：设第j扇区和第j+1扇区之间的重量和不满足条件，只需更换其中一个扇区中某一工件。不妨设更换第j 个扇区中的一个工件，记该工件的重量为w , 这样，更换后第j扇区的重量和为w(j+1)，则w(j+1)需满足： e解得：即：令= g(j+1) g(j+1)则的范围：设新工件的重量为w=+w，所以新工件的重量范围为： (二) 同时考虑重量和体积时 当体积满足要求，重量不满足要求时，在更换时，我们只需按上述(一)的方法只更换工件的重量而保持其体积不变。 当重量满足要求，体积不满足要求时，我们可以按照上述(一)的思想方法进行更换，具体更换方法如下：我们假设第i 个工件和第i+1个工件之间的体积不满足条件，只需更换i，i+1中某一工件。不妨更换第i+1个工件。这样，更换后第i+1个工件的体积为v ( i+1) ,则v ( i+1)需满足：解得：即：或当重量和体积都不满足要求时，我们可以分步更换：先不考虑体积，只考虑重量，则可以按上述(一)的方法将其重量更换为满足重量要求的情形。然后再按照(二)-的方法将其体积更换为满足体积要求的情形。若先不考虑重量，只考虑体积， (二)- 的方法将其体积更换为满足体积要求的情形。然后再按照(二)- 的方法将其重量更换为满足重量要求的情形。六、对模型的评价与推广1、本论文所建模型运用简单的数学知识和数学软件lingo求解，简便易懂，具有较强的实践意义。2、模型在建立过程中综合考虑了重量、体积对工件排序的影响，使得所建模型更加优化、更具有实践意义。3、整数规划得到的结果稳定，只要给出基本的约束条件就能得到理想的结果，而约束条件只随题目的基本情况而改变，便于修改。4、由于m与h所给的范围较大，lingo程序在运行中，时间过长，故应尽量减小 m与h的所给范围。参考文献 1唐焕文，数学模型引论（第三版） ，北京：高等教育出版社， 2005。2运筹学教材编写组，运筹学（修订版），北京：清华大学出版社，1982。3汪晓银，数学软件与数学实验，北京，科学出版社，2008。附表一模型程序:model:sets:gongjian/1.24/:g;qu/1.6/:w;paisheng(gongjian,qu):x;endsetsdata:g=348352347349347.5347330329329327.5329331.5348.5347346.5348347.5348333330332.5331.5331.5332;!g=358.5357.5355351355.5357341342340344342.5343.5357.5355353.5356.5356352.5342.5344339.5341.5341345;enddatamin=m;for(qu(j):sum(gongjian(i):x(i,j)=4);for(gongjian(i):sum(qu(j):x(i,j)=1);for(qu(j):sum(gongjian(i):g(i)*x(i,j)=w(j);for(qu(j)|j#le#5:abs(w(j+1)-w(j)m);abs(w(6)-w(1)m;m0.5;for(paisheng:bin(x);End模型结果:Global optimal solution found. Objective value: 0.5000000 Objective bound: 0.5000000 Infeasibilities: 0.5684342E-13 Extended solver steps: 378 Total solver iterations: 5017 Variable Value Reduced Cost M 0.5000000 0.000000 W( 1) 1357.000 0.000000 W( 2) 1357.500 0.000000 W( 3) 1357.000 0.000000 W( 4) 1357.500 0.000000 W( 5) 1357.000 0.000000 W( 6) 1356.500 0.000000 X( 1, 1) 0.000000 0.000000 X( 1, 2) 0.000000 0.000000 X( 1, 3) 0.000000 0.000000 X( 1, 4) 0.000000 0.000000 X( 1, 5) 0.000000 0.000000 X( 1, 6) 1.000000 0.000000 X( 2, 1) 0.000000 0.000000 X( 2, 2) 1.000000 0.000000 X( 2, 3) 0.000000 0.000000 X( 2, 4) 0.000000 0.000000 X( 2, 5) 0.000000 0.000000 X( 2, 6) 0.000000 0.000000 X( 3, 1) 0.000000 0.000000 X( 3, 2) 0.000000 0.000000 X( 3, 3) 0.000000 0.000000 X( 3, 4) 0.000000 0.000000 X( 3, 5) 0.000000 0.000000 X( 3, 6) 1.000000 0.000000 X( 4, 1) 0.000000 0.000000 X( 4, 2) 0.000000 0.000000 X( 4, 3) 0.000000 0.000000 X( 4, 4) 1.000000 0.000000 X( 4, 5) 0.000000 0.000000 X( 4, 6) 0.000000 0.000000 X( 5, 1) 0.000000 0.000000 X( 5, 2) 0.000000 0.000000 X( 5, 3) 0.000000 0.000000 X( 5, 4) 0.000000 0.000000 X( 5, 5) 1.000000 0.000000 X( 5, 6) 0.000000 0.000000 X( 6, 1) 1.000000 0.000000 X( 6, 2) 0.000000 0.000000 X( 6, 3) 0.000000 0.000000 X( 6, 4) 0.000000 0.000000 X( 6, 5) 0.000000 0.000000 X( 6, 6) 0.000000 0.000000 X( 7, 1) 0.000000 0.000000 X( 7, 2) 0.000000 0.000000 X( 7, 3) 0.000000 0.000000 X( 7, 4) 0.000000 0.000000 X( 7, 5) 1.000000 0.000000 X( 7, 6) 0.000000 0.000000 X( 8, 1) 1.000000 0.000000 X( 8, 2) 0.000000 0.000000 X( 8, 3) 0.000000 0.000000 X( 8, 4) 0.000000 0.000000 X( 8, 5) 0.000000 0.000000 X( 8, 6) 0.000000 0.000000 X( 9, 1) 0.000000 0.000000 X( 9, 2) 0.000000 0.000000 X( 9, 3) 0.000000 0.000000 X( 9, 4) 1.000000 0.000000 X( 9, 5) 0.000000 0.000000 X( 9, 6) 0.000000 0.000000 X( 10, 1) 0.000000 0.000000 X( 10, 2) 1.000000 0.000000 X( 10, 3) 0.000000 0.000000 X( 10, 4) 0.000000 0.000000 X( 10, 5) 0.000000 0.000000 X( 10, 6) 0.000000 0.000000 X( 11, 1) 0.000000 0.000000 X( 11, 2) 0.000000 0.000000 X( 11, 3) 1.000000 0.000000 X( 11, 4) 0.000000 0.000000 X( 11, 5) 0.000000 0.000000 X( 11, 6) 0.000000 0.000000 X( 12, 1) 0.000000 0.000000 X( 12, 2) 0.000000 0.000000 X( 12, 3) 0.000000 0.000000 X( 12, 4) 1.000000 0.000000 X( 12, 5) 0.000000 0.000000 X( 12, 6) 0.000000 0.000000 X( 13, 1) 0.000000 0.000000 X( 13, 2) 0.000000 0.000000 X( 13, 3) 1.000000 0.000000 X( 13, 4) 0.000000 0.000000 X( 13, 5) 0.000000 0.000000 X( 13, 6) 0.000000 0.000000 X( 14, 1) 0.000000 0.000000 X( 14, 2) 0.000000 0.000000 X( 14, 3) 1.000000 0.000000 X( 14, 4) 0.000000 0.000000 X( 14, 5) 0.000000 0.000000 X( 14, 6) 0.000000 0.000000 X( 15, 1) 0.000000 0.000000 X( 15, 2) 1.000000 0.000000 X( 15, 3) 0.000000 0.000000 X( 15, 4) 0.000000 0.000000 X( 15, 5) 0.000000 0.000000 X( 15, 6) 0.000000 0.000000 X( 16, 1) 0.000000 0.000000 X( 16, 2) 0.000000 0.000000 X( 16, 3) 0.000000 0.000000 X( 16, 4) 1.000000 0.000000 X( 16, 5) 0.000000 0.000000 X( 16, 6) 0.000000 0.000000 X( 17, 1) 0.000000 0.000000 X( 17, 2) 0.000000 0.000000 X( 17, 3) 0.000000 0.000000 X( 17, 4) 0.000000 0.000000 X( 17, 5) 1.000000 0.000000 X( 17, 6) 0.000000 0.000000 X( 18, 1) 1.000000 0.000000 X( 18, 2) 0.000000 0.000000 X( 18, 3) 0.000000 0.000000 X( 18, 4) 0.000000 0.000000 X( 18, 5) 0.000000 0.000000 X( 18, 6) 0.000000 0.000000 X( 19, 1) 1.000000 0.000000 X( 19, 2) 0.000000 0.000000 X( 19, 3) 0.000000 0.000000 X( 19, 4) 0.000000 0.000000 X( 19, 5) 0.000000 0.000000 X( 19, 6) 0.000000 0.000000 X( 20, 1) 0.000000 0.000000 X( 20, 2) 0.000000 0.000000 X( 20, 3) 0.000000 0.000000 X( 20, 4) 0.000000 0.000000 X( 20, 5) 0.000000 0.000000 X( 20, 6) 1.000000 0.000000 X( 21, 1) 0.000000 0.000000 X( 21, 2) 0.000000 0.000000 X( 21, 3) 1.000000 0.000000 X( 21, 4) 0.000000 0.000000 X( 21, 5) 0.000000 0.000000 X( 21, 6) 0.000000 0.000000 X( 22, 1) 0.000000 0.000000 X( 22, 2) 0.000000 0.000000 X( 22, 3) 0.000000 0.000000 X( 22, 4) 0.000000 0.000000 X( 22, 5) 0.000000 0.000000 X( 22, 6) 1.000000 0.000000 X( 23, 1) 0.000000 0.000000 X( 23, 2) 1.000000 0.000000 X( 23, 3) 0.000000 0.000000 X( 23, 4) 0.000000 0.000000 X( 23, 5) 0.000000 0.000000 X( 23, 6) 0.000000 0.000000 X( 24, 1) 0.000000 0.000000 X( 24, 2) 0.000000 0.000000 X( 24, 3) 0.000000 0.000000 X( 24, 4) 0.000000 0.000000 X( 24, 5) 1.000000 0.000000 X( 24, 6) 0.000000 0.000000附表二模型程序:model:sets:gongjian/1.24/:g,v;qu/1.6/:w;kuai/1.24/:;paisheng(gongjian,kuai):x;endsetsdata:g=348 352 347 349 347.5 347 330 329 329 327.5 329 331.5 348.5 347 346.5 348 347.5 348 333 330 332.5 331.5 331.5 332;!g=358.5357.5355351355.5357341342340344342.5343.5357.5355353.5356.5356352.5342.5344339.5341.5341345;v=101.5 102 105 105.5 106 104 94 98 100.5 98.5 98 99 104.5 105 107.5 104.5 104 104.5 97 97 99 98 96.5 94.5;!v=103103103103.51031029696.595.59795.196.5102.5103103.5103.5103.51049896.598969697;enddatamax=h/m;for(kuai(j): sum(gongjian(i):x(i,j)=1);for(gongjian(i): sum(kuai(j):x(i,j)=1);sum(kuai(j)|j#le#4: sum(gongjian(i):g(i)*x(i,j)=w(1);sum(kuai(j)|j#ge#5#and#j#le#8: sum(gongjian(i):g(i)*x(i,j)=w(2);sum(kuai(j)|j#ge#9#and#j#le#12: sum(gongjian(i):g(i)*x(i,j)=w(3);sum(kuai(j)|j#ge#13#and#j#le#16: sum(gongjian(i):g(i)*x(i,j)=w(4);sum(kuai(j)|j#ge#17#and#j#le#20: sum(gongjian(i):g(i)*x(i,j)=w(5);sum(kuai(j)|j#ge#21#a