特殊指派问题之求解算法对比分析

曹迎槐

摘要：该文以混合泳接力项目这种特殊的类指派问题为例，一改传统的0-1规划解法，不仅提出了基于GA和偶图的求解思路，更提出了一种基于各泳姿成绩表差值的表上求解算法，并对各算法做了汇总分析。

关键词：混合泳接力；指派；绩差求解；GA；偶图

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）17-0220-02

1背景

生活中的指派问题很常见，但运动会上的类指派接力项目却有些特殊。接力项目既可出现在田径场上，也可出现在游泳池里，既可设男子项目，亦可设女子项目，甚至还有男女混合接力，观赏性非常强。田径场上的接力比赛之接棒技术很有讲究，但游泳池里的混合接力虽省去了接棒压力，但增加了泳姿要求，需考虑的因素反而更多。

例如：4×100m混合泳接力项目全程400米，规定每个队由4人组成，必须按仰泳、蛙泳、蝶泳、自由泳的顺序进行，每人只能用一种泳姿游完100m，每种泳姿的技术要求依据本泳姿之相关规则。不难理解，当备选人数较多时，如何确定组队人选就颇费脑筋。较传统意义上的指派问题而言，此类问题存在淘汰机制，不可随意指派，且同时存在着人员选择与泳姿分配等纵、横双向对比分析，相对复杂，其特殊性一目了然。为便于说明问题，设现有8名备选队员，其平时成绩如表1，试分析如何组队，可使全队的总成绩最好。

此类问题的常见解法多用0-1规划，属LP范畴。其实，还有多种求解思路。

2基于GA的求解分析

作为指派问题，因其非线性特征十分明显，且不连续，在数据规模较大时解空间相对可观，所以基于GA求解也是个不错的选择。仍以上述想定案例为基础，因备选人数有8人，故可用3位二进制0-1编码来精确描述每个选手，如表2所示。

于是，GA的个体即可用人选的4位选手之0-1编码（长为固定的12位）来表示。例如：个体‘101 000 100 010，即表示‘己、甲、戊、丙四位选手，按照仰泳、蛙泳、蝶泳、自由泳的规定顺序组队参赛。

至于GA之操作算子设计，倒也没有太多的特殊性，无非是交叉、突变，甚至选择等。但在GA的求解过程中，每迭代生成一个新个体，都必须检测其规范性，即必须保证四位选手不重，以规避一人游多个泳姿的情形。而适应度函数十分简单，只需计算四名选手的总成绩并求最小即可。在本案例中，种群规模可设置为80，大约相当于解空间的二十分之一左右。而交叉、遗传和突变等概率，则按常规处之就好，无须做额外设计。

经MATLAB软件实际运行可知，用GA求解确无把握得到最优解，所以，用GA求解本案例之指派问题，旨在对比分析几种不同求解方法之异同和特点，从而强化学生的运筹优化意识和对现实问题的分析思路或角度。

3基于成绩差的表上求解算法嘲

首先，先将表1中的成绩统一为以秒为单位，称‘归秒处理。结果如表3。

接着，再求成绩差，称‘绩差。即找到各泳姿的最优成绩，然后求出该泳姿的其他各选手之成绩与该最优成绩之差，结果当然均非负。其中，最优成绩不变。如表4。

虽然最小绩差是0.3，但因选手戊已确定自由泳，且选手戊没有其他任务，所以可不考虑该绩差。次小绩差是1.5，有两个点，即‘丁的蛙泳、‘辛的蝶泳。不妨先考虑点‘丁的蛙泳，即调整蛙泳的人选，用选手丁取代选手乙，游蛙泳。如表5。

再考虑另外一个次小绩差1.5的对应点‘辛的蝶泳的情形，可调整蝶泳的人选，用选手辛取代选手乙，游蝶泳。如表6。

此刻，泳队人选已确定完成。即：乙游仰泳、丁游蛙泳、戊游自由泳、辛游蝶泳，总成绩251.7秒。

4基于LP之0-1规划求解分析

5基于偶图之交替链求解分析

此类指派问题实质上可直接描述为一个二部图，即偶图K_2.4，如图2所示。对应于前面几种解法得出的最优解便是图中粗線组成的边集。该边集显然是交替链：‘自由泳—戊，戊、蛙泳，蛙泳—丁，丁—蝶泳，蝶泳—辛，辛—仰泳，仰泳—乙中的一部分。换言之，在偶图K_2.4中求解，即找出图中所有这些长度为7的交替链，该链从泳姿点集出发，到选手点集结束，点不重，边不重，从中找出交替链总权值最小的那条，取相间的4条边即为最优解。容易理解，这种方法的运行效率不会很高，其复杂度与穷举法几乎无异。

6诸算法之对比分析

汇总上述几种求解思路得表7。不难看出，不论是从求解工具、可操作性、分析思路，还是求解前的数据准备，甚至复杂度等诸多方面来看，基于成绩差的表上求解算法都处于十分突出的位置。

鉴于水平所限，不妥或错误难免，敬请大家批评指正！