协作比赛的组队问题数学建模竞赛论文

1、第2题 最佳组队方案问题 在一年一度的我国和美国大学生数学建模竞赛活动中,任何一个参赛院校都会遇到如何选拔最优秀的队员和科学合理地组队问题这是一个最实际的,而且首先需要解决的数学模型问题.现假设有20名队员准备参加竞赛,根据队员的能力和水平要选出18名优秀队员分别组成6个队,每个队3名队员去参加比赛,选拔队员主要考虑的条件依次为有关学科成绩(平均成绩)、智力水平(反映思维能力、分析问题能力和解决问题能力等)、动手能力(计算机的使用和其他方面实际操作能力) 写作能力、外语能力、协作能力(团结协作能力)和其他特长.每个队员的基本条件量化后如表.假设所有队员接受了同样的培训,外部条件相同,竞赛中不考

2、虑其他的随机因素,竞赛水平的发挥只取决于表中所给的各项条件,并且参赛队员都能正常发挥自己的水平.现在的问题是:1) 在20名队员中选择18名优秀队员参加竞赛;2) 确定一个最佳的组队使竞赛技术水平最高；3) 给出由18名队员组成6个队的组队方案，使整体竞赛技术水平最高，并给出每个队的竞赛技术水平。队员学科成绩（1）智力水平（2）动手能力（3）写作能力（4）外语水平（5）协作能力（6）其它特长（7）abcdefghijklmnopqrst8.68.28.08.68.89.29.27.07.78.39.09.69.58.69.19.38.48.77.89.09.08.88.68.98.49.29.

3、68.08.28.18.29.19.68.38.78.48.08.38.18.88.28.18.58.38.58.29.09.88.48.68.08.18.38.28.88.69.49.29.69.58.06.58.59.67.77.97.26.26.56.97.89.98.18.18.48.89.29.17.67.97.97.79.29.78.69.09.18.79.68.59.08.79.09.08.88.68.48.79.07.79.59.19.69.79.29.09.29.79.3.9.49.59.79.3.9.09.49.59.19.29.69.0628896965456755678

4、96一、 问题的提出在一年一度的国际数学建模竞赛中，各个单位都会遇到如何组队问题。现由20名队员。根据其能力选拔18名参加竞赛，选拔队员主要考虑的条件依次为学习成绩，智力水平（反映思维能力，分析问题、解决问题的能力，分析问题，解决问题的能力），动手能力（计算机的使用和其它方面的实际操作能力），写作能力，外语能力，协作能力（相互协作能力），其他特长（如身体素质等）每个队员的基本条件如下表（满分10分记）： 条件队员学习成绩智力水平动手能力写作能力外语能力协作能力其他特长18.69.08.28.07.99.5628.28.88.16.57.79.2238.08.68.58.59.29.6848.6

5、8.98.39.69.79.7858.88.48.57.78.69.2969.29.28.27.99.09.0679.29.69.07.29.19.2987.08.09.86.28.79.7697.78.28.46.59.69.35108.38.18.66.98.59.44119.08.28.07.89.09.55129.69.28.19.98.79.76139.59.68.38.19.09.37148.68.38.28.19.09.05159.18.78.88.48.89.45169.38.48.68.88.69.56178.48.09.49.28.49.17188.78.39.29.18.

6、79.28197.88.19.67.69.09.69209.08.89.57.97.79.06现在要解决的问题是：1.在20名队员中选择18名优秀队员，参加竞赛。2.给出18名队员组成6个队的组队方案是整体竞赛水平最高，并给出每队的竞赛水平。3.给出一个最高水平的参赛队。4.如果学习的权重为0.2，智力水平权重为0.2，动手能力的权重为0.2，写作能力的权重为0.1，外语能力的权重为0.1 ，协作能力的权重为0.15，其他权重为0.05，则应如何考虑？5.如果每个队员在竞赛时，受某种原因干扰，在某一方面发挥不好，但在另一方面发挥很好，应如何考虑？ 二、问题的分析协作比赛的组队问题是要从众多备选

7、队员中按照给定的量化标准，选出综合素质较高的若干名队员，以保证参赛队员的整体水平（即本题问题1）。通过分析我们知道这是一个多条件多方案的选择问题，属于层次分析问题，需要建立层次结构模型。为了尽可能体现参赛单位整体水平我们要对选出的这些优秀队员作出适当的搭配组合。使各组队员之间起到优势互补作用，这样就可以提高该组合的水平。通过队员间的搭配组合，组合出来的队伍的整体综合素质就会提高。这样这个单位派出的所有参赛队伍就都具有一定的水平，夺奖的机率会增加许多（即本题问题2）。但是，为了尽可能体现参赛单位的最高水平，并且提高获大奖的概率，就需要组合出一个“最佳阵容”，即该组合的各项水平几乎都是参赛单位的最

