叶片排序论文

《叶片排序论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

压气机叶片排序问题摘要本文考虑压气机叶片重量及频率的差异，结合实际情况，给出不同约束条件下的叶片安排模型，并给出相应的叶片安排方案。对于问题一，本文以动态规划模型为基础，将所冇叶片分为4组，分4个阶段分配给每个象限，使每次分配后相邻象限质量差的总和最小。每阶段选取5组较优解，作为下阶段的初始状态。在最终得到的625组结果中选取较优解。利用该模型为第一组叶片排序，得到的相邻象限质量差的最大值为lg,质量差的总和分别为2go对于问题二，本文在问题一结果的基础上，加入了频率限制条件。利用模拟退火的改进算法，对问题一的结呆进行优化，得到了满足重量、频率限制条件的基本可行解。随后，采用局部搜索方法对基本可行解进一步优化，得到符合题意的较优解。对于问题三，本文考虑到应尽量减少更换叶片数量，首先建立了调整区判别模型，优先更换质量调整区与频率调整区交汇处的叶片，对需要更换的叶片实现了定位。随后，建立了叶片更换模型，分别考虑质量与频率约束条件，使调整区逐步扩大，直到使相邻象限的质量差与相邻叶片的频率差满足要求，并给出了质量和频率的调整范围。对于问题四，本文依次利用动态规划模型、模拟退火模型与叶片更换模型，得到了两组叶片的合理排序。相邻彖限质量差的总和均为2g,相邻叶片频率差的总和分别为336Hz、316Hz。最后，本文给出了模型的评价与推广。关键字：动态规划模拟退火局部搜索叶片更换 一、问题重述由于加工出的压气机叶片的重量和频率不同，安装吋需要按工艺要求重新排序。（1）压气机24片叶片均匀分布在一圆盘边上，分成六个象限，每彖限4片叶片的总重量与相邻象限4片叶片的总重量Z茅不允许超过一定值（如8g）o（2）叶片排序不仅要保证重量差，还要满足频率要求，两相邻叶片频率差尽量大，使相邻叶片频率差不小于一定值（如6Hz）o（3）当叶片确实不满足上述要求时，允许更换少量叶片。请按上述要求给出：（1）按重量排序算法；（2）按重量和频率排序算法；（3）叶片不满足要求吋，指出所更换叶片及新叶片的重量和频率值范围；（4）当叶片保证了重量差和频率差时，安排列顺序输出。二、问题分析加工出的不同的压气机叶片具有不同的重量和频率，利用这些叶片安装压气机时需耍符合一定的条件，从而满足工业耍求。对于问题一，题目耍求在满足相邻象限重量差不大于某一定值的条件下给出相应的排序算法。将重量差条件作为约束条件，问题一即可转化为寻找符合约束条件的解集。可以以重量差为基础构造口标函数，从而将问题一•转化为最优化问题。本文考虑以动态规划思想为基础，将24个叶片分组、分阶段分配给压气机圆盘的6个彖限，每个决策阶段只需在之前的已定初始状态基础上进行叶片分配。对于问题二，本问需同时考虑相邻象限重量差不大于某一定值、相邻叶片频率差不小于某一定值的限制条件，在此基础上给出叶片分配方案。因为重量差与频率差所针对的研究对象不同，分别为象限和单个叶片，所以如果仍然沿用问题一的动态规划思想，则在叶片分组分配时会冇很大的困难。考虑到模拟退火算法较Z其他算法在搜索全局最优解方面的优势，木文首先采用模拟退火算法，并在英基础上加以改进使得运算量得到大幅度减少，得到寻找可行解的改进模拟退火算法；而后以可行解为初始解利用局部搜索方法寻找符合条件的较优解。 对于问题三，曲于涉及到质量和频率两方面的调整，为了使更换的叶片最少,应尽可能使被更换的叶片位于质量调整区和频率调整区的交汇处。对于质量的调整，应先确定调整的象限数，若调整当前象限无法满足要求，再扩大象限数。确定所调整的象限后，根据临近的彖限质量确定质量调整范围。频率调整方法与此类似。对于问题四，利用上述建立的模型，可对两组叶片分别给出合理排序。三、模型假设1•假设叶片的性能足够好，不会因磨损而改变质量和频率等参数。2•假设任意规格的叶片都可生产出。符号说明符号符号含义bi第i个叶片(i=l,2・・・23,24)第i个叶片的重量z第i个叶片的频率N优化系数sj状态变量（匸0丄2,3,4）第k个象限(61,2,3,4,5,6)mqk第k个象限的总重量fm相邻象限重量渥允许最大值tf相邻叶片频率差允许最小值 五、模型的建立与求解5.1模型一：质量排序模型5.1.1问题分析本题共有24个叶片需要安排，若用普通的动态规划方法解决此问题，相当于穷举所有情况后比较口标函数并从屮选取最优解，运算量过大；若采用遗传算法或模拟退火算法，虽然算法可以实现，但其作为启发式算法运算量依然过大。为了减少运算量，提高算法运行效率，考虑到穷举法运算量是成指数形式增长的,木文将叶片分组、分阶段进行象限分配，从而避免了指数型增长所形成的巨大运算量。以每次给每个象限分配一个叶片为标准，可以将24个叶片分为4组，每组6个叶片。挑选一组叶片分配给6个象限时，共有C；xC：xA；=60种分配方案。若将每种分配方案均保留下來作为下一个决策阶段的初始状态，则运算量依然成指数形式增长，当到达最后状态时约有604«1.2x107种情况。考虑到动态规划方法每次决策前的状态均为最优状态，本题设计算法时可以考虑对每次决策进行评价，从每次决策后的状态中选取一部分符合约束条件11目标函数值较优的状态作为下一决策阶段前的初始状态，依此类推，在最终的状态屮寻找较优解。故用动态规划的方法解决问题一，其基本思想为：将叶片分组，毎个决策阶段挑出一组叶片分配给压气机圆盘的每个象限，每个彖限分配一个叶片；分配Z后，此时可将圆盘象限包含叶片的情况作为动态规划的一个状态，从这些状态中挑选最符合廿标函数及约束条件的若干状态作为此时的最优分配策略，继而挑选下一组叶片进行下一步的决策；依此类推，直到所有叶片分配完，每个象限具有4个叶片时，在分配结果中选取较优解。5.1.2模型建立(1)建立口标函数。由于问题一只需考虑相邻象限叶片重量差不大于某一定值，设,77(5.)为平衡 度（各象限重量差Z和），本文建立目标函数如下：m（SJ）=|m.l-mg2|+m,2-m（i3|+•••+|m.5-m,6+m,6-（口）（2）叶片分组，确定组间分配次序。将24个叶片按重量由小到大排列,得到加2$…优2优3方24的叶片排序（加］/（5）116g,无论怎样调整B彖限的质量，也无法同吋满足^Mab<8g、AAlpc§8g，此吋转SteP2.若AM祀M16g,口J修改B象限的质量，使得AMAB<8g且AM肚W8g。令该象限中被更换叶片的质量为加o,其余三片叶片的质量之和为刈。当M+MM+M叭<爲c时,更换最轻叶片；当Mr>爲c时，更换最重叶片。B象限可取的质量范围为&Mb+8],则新叶片可取的质量范围为[Ma-a+8—TWj]A[Mb—S——,频率值与原叶片相同。Step2令修改范围为C象限。 判断AM眈是否大于16g。若AMfiD>16g,无论怎样调整C象限的质量，也无法同吋满足酗兀三龙、AMCD24g,无论怎样调整B、C象限的质量,也无法满足要求。说明不仅仅是B、C象限的问题，应对邻近的A、D象限进行检杳,此时转Stcp4.若AM初<24g，可调整B、C象限的质量，使得MAB.W5C、AMg均小于8g。B象限可取的质量范围如图3.5阴彩部分所示，4-8AD-16A+3A+16D2+8图3.5B彖限取值范围示意图其表达式为［Md-6,Ma+8］,则新叶片可取的质量范围为［MD-6-m},MA4-8-mJ。C象限中新叶片可取的质量范围为［Mb-8-+8-“］n［M“-8-+8-“］。Step4令修改范围为A、B象限。判断Mec是否大于24g。若AMEC>24g,无论怎样调整A、B象限的质量，也无法满足要求，此吋转Step5.若AA/Ec<24g,可调整A、B象限的质量，使得AMea.AMab.血bc均小于农。新叶片的取值原则与Step3相同。Step5令修改范围为A、B.C象限。判断汕。是否大于32g。若AMED>32g,无论怎样调整A、B、C象限的 质量，也无法满足要求，此吋转Step6.若酗血＜32&,可调整A、B、C象限的质量，使AM嘲、酗眈、凶cd均小于鬼。新叶片的取值原则与Step3相同。Step6令修改范围为C、D象限。若仍无法满足题意，令修改范围为氏C、D象限，依次类推。可以看出，该算法的原则为：逐步扩大质量调整区的彖限数，直到各彖限间的质量羌均满足条件。事实上，曲于本题中的轮盘被划分为6个象限，且为圆盘形排列，如图3.6所示 图3.6象限划分图当质量调整区扩大到B、C彖限时，已无需再扩大。可以看出，由于Me、酗仙均小于或等于故＜24go因此质量调整区限制在B、C象限内。2.频率调整算法频率调整算法与质量调整算法类似，只需将调整范围由象限改为叶片，将约束条件由质量改为频率。5.4问题四利用模型一、模型二所给算法对题目所给两组数据进行求解，可得以下结果：数据一的计算结果为：表4.1数据一•叶片排列顺序位置编号123456789101112叶片编号2413115818231732117位置编号131415161718192021222324叶片编号22612141016194915202各项指标值为为：表4.2数据一求解结果各项指标值频率差最小值重量差最犬值重量差之和频率差之和12336数据一的计算结果为：表4.3数据二叶片排列顺序位置编号123456789101112叶片编号8171937222523152016位置编号131415161718192021222324叶片编号91810111624421141213各项指标值为：表4.4数据二求解结果各项指标值 频率差最小值重量差最大值重量差之和频率差之和1012316六、模型的评价与推广模型优点:1.本文建立了动态规划的改进算法，每一阶段选取五组较优解作为下一阶段的初始状态，在保证了算法合理性的同时，降低了算法复杂度。2.本文利用模拟退火算法得;II基本初始可行解后，利用局部搜索法对所得结果进行优化，有效提高了算法效率。模型缺点:本文建立的排序模型只考虑到叶片的质量与频率约束条件，未考虑摩擦、压气机的工作环境等因素。 模型推广：本文建立的叶片排序及更换模型，可应用于机械工程中的零件配对、齿轮配对等领域，对于损坏零件的更换选择亦冇较大帮助。七、参考文献［1］、何坚勇，最优化方法［M］,北京：清华大学出版社，2007o［2］、熊义杰，运筹学教程［M］,北京：国防工业出版社，2004。［3］、绑学军，周凯，宋军全，数学建模竞赛辅导教程，杭州：浙江大学出版社,2009o［4］、苏金明、阮沈勇，MAHAB实用教程［M］。北京，电子工业出版社，2005o