零件装配优化问题(1)

《零件装配优化问题(1)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、零件装配优化问题数学模型分析[摘要]本文研究了圆盘上19个零件优化排序的问题，针对频率和质量要求建立了0-1规划模型，利用回溯法对模型进行了求解，利用剪枝条件简化了运算，并用递归调用将算法在编程上得以实现，在较短时间内求得了可行解。本文建立的算法及模型具有通用性，可以在零件数目增多的情况下推广。本文还对实际情况下某些不存在可行解的零件组进行了分析，便于实际中更换零件的需要。[关键字]0-1规划，NP难题，回溯，剪枝，递归一、问题重述：在航空工业特别是飞机工业制造中，由于零件具有一定的固有频率，相近频率相邻会产生强烈的共

2、振，不仅产生噪音，而且影响整个装置的性能。因此要使零件间的干扰对装置正常工作影响较小，我们要合理安排零件的排序。现有19个零件均匀装配在一个圆盘周围，每个零件具有一定的频率和质量，装配时要求满足以下条件：1.相邻零件应具有频率差，且为一大一小分布。1.相邻两零件频率差应不小于6Hz，允许在不相邻的三处，相邻零件频率差不小于4Hz。2.整个圆盘上的配重值不大于10g，配重值计算公式为：具体要求如下：a：设计满足上述要求的优化算法；并用所给的表中三组数据验证；表见附录[1]。b：如果数据可做局部调整（可换一个零件），分析对

3、装配效果的影响。二、模型假设及说明：⑴零件除重量和频率不同外，其余参数均相同。⑵零件在调整顺序前能够准确知道其重量和频率。⑶所要排列的一组零件存在符合要求的排列。0⑷按频率排序时，不考虑零件质量及其他因素的影响。⑸零件安装前后参数不变。⑹放在第一个位置上的零件比它相邻的两个零件频率大。由于圆盘上零件分布均匀，所以此假设对排序结果不造成影响。合理性解释：为简化问题，突出主要矛盾，我们做出上述假设，以方便讨论。三、符号说明：四、问题分析及模型建立：l问题分析：我们对题目提供的供验证的三组数据进行了分析，用于判断零件重量和频

4、率之间的关系。应用Matlab绘制了三组数据的质量-频率折线图（图1）。图1由图，我们可以分析出频率与质量近似成线性关系。即大质量对应大频率，小质量对应小频率。每组的关系点都大体集中在对角区域。这种分布对我们的算法设计提供了导向作用。在现有条件下，求全部可行解是不可能的，也是没有实际意义的。初步来看，此问题是一个优化问题中的一类特殊的线性规划问题——指派问题，即一对一的问题。此类问题是经典的组合优化问题，属于NP难题，只有用穷举法才能找到在所定标准下的最优解。在现有条件下，当零件个数n>=13时，用穷举法就不能求全部可

5、行解。零件不同数目时在主频为800MHz的微机上运算所用时间时如图2所示图2零件数51011121314时间s<1105100936049468000失效因此，我们就根据对数据的分析建立一定的模型和算法，求出一部分可行解，并经过我们的比较，找到比较合理的解。因此，我们用回溯法来寻找可行解。我们将条件一和二综合考虑，.建立0-1规划模型用回溯法算法求可行解，由于回溯法的时间复杂度往往是问题规模的指数函数，因此对于规模稍大一些的问题往往有些力不从心，而合理的剪枝因为可以减少一些时间上的消耗就显得格外有意义，所以我们利用剪枝

6、函数去掉许多“枝叶”，能够大大缩短搜索时间。l模型建立：模型一：圆盘上零件的次序排好后，每个零件都应占有一个确定的位置，即对于圆盘上某一确定位置来说，任意一个零件是否在此位置是确定的。因此，可以引入0-1整数变量建立规划模型。“0”由于他在数学上的特性可以很好地代表“无”或“否”，而1可以很好地代表“有”或“是”。0-1变量一般可以表示为：本问题可描述为：首先将19个零件从1到19标号，设其频率依次为，质量为。再将圆盘上从某一个位置开始的19个位置从1到19标号。设有一个的矩阵，元素用表示。列数j表示圆盘上位置的序号，

7、行数i表示零件的序号。其元素规定为：由于每个确定的位置仅有一个零件，则有：由于每一个零件仅有一个确定的位置，则有：位置j处零件的频率为：位置j处零件的质量为：由于要求相邻零件的频率差不小于6Hz，且为一大一小排列，且基于假设（6），第一个位置的零件频率大于它相邻的零件的频率，则：由于要求整个圆盘配重值不大于10g，则：注意到在这个模型中第19个位置上的零件与相邻零件不可能满足一大一小的要求。所以我们简化此模型，并利用题中条件在不相邻的三处，相邻零件频率差不小于4Hz,构造如下模型。模型二：每相邻两个零件的频率差至少应不

8、小于4Hz；则：允许有三处相邻零件的频率差不小于4Hz，但其余各处相邻零件间频率差应不小于6Hz。则：由于频率差不小于4Hz的位置最多有三处，则：且：质量满足的条件同模型一，即：五、模型求解与优化l模型的求解：求解0-1规划问题，一般会想到穷举法。但就本题来说，则需对种排列方式进行一一验证。这几乎是不可能的。对于较大规模的0-1规