最佳组队问题

1、最佳组队问题的求解与分析摘要参加重大比赛前，院校如何选拔最优秀的队员并科学合理地组队是各院校取得 优秀名次的关键。本文就此通过层次分析法建立层次结构模型（模型一），结合模 型比较得出参赛的18名队员。根据所得18名成员建立优化模型（模型二）求解最 佳竞赛技术队。接着，使用非线性规划模型（模型三）求解整体竞赛技术水平最高 问题，最后，通过误差分析得到模型四推翻模型一，同时重解模型二.三，得出优 化后的组队分配。针对问题一，本文通过建立成对比较矩阵确定各项权重及其一致性，并通过权 重计算得出淘汰队员应为LHo针对问题二，本文通过问题一的权重以及优化模型求解，得出G, L,S组成的队 伍是竞赛技术水

2、平最高的最佳组队。针对问题三，本文通过非线性规划模型，得出以下组队方案:第一队第二队第三队第四队第五队第六队AEDKGCBFJMOPLNSRQT经过模型的误差分析，重新建立彳莫型四，得：1. 应淘汰A、O队员。2. 最强队组合人员应为GH,L3最佳组队方案应如下所示：第一队第二队第三队第四队第五队第六队EIBCDHFJGNMISKPRQT关键词层次分析法 权重优化模型 非线性规划模型一、问题重述1.1问题背景在一年一度的我国和美国大学生数学建模竞赛活动中，任何一个参赛院校都会 遇到如何选拔最优秀的队员和科学合理地组队问题，因此现假设有20名队员准备 参加竞赛，请根据问题及所给参数进行相关选拔及

3、组合。12题目所给信息及参数根据队员的能力和水平选出18名优秀队员分别组成6个队，每个队3名队员去 参加比赛。其中选拔队员主要考虑的条件按重要度依次为有关学科成绩（平均成 绩）、智力水平（反映思维能力、分析问题和解决问题的能力等）、动手能力（计算 机的使用和其它方面实际操行能力）、写作能力、外语能力、协作能力（团结协作 能力）和其它特长，相关数据如下表所示。队员 编号学科成 绩xl智力水平x2动手能 力x3写作能 力x4外语水平x5协彳 力乍能$6其它特长x7A8.6908.28.07.9956B8.2888. 16.57.7 -912C8.0868.58.59.2968D8.6898.39.

4、69.7978E8.8848.57.78.6929F9.292& 27.99.0906G9.2969.07.29. 1929H7.0809.86.28.7976I7.7828.46.59.6935J8.3818.66.98.5944K9.0828.07.89.0955L9.6918. 19.98.7976M9.5968.38. 19.0937N8.6838.28. 19.090509. 1878.88.48.8945P9.3848.68.88.6956Q8.4809.49.28.4917R8.7839.29. 18.7928S7.7819.67.69.0969T9.08.89.57.9

5、7.719.06表队员各项能力汇总表13所需解决问丿（1）在20名队员中选择18名优秀队员参加竞赛。（2）确定一个最佳的组队使竞赛技术水平最高。（3）给出山18名队员组成6个队的组队方案，使整体竞赛技术水平最高，并给出每个队的竞赛技术水平。二、问题分析2.1问题一分析山于题中已提及选拔队员主要考虑的条件按重要度依次为有关学科成绩、智力 水平、动手能力、写作能力、外语能力、协作能力和其它特长，因此通过比较确定 表一中各项能力对队员选拔的权重，继而建立层次结构模型（模型一）进行队员的 筛选。2.2问题二分析山于题tJ要求在已选出的18名队员中组合出一组最佳组合使得其竞赛技术水 平最高，因此本文采用

6、优化模型（模型二）来求解。2.3问题三分析问题要求寻求各队整体竞赛水平最高的分队方法，首先应该给每一对的整体竞 赛水平一个精确标准，根据经济学原理，在社会中总是从事自己最有优势的工作， 即最擅长的工作。因此在组队的过程中，每队的三名选手至少有两项能力在整体平 均能力以上，根据这一原则以及三人综合水平尽可能高进行组队。因此本文通过非 线性规划模型（模型三）来解决问题。三、模型勺（1）题LI所给各项指标真实客观反映选手水平。（2）竞赛过程中不考虑其他各类因素影响，竞赛水平的展现只取决于表1中数据（3）选拔过程遵循本文标准公平公正公开。（4）各竞赛水平山各个单项指标来衡量，各队的各单项竞赛水平山此项

