工件的安装与排序问题
摘要
工件在安装时需要按工艺要求进行排序，在实践中具有一定的意义。本文讨论的是工件在安装时按重量排序、按重量和，以及在工件不满足要求时，怎样更换工件及求出新工件的重量和体积值范围。
问题一要求按重量排序，而且相邻区域的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 ，体积单位： ），进行实时计算：
序号 重量 1 2 3 4 5 6 体积 348 352 347 349 347.5 347 序号 重量 102 105 105.5 106 104 体积 103 103 103 103.5 103 102 101.5 1 358.5 2 357.5 3 4 6 355 351 357 5 355.5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
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 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 7 8 9 10 341 342 340 344 96 96.5 95.5 97 95.1 96.5 102.5 103 103.5 103.5 103.5 104 98 96.5 98 96 96 97 11 342.5 12 343.5 13 357.5 14 355 15 353.5 16 356.5 17 356 18 352.5 19 342.5 20 344 21 339.5 22 341.5 23 24 341 345 二、问题假设
1、所给的24 个工件的重量在某范围内，相差不大，不会出现很重或很轻的工件
2、圆盘足够大，每个扇形区域内的工件重量无论多大，均能放在扇形区域内，不会影响其他区域的重量
3、存在重量相同但体积不同的工件和体积相同但重量不同的工件供我们更换
三、变量说明
1、gi—第i个工件的重量
2、wj—第j个扇形区工件的总重量 3、vi—未经过排序的第i个工件的体积 4、V′j—已经过排序的第j个工件的体积 5、ε—相邻扇区质量和之差的要求范围 6、γ—相邻工件体积之差的要求范围
四、问题分析
分析问题一：
我们通过0-1规划来选择哪个工件应该分配在哪个区，并且每个区分配4个工件，每个工件只能选一次，不能重复选。题意要求相邻区域的4个工件总重量之差不允许超过一定值，我们假设这个值为m，我们可以知道m?
1
×（4个最重工件的重量之和 — 4个最轻工件3
的重量之和），即m?27.6。而且我们通过数据表格分析可知，所以数据都是0.5的倍数，所以m最小不能小于0.5g,即m?0.5。为了得出最佳分配方案，我们以求m的最小值为目
标函数建立模型Ⅰ。
分析问题二：
在问题一中按重量排序可以求得每个扇形区域所含的4个工件，但4个工件的顺序并没有确定，可能不满足按体积的排序。所以为了解决问题二，我们将圆盘分成24块区域，并且使相邻的4块构成一个扇形区域。用0-1规划选择第i个工件放在第j块区域，且第i个工件只能放在1块区域里，1块区域只能放一个工件；同时默认第1块区域到第4块区域构成第一个扇形区域，依次可得到第二、三、四、五、六块扇形区域。再根据重量和体积排序算法确定24个工件的具体放法。 分析问题三：
明确不满足的情况有两大种：
（1）只考虑重量时，不满足重量的要求
（2）综合考虑重量和体积时，分为以下3 种：
?当相邻工件的体积满足要求时,重量不能满足要求? ?当相邻工件的重量满足要求时,体积不能满足要求?重量和体积都不满足要求?
五、模型建立与求解
问题一
1, 第i个工件放在第j个扇形区为解决问题一，我们引入xij：xij?{0, 第i个工件不放在第j个扇形区
建立模型Ⅰ 目标函数:min=m 约束条件：wj??g×xii?124ij
w(j?1)?wj?m，j??1,5?
w6?w1?m
?Xi=124ij?4
?Xj=16ij?1
0.5?m?27.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 约束条件：
?Xi=124ij?1
?Xj=124424ij?1
??gxi=12418iij?w1
??gxi=15iij?w2
??gxi=1249162412iij?w3
??gxi=11324iij?w4
??gxi=117242420iij?w5
??gxi=121iij?w6
w(j?1)?wj?m，j??1,5?
w6?w1?m v'j=?vixij
i?124v'j+1-v'j?h,j??1，,23?
v'24-v'1?h
0.5?m?27.6 h?13.5
运用数学软件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)需满足：
??j?1?－w?j?|???|wˊ ? ? ?|wˊj?1－wj?2|????????解得：
??j?1??w?j????w?j????wˊ ?wj+2???wˊj?1?wj+2??????????即：maxw?j???,w?j+2?????wˊ?j?1??minw?j???,w?j+2??? 令μ= gˊ(j+1) －g(j+1)
则μ的范围：
???max?w?j???,w?j+2?????w?j?1??μ?min?w?j???,w?j+2?????w?j?1?
设新工件的重量为w′=μ+w， 所以新工件的重量范围为：