数值分析---组队问题

《数值分析---组队问题》由会员分享，可在线阅读，更多相关《数值分析---组队问题（9页珍藏版）》请在金锄头文库上搜索。

1、1数学建模参赛的组队问题数学建模参赛的组队问题摘要摘要队员的组队问题是历来数学建模的一大难题。本次建模中要解决的就是参赛队员的组队问题，在本次建立的模型中用权重的方法得到队员的综合能力量化值，主要用非线性规划方法建立模型，并且用Excel分析数据，LINGO编程，得到所需数据。针对问题一，如何组队，使得每队的实力相当，队员的4个条件按相应的权重在Excel中用记权型法得到30名队员的综合能力（见文中表1） 。以每队队员的综合能力指标的平均值与所有队员的综合能力指标的平均值的差值的平方为目标函数建立第一个非线性规划模型，再结合题目中不同性别、不同学院、不同专业的约束条件求目标函数的最小值。针对问

2、题二，如何组队使获奖最大化，根据表中各队员的各项能力指标以及相应的权重建立以总的竞赛技术水平（包括所有队员在内）为目标函数的第二个非线性规划模型，再结合不同性别、不同学院、不同专业等约束条件求目标函数的最大值。针对问题三，如果考虑团队合作意识这一因素，如何建立模型。鉴于团队合作意识关系到各个团队能力的发挥程度，因此各队员的各项能力指标都要乘以相应的团队合作意识量化值，经过如此处理后得到的数据方可在问题一和问题二中使用。关键词关键词：权重，非线性规划，权重，非线性规划，LINGOLINGO，ExcelExcel处理数据，处理数据，显隐性显隐性 2一、问题重述一、问题重述河海大学常州校区每年都会有

3、一定数量的学生参加全国大学生数学建模比 赛，为此，数理部每年暑期将会对学生进行培训，最后选拔出参赛的队员。选 拔条件为：思维活跃、编程能力强、熟练的写作技巧、良好团队合作意识。 这是一个最优组队的问题。现有一批已经选拔出来的学生的相关信息，包 括：编程、想法、写作、数学能力等（见附表 1） 。根据所给的信息，进行组队， 每队三人，组队原则如下： 1) 尽可能地不同学院、不同性别； 2) 如果同一学院，尽可能地不同专业； 3) 每个队伍中，至少一个人能胜任编程、想法、写作中的一项。 在上述三个要求下，实现下面三个问题的模型： 1、如何组队，使得每队的实力相当； 2、当考虑到获奖最大化时，如何组队

4、； 3、数据中没有给出团队合作意识的量化数据，问，如果考虑团队合作意识这一 因素，如何建立模型。二、问题分析二、问题分析问题一，要求每队实力相当，即每队的综合能力水平相当，即每个队的三 个队员的平均综合水平与所有队员的平均综合水平之间的差最小。结合每队队 员要符合不同学院、不同性别、不同专业的条件，建立目标函数，求最小值。 问题二，要求获奖最大化，每队3名同学都具备4种能力，但能力指标不同， 只有某种能力在队内最高才能在竞赛技术水平中得以体现，我们称得以体现的 能力为显性的, 得不到体现的能力为隐性的。然后以总的最高竞赛技术水平为 目标，建立目标函数，求最大值。 问题三，要求考虑团队合作意识，

5、因为个人能力的发挥受团队合作意识的 影响，所以各队员的各项能力指标都要乘以相应的团队合作意识量化值方可得 到各队员所能发挥的各项能力的量化值。三、符号说明三、符号说明符号说明ijkx第 个队员的第种能力在第个队中的显ijk 隐性ijc第 个队员的第种能力指标ijikw第 个队员的综合能力在第个队中的显隐ik 性im第 个队员的学院ijp第种能力在竞赛技术水平中的权重j3ic第 个队员的综合能力指标ix30名队员的综合能力指标的平均值四、模型的假设四、模型的假设1、假设问题给出的数据均为可供分析的可靠数据，不存在错误数据； 2、假设每个队员在参赛以前接受相同的培训，相同的外部环境，在参赛过程中

6、不考虑随机因素并且个人能力可完全发挥； 3、假设题中的 4 个能力指标的影响程度是逐渐升高的； 4、假设各个队之间在参赛中相互独立，不相互影响； 5、假设个人实力由其综合能力来评定； 6、假设每队队员具有互补性，即一个队的水平为最高者的水平； 五、模型建立及求解五、模型建立及求解1 1、问题一模型的建立及求解问题一模型的建立及求解设为第种能力在竞赛技术水平中的权重，则jpj，其中 0.1,0.2,0.3,0.4T jMp1,2,3,4j （1） 依权重可用 Excel 求得各个队员的综合能力，见表 1。表 1 30 名队员的综合能力指标及其平均值根据实际情况和对问题的理解，组队遵循以下原则：4

7、(1) 每组的队员应尽可能地不同性别。由于所给 30 名队员中有 8 名女生和 22名男生，为了满足尽可能不同性别的要求，则每组至多有一名女生。 为il第 个队员的性别，值为 0 表示是男，值为 1 表示女；表示第 个队员iikwi的综合能力在第个队中的显隐性，值为 1 表示显性，值为 0 表示隐性；k 则1,1,2,.,10iik il wk（2） (2) 每组的队员应尽可能地不同学院不同专业。由于所给30名队员中只有一名 为商学院，17名为机电学院，所以每个队中须有一名或两名机电学院学生，用表示第 个队员的学院，值为1表示机电学院，值为0表示计信学院或imi商学院；则12,1,2,.,10