8、高水平（即本题问题3）。我们知道以上两个问题都属于动态规划问题，需要我们建立动态规划模型。由于体现参赛队员水平的量化指标很多，但各量化指标的重要程度不尽相同，这就需要对量化指标加入一个可以代表“重要程度”的衡量方式。本题是对各项量化指标进行加权，用权重来表示该项量化指标体现学生综合水平的程度。在此基础上来考虑参赛队员的选择以及组队问题（即本题问题4）。我们可以在题目所给权重的条件下，结合所建立的两个模型来解决问题。实际参赛时还有一个临场发挥问题，在比赛时受某种条件干扰队员的实际水平有可能超常发挥也可能失常发挥（即本题问题5）。怎样可以表示出队员水平的变化状态？我们可以借助矩阵来解决这一问题。三

9、、模型假设（1） 假设题目中所给的每个队员的各项信息都能真实地体现队员的各项能力和水平。（2） 假设每个队员在比赛能不受外界原因干扰，将自己的单项水平都发挥到正常水平（问题5除外）。（3） 假设一个参赛队单项能力或水平是由该队中水平最高的队员体现的。（即组合中的单项水平取三名队员中该项水平最高的）。（4） 假设问题3中选择一个体现参赛单位最高水平的组合是在问题1选出的18名队员中挑选。但它不受问题2中组队方案的影响（即不是直接在问题2已经组好6个队伍的基础上选取水平最高的）。（5） 假设题目中所给出的衡量学生综合素质的7项指标从左往右“重要程度”是依次降低的。四、符号说明表示准则i与准则j对目

10、标决策的重要程度之比r.i表示随机一致性指标ak =()20*20 表示方案层对准则层的比较矩阵c.r(1) 表示准则层（c）对目标层（o）一致性比例指标五、模型的建立及求解对问题1： 从20名队员中选择18名优秀队员。1.利用层次分析法首先建立该问题的层次结构模型图，如下：选择优秀队员其它特长协作能力外语能力写作能力动手能力智力水平学习成绩队员1队员2队员3队员4队员5队员6队员7队员8队员9队员10队员11队员12队员13队员14队员15队员16队员17队员18队员19队员20（层次结构模型图）根据层次分析法，我们可以知道第一层是目标层（记为o），是要解决的问题（即要从20名队员之中挑选1

11、8名队员）第二层是准则层（记为c），是要解决问题时所要考虑的各种因素，即学科代表、智力水平、动手能力、写作能力、外语能力、协作能力、其他特长7项因素。第三层是方案层（记为p），使该问题可以选择的各种方案，即20名备选队员。2.确定准则层（c）对目标层（o）的权重构造比较矩阵根据假设，准则层的7项因素从左到右的“重要程度”是依次减弱的。则1(1=ij=7),我们现在近似的认为任意两项因素的影响程度之差相等。因此，我们假设比较矩阵为 1 2 3 4 5 6 7 1/2 1 2 3 4 5 6 1/3 1/2 1 2 3 4 5a= 1/4 1/3 1/2 1 2 3 4 1/5 1/4 1/3 1

12、/2 1 2 3 1/6 1/5 1/4 1/3 1/2 1 2 1/7 1/6 1/5 1/4 1/3 1/2 1 计算比较矩阵a的特征值及特征向量由特征方程a-=0,利用matlab软件可以求出（求解过程附后）最大的特征值；max7.1955，相应的特征向量位w0=（0.3543，0.2399，0.1586，0.1036，0.0676，0.0448，0.0312）则该特征向量w0,即为准则层（c）对目标层（o）的权重 一致性检验由于比较矩阵a的阶数为7，其随机一致性指标为r.i=1.32（注：见数学模型姜启源p312表9-2）c.i(1)= (max -7)/(7-1)0.0326于是 一

13、致性比例指标为c.r(1)= c.i(1)/ r.i0.0247，则对应的（x,y,z）就可能是一个组队；任取3名队员组合，求出相应的技术水平指标，使6个技术水平指标之和为最佳组队方案。2.建立组队模型通过以上的分析，我们可以清楚的知道这就是一个动态规划问题。因而需要利用动态规划模型解决这个问题。利用动态规划的方法，分决策过程为6个阶段，分步给出6个队的组队方案，每一个阶段确定一个队。决策变量：xk =（x,y,z）k (k=1,2,3,4,5,6),即任取三名队员（x,y,z）所组成的一个组队方案。 状态变量：s k(k=1,2,3,4,5,6)，即从第k（1k6）个到第6个组队的组队方案所

