最佳组队问题

最佳组队问题的求解与分析摘要参加重大比赛前，院校如何选拔最优秀的队员并科学合理地组队是各院校取得优秀名次的关键。本文就此通过层次分析法建立层次结构模型（模型一），结合模型比较得出参赛的18名队员。根据所得18名成员建立优化模型（模型二）求解最佳竞赛技术队。接着，使用非线性规划模型（模型三）求解整体竞赛技术水平最高问题，最后，通过误差分析得到模型四推翻模型一，同时重解模型二、三，得出优化后的组队分配。针对问题一，本文通过建立成对比较矩阵确定各项权重及其一致性，并通过权重计算得出淘汰队员应为I,H。针对问题二，本文通过问题一的权重以及优化模型求解，得出G,L,S组成的队伍是竞赛技术水平最高的最佳组队。针对问题三，本文通过非线性规划模型，得出以下组队方案:第一队第二队第三队第四队第五队第六队AEDKGCBFJMOPLNSRQT经过模型的误差分析，重新建立1模型四，得：应淘汰A、O队员。最强队组合人员应为G,H,L最佳组队方案应如下所示：第一队第二队第三队第四队第五队第六队EIBCDHFJGNMISKPRQT关键词层次分析法权重优化模型非线性规划模型一、问题重述1.1问题背景在一年一度的我国和美国大学生数学建模竞赛活动中，任何一个参赛院校都会遇到如何选拔最优秀的队员和科学合理地组队问题，因此现假设有20名队员准备参加竞赛，请根据问题及所给参数进行相关选拔及组合。1.2题目所给信息及参数根据队员的能力和水平选出18名优秀队员分别组成6个队，每个队3名队员去参加比赛。其中选拔队员主要考虑的条件按重要度依次为有关学科成绩（平均成绩）、智力水平（反映思维能力、分析问题和解决问题的能力等）、动手能力（计算机的使用和其它方面实际操行能力）、写作能力、外语能力、协作能力（团结协作能力）和其它特长，相关数据如下表所示。队员编号学科成绩x1智力水平x2动手能力x3写作能力x4外语水平x5协作能力x6其它特长x7A869082807.9956B82888165 7.7912C808685859.2968D868983969.7978E888485778.6929F929282799.0906G929690729.1929H70809862 8.7976I| 778284659.6935ji838186698.5944K90828078 9.0955L969181998.7976M959683819.0937N868382819.0905O918788848.8945P938486888.6956Q848094928.4917R8 _____78392-1918.791-28S 778196769.0969T9.08.89.5797.7906表1-队员各项能力汇总表1.3所需解决问题（1） 在20名队员中选择18名优秀队员参加竞赛。（2） 确定一个最佳的组队使竞赛技术水平最高。（3） 给出由18名队员组成6个队的组队方案，使整体竞赛技术水平最高，并给出每个队的竞赛技术水平。二、 问题分析2.1问题一分析由于题中已提及选拔队员主要考虑的条件按重要度依次为有关学科成绩、智力水平、动手能力、写作能力、外语能力、协作能力和其它特长，因此通过比较确定表一中各项能力对队员选拔的权重，继而建立层次结构模型（模型一）进行队员的筛选。2.2问题二分析由于题目要求在已选出的18名队员中组合出一组最佳组合使得其竞赛技术水平最高，因此本文采用优化模型（模型二）来求解。2.3问题三分析问题要求寻求各队整体竞赛水平最高的分队方法，首先应该给每一对的整体竞赛水平一个精确标准，根据经济学原理，在社会中总是从事自己最有优势的工作，即最擅长的工作。因此在组队的过程中，每队的三名选手至少有两项能力在整体平均能力以上，根据这一原则以及三人综合水平尽可能高进行组队。因此本文通过非线性规划模型（模型三）来解决问题。三、 模型假设（1） 题目所给各项指标真实客观反映选手水平。（2） 竞赛过程中不考虑其他各类因素影响，竞赛水平的展现只取决于表1中数据（3） 选拔过程遵循本文标准公平公正公开。（4） 各竞赛水平由各个单项指标来衡量，各队的各单项竞赛水平由此项最优队员水平为准。（5） 所有被选择队员参赛时无不参赛的情况或厌赛心理（6） 问题二和问题三中各组成队伍里的各队员相处写作融洽四、 符号说明x.依次为学科成绩、智力水平、动手能力、写作能力、外语水平、协作能力和I其他特长气表示第i个队员在第j个基本条件下的成绩七表示第j个条件在选队员时所占的权重aj表示第i个因素比第j个因素对目标层的影响程度xi表示每个队员的编号乂疝表示第k个队的第i个队员七第i个队员的竞赛技术水平k第k个队的总体竞赛技术水平/V五、模型建立与求解5.1问题一由于题目要求在20进18的选队员过程中首先看学科成绩，其次看智力水平，再看动手能力、写作能力、外语能力、协作能力和其他特长。因此我们先建立成对比较矩阵再使用层次分析结构模型进行问题一的求解。5.1.1利用层次分析法建立层次结构模型图1-层次结构模型■t..ll图1-层次结构模型■t..ll;4t5.1.2建立成对比较矩阵设A为因素层次的成对比较矩阵，为了便于构造，假设每两个相邻因素的比较值相同，即aii+1=常数。因此引进比较尺（表2）尺度 含义1 第i个因素与第j个因素影响相同3 第i个因素与第j个因素影响稍强5 第i个因素与第j个因素影响强7 第i个因素与第j个因素影响较强9 第i个因素与第j个因素影响很强2，4，6，8为位于1，3，5，7，9中间的值另Li1=1.5，并建立成对比较阵:4.567.59)r11.531/1.511.534.567.51/31/1.511.534.56A=1/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.51J5.1.3确定各项权重及一致性检验1）计算成对比较矩阵A的最大特征值入=7.0870（附件一）其对应特征向量为：w'=(0.7508,0.5102,0.3277,0.2055,0.1280,0.0818,0.0573”归一化得：w=（0.3649,0.2479,0.1593,0.0999,0.0622,0.0398,0.0261”w的值依次表示下一个元素对上一个元素的影响程度2）一致性检验由于一致性指标所以C=n—n=言=。0145由下表（表3）可知，RI=1.32随机一致性指标n1234567891011RI000.580.901.121.241.321.411.451.491.51表3-随机一致性指标ri数值表一致性比率:CR=C=^01^5=0.0110<0.1RI1.32所以A不一致度在容许范围内，可用其归一化特征向量3作为其权重5.1.4根据权重计算个人竞赛水平定义每位队员竞赛技术水平：P.=di.*o. i=A,B，…,T

