零件装配优化问题(1).docVIP

零件装配优化问题 数学模型分析 [摘要] 本文研究了圆盘上19个零件优化排序的问题， 针对频率和质量要求建立了0-1规划模型，利用回溯法对模型进行了求解，利用剪枝条件简化了运算，并用递归调用将算法在编程上得以实现，在较短时间内求得了可行解。 本文建立的算法及模型具有通用性，可以在零件数目增多的情况下推广。 本文还对实际情况下某些不存在可行解的零件组进行了分析，便于实际中更换零件的需要。 [关键字] 0-1规划，NP难题，回溯，剪枝，递归 一、问题重述： 在航空工业特别是飞机工业制造中，由于零件具有一定的固有频率，相近频率相邻会产生强烈的共振，不仅产生噪音，而且影响整个装置的性能。因此要使零件间的干扰对装置正常工作影响较小，我们要合理安排零件的排序。 现有19个零件均匀装配在一个圆盘周围，每个零件具有一定的频率和质量，装配时要求满足以下条件： 相邻零件应具有频率差，且为一大一小分布。 相邻两零件频率差应不小于6Hz，允许在不相邻的三处，相邻零件频率差不小于4Hz。 整个圆盘上的配重值不大于10g，配重值计算公式为： 具体要求如下： a：设计满足上述要求的优化算法；并用所给的表中三组数据验证；表见附录[1]。 b：如果数据可做局部调整（可换一个零件），分析对装配效果的影响。 二、模型假设及说明： ⑴ 零件除重量和频率不同外，其余参数均相同。 ⑵ 零件在调整顺序前能够准确知道其重量和频率。 ⑶ 所要排列的一组零件存在符合要求的排列。0 ⑷ 按频率排序时，不考虑零件质量及其他因素的影响。 ⑸ 零件安装前后参数不变。 ⑹ 放在第一个位置上的零件比它相邻的两个零件频率大。由于圆盘上零件分布均匀，所以此假设对排序结果不造成影响。 合理性解释：为简化问题，突出主要矛盾，我们做出上述假设，以方便讨论。 三、符号说明： 四、问题分析及模型建立： 问题分析： 我们对题目提供的供验证的三组数据进行了分析，用于判断零件重量和频率之间的关系。应用Matlab绘制了三组数据的质量-频率折线图（图1）。 图1 由图，我们可以分析出频率与质量近似成线性关系。即大质量对应大频率，小质量对应小频率。每组的关系点都大体集中在对角区域。这种分布对我们的算法设计提供了导向作用。 在现有条件下，求全部可行解是不可能的，也是没有实际意义的。 初步来看，此问题是一个优化问题中的一类特殊的线性规划问题——指派问题，即一对一的问题。此类问题是经典的组合优化问题，属于NP难题，只有用穷举法才能找到在所定标准下的最优解。在现有条件下，当零件个数n=13时，用穷举法就不能求全部可行解。零件不同数目时在主频为800MHz的微机上运算所用时间时如图2所示 图2 零件数 5 10 11 12 13 14 时间s 1 105 1009 36049 468000 失效 因此，我们就根据对数据的分析建立一定的模型和算法，求出一部分可行解，并经过我们的比 较，找到比较合理的解。因此，我们用回溯法来寻找可行解。 我们将条件一和二综合考虑，.建立0-1规划模型用回溯法算法求可行解，由于回溯法的时间复杂度往往是问题规模的指数函数，因此对于规模稍大一些的问题往往有些力不从心，而合理的剪枝因为可以减少一些时间上的消耗就显得格外有意义，所以我们利用剪枝函数去掉许多“枝叶”，能够大大缩短有哪些信誉好的足球投注网站时间。 模型建立： 模型一： 圆盘上零件的次序排好后，每个零件都应占有一个确定的位置，即对于圆盘上某一确定位置来说，任意一个零件是否在此位置是确定的。 因此，可以引入0-1整数变量建立规划模型。“0”由于他在数学上的特性可以很好地代表“无”或“否”，而1可以很好地代表“有”或“是”。0-1变量一般可以表示为： 本问题可描述为： 首先将19个零件从1到19标号，设其频率依次为，质量为。 再将圆盘上从某一个位置开始的19个位置从1到19标号。 设有一个的矩阵，元素用表示。列数j表示圆盘上位置的序号，行数i表示零件的序号。其元素规定为： 由于每个确定的位置仅有一个零件，则有： 由于每一个零件仅有一个确定的位置，则有： 位置j 处零件的频率为： 位置j处零件的质量为： 由于要求相邻零件的频率差不小于6Hz，且为一大一小排列，且基于假设（6），第一个位置的零件频率大于它相邻的零件的频率，则： 由于要求整个圆盘配重值不大于10g，则： 注意到在这个模型中第19个位置上的零件与相邻零件不可能满足一大一小的要求。所以我们简化此模型，并利用题中条件在不相邻的三处，相邻零件频率差不小于4Hz,构造如下模型。 模型二： 每相邻两个零件的频率差至少应不小于4Hz；则： 允许有三处相邻零件的频率差不小于4Hz，但其余各处相邻零件间频率差应不小于6Hz。则： 由于频率差不小于4Hz的位置最多有三处