工件的安装与排序问题.doc

工件的安装与排序问题 王晓楠，崔超，陈涛 （中国矿业大学，徐州 221008） 摘要：本文首先深入分析了组合优化的特点，然后针对本题中设备对工件排血安装时的重量约束和体积约束的特点，就题目中提出几个问题分别设计了不同的算法，通过不同的算法的优劣的比较，不仅较好的解决了工件的排序安装问题，还得出了问题中算法设计的一些根据。 在问题1中，我们引入了贪心策略和自适应方法对搜索算法进行改进，大大减小了搜索的规模得到了一种效率和性能都不错的搜索算法，另外还针对数据的特点给出了一种操作简便的简化算法，通过两种算法的比较得出了一些有用的算法设计结论。在问题1的算法设计过程中我们还适当的引入了一些理论证明，使算法更加有说服力，最终通过MATLAB软件得出了令人满意的结果，有力的证明了算法的可行性。 在问题2中将问题1的算法进行综合，然后分别从不同的出发点提出了两种算法，一种是适用性较强但不易实现的解析算法，另一种针对数据特点的较简便的针对性算法，并比较了两种算法各自的适应性，简便的求出了第二组数据的排序结果，并得出第一组数据无解的结论。 问题3根据前面的结论，如果只考虑重量，分析了两种相临扇区总重量差最大的情况，通过数学分析得出工件调整幅度，如果还要考虑体积因素，通过对工件的贪心选择，不断修正工件重量和体积，筛选出满足条件的工件组合 。 我们在论文的最后还给出了模型的评价和推广。 一 问题重述 某设备由24个工件组成，安装时需要按工艺要求重新排序。 Ⅰ．设备的24个工件均匀分布在等分成六个扇形区域的一圆盘的边缘上，放在每个扇形区域的4个工件总重量与相邻区域的4个工件总重量之差不允许超过一定值（如4g）。 Ⅱ．工件的排序不仅要对重量差有一定的要求，还要满足体积的要求，即两相邻工件的体积差应尽量大，使得相邻工件体积差不小于一定值（如3）； Ⅲ．当工件确实不满足上述要求时，允许更换少量工件。 问题1．按重量排序算法； 问题2．按重量和体积排序算法； 问题3．当工件不满足要求时，指出所更换工件及新工件的重量和体积值范围，并输出排序结果。 请按下面两组工件数据（重量单位：g ，体积单位：），进行实时计算： 序号 重量 体积 序号 重量 体积 1 348 101.5 1 358.5 103 2 352 102 2 357.5 103 3 347 105 3 355 103 4 349 105.5 4 351 103.5 5 347.5 106 5 355.5 103 6 347 104 6 357 102 7 330 94 7 341 96 8 329 98 8 342 96.5 9 329 100.5 9 340 95.5 10 327.5 98.5 10 344 97 11 329 98 11 342.5 95.1 12 331.5 99 12 343.5 96.5 13 348.5 104.5 13 357.5 102.5 14 347 105 14 355 103 15 346.5 107.5 15 353.5 103.5 16 348 104.5 16 356.5 103.5 17 347.5 104 17 356 103.5 18 348 104.5 18 352.5 104 19 333 97 19 342.5 98 20 330 97 20 344 96.5 21 332.5 99 21 339.5 98 22 331.5 98 22 341.5 96 23 331.5 96.5 23 341 96 24 332 94.5 24 345 97 二 问题分析 本题要求给出一种算法对24个工件按重量和体积的约束条件进行组合和排序， 并安装到设备圆周的六个等分扇区上，每个扇区放置四个工件。相邻扇区的工件的重量之差不允许超过一定值，而相邻工件之间的体积差也要满足不小于一定值的约束。表面上看似乎算法只要算法能给出一组排序满足要求即可，不需要进行最优化，但是通过深入分析可知，由于数据可能并不理想，满足要求的可行解的集合可能很大，但也可能很小甚至并不存在，因此要提高算法的适应性就必须对排序的结果进行目标优化，使结果尽可能满足要求，而不是简单的给出一组可行解，这样我们就可以通过最优或极优可行解来验证是否可以找到可行方案。因此问题可变为如下的优化问题： 其中为一组排序方案，为所有可能排序的集合。由于每个位置上的工件只能从给定的24个工件中选，因此这是一种典型的组合优化问题。 问题1只要求考虑重量约束下的排序，是单目标组合优化问题。我们将目标函数定义为相邻扇区重量之差的最大值，寻找使该值最小的排序方案。 目前对于组合优化问题的解决方案主要有两种策略，一是对搜索算法进行改进，以减少搜索的时间复杂度，如禁忌