将表1中各项数据代入上式，计算得出各人竞赛水平排序（表4）队员编号学科成绩x1智力水平x2动手能力x3写作能力x4外语水平x5协作能力x6其它特长x7竞赛技术水平七L9.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.7947O9.18.78.88.48.89.458.7703T98.89.57.97.7968.7619R8.78.39.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.38.18.66.98.59.448.1032B8.28.88.16.57.79.128.0067I7.78.28.46.59.69.357.9277H789.86.28.79.767.8018表4-各人竞赛技术水平排序由表可知淘汰队员为I,H。5.2问题二为从18名队员中选取一组最佳组合使得其队竞赛水平最高采用优化模型以解决此问。5.2.1对18名优秀队员及其基本条件进行编号队员ABCDEFGHIJ编号12345678910队员KLMNOPQRST编号11121314151617181920表5-优秀队员编号条件学科成绩x1智力水平x2动手能力x3写作能力x4外语水平x5协作能力x6其它特长x7编号1234567表6-个人各项能力编号评价一个队的竞赛技术水平高低，取决于所选队员的每个基本条件。因此一个队的竞赛技术水平高低使用整体法加以说明，即给一组JJj=1,2,L,7来表示这个队的各基本条件的值，然后再分别乘以权值，最后加和就用这个值来表示一个队的竞赛技术水平u，即u二£p*.j=1 .接下来我们确定p.，由于竞赛水平的发挥只取决于表一中所给的各项条件，并且，参赛队员都能正常发挥自己的水平，所以应采取优势互补的办法来定义。基于如上考虑我们让Pj取三个队员在第j个基本条件下的值中的最大值，即：

