压气机排序河海大学摘要：在本文中我们针对压气机实际生产中的问题,试图找到满足题意的可行解,使压气机的叶片在这种排列组合下能够满足生产中规定的所组合在一起的叶片在重量和频率方面的要求，从而使其能够正常运作。

对第一个问题,我们主要采取理论分析的方法将24个叶片的按照重量大小进行排序,然后采取大小结合的办法，将重量大的和重量小的合为一组,依次进行下去,尽量保证组合后的12组叶片重量和相差不大（相等最好）,这样做得目的是为了使每两组数据之和与另外两组数据之和的差不超过8g，对于不满足要求的进行调整。

这样做就能够保证这12组叶片任意两组组成一个象限均能满足质量要求了。

在满足质量要求后，我们就可以在这些组合中寻找满足频率要求的组合。

具体方法与问题一方法相似，根据问题一中的排序依次写出频率值。

比较每一组的频率之差，使差的绝对值不小于6。

对于不能满足此要求的可以进行微调，微调时还要顾及质量要求。

这样组成的12组叶片序对在根据频率要求进行排序，具体方法是：每组中的两个叶片相连，一组中频率小的叶片和另外一组频率大的叶片相连，使相连两点地频率差不下于6，不满足要求的继续微调。

这样到最后就形成一条链，如果这条链首尾两点也满足频率要求，那么此链连接的点的顺序就是叶片排序的一组可行解。

根据上面提供的算法我们分别对试题中的两组叶片排序，通过较少的微调就可以得到满足题意的可行解（可行解不止一个，通过多次微调可以得到多个），第一象限依次是：10-2-4-9；第二象限依次是：13-8-18-11；第三象限依次是：16-20-1-7；第四象限依次是：5-12-17-22；第五象限依次是：3-23-14-24；第六象限依次是：21-6-19-15。

用同样的方法对第二组数据进行排序，得到结果如下：第一象限顺序：4-24-1-21；第二象限顺序：2-9-13-7；第三象限顺序：6-23-16-22；第四象限顺序：17-8-5-19；第五象限顺序：14-11-3-12；第六象限顺序：15-10-18-20。

关键词：微调、叶片排序、频率差、重量差一、问题重述在实际生产中，由于加工出的压气机叶片的重量和频率不同，所以在安装时就需要按工艺要求对叶片进行重新排序。

具体的工艺要求有：（1）压气机24 片叶片均匀分布在一圆盘边上，分成六个象限，每象限4 片叶片的总重量与相邻象限4 片叶片的总重量之差不允许超过8g。

（2）叶片排序不仅要保证重量差，还要满足频率要求，两相邻叶片频率差尽量大，使相邻叶片频率差不小于6Hz。

（3）当叶片不满足上述要求时，允许更换少量叶片。

表1 两组叶片的重量和频率数据第一，给出按重量排序的算法； 第二，给出按重量和频率排序的算法；第三，当叶片保证了重量差和频率差时，按排列顺序输出叶片的序号。

二、 问题分析这是一个典型的组合优化问题，排序的过程中需要同时考虑三个因素： 1、 每象限4 片叶片的总重量与相邻象限的总重量之差不允许超过8g 。

2、两相邻叶片频率差尽量大，使相邻叶片频率差不小于6Hz 。

3、不能把相对应的质量和频率单独分开。

4、质量相同或者频率相同的叶片单独标上记号，微调时候可以从这些叶片着手。

三、 符号系统i ：叶子的序号（按照质量从低到高顺序），本文中124i ≤≤且为整数。

i f ：第i 片叶子。

i m ：第i 片叶子的质量。

i n ：第i 片叶子的频率。

k F ：依次表示i f 与25i f -编成的组（共12组）。

四、 模型建立与求解首先我们先求总重量之差不允许超过8g 的具体方案，在满足其基础上建立自由组合，在根据频率之差要求寻找可行解。

首先我们根据叶片的质量从低到高的顺序重新排列，若能使这六个象限中每个象限的叶子质量之和相等（或接近），就能保证每象限4 片叶片的总重量与相邻象限4 片叶片的总重量之差最小。

同时要考虑到频率差的因素，因此我们采用将维法先将这24片叶子按照质量因素分成12份，使得每一份质量之和都接近（相等），若悬殊很大，则进行微调。

这样若是将这12份中的任意2份组合成一个象限，均能保证每个象限与相邻象限的质量之差最小，而将12份分成六个象限的方法是多种的，我们就在这多种方法中用试探的方法来选择满足每片叶子频率之差较大的排序。

问题一：按照重量排序算法步骤如下：（1）将i f 与25i f -组成一组，共计组成12组。

按照顺序分别记为k F 其中k 为整数且112k ≤≤。

（2）计算每组的质量均值。

（3）计算质量均值最大的两组质量之和减去质量均值最小的两组质量之和的差。

若差小于等于8，进入步骤5。

若差大于8，则进入步骤4。

（4）分别将这四组中八片叶子的质量与整个24片叶子质量均值比较，将相差最大的叶子进行更换。

这样就能保证这12组叶子任意分到六个象限中（每个象限分两个，不可重复）均能满足质量排序需求。

问题二：在按重量排序的基础上，我们根据频率要求选择合适的排序。

（1）、记k F 中两片叶子的频率分别为,1k y 和,2k y ，分别计算,1,2k k y y -，若所有的,1,26k k y y -≥，进入第3步。

否则进入步骤2。

