零件装配优化问题(1)

《零件装配优化问题(1)》由会员分享，可在线阅读，更多相关《零件装配优化问题(1)（19页珍藏版）》请在金锄头文库上搜索。

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

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

3、对装配效果的影响。二、模型假设及说明：二、模型假设及说明： 零件除重量和频率不同外，其余参数均相同。 零件在调整顺序前能够准确知道其重量和频率。 所要排列的一组零件存在符合要求的排列。0 按频率排序时，不考虑零件质量及其他因素的影响。 零件安装前后参数不变。 放在第一个位置上的零件比它相邻的两个零件频率大。由于圆盘上零件分布均匀，所以此假设对排序结果不造成影响。合理性解释：为简化问题，突出主要矛盾，我们做出上述假设，以方便讨论。三、符号说明：三、符号说明：iif第个零件的频率iim第个零件的质量jijxi矩阵行列的元素p整个圆盘的配重值（衡量优化排序的一个标准）jF圆盘第j个位置的零件的频率j

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

5、用穷举法才能找到在所定标准下的最优解。在现有条件下，当零件个数 n=13 时，用穷举法就不能求全部可行解。零件不同数目时在主频为 800MHz 的微机上运算所用时间时如图2 所示图图 2 2零件数51011121314时间 s20 时，进行步骤 6；若不满足，则进行步骤 5。5. i=i-1，在数组 f20中未填入数组 x20中的元素（除去 fj）的元素中继续搜索，进行步骤 3。6. 对满足频率要求的可行解，用配重值函数进行筛选，若满足配重值要求，则输出数组 x20及元素原序号，并输出配重值。通过对附录1中的数据求解，我们对第二组和第三组数据求出了可行解。第二组，第三组存在的一个可行解的排列结

6、果见图 4，图 5。第一组：通过程序的运行，本组数据没有符合条件的可行解，我们不妨将第 19 元素频率由 101 换为 107，则换后的这组数据有满足题设条件的可行解。其排列结果如图 6 所示：图图 4位置零件序号质量频率116211222329633901134442975559106662796774810088419691055105109259611116011212124997131482108141320971516841111615459617174711018186297191962108配重值6.7949图图 58.1523图图 6位置零件序号质量频率114911022109

7、8335911044399855591086659879621088739969832100101516961112741081210329813168010814112098151760109161129817135210718183098191437102配重值8位置零件序号质量频率11701112432100326510845501025386112663610078671068710999137110910926981110351021211169713159210914129310015162011316143899171766109181827100191966107配重值7.96

8、18六、模型的推广与评价：六、模型的推广与评价： 模型的推广：模型的推广：1. 本文对 19 个零件进行了排序，此题中用到的模型和算法还可推广到更多的零件排序的问题，在计算机运算许可范围内，前述模型具有通用性。2. 本问题我们利用 0-1 规划建立了模型，并利用回溯法求得可行解。但我们的模型是在可行解存在的前提下提出的，实际情况下，某些零件组其参数不存在可行解，因此需对某些参数进行调整。我们利用所编程序排序时也遇到这样的情况。我们采用如下方法来解决这一问题，先弱化题设条件，排出某些候选解，然后观察哪些元素不符合题设条件，根据具体情况予以调整。如我们对第一组数据的处理。本模型的优缺点本模型的优缺

9、点：本文的优点是对模型进行了合理的假设，抓住主要矛盾，忽略了次要矛盾，利用 0-1 规划建立了模型，在短时间内得出了可行解。1) 建立模型过程中，将条件合理地进行了综合和分类，为算法的进行创造了有利条件，对解进行层层筛选，得出可行解。2) 算法是关键所在，也是难点所在。对可行解搜索时，运用了回溯法和剪枝法，比穷举法能大大缩短搜索时间。3) 在编程过程中，我们利用递归调用实现了回溯算法，并利用所编程序对多组数据列出可行解，并在此基础上进行了比较分析，对更换一个零件某一参数值对排序的影响进行了研究。本模型缺点在于：1) 不能求出最优解 ，只能求出符合条件的可行解；2) 随着零件数的增加，计算时间逐

10、渐让人无法忍受。七、参考文献七、参考文献：1. 何坚勇 运筹学基础 清华大学出版社2. 王谭浩强 C 程序设计 （第二版） 清华大学出版社3. 岩冰 郑明春 刘弘 回溯算法的形式模型 计算机研究与发展第 38 卷第 19 期 TP301.6 TP18 4. 戴义平 江才俊 卢世明 基于遗传算法的叶片安装排序优化系统的开发及应用 汽轮机技术第 45 卷第 5 期 TK268.+3 TP301.6八、附录八、附录：附录1 序号频率Hz质量g 序号频率Hz质量g序号频率Hz质量 g111170196391963221086521003221139031128631086231065941003249

11、8104962751025051105951004861003669832696417991079820796258106678108748105559982691104991126310 102351098510974211 971611981211972512 1002012983012974913 10971139616131086014 9938141088014962015 109931510960151126216 113721610752161118217 109661710859171108418 1002718983918974519 1016619102371910847附

12、录2 源程序清单fillin.c（运行环境 Windows XP，Microsoft VC+ 6.0）#include#include#define N 19void fillin(int); / 递归调用的函数int isvalid(int,int); / 判断有效性int multiply(int); void pweight(void); / 计算配重值int fN+1=0,111,108,112,100,102,100,99,106,98,102,97,100,109,99,109,113,109,100,101; / 待排序的零件频率，f0不计入在内int mN+1=0,70,65,

13、85,32,50,36,10,67,26,35,16,20,71,38,93,72,66,27,66; / 待排序的零件质量，m0不计入在内int vN+1; / 记录已排入的零件的序号,初始化为 0int xN+1; / 排好的零件频率void main(void) int k;for(k=1;kN)pweight();printf(“n“);for(k=1;k=4):0)xi=fj;vi=j;fillin(i+1);elsecontinue;int isvalid(int i,int j)int k=0;if(multiply(i)*(xi-1-fj)=4)for(k=1;kN)return 1;else return 0;int multiply(int k)int i,sum=1;for(i=1;i=k;i+)sum*=(-1);return sum;void pweight(void)double p1=0.0,p2=0.0;int i;for(i=1;i=N;i+)p1+=mvi*cos(i*360.0/N);p2+=mvi*sin(i*360.0/N);printf(“%.4f“,sqrt(p1*p1+p2*p2);