7、最优队员 水平为准。（5）所有被选择队员参赛时无不参赛的情况或厌赛心理（6）问题二和问题三中各组成队伍里的各队员相处写作融洽四、符号说明X,依次为学科成绩、智力水平、动手能力、写作能力、外语水平、协作能力和 其他特长心表示第i个队员在第丿个基本条件下的成绩匕表示第丿 个条件在选队员时所占的权重表示第i个因素比笫丿个因素对LI标层的影响程度川表示每个队员的编号欺表示第k个队的第i个队员P第i个队员的竞赛技术水平丛第鸟个队的总体竞赛技术水平五、模型建立与求解5.1冋题一山于题U要求在20进18的选队员过程中首先看学科成绩，其次看智力水平， 再看动手能力、写作能力、外语能力、协作能力和其他特长。因此

8、我们先建立成对 比较矩阵再使用层次分析结构模型进行问题一的求解。利用层次分析法建立层次结构模型目标层学科成绩智力水平功手能力写作能力外语水平协作能力其他恃长准则层JJ K _L MN图层次结构模型G方层51.2建立成对比较矩阵设A为因素层次的成对比较矩阵，为了便于构造，假设每两个相邻因素的比较 值相同，即仏.，"常数。因此引进比较尺（表2）尺度含义1第i个因素与第丿个因素影响相同3第i个因素与第丿个因素影响稍强5第i个因素与第丿个因素影响强7第i个因素与第丿个因素影响较强9第i个因素与第丿个因素影响很强2, 4, 6, 8为位于1, 3, 5, 7, 9中间的值表2比较尺另并建立成对

9、比较阵：r 11.534.567.59、1/1.511.534.567.51/31/1.511.534.561/4.51/31/1.511.534.51/61/4.51/31/1.511.531/7.51/61/4.51/31/1.511.5< 1/91/7.51/61/4.51/31/1.51 >确定各项权重及一致性检验1）计算成对比较矩阵A的最大特征值入=7.0870 （附件一） 其对应特征向量为：IV* = （0.750&0.5102,0.3277,0.2055,0.1280,0.081 &O.O573）?归一化得：w = （0.36490247901593,

10、0.0999,0.0622,0.039&0.0261），w的值依次表示下一个元素对上一个元素的影响程度2） 一致性检验山于一致性指标所以C/=7（）S7（）- =0.0145”一17-1n1234567891011R1000.580.901. 121.211.321.411.451.491.51由下表（表3）可知,刃=132一致性比率:随机一致性指标CI0.0145CR =RI=O.OllOvO.l1.32表3随机一致性指标血数值表所以A不一致度在容许范圉内,可用其归一化特征向量3作为其权重根据权重计算个人竞赛水平定义每位队员竞赛技术水平：Pi = dij * （Di i =将表1中各

11、项数据代入上式，计算得出各人竞赛水平排序（表4）队员学科成智力水动手能写作能外语水协作能其它特竞赛技术水编号绩xl平x2力x3力x4力x6长x7平PL9.69. 18. 19.98.79. 769. 1221M9.59.68.38. 199. 379. 0904G9.29.697.29. 19.299. 0570D8.68.98.39.69.79. 788. 8239F9.29.28.27.99968. 8078P9. 38.48.68.88.69.568. 794709. 1& 78.88.48.89.458. 7703T98.89.57.97.7968. 7619R8. 78. 3

12、9.29. 18.79.288. 7230E8.88.48.57. 78.69.298. 5527Q8.489.49.28.49. 178. 5322A8.698.287.99. 568. 5008K98.287.899.558. 4389C88.68.58. 59.29.688.4175N8.68. 38.28. 19958. 3597S7. 78. 19.67.699.698. 3195J8. 3& 18.66.98.59.448. 1032B8.28.88. 16.57.79. 128. 0067I7. 78.28.46.59.69. 357. 9277H789.86.28. 7