（2）与k m 相等的叶子相调换，这时候频率k n 也跟着调换。

重新返回步骤1。

（3）在直角坐标系中作出点1(,)k k y 以及2(,)k k y ，1,212k = 这24个点，用直线连接12,k k y y ，这样就作出了12条竖直的线段，线段的两端分别称之为顶点和末点。

（4）从第k 条线段中顶点与末点中选择一点与第k+1条线段的一端点相连，将第k 条线段中剩下的一端点与第k-1条线段的一端点相连。

其中k 为整数且112k ≤≤。

当k=12时，可将第一条线段作为第k+1条线段，当k=1时，第k-1条线段可认为是第12条线段。

相连时要满足：相连的两个端点频率之差的绝对值不小于6，对于其中一个端点可以与隔壁两个端点均可相连的地方作标记，作为微调点（我自己给起的名词），随便选择一条路径连下去。

若不满足相连频率条件，转如步骤5。

否则进入步骤6。

（5）返回到微调点，选择另外一条路径走下去，若还不能满足将不能满足差的绝对值全部不小于6，则将此线段与其他线段对调位置。

（6）确定排序路线后，根据排序路线找出相对应的叶子序号，排序。

排序时要保证k F 中的两片叶子在同一个象限。

问题三：我们根据试题所给数据，利用上述算法对叶子进行排序，其过程如下：1、先将第一组数据按照质量从低到高重新排列，排列后的顺序如表一：均值，如表二：3、均值最大的两个数是在1F 组与11F 组，均值分别为679.5，679.5。

均值最小的两个数在2F 组与4F 组，均值分别为677，677。

比较(679.5+679.5)-(677+677)与8的大小。

(679.5+679.5)-(677+677)=5<8。

即说明将112F F 任意分到六个象限中去（每个象限分两个）均能满足质量要求。

4、表二中是质量1、2行是各片叶子的质量，我们将相对应的频率标记出来，并计算差的绝对值值。

如表三。

5、由表三可以看出，差的绝对值全部大于6，这就说明k F （其中112k ≤≤）中的两片叶子可以排在一起。

6、连接中要求连接的两个频率差的绝对值大于等于6，其过程如下：在1F 选择204与2F 中211相连（因为|204211|76-=>），将2F 中剩余的频率201与3F 中209相连，3F 中196与4F 中209相连，4F 中196与5F 中209相连， 5F 中194与6F 中203连接，6F 中188与7F 中212连接，7F 中198与8F 中208连接，8F 中196与9F 中210连接，9F 中193与10F 中210连接，由于10F 中189可以与11F 中198，208均可连接，在此标上标记，为做可微调点。

我们先选择208，那么11F 中198要与12F 中215相连，12F 中194与1F 中197不能相连（之差为3），所以不满足。

需要微调，返回到微调点11F ，将10F 中189改为与11F 中198连接，11F 中208与12F 中194连接，12F 中215与1F 中197连接。

这样经过微调后，均满足频率之差要求了。

7、按照6中连接顺序，相应的连接顺序如下表箭头所示：-8-16-9-15-10-11-14-12-13。

k F 中的两片叶子在同一个象限，故可将1-24-23-2归为第一象限，22-3-21-4为第二象限， 11-14-12-13为第六象限。

这里面的叶子序号是按照质量由轻到重排序后的序号，将其还原为试题中所给序号，其排列应该为第一象限依次是：10-2-4-9；第二象限依次是：13-8-18-11；第三象限是：16-20-1-7；第四象限依次是：5-12-17-22；第五象限依次是：3-23-14-24；第六象限依次是：21-6-19-15。

用同样的方法对第二组数据进行排序，得到结果如下：第一象限顺序：4-24-1-21；第二象限顺序：2-9-13-7；第三象限顺序：6-23-16-22；第四象限顺序：17-8-5-19；第五象限顺序：14-11-3-12；第六象限顺序：15-10-18-20；五、 模型分析文中给出的算法在根据质量排序的时候，通过最大项与最小项结合，这样就能达到中和作用，不会出现过大偏差。

对于一般情况下都可以找出具体可行解，但是当所给的数据比较特殊时， 也会出现要求更换叶片情况，比较麻烦。

此时我们可以在均值最大的两个位置上或者均值最小的两个位置上作标记。

在后面排序中注意不要将他们排列在一个象限即可。

例如对于第二组数据，将i f 与25i f -组成一组，共计分成12组后。

均值最大的两组3f ，9f 质量之和减去均值最小的两组11f ，12f 结果为9，不能满足要求。

除了这种情况外，其他各组均满足质量要求，那么我们只需要在后面的排序中将11f ，12f 或者3f ，9f 分在不同的象限即可。

这样就避免了更换叶片的麻烦。

但是并不是所有这样的情况都是可以调节的，当所给叶片数据中出现一个或多个质量与其他各叶片质量相差过大时候，这仍然需要更换叶片。

比如对于所给第一组数据中，有个叶片质量只有300克，无论怎么排列都不能满足质量要求，这样的叶片就需要更换。

而对于频率来说，若出现过多叶片频率集中于某一值的情况，则需要更换少量的叶片。

这与现实也是比较吻合的。

六、 结论利用微调法，我们根据试题所提供的两组数据可以很快地求出可行解。

此种解法对于一般的数据都是可以很快地求解，但是对于一些可行解比较少的数据具有很大的复杂性。

另外此算法得出的结果只是可行解，而得不到所有解。

这也是此模型需要进一步完善的地方。