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

《特殊指派问题之求解算法对比分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、特殊指派问题之求解算法对比分析摘要：该文以混合泳接力项目这种特殊的类指派问题为例，一改传统的0-1规划解法，不仅提出了基于GA和偶图的求解思路，更提出了一种基于各泳姿成绩表差值的表上求解算法，并对各算法做了汇总分析。本文采集自网络，本站发布的论文均是优质论文，供学习和研究使用，文中立场与本网站无关，版权和著作权归原作者所有，如有不愿意被转载的情况，请通知我们删除匕转载的信息，如果需要分享，请保留本段说明。关键词：棍合泳接力；指派；绩差求解；GA;偶图中图分类号：TP311文献标识码：A文章编号：1009-3044(2017)17-0220-021背景生活中

2、的指派问题很常见，但运动会上的类指派接力项目却有些特殊。接力项0既可出现在田径场上，也可出现在游泳池里，既可设男子项目，亦可设女子项目，甚至还有男女混合接力，观赏性非常强。田径场上的接力比赛之接棒技术很有讲究，但游泳池里的混合接力虽省去了接棒压力，但增加了泳姿要求，需考虑的因素反而更多。例如：4X100m混合泳接力项目全程400米，规定每个队由4人组成，必须按仰泳、蛙泳、蝶泳、自由泳的顺序进行，每人只能用一种泳姿游完100m,每种泳姿的技术要求依据本泳姿之相关规则。不难理解，当备选人数较多时，如何确定组队人选就颇费脑筋。较传统意义上的指派问题而言，此类问题

3、存在淘汰机制，不可随意指派，且同时存在着人员选择与泳姿分配等纵、横双向对比分析，相对复杂，其特殊性一H了然。为便于说明问题，设现有8名备选队员，其平时成绩如表1，试分析如何组队，可使全队的总成绩最好。此类问题的常见解法多用0-1规划，属LP范畴。其实，还有多种求解思路。2基于GA的求解分析作为指派问题，因其非线性特征十分明显，且不连续，在数据规模较大时解空间相对可观，所以基于GA求解也是个不错的选择。仍以上述想定案例为基础，因备选人数有8人，故可用3位二进制0-1编码来精确描述每个选手，如表2所示。于是，GA的个体即可用人选的4位选手之0-1编码（长为固定

4、的12位）来表示。例如：个体‘101000100010’，即表示‘己、屮、戊、丙’四位选手，按照仰泳、蛙泳、蝶泳、自由泳的规定顺序组队参赛。至于GA之操作算子设计，倒也没有太多的特殊性，无非是交叉、突变，甚至选择等。但在GA的求解过程中，每迭代生成一个新个体，都必须检测其规范性，即必须保证四位选手不秉，以规避一人游多个泳姿的情形。而适应度函数十分简单，只需计算四名选手的总成绩并求最小即可。在本案例中，种群规模可设置为80,大约相当于解空间的二十分之一左右。而交叉、遗传和突变等概率，则按常规处之就好，无须做额外设计。经MATLAB软件实际运行可知，用GA求解

5、确无把握得到最优解，所以，用GA求解本案例之指派问题，旨在对比分析几种不同求解方法之异同和特点，从而强化学生的运筹优化意识和对现实问题的分析思路或角度。3基于成绩差的表上求解算法嘲首先，先将表1中的成缋统一为以秒为单位，称‘归秒’处理。结果如表3。接着，再求成绩差，称‘绩差’。即找到各泳姿的最优成绩，然后求出该泳姿的其他各选手之成绩与该最优成绩之差，结果当然均非负。其中，最优成绩不变。如表4。虽然最小绩差是0.3,但因选手戊己确定自由泳，且选手戊没有其他任务，所以可不考虑该绩差。次小绩差是1.5,有两个点，即‘丁的蛙泳’、‘辛的蝶泳’。不妨先考虑点‘丁的蛙

6、泳’，即调整蛙泳的人选，用选手丁取代选手乙，游蛙泳。如表5。再考虑另外一个次小绩差1.5的对应点‘辛的蝶泳’的情形，可调整蝶泳的人选，用选手辛取代选手乙，游蝶泳。如表6。此刻，泳队人选已确定完成。即：乙游仰泳、丁游蛙泳、戊游自由泳、辛游蝶泳，总成绩251.7秒。4基于LP之0-1规划求解分析5基于偶图之交替链求解分析此类指派问题实质上可直接描述为一个二部图，即偶图K2.4,如图2所示。对应于前面几种解法得出的最优解便是图中粗?组成的边集。该边集显然是交替链：‘自由泳一戊，戊、蛙泳，蛙泳一丁，丁一蝶泳，蝶泳一辛，辛一仰泳，仰泳一乙’中的一部分。换言之，在偶图

7、K2.4中求解，即找出图中所存这些长度为7的交替链，该链从泳姿点集出发，到选手点集结束，点不重，边不重，从中找出交替链总权值最小的那条，取相间的4条边即为最优解。容易理解，这种方法的运行效率不会很高，其复杂度与穷举法几乎无异。6诸算法之对比分析汇总上述几种求解思路得表7。不难看出，不论是从求解工具、可操作性、分析思路，还是求解前的数据准备，甚至复杂度等诸多方面来看，基于成绩差的表上求解算法都处于十分突出的位置。鉴于水平所限，不妥或错误难免，敬请大家批评指正！