p=max^xd,xd,L,xd}j=1,2,3,4,5,6,7j 11j22j1818j由于要从18名队员中选出3名组为一队，所以要求ZX〔只能等于3（x,表示第i个i=1队员是否被选中：1选中，0不选中），即ZX〔=3i=15.2.2模型二的数学建立目标函数：maxu=£p*wj=1p=max^xd,xd,L,xd}j=1,2,L,7j 11j22j1818j约束条件:凌8Xj=3i=1x〔i为0，1变量5.2.3模型二求解当x7=x10=x17=1时目标达到最大值u=9.588150，同时p=9.6,p=9.6,p=9.6,p=9.9,p=9.1,p=9.7,p=91 2 3 4 5 6 7即G,L,S三个队员组成一队时竞赛技术水平最高，竞赛技术水平值为:9.5881505.3问题三结合问题二可知若18名队员组成6个队，要使得整体竞赛技术水平人最高Z七需达到最大值。k=1模型的目标函数为R=ZUKK=1由问题二可知U=Tp*①k=1p=max立*d,x*U=Tp*①k=1p=max立*d,x*d,L,xkij kl 1jk22j k18*d18jIj=1,2,...,7k=1,2,...,6每一个人只能被一个队选中，所以£xki=1k=1且每队只能有三个人，因此：£x^.=3i=15.3.1模型的的数学建立i=1,2,...,18k=1,2,...,6目标函数:maxR=寸U

k

k=1

=£p*①i=1j=1,2,L,7Pk.=maxk*d,x*d,Lxk12jk18*d18jIj=1,2,L,7

k=1,L,6约束条件Ii=约束条件Ii=1,2,L,18k=1,2,L,6k=1如JX=3i=1x.=0或15.3.2模型求解求解得下两表:k123456数值9.1388.96189.057079.367749.328469.13068表7-每个队的竞赛技术水平uij12345619.69.28.69.59.29.329.19.28.99.69.68.838.28.59.69.29.49.549.98.19.69.19.28.858.79.09.79.09.19.269.79.29.79.59.49.376.09.09.08.09.08.0表8-第k个队的基本条件值pkj由表7-每个队的竞赛技术水平U和表8-第k个队的基本条件值p..得出此学校整体竞赛技术水平最高的组队方案如下表（表9）所示：

第一队第二队第三队第四队第五队第六队AEDKGCBFJMOPLNSRQT表9-组队方案六、模型误差分析由于模型一中只考虑每个队员的竞赛技术水平，而没有考虑一个队的竞赛技术水平，但问题三希望的是每个队参赛技术水平最高，所以不能从个人的角度去选择队员，因此我们希望用类似模型三的解法来解决问题一选队员的问题，即从20人中选择18人组成6队使得整体竞赛技术水平最高。6.1模型四6.1.6模型四的数学建立maxR=寸U目标函数： kmaxR=寸U目标函数： k=1kU=£p*oi=1Jp=maxu*d,x*d,L云尸1k=1JX=3i=1气.=0或1约束条件」j=1,2,L,7ILd18jIk2*2ji=1,2,L,20k=1,2,L,6j=1,2,L,7;k=1,L,66.1.2模型的解k123456数值9.1338.5729.2658.8449.59.392表10-每个队的竞赛技术水平U.123456719.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.69.19.89.98.79.76.0表11-第k个队的基本条件值Pkj由表10-每个队的竞赛技术水平U和表11-第k个队的基本条件值Pk可得出最终的使整体竞赛技术水平最高的组队方案如下：第一队第二队第三队第四队第五队第六队EIBCDHFJGNMISKPRQT因此则被淘汰的队员为：A和O6.1.3重验模型二求解在模型四的基础上，通过模型二我们计算问题二的值，得到：当选择G、H和L时目标达到最大值u=9.62，同时p=9.6,p=9.6,p=9.8,p=9.9,p=9.1,p=9.7,p=9.01 2 3 4 5 6 7 。即当把G、H、L这三个队