《工件的安装与排序问题.doc》由会员分享，可在线阅读，更多相关《工件的安装与排序问题.doc（21页珍藏版）》请在金锄头文库上搜索。
1、工件的安装与排序问题王晓楠，崔超，陈涛（中国矿业大学，徐州 221008）摘要：本文首先深入分析了组合优化的特点，然后针对本题中设备对工件排血安装时的重量约束和体积约束的特点，就题目中提出几个问题分别设计了不同的算法，通过不同的算法的优劣的比较，不仅较好的解决了工件的排序安装问题，还得出了问题中算法设计的一些根据。在问题1中，我们引入了贪心策略和自适应方法对搜索算法进行改进，大大减小了搜索的规模得到了一种效率和性能都不错的搜索算法，另外还针对数据的特点给出了一种操作简便的简化算法，通过两种算法的比较得出了一些有用的算法设计结论。在问题1的算法设计过程中我们还适当的引入了一些理论证明，使算法更加
2、有说服力，最终通过MATLAB软件得出了令人满意的结果，有力的证明了算法的可行性。在问题2中将问题1的算法进行综合，然后分别从不同的出发点提出了两种算法，一种是适用性较强但不易实现的解析算法，另一种针对数据特点的较简便的针对性算法，并比较了两种算法各自的适应性，简便的求出了第二组数据的排序结果，并得出第一组数据无解的结论。问题3根据前面的结论，如果只考虑重量，分析了两种相临扇区总重量差最大的情况，通过数学分析得出工件调整幅度，如果还要考虑体积因素，通过对工件的贪心选择，不断修正工件重量和体积，筛选出满足条件的工件组合 。我们在论文的最后还给出了模型的评价和推广。一 问题重述某设备由24个工件组
3、成，安装时需要按工艺要求重新排序。设备的24个工件均匀分布在等分成六个扇形区域的一圆盘的边缘上，放在每个扇形区域的4个工件总重量与相邻区域的4个工件总重量之差不允许超过一定值（如4g）。工件的排序不仅要对重量差有一定的要求，还要满足体积的要求，即两相邻工件的体积差应尽量大，使得相邻工件体积差不小于一定值（如3）；当工件确实不满足上述要求时，允许更换少量工件。问题1按重量排序算法；问题2按重量和体积排序算法；问题3当工件不满足要求时，指出所更换工件及新工件的重量和体积值范围，并输出排序结果。请按下面两组工件数据（重量单位：g ，体积单位：），进行实时计算：序号重量体积序号重量体积1348101.
4、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.518348
5、104.518352.5104193339719342.59820330972034496.521332.59921339.59822331.59822341.59623331.596.523341962433294.52434597二 问题分析本题要求给出一种算法对24个工件按重量和体积的约束条件进行组合和排序， 并安装到设备圆周的六个等分扇区上，每个扇区放置四个工件。相邻扇区的工件的重量之差不允许超过一定值，而相邻工件之间的体积差也要满足不小于一定值的约束。表面上看似乎算法只要算法能给出一组排序满足要求即可，不需要进行最优化，但是通过深入分析可知，由于数据可能并不理想，满足要求的可行解的集
6、合可能很大，但也可能很小甚至并不存在，因此要提高算法的适应性就必须对排序的结果进行目标优化，使结果尽可能满足要求，而不是简单的给出一组可行解，这样我们就可以通过最优或极优可行解来验证是否可以找到可行方案。因此问题可变为如下的优化问题：其中为一组排序方案，为所有可能排序的集合。由于每个位置上的工件只能从给定的24个工件中选，因此这是一种典型的组合优化问题。问题1只要求考虑重量约束下的排序，是单目标组合优化问题。我们将目标函数定义为相邻扇区重量之差的最大值，寻找使该值最小的排序方案。目前对于组合优化问题的解决方案主要有两种策略，一是对搜索算法进行改进，以减少搜索的时间复杂度，如禁忌搜索算法；另一种
7、是利用遗传算法、模拟退火算法等概率算法计算最优解。本问题所有可能的排序共有种，我们选择第一种方法，引入贪心策略通过搜索近似最优解以大降低搜索的复杂度，然后在保证算法结果不会恶化的前提下逐渐简化算法，提高算法的效率。问题2既要求满足重量约束又要求满足体积约束，是多目标优化问题，由于重量与体积之间相互并不一定有太大关联，因此若数据不理想而两者又要同时满足可能是非常困难的。我们的解决办法从满足体积约束的排序方案中进行选择，找出最满足重量要求的可行方案，即把对体积的要求作为一项约束条件，按重量目标优化。当然也可以把重量作为约束条件，按体积目标优化，但是由于体积的优化牵扯到了NP-C问题，我们采用前一种
8、解决方案。问题3是在不满足前两个问题的情况下对个别工件进行调整，当工件不满足要求时，允许更换少量的数据。根据前面解决问题的算法可以得出两种修改策略：一是按重量排序；二是按重量和体积排序。针对问题一：根据问题一证明，使平均值是在不断自我修整的，后面扇区的工件总重量最大可能接近前面扇区的总重量，但由于本设备的形状是一个圆盘，第六个扇区与第一个扇区相临，此时第六个扇区总重量和第一个扇区总质量之差是累计误差最大的。三 模型的基本假设1. 圆盘被均匀分成六个扇形区域，每个区域是固定划分的，工件是按照一定顺序安装到各个位置上去的。2. 问题1中各扇区内工件的可以随便排列，只要工件相同都算是同一排列。四 符
9、号说明： 扇区的工件总重量： 扇区的工件平均重量： 所有工件的平均重量： 扇区和扇区的工件总重量之差，其中扇区和扇区相邻： 相邻区域工件总重量之差允许的最大值： 位置处的工件体积： 位置与位置处的体积之差，位置与位置相邻： 相邻位置处的工件体积之差所允许的最小值： 工件的全排序集： 一组排序方案： 工件总集： 算法第步操作后的剩余可选工件集：剩余可选工件集中工件的平均重量： 工件五 模型的建立和求解问题1：模型的建立：1) 理论说明：首先建立组合优化的模型，前面的分析中已经说明，我们采用的目标函数为相邻扇区重量之差的最大值，寻找一组排序方案使这个值最小，即 （1）其中：，为第个扇区的所有可能的
10、工件组合的质量。若使用完全搜索算法，则总共需要搜索个结果，这显然代价太高昂了，所以有必要对搜索算法进行改进。目标函数要求相邻扇区的工件总重量之差的最大值尽可能小，由于工件摆放在设备的圆周上，易知沿某一固定方向（如顺时针）相邻扇区的工件总重量差不能一直递增或递减，而应保持有增有减的趋势才可能满足题目要求的重量约束条件，因此对这一目标进行优化得到的各扇区的工件总重量相对而言一定比较接近且一定在所有工件重量的平均值附近，针对目标函数的这一要求，我们可以对目标函数进行转化，将目标函数转换为： （2）通过分析可知目标函数（2）的要求比目标函数（1）的要求要强，即满足目标函数（2）一定能满足目标函数（1）
11、，也就是说目标函数（2）对目标函数（1）具有充分性。当然这里只是从直观的角度去分析的，下面将给出理论上的严格说明。我们对24个工件进行排序，假设找到一组排序，设每个扇形区域的总重量分别为、，为了使每个扇形区域的工件总重量与相邻区域的工件总重量之差尽可能的小，使其满足不超过一个定值（如4），这就要求、尽量的相等，既接近算术平均值4。如果我们从24个工件中找到这组排序，使每个扇区的重量分别为、即最接近算术平均值4的一组排序，而它们当中却有两个相邻扇形区域的总重量超过一定值（如4），即不满足重量条件，则可得出：这24个工件无论怎么排序都不能满足每个扇形区域的四个工件总重量与相邻区域的四个工件总重量之
12、差不允许超过一定值（4）这个条件。下面来证明我们的结论：结论一：如果从24个工件中找到一种排序，使每个扇区4个工件的总重量、尽量相等，即等于所有工件重量的算术平均值4，则每个扇形区域的工件总重量与相邻区域的工件总重量之差的和最小，同时也使相邻两个扇形区域的总重量之差的最大值最小，即这种排序为最优排序。证明：假设存在另外一种排序，在六个扇形区域重量的排序为、，其中 则相邻扇形区域的重量差为：我们知道对于不等式，当时取等号，故：当时，取最小值。同理、也能取最小值。由于、离散取值，由条件可知每个扇区的总重量近似相等，即、，此时、；又由于，所以此时这样就证明了此排序使每个扇形区域的工件总重量与相邻区域
13、的工件总重量之差的和最小，同时也使相邻两个扇形区域的总重量之差的最大值最小，即这种排序为最优排序。结论二：如果找到一种排序，使每个扇形区域的四个工件的总重量尽量相等，即接近于4，而这种排序不满足重量的约束要求，即不能使所有相邻扇形区域的重量差小于一定的值（4），则得出结论：这24个工件无论怎么样排序，都不能满足重量要求。根据结论一，我们得到了这种排序即每个扇区四个工件总重量尽量等于4是最优排序，使相邻两个扇形区域的总重量之差的最大值最小，如果这种最优排序都不满足要求，则其它的排序一定不满足要求。2) 算法设计：如何找到这种排序，使每个扇形区域的四个工件总重量尽量相等，即等于4。此类问题是典型的
14、组合优化问题。为了解决这一问题，我们可以对完全搜索算法进行改进，通过在搜索算法中引入贪心策略，将较大的搜索空间分为几个小的搜索空间，可以大大减小搜索规模而搜索的结果不会恶化，即至少仍可以得到一组近似最优解甚至是全局最优解。算法一：引入贪心策略的搜索算法算法步骤：Step1：初始化。求出24个工件的平均值，给出初始可选工件集合。Step2：从可选的工件集中选出四个工件，选取原则为工件组合的重量平均值最接近于。Step3：从初始可选工件集中去掉已选择的4个工件，得到剩余可选工件集，之后有两种操作方法：一种方案是用代替重复进行Step2，直至工件选完全部安装到设备上，标准重量平均值始终用，我们称之为固定平均值法；另一方案是求出剩余可选工件集中工件的平均重量，用、代替和，重复进行Step2，直到工件选完全部安装到设备上算法结束，标准重量平均值用剩余可选工件集的平均重量，这种称为自适应平均值法。引入贪心策略后，搜索算法的规模为，主要由前两项决定，同完全搜索算法的规模相比计算式中的各部分由相乘变为相加，规模大为降低，这使得计算机求解变得不仅可行而且十分简便快捷。至于结果是否合理我们将在模型求解中讨论。这里之所以采用贪心策略，是考虑到由于工件数较多，
