《叶片排序 论文》由会员分享，可在线阅读，更多相关《叶片排序 论文（21页珍藏版）》请在金锄头文库上搜索。
1、压气机叶片排序问题摘要本文考虑压气机叶片重量及频率的差异，结合实际情况，给出不同约束条件 下的叶片安排模型，并给出相应的叶片安排方案。对于问题一，本文以动态规划模型为基础，将所有叶片分为 4 组，分 4 个阶 段分配给每个象限，使每次分配后相邻象限质量差的总和最小。每阶段选取 5 组较优解，作为下阶段的初始状态。在最终得到的 625组结果中选取较优解。利 用该模型为第一组叶片排序，得到的相邻象限质量差的最大值为lg，质量差的 总和分别为 2g。对于问题二，本文在问题一结果的基础上，加入了频率限制条件。利用模拟 退火的改进算法，对问题一的结果进行优化，得到了满足重量、频率限制条件的 基本可行解。
2、随后，采用局部搜索方法对基本可行解进一步优化，得到符合题意 的较优解。对于问题三，本文考虑到应尽量减少更换叶片数量，首先建立了调整区判别 模型，优先更换质量调整区与频率调整区交汇处的叶片，对需要更换的叶片实现 了定位。随后，建立了叶片更换模型，分别考虑质量与频率约束条件，使调整区 逐步扩大，直到使相邻象限的质量差与相邻叶片的频率差满足要求，并给出了质 量和频率的调整范围。对于问题四，本文依次利用动态规划模型、模拟退火模型与叶片更换模型， 得到了两组叶片的合理排序。相邻象限质量差的总和均为2g，相邻叶片频率差 的总和分别为 336Hz 、3l6Hz。最后，本文给出了模型的评价与推广。关键字： 动
3、态规划模拟退火局部搜索叶片更换一、问题重述由于加工出的压气机叶片的重量和频率不同，安装时需要按工艺要求重新排 序。（1）压气机24片叶片均匀分布在一圆盘边上，分成六个象限，每象限4 片 叶片的总重量与相邻象限 4 片叶片的总重量之差不允许超过一定值（如 8g）。（2）叶片排序不仅要保证重量差，还要满足频率要求，两相邻叶片频率差 尽量大，使相邻叶片频率差不小于一定值（如 6Hz）。（3）当叶片确实不满足上述要求时，允许更换少量叶片。 请按上述要求给出：（1）按重量排序算法；（2）按重量和频率排序算法；（3）叶片不满足要求时，指出所更换叶片及新叶片的重量和频率值范围；（4）当叶片保证了重量差和频率
4、差时，安排列顺序输出。二、问题分析加工出的不同的压气机叶片具有不同的重量和频率，利用这些叶片安装压气 机时需要符合一定的条件，从而满足工业要求。对于问题一，题目要求在满足相邻象限重量差不大于某一定值的条件下给出 相应的排序算法。将重量差条件作为约束条件，问题一即可转化为寻找符合约束 条件的解集。可以以重量差为基础构造目标函数，从而将问题一转化为最优化问 题。本文考虑以动态规划思想为基础，将24 个叶片分组、分阶段分配给压气机 圆盘的 6 个象限，每个决策阶段只需在之前的已定初始状态基础上进行叶片分 配。对于问题二，本问需同时考虑相邻象限重量差不大于某一定值、相邻叶片频 率差不小于某一定值的限制
5、条件，在此基础上给出叶片分配方案。因为重量差与 频率差所针对的研究对象不同，分别为象限和单个叶片，所以如果仍然沿用问题 一的动态规划思想，则在叶片分组分配时会有很大的困难。考虑到模拟退火算法 较之其他算法在搜索全局最优解方面的优势，本文首先采用模拟退火算法，并在符号mqk其基础上加以改进使得运算量得到大幅度减少，得到寻找可行解的改进模拟退火 算法；而后以可行解为初始解利用局部搜索方法寻找符合条件的较优解。对于问题三，由于涉及到质量和频率两方面的调整，为了使更换的叶片最少， 应尽可能使被更换的叶片位于质量调整区和频率调整区的交汇处。对于质量的调 整，应先确定调整的象限数，若调整当前象限无法满足要
6、求，再扩大象限数。确 定所调整的象限后，根据临近的象限质量确定质量调整范围。频率调整方法与此 类似。对于问题四，利用上述建立的模型，可对两组叶片分别给出合理排序。三、模型假设1假设叶片的性能足够好，不会因磨损而改变质量和频率等参数。2假设任意规格的叶片都可生产出。四、符号说明符号含义第i个叶片(i=l,223,24)第i个叶片的重量第i个叶片的频率优化系数状态变量(j=0,l,2,3,4)第 k 个象限(k=l,2,3,4,5,6)第k个象限的总重量相邻象限重量差允许最大值五、模型的建立与求解5.1 模型一：质量排序模型5.1.1 问题分析本题共有 24 个叶片需要安排，若用普通的动态规划方法
7、解决此问题，相当 于穷举所有情况后比较目标函数并从中选取最优解，运算量过大；若采用遗传算 法或模拟退火算法，虽然算法可以实现，但其作为启发式算法运算量依然过大。 为了减少运算量，提高算法运行效率，考虑到穷举法运算量是成指数形式增长的， 本文将叶片分组、分阶段进行象限分配，从而避免了指数型增长所形成的巨大运 皆算量。以每次给每个象限分配一个叶片为标准，可以将 24 个叶片分为 4 组，每组 6个叶片。挑选一组叶片分配给6个象限时，共有C1 xC2 x A2=60种分配方案。542 若将每种分配方案均保留下来作为下一个决策阶段的初始状态，则运算量依然成 指数形式增长，当到达最后状态时约有604沁1
8、.2x 107种情况。考虑到动态规划方 法每次决策前的状态均为最优状态，本题设计算法时可以考虑对每次决策进行评 价，从每次决策后的状态中选取一部分符合约束条件且目标函数值较优的状态作 为下一决策阶段前的初始状态，依此类推，在最终的状态中寻找较优解。故用动态规划的方法解决问题一，其基本思想为：将叶片分组，每个决策阶 段挑出一组叶片分配给压气机圆盘的每个象限，每个象限分配一个叶片；分配之 后，此时可将圆盘象限包含叶片的情况作为动态规划的一个状态，从这些状态中 挑选最符合目标函数及约束条件的若干状态作为此时的最优分配策略，继而挑选 下一组叶片进行下一步的决策；依此类推，直到所有叶片分配完，每个象限具
9、有 4 个叶片时，在分配结果中选取较优解。5.1.2 模型建立(1)建立目标函数。由于问题一只需考虑相邻象限叶片重量差不大于某一定值，设m(s.)为平衡度(各象限重量差之和)，本文建立目标函数如下：m(s )=m - m+m - m+m - m+m - mjq1q 2q 2q 3q 5q 6q 6q12)叶片分组，确定组间分配次序。1.1)将 24 个叶片按重量由小到大排列，得到bbbb b b的叶片排序1 2 3 22 23 24(m m m m m m)。取b -b 为第一组，b -b 为第二组，1 2 3 22 23 24 1 6 7 12b -b 为第三组， b -b 为第四组。13
10、18 19 24 考虑到叶片最小重量与最大重量的不稳定性，应首先分配第一组和第四组的 叶片，使最大重量叶片与最小重量叶片的重量形成较好的互补。本文采用先分配 第一组叶片，再分配第四组叶片，继而分配第三组、分配第四组的分配顺序。( 3 )建立状态转移方程。 每一个决策阶段都相当于给每个象限分配一个新的叶片，所以状态转移即为 象限内叶片质量的增加。所以建立状态转移方程如下：m = m + mqk j+1qk j k j(1.2)该状态转移方程含义为第k个象限在第j +1个状态的总重量等于该象限在第 j 个状态的总重量加该决策阶段分配给该象限的叶片的重量。( 4)建立基本方程。分配叶片策略：基本条件
11、为保证相邻象限叶片总重量差不大于一个定值；在 基本条件的基础上使目标函数值最小化。因此建立基本方程如下：g(s ) = min m(s )j+1j+1:+ m ) - (m+ m )q6 j6 jq1 j 1 j=min(|(m+ m ) - (m+ m ) + (mI q1 j 1 j q2 j 2 j1.3)m -mmq1q 2m -一 mmq 2q 3m -mmq 3q 4m -mmq 5q 6m -一 mmq 6q11.4)（5）具体动态规划分配方法。s 0状态时，分配第一组叶片。在满足相邻象限总重量差不大于某一定值的 约束条件下，比较所有分配方案，选取目标函数值最优的前 N 个分配方
12、案，以 ss其分配后的状态作为 1， 1状态共有 N 个子状态。S1状态时，分配第四组叶片，分配方法同上。所得结果为S2状态共有N2 个子状态。同理，S3状态共有N 3个子状态，S4状态共有N4个子状态。（6）选取最优解。对 s4 的 N 4 个子状态依据目标函数值的优劣进行排序，选取前 5 种分配方 案作为问题一的较优解。5.1.3 模型分析此模型以动态规划思想为基础设计算法，当 N 取 5 时，共需计算约60 + 5x 60 + 25 x60 +125 x60二9360次，大大缩减了算法运算次数，大幅度提高了 算法的运算效率。5.1.4 模型验证 本文利用题目所给第一组叶片数据进行模型及算
13、法验证。 首先根据重量从小到大的顺序进行排序,分为 ABCD 四个组，结果如下：表 1.1 叶片分组数据表序号重量频率分组序号重量频率分组10655197A112663198B18658196A222663196B29658201A323663193B311658196A424664189B47660188A521665198B520660194A619666194B615693215C11696203D13694210C216696209D26694208C318696209D314694210C413697209D45695212C54698211D517695208C62704204D6
14、利用本文所给算法对上述数据进行求解可得：表 1.2 求解结果N运行时间（ms）结果数平衡度最优解130122246161431255264250120654686082679612482求解情况直观图如下图所示：图 1.1 求解结果情况有求解结果可以看出，当N=5时，运行结果已经很优，平衡度最少为2,且程序运行时间仅为0.468s，所以本文所给算法运行效率、计算精度均很高。5.2 模型二：质量和频率排序模型5.2.1 问题分析考虑到动态规划方法在同时考虑重量差和频率差时的不便性，本文采用模拟 退火算法和局部搜索方法解决问题二。运用模拟退火算法最关键的问题在于如何增大解的收敛速度。针对本题考 虑，因为各个叶片的重量、频率为定值，且各个叶片的邻接叶片情况均不同，所 以在增强产生新解的导向性方面会有很大的困难。如果始终运用模拟退火方法寻 找最优解，因为在状态转移准则中含有不优解的接收概率，所以收敛速度会很慢， 算法运行效率会很低。对第一问结果和近似求得的较优解叶片排列方案进