8、iik im wk（3） （3）每个队有三个人，则3,1,2,.,10ik iwk（4） （4）每个人参与且只能参与一个队，则1,1,2,.,30ik kwi（5） 我们的目标是找到一种组队，使每队队员综合能力指标的平均值与所有队员综合能力指标的平均值（即）的差值最小，因此我们建立了如下的目标函x数：222i3iikiikiik kkikiLc wxl wm w 1,2,.,30;1,2,.,10ik（6） 的值最小时的组队方式即为每队实力相当的组队方式。L 综合以上目标和原则，可得以下非线性规划模型：222 3iikiikiik kikikiMINLc wxl wm w 1,2,.,30;1

9、,2,.,10ik5S.T. 0,1ikw 3,1,2,.,10ik iwk1,1,2,.,30ik kwi1,1,2,.,10iik il wk12,1,2,.,10iik im wk根据上述模型，我们使用 LINGO 软件进行求解(具体程序见附表中程序 1)， 结果如下： 目标函数的最小值为39.441； 组队情况见表2。 表2 问题一的组队结果 组队序 号队员1队员2队员31FUA1 2KNS 3DHM 4BIX 5COA2 6TZA4 7EQW 8PYA3 9GRV 10AJL2、问题二模型的建立及求解问题二模型的建立及求解 共有30名队员组队参赛，按照大学生数学建模竞赛的要求，每3人

10、组成一队，共 计10队。每队3名同学都具备4种能力，但能力指标不同，只有某种能力在队内 最高才能在竞赛技术水平中得以体现，我们不妨称得以体现的能力为显性的。 为方便表述，设如下的随机变量：表示第 队员的第种能力在第个队中的显隐性，值为1表示显性，值为0ijkxijk表示隐性；为第 个队员的第种能力指标；ijcij为第种能力在竞赛技术水平中的权重；jpj； 0.1,0.2,0.3,0.4T jMp6其中1,2,.,30;1,2,3,4;1,2,.,10ijk则10个队总的竞赛技术水平可以表示为：jijijk ijkSp c x（7） 我们的目标是找到一种组队，使S最大。 根据实际情况和对问题的理

11、解，组队遵循以下原则： (1)每个队都有4种能力呈显性；则4ijk ijx1,2,.,10k （8） (2)1个队员只能参与1个队，本原则可以理解为一个队员的能力只能在一个队中 呈显性，且多种能力可以同时呈显性，设 为定值,本原则可以表述为：i19ijk kjx1,2,.,30i （9） (3)每个队的每种能力只能有一个队员呈显性；则1ijk ix1,2,3,4j 1,2,.,10k （10）(4)每个队有3个人，取1意味着第 个队员参与了第个队，本原则可以表ijkxik述为：127ijk ijx1,2,.,10k （11）综合以上目标和原则，可得以下非线性规划模型： MAXjijijk ij

12、kSp c xS.T.4ijk ijx1,2,.,10k 19ijk kjx1,2,.,30i 1ijk ix1,2,3,4j 1,2,.,10k 127ijk ijx1,2,.,10k 7 0,1ijkx1iijk il x1,2,.,30i 2iijk im x1,2,.,30i 根据上述模型，我们使用 LINGO 软件进行求解（具体程序见附表中程序 2） ， 结果如下： 目标函数的最大值为90.8； 组队情况见表3。表3 问题二的组队结果 组队序号队员1队员2队员3 1EJO 2GIT 3DA2A4 4FQS 5HXY 6BKV 7RA3U8MNW 9PZA1 10ACL六、模型结果分析

13、六、模型结果分析（1 1）结果的合理性）结果的合理性 由问题一的组队结果可以看出，最终每队队员总体水平实力相当，且基本上满 足每组组员不同性别、不同学院、不同专业等约束条件。 由问题二的组队结果可以看出，在考虑每队组员性别、学院以及专业的基础上， 整个团队的实力最高，及获奖得到了最大化。七、模型优点七、模型优点优点优点： （1）我们用权重的方法得到队员的综合能力量化值使求解得到简化，进而 能够在计算机上得到满意的解。 （2）问题一、二采用的模型形式统一，便于推广，可借助于优化计算软件 进行计算，适于解决大规模问题，具有实际意义。并且其结果表述更为直观、 清晰。8参考文献：参考文献：1 韩中庚，

14、最佳组队方案与模型J，数学的实践与认识，1997；(4) 2王磊,最佳组队模型的研究，武汉船舶职业技术学院学报，6 期，2009 年 6 月； 3 袁新生，LINGO和EXCEL在数学建模中的应用M，北京：科学出版社， 2007； 4吴祈宗，运筹学与最优化方法 北京：机械工业出版社，2003 年； 5李继成，数学实验，西安：西安交通大学出版社，2003 年；附录附录表 1 30 名队员的各项能力指标程序1：model:9title question1; sets: people/1.30/:c,l,m; team/1.10/; link(people,team):w; endsets data

15、: c=ole(D:/data.xls,ci); l=ole(D:/data.xls,li); m=ole(D:/data.xls,mi); enddata objmin=sum(team(k):(sum(people(i):c(i)*w(i,k)- 25.03)2+(sum(people(i):l(i)*w(i,k)2+(sum(people(i):m(i)*w(i,k) 2); FOR(people(i):sum(team(k):w(i,k)=1); for(team(k):sum(people(i):w(i,k)=3); for(team(k):sum(people(i):l(i)*w(i,k)=1); for(link:bin(w); End程序2：model: title question2; sets: people/1.30/:l,m; team/1.10/; bility/1.4/:p; link1(people,bility,team):x; link2(people,bility):c; endsets data: p=o