零件装配优化问题

1、课程论文题 目：零件装配优化问题数据模型分析课程：机械优化设计姓名：专业：机械设计制造及其自动化班 级：学号：指导教师：职称: 20012年12月10日零件装配优化问题数学模型分析作者：导师：摘要 本文研究了圆盘上19个零件优化排序的问题，针对频率和质量要求建立 了 0-1规划模型，利用回溯法对模型进行了求解，利用剪枝条件简化了运算，并 用递归调用将算法在编程上得以实现，在较短时间内求得了可行解。本文建立的 算法及模型具有通用性，可以在零件数目增多的情况下推广。本文还对实际情况 下某些不存在可行解的零件组进行了分析，便于实际中更换零件的需要。关键字 0-1规划，NP难题，回溯，剪枝，递归1问题

2、重述：在航空工业特别是飞机工业制造中，由于零件具有一定的固有频率，相近频率相 邻会产生强烈的共振，不仅产生噪音，而且影响整个装置的性能。因此要使零件 间的干扰对装置正常工作影响较小，我们要合理安排零件的排序。现有19个零件均匀装配在一个圆盘周围，每个零件具有一定的频率和质量，装 配时要求满足以下条件：1）相邻零件应具有频率差，且为一大一小分布。2）相邻两零件频率差应不小于6Hz，允许在不相邻的三处，相邻零件频率差不 小于4Hz。3）整个圆盘上的配重值不大于10g，配重值计算公式为：（360i/19 ） 2 + m sin（360i/19 ）iL i=1-具体要求如下: a：设计满足上述要求的优

3、化算法；并用所给的表中三组数据验证；表见附录1。b：如果数据可做局部调整（可换一个零件），分析对装配效果的影响。2模型假设及说明：1）零件除重量和频率不同外，其余参数均相同。2）零件在调整顺序前能够准确知道其重量和频率。3）所要排列的一组零件存在符合要求的排列。4）按频率排序时，不考虑零件质量及其他因素的影响。5）零件安装前后参数不变。6）放在第一个位置上的零件比它相邻的两个零件频率大。由于圆盘上零件分布 均匀，所以此假设对排序结果不造成影响。合理性解释：为简化问题，突出主要矛盾，我们做出上述假设，以方便讨论。3符号说明：f第i个零件的频率im.第i个零件的质量j矩阵i行j列的元素p整个圆盘的

4、配重值（衡量优化排序的一个标准）F圆盘第j个位置的零件的频率Mj圆盘第j个位置的零件的质量问题分析及模型建立：4.1问题分析：我们对题目提供的供验证的三组数据进行了分析，用于判断零件重量和频率之间的关系。应用Matlab绘制了三组数据的质量-频率折线图（图1）。由图，我们可以分 析出频率与质量近似 成线性关系。即大质量 对应大频率，小质量对 应小频率。每组的关系 点都大体集中在对角 区域。这种分布对我们 的算法设计提供了导 向作用。图1三组数据的质量-频率折线图在现有条件下，求全部可行解是不可能的，也是没有实际意义的。初步来看，此问题是一个优化问题中的一类特殊的线性规划问题指派问 题，即一对一

5、的问题。此类问题是经典的组合优化问题，属于NP难题，只有用 穷举法才能找到在所定标准下的最优解。在现有条件下，当零件个数n=13时， 用穷举法就不能求全部可行解。零件不同数目时在主频为800MHz的微机上运算所用时间时如图2所示:零件数51011121314时间s1105100936049468000失效图2时间表我们就根据对数据的分析建立一定的模型和算法，求出一部分可行解并经过比较 找到比较合理的解。因此，我们用回溯法来寻找可行解。我们将条件一和二综合考虑，建立0-1规划模型用回溯法算法求可行解，合理的 剪枝因为可以减少一些时间上的消耗就显得格外有意义，所以我们利用剪枝函数 去掉许多“枝叶”

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

7、示圆盘上位置的序号，行数 i表示零件的序号。其元素规定为：1标号为i的零件在圆盘第j个位置上x = 6 j = 1,2,.18 6 j = 19由于要求整个圆盘配重值不大于10g，则：p = J 艺 M cos (360i/19 ) 2 + 力 M sin (360i/19 ) 2 4 (j = 1,2,.,18 ) F1 -气 | 4 (j = 19 )允许有三处相邻零件的频率差不小于4Hz，但其余各处相邻零件间频率差应不小 于6Hz。则:-F +酉-气 | 16 x 6 + 3 x 4 = 108为F +1j=1由于频率差不小于4Hz的位置最多有三处，则:且：-F + F - F 10(J

8、 = 1,2,.,17 )j+1j +1jIf -f 1 + If -f | 10 (j = 18)1 1191918 1|F -F| + |F -F 10 (j = 18)21119MaxF - F 1 + |F -F I,11919181918If -Fl+If -f I.21119(j = 1,2,3,.,17 )F+2-fj+1质量满足的条件同模型一，即:fl M cos(360/19 )2 + M sin(360/19 ) 2 20时，进行步骤6；若不满足，则进行步骤5。5）i=i-1，在数组f20中未填入数组x20中的元素（除去fj）的元素中继 续搜索，进行步骤3。6）对满足频率要

9、求的可行解，用配重值函数进行筛选，若满足配重值要求， 则输出数组x20及元素原序号，并输出配重值。通过对附录1中的数据求解，我们对第二组和第三组数据求出了可行解。模型的推广与评价：6.1模型的推广：1）本文对19个零件进行了排序，此题中用到的模型和算法还可推广到更多 的零件排序的问题，在计算机运算许可范围内，前述模型具有通用性。2）本问题我们利用0-1规划建立了模型，并利用回溯法求得可行解。但我们的模型是在可行解存在的前提下提出的，实际情况下，某些零件组其 参数不存在可行解，因此需对某些参数进行调整。我们利用所编程序排序时也遇 到这样的情况。我们采用如下方法来解决这一问题，先弱化题设条件，排出

10、某些候选解，然 后观察哪些元素不符合题设条件，根据具体情况予以调整。如我们对第一组数据 的处理。7总结：本文综上所述的优点是对模型进行了合理的假设，抓住主要矛盾，忽略了次 要矛盾，利用0-1规划建立了模型，在短时间内得出了可行解。1）建立模型过程中，将条件合理地进行了综合和分类，为算法的进行创造了 有利条件，对解进行层层筛选，得出可行解。2）算法是关键所在，也是难点所在。对可行解搜索时，运用了回溯法和剪枝 法，比穷举法能大大缩短搜索时间。3）在编程过程中，我们利用递归调用实现了回溯算法，并利用所编程序对多 组数据列出可行解，并在此基础上进行了比较分析，对更换一个零件某一参数值对排序的影响进行了

11、研究。本模型缺点在于：1）不能求出最优解，只能求出符合条件的可行解；2）随着零件数的增加，计算时间逐渐让人无法忍受。参考文献何坚勇运筹学基础 清华大学出版社王谭浩强 C程序设计（第二版） 清华大学出版社岩冰郑明春刘弘回溯算法的形式模型计算机研究与发展第38卷第 19 期 TP301.6 TP18戴义平江才俊卢世明基于遗传算法的叶片安装排序优化系统的开发 及应用 汽轮机技术第45卷第5期 TK268.+3 TP301.6附录附录1序号频率Hz质量g序号频率Hz质量g序号频率Hz质量g111170196391963221086521003221139031128631086231065941003249810496275102505110595100486100366983269641799107982079625810667810874810555998269110499112