14、包含的队员，其中s 1 =队员1，队员2，队员3，队员20（不含队员8，队员9）。状态转移方程：s k+1 = s k -xk (k=1,2,3,4,5)允许决策集合：dk =（x,y,z）；x，y，zs k ，vk =（x,y,z）w (k=1,2,3,4,5,6) 指标函数：vk （s k ，xk）表示决策xk （一个组队）关于状态s k的技术水平指标，即vk （s k ，xk）=m* 最优值函数：fk（s k）表示在状态s k下确定的k（1k6）个组队的技术水平指标之和的最大值。则有逆序解法的基本方程：fk（s k）=max vk (s k ，xk)+ fk+1（s k+1） xk dk

15、k=6,5,4，3，2，1 f6（s 6）=max vk (s k ，xk)当 x6 = sn 其中s k+1 =s k -xk k=1,2,3,4,53.模型求解把18名队员分成6个组共有816种分法,根据组队原则,用计算机编程可算得：组队xkx1x2x3x4x5x6队员(x,y,z)(3,10,11)(1,14,15)(2,16,18)(4,6,20)(5,13,17)(7,12,19)水平vk （x,y,z）0.05160.05190.05330.05460.05530.0563其最优值为f1（s 1）=0.32315对问题3：确定一个最佳的组队使竞赛水平最高模型的建立及求解：注意：由于

16、在问题2中，可以用计算机编程把18名队员分成6个组，通过计算相应的技术水平指标，找出最高者的组队，其结果为（12,7,19）下面我们通过分析法来说明其结果的正确性：由假设知，每个队中的三名队员具有互补性，即三个人中各单项水平指标的最高者为该队的单项水平指标，最佳组队主要体现全队在各单项水平指标水平最高,不应有貌相述评指标比其他的队低.由问题(1)中的准则c层对目标o层的权重w0可知,七项准则是按顺序依次排列的,对目标决策的影响是不同的,而且前四项对目标决策起着决定性作用,即水平指标主要体现在前四项上.(1) 最佳组队原则设mi(x)表示队员x的第i项水平指标，mi(x,y,z)表示由队员x,y

17、,z组队(x,y,z)的第i项水平指标，则mi(x,y,z)= max mi(x), mi(y), mi(z) ( i =1，2，3，7)(2)组队方案根据组队原则，最佳组队中的队员一定是前四项水平指标的最高者。显然由表13-2可得mi(12)=0.055 6为最高，于是mi= m1(12)= 0.055 619 9，则队员12是首先入选的队员。其次m2(7)= m2(13)= 0.055 7,而m2(7) m3(13)，故m2= m2(7)= 0.055 716 8，则队员7是第二个入选的队员。另外，m3(19)=0.055 395 3，于是m3 =m3(19) =0.055 395 3。而

18、且m4= m4(12)=0.061 913 7，则队员19应是第三个入选的队员，并且注意到m5= m5(7)=0.052 029 7，m6= m6(12)=0.051 871 7，m7= m7(7)=0.070 866 1也都是相对的较高者，即m=（0.055 619 9，0.055 716 8，0.055 395 3，0.061 913 7，0.052 029 7，0.051 871 7，0.070 866 1）.因此，由队员12,7,19组成（12,7,19）队的技术水平指标为:v（12,7,19）=m* w0 t=0.563 246是最高的,所以,最佳组队为（12,7,19）对问题4：

19、如果学习的权重为0.2，智力水平权重为0.2，动手能力的权重为0.2，写作能力的权重为0.1，外语能力的权重为0.1 ，协作能力的权重为0.15，其他权重为0.05，则应如何考虑？模型的建立及求解：利用准则层（c）对目标层（o）的权重（0.2 ，0.2， 0.2，0.1，0.1，0.15，0.05）以及方案层（p）对准则层（c）的权重，可以计算方案层（p）对目标层（o）的权重，根据公式得：w=（w1, w2, w3, w4, w20）t= w1, w2, ,w7* w0经过matlab软件计算（过程附后）得：w = （ 0.0498，0.0464，0.0497，0.0520，0.05030.0

20、515，0.0531，0.0458，0.0464，0.04720.0494，0.0535， 0.0515， 0.0489，0.05120.0516，0.0502，0.0513，0.0491，0.0512）t根据计算出的这个权重,按我们模型的计算流程可以得出在(4)所给出的条件下每个问题的答案。这说明准则层（c）对目标层（o）的权重不同，方案层（p）对目标层（o）的影响程度也不一样；因此我们在选择参考条件时，一定要分清主要条件和次要条件。对问题5：如果每个队员在竞赛时，受某种原因干扰，在某一方面发挥不好，但在另一方面发挥很好，应如何考虑？模型的建立为了避免这种情况的出现，应该在计算时考虑这种因素。我们先设外界干扰对队员的发挥影响程度为x每个队员在某一方面发挥好则其水平数据为原来的（1+x）在某一方面发挥不好则其水平数据为原来的（1-x）发挥正常则其水平数据为原来的数据不妨设x取0.2，则：某一方面发挥好其水平数据为