13、9. 767. 8018表4-各人竞赛技术水平排序山表可知淘汰队员为LH。5.2问题二为从18名队员中选取一组最佳组合使得其队竞赛水平最高采用优化模型以解 决此问。对18名优秀队员及其基本条件进行编号队员ABCDEFGHIJ编号12345678910队员KLMNOPQRST编号11121314151617181920表5-优秀队员编号条件学科成绩X1智力水平X2动手能力x3写作能力x4外语水平x5协作能力x6其它特长x7编号1231567表6个人各项能力编号评价一个队的竞赛技术水平高低，取决于所选队员的每个基本条件。因此一个队的竞 赛技术水平高低使用整体法加以说明，即给一组匕 ) = 1,2,

14、7来表示这个队的各基本条件的值，然后再分别乘以权值，最后加和就用这个值来表示一个队的竞赛技术水平",7即 « = X Pi®接下来我们确定匕，由于竞赛水平的发挥只取决于表一中所给的各项条件，并且， 参赛队员都能正常发挥自己的水平，所以应采取优势互补的办法来定义。基于如上考虑我们让匕取三个队员在第丿个基本条件下的值中的最大值，即：Pj = maxj, x2d2）,州皿切J = 1,2,3,4,5,6,7由于要从18名队员中选出3名组为一队，所以要求只能等于3 （兀表示第i个1-118队员是否被选中：1选中，0不选中），即£x,=3522模型二的数学建立LI

15、标函数：7 max u =工 p)*j"Pj = max xxdxjy x2d2j,， j = 1,2, , 7约束条件:<181-1兀为变爪523模型二求解肖Xi = mo = Xi? = 1时U标达到最大值u = 9.588150,同时Pi = 9.6, p2 = 9.6, “3 = 9.6, /?4 = 9.9,必=9.1, p6 = 9.7, p7 = 9即G、L、S三个队员组成一队时竞赛技术水平最高，竞赛技术水平值为：9.5881505.3问题三结合问题二可知若18名队员组成6个队，要使得整体竞赛技术水平最高 £畋需达到最大值。A-16模型的口标函数为R =

16、Uk K-1由问题二可知uk =2昇冬j = '、2，,721每一个人只能被一个队选中，所以乞X/127 = 1,2，,7k = 12,6i = 1,2,. J8Ihij = max xk| *4八“/2门，畑*仏18且每队只能有三个人，因此：工X短=3k = 1,2,6531模型的的数学建立目标函数：maxR =6A-17U产工Pf叫r-1约束条件:xh = 0或 1532模型求解求解得下两表:k123456数值9.1388.96189.057079.367749.328469.13068表7每个队的竞赛技术水平12345619.69.28.69.59.29.329.19.28.99

17、.69.68.838.28.59.69.29.49.549.98.19.699.28.858.79.09.79.09.19.269.79.29.79.59.49.376.09.09.08.09.08.0表&第R个队的基本条件值曲表7每个队的竞赛技术水平u和表8第个队的基本条件值得出此学校整 体竞赛技术水平最高的组队方案如下表（表9）所示：第一队第二队第三队第四队第五队第六队AEDKGCBFJMOPLNSRQT表9-组队方案六. 模型误差分析由于模型一中只考虑每个队员的竞赛技术水平，而没有考虑一个队的竞赛技术水 平，但问题三希望的是每个队参赛技术水平最高，所以不能从个人的角度去选择队员，

18、 因此我们希望用类似模型三的解法来解决问题一选队员的问题，即从20人中选择18 人组成6队使得整体竞赛技术水平最高。61模型四6丄.6模型四的数学建立6max R =工比目标函数：27U产厂1,2,.,7pkij =mnx® *心,兀2*2厂无18*切) = 12,7;& = 1,6约束条件 J£xw<li = l,2,.,20*】18工 X=3£ = 1,2,6/-Ixki = 0或 16丄.2模型的解k123456数值9.1338.5729.2658.8449.59.392表10 每个队的竞赛技术水平U123456719.29.29.67.99.09.69.029.08.28.67.89.69.55.039.39.69.08.89.19.59.048.78.69.29.19.29.68.059.59.69.49.69.79.78.069.699.89.98.79.76.0表LL第£个队的基本条件值P灯由表10-每个队的竞赛技术水平U和表11第R个队的基本条件值凡可得出最终的使整体竞赛技术水平最高的组队方案如下：第一队第二队第三队第四队第五队第六队EIBCDHFJGNMISKPRQT因此则被淘汰的队员为：A和O重验模型二求解在模型四的基础上，通过模型二我们计算问题二的值，得到：当选择G、H和L时目标达到最大值u=