《协作比赛的组队问题_数学建模竞赛_论文》由会员分享,可在线阅读,更多相关《协作比赛的组队问题_数学建模竞赛_论文(11页珍藏版)》请在金锄头文库上搜索。
1、1第 2 题 最佳组队方案问题在一年一度的我国和美国大学生数学建模竞赛活动中,任何一个参赛院校都会遇到如何选拔最优秀的队员和科学合理地组队问题这是一个最实际的,而且首先需要解决的数学模型问题.现假设有 20 名队员准备参加竞赛,根据队员的能力和水平要选出 18 名优秀队员分别组成 6 个队,每个队 3 名队员去参加比赛,选拔队员主要考虑的条件依次为有关学科成绩(平均成绩)、智力水平(反映思维能力、分析问题能力和解决问题能力等)、动手能力(计算机的使用和其他方面实际操作能力) 写作能力、外语能力、协作能力(团结协作能力)和其他特长.每个队员的基本条件量化后如表.假设所有队员接受了同样的培训,外部
2、条件相同,竞赛中不考虑其他的随机因素,竞赛水平的发挥只取决于表中所给的各项条件,并且参赛队员都能正常发挥自己的水平.现在的问题是:1) 在 20 名队员中选择 18 名优秀队员参加竞赛;2) 确定一个最佳的组队使竞赛技术水平最高;3) 给出由 18 名队员组成 6 个队的组队方案,使整体竞赛技术水平最高,并给出每个队的竞赛技术水平。队员 学科成绩(1)智力水平(2)动手能力(3)写作能力(4)外语水平(5)协作能力(6)其它特长(7)ABCDEFGHIJK8.68.28.08.68.89.29.27.07.78.39.09.08.88.68.98.49.29.68.08.28.18.28.28
3、.18.58.38.58.29.09.88.48.68.08.06.58.59.67.77.97.26.26.56.97.87.97.79.29.78.69.09.18.79.68.59.09.59.19.69.79.29.09.29.79.3.9.49.5628896965452LMNOPQRST9.69.58.69.19.38.48.77.89.09.19.68.38.78.48.08.38.18.88.18.38.28.88.69.49.29.69.59.98.18.18.48.89.29.17.67.98.79.09.08.88.68.48.79.07.79.79.3.9.09.49.
4、59.19.29.69.0675567896一、 问题的提出在一年一度的国际数学建模竞赛中,各个单位都会遇到如何组队问题。现由 20 名队员。根据其能力选拔 18 名参加竞赛,选拔队员主要考虑的条件依次为学习成绩,智力水平(反映思维能力,分析问题、解决问题的能力,分析问题,解决问题的能力) ,动手能力(计算机的使用和其它方面的实际操作能力) ,写作能力,外语能力,协作能力(相互协作能力) ,其他特长(如身体素质等)每个队员的基本条件如下表(满分 10分记):条件队员学习成绩智力水平动手能力写作能力外语能力协作能力其他特长1 8.6 9.0 8.2 8.0 7.9 9.5 62 8.2 8.8
5、8.1 6.5 7.7 9.2 23 8.0 8.6 8.5 8.5 9.2 9.6 84 8.6 8.9 8.3 9.6 9.7 9.7 85 8.8 8.4 8.5 7.7 8.6 9.2 96 9.2 9.2 8.2 7.9 9.0 9.0 67 9.2 9.6 9.0 7.2 9.1 9.2 98 7.0 8.0 9.8 6.2 8.7 9.7 69 7.7 8.2 8.4 6.5 9.6 9.3 510 8.3 8.1 8.6 6.9 8.5 9.4 411 9.0 8.2 8.0 7.8 9.0 9.5 512 9.6 9.2 8.1 9.9 8.7 9.7 613 9.5 9.6
6、 8.3 8.1 9.0 9.3 714 8.6 8.3 8.2 8.1 9.0 9.0 515 9.1 8.7 8.8 8.4 8.8 9.4 516 9.3 8.4 8.6 8.8 8.6 9.5 617 8.4 8.0 9.4 9.2 8.4 9.1 718 8.7 8.3 9.2 9.1 8.7 9.2 819 7.8 8.1 9.6 7.6 9.0 9.6 9320 9.0 8.8 9.5 7.9 7.7 9.0 6现在要解决的问题是:1.在 20 名队员中选择 18 名优秀队员,参加竞赛。2.给出 18 名队员组成 6 个队的组队方案是整体竞赛水平最高,并给出每队的竞赛水平。3.给
7、出一个最高水平的参赛队。4.如果学习的权重为 0.2,智力水平权重为 0.2,动手能力的权重为 0.2,写作能力的权重为 0.1,外语能力的权重为 0.1 ,协作能力的权重为 0.15,其他权重为 0.05,则应如何考虑?5.如果每个队员在竞赛时,受某种原因干扰,在某一方面发挥不好,但在另一方面发挥很好,应如何考虑? 二、问题的分析协作比赛的组队问题是要从众多备选队员中按照给定的量化标准,选出综合素质较高的若干名队员,以保证参赛队员的整体水平(即本题问题 1) 。通过分析我们知道这是一个多条件多方案的选择问题,属于层次分析问题,需要建立层次结构模型。为了尽可能体现参赛单位整体水平我们要对选出的
8、这些优秀队员作出适当的搭配组合。使各组队员之间起到优势互补作用,这样就可以提高该组合的水平。通过队员间的搭配组合,组合出来的队伍的整体综合素质就会提高。这样这个单位派出的所有参赛队伍就都具有一定的水平,夺奖的机率会增加许多(即本题问题 2) 。但是,为了尽可能体现参赛单位的最高水平,并且提高获大奖的概率,就需要组合出一个“最佳阵容” ,即该组合的各项水平几乎都是参赛单位的最高水平(即本题问题 3) 。我们知道以上两个问题都属于动态规划问题,需要我们建立动态规划模型。由于体现参赛队员水平的量化指标很多,但各量化指标的重要程度不尽相同,这就需要对量化指标加入一个可以代表“重要程度”的衡量方式。本题
9、是对各项量化指标进行加权,用权重来表示该项量化指标体现学生综合水平的程度。在此基础上来考虑参赛队员的选择以及组队问题(即本题问题 4) 。我们可以在题目所给权重的条件下,结合所建立的两个模型来解决问题。实际参赛时还有一个临场发挥问题,在比赛时受某种条件干扰队员的实际水平有可能超常发挥也可能失常发挥(即本题问题 5) 。怎样可以表示出队员水平的变化状态?我们可以借助矩阵来解决这一问题。三、模型假设(1) 假设题目中所给的每个队员的各项信息都能真实地体现队员的各项能力和水平。(2) 假设每个队员在比赛能不受外界原因干扰,将自己的单项水平都发挥到正常水平(问题 5 除外) 。(3) 假设一个参赛队单
10、项能力或水平是由该队中水平最高的队员体现的。 (即组合中的单项水平取三名队员中该项水平最高的) 。(4) 假设问题 3 中选择一个体现参赛单位最高水平的组合是在问题 1 选出的 18名队员中挑选。但它不受问题 2 中组队方案的影响(即不是直接在问题 2 已经组好 6 个队伍的基础上选取水平最高的) 。4(5) 假设题目中所给出的衡量学生综合素质的 7 项指标从左往右“重要程度”是依次降低的。四、符号说明表示准则 i 与准则 j 对目标决策的重要程度之比ijaR.I 表示随机一致性指标Ak =( )20*20 表示方案层对准则层的比较矩阵(ijC.R(1) 表示准则层(C)对目标层(O)一致性比
11、例指标五、模型的建立及求解对问题 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 名队员之中挑选 18 名队员)第二层是准则层(记为 C) ,是要解决问题时所要考虑的各种因素,即学科代表、智力水平、动手能力、写作能力、外语能力、协作能力、其他特长 7 项因素。第三层是方案层(记为 P) ,使该问
12、题可以选择的各种方案,即 20 名备选队员。2.确定准则层(C)对目标层(O)的权重构造比较矩阵选择优秀队员其它特长 其它特长 协作能力 其它特长 外语能力 其它特长 写作能力 其它特长 动手能力 其它特长 智力水平 其它特长 学习成绩 其它特长 5根据假设,准则层的 7 项因素从左到右的“重要程度”是依次减弱的。则 ija1(1 ,则对应的(x,y,z)就可能是一个组队;W任取 3 名队员组合,求出相应的技术水平指标,使 6 个技术水平指标之和为最佳组队方案。2.建立组队模型通过以上的分析,我们可以清楚的知道这就是一个动态规划问题。因而需要利用动态规划模型解决这个问题。利用动态规划的方法,分
13、决策过程为 6 个阶段,分步给出 6 个队的组队方案,每一个阶段确定一个队。决策变量:X k =(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 个组队的组队方案所包含的队员,其中 S 1 =队员 1,队员 2,队员 3,队员 20(不含队员 8,队员 9) 。状态转移方程:S k+1 = S k -Xk (k=1,2,3,4,5)允许决策集合:D k =( x,y,z) ;x,y,zS k ,v k =(x,y,z )W (k=1,2,3,4,5,6)指标函数
14、:v k (S k , Xk)表示决策 Xk (一个组队)关于状态 S k 的技术水平指标,即 vk (S k , Xk)=M* TW0最优值函数:f k(S k)表示在状态 S k 下确定的 k(1k6)个组队的技术水平指标之和的最大值。则有逆序解法的基本方程:fk(S k) =max vk (S k , Xk)+ fk+1(S k+1) x k D kk=6,5,4,3,2,1f6(S 6)=max vk (S k , Xk)当 x6 = sn 其中 S k+1 =S k -Xk k=1,2,3,4,53.模型求解把 18 名队员分成 6 个组共有 816 种分法,根据组队原则,用计算机编
15、程可算得:组队 Xk X1 X2 X3 X4 X5 X6队员(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.0516 0.0519 0.0533 0.0546 0.0553 0.0563其最优值为 f1(S 1)=0.32315对问题 3:确定一个最佳的组队使竞赛水平最高模型的建立及求解:10注意:由于在问题 2 中,可以用计算机编程把 18 名队员分成 6 个组,通过计算相应的技术水平指标,找出最高者的组队,其结果为(12,7,19)下面我们通过分析法来说明其结果的正确性:由假设知,
16、每个队中的三名队员具有互补性,即三个人中各单项水平指标的最高者为该队的单项水平指标,最佳组队主要体现全队在各单项水平指标水平最高,不应有貌相述评指标比其他的队低.由问题(1)中的准则 C 层对目标 O 层的权重 W0 可知,七项准则是按顺序依次排列的,对目标决策的影响是不同的,而且前四项对目标决策起着决定性作用,即水平指标主要体现在前四项上.(1) 最佳组队原则设 mi(x)表示队员 x 的第 i 项水平指标,M i(x,y,z)表示由队员 x,y,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)=