《混合泳接力队选拔模型3.docx》由会员分享，可在线阅读，更多相关《混合泳接力队选拔模型3.docx（12页珍藏版）》请在金锄头文库上搜索。
1、混合泳接力队选拔模型18组：张鹏举 方志成 汤虹2015.03.29摘要从5名游泳队员中选择4人组成接力队，参加学校的4*100m混合泳接力比赛。要求每人一种泳姿，且4人的泳姿各不相同，使接力队的成绩最好。容易想到的一个办法是穷举法，组成接力队的方案有5！=120种，逐一计算并作比较，即可找出最优方案，显然这种方法过于繁琐，耗时太多，且随着问题规模的变大，穷举法的计算量将是无法接受的。所以为更加科学地解决混合泳接力队选拔这个问题，本文运用0-1规划模型，采用矩阵先把5名游泳队员4种泳姿的成绩统一起来，便于计算；再利用条件“每人一种泳姿，且4人的泳姿各不相同”，我们采用只有0和1组成的矩阵；然后
2、只要把这两个矩阵相乘，就是所求接力队的成绩；最后结合LINGO软件求解得出最好的方案。对于问题一，直接采用这种方法，就可找出最佳方案；问题二只是在问题一的基础上，改变了其中两个数据，用一下LINGO程序，同样可以很快地找出最佳方案。关键词：混合泳接力队选拔 0-1规划模型 矩阵 LINGO软件 11一 问题重述某班准备从5名有用队员中选择4人组成接力队，参加学校的4*100m混合泳接力比赛。5名队员4种泳姿的百米平均成绩如表1所示。问题一：如何选拔队员组成接力队，使得接力队的成绩最好？问题二：如果最近队员丁的蛙泳成绩有较大退步，只有1152；而队员戊经过艰苦训练自由泳有所进步，达到575，组成
3、接力队的方案是否应该调整？表1 5名队员4种泳姿的百米平均成绩甲乙丙丁戊蝶泳10685721181101074仰泳115610610781142111蛙泳1271064124610961238自由泳586535945721024二 问题分析从5名队员中选出4人组成接力队，每人一种泳姿，且4人的泳姿各不相同，使接力对的成绩最好。容易想到的一个办法是穷举法，组成接力队的方案有5！=120种，逐一计算并作比较，即可找出最优方案，显然这不是解决这类问题的好方法，随着问题规模的变大，穷举法的计算量将是无法接受的。可以用0-1规划表示一个队员是否入选接力队，从而建立这个问题的0-1规划模型，借助LINGO
4、数学软件求解。三 模型假设1. 假设选拔遵循公平，公正的原则。2. 假设队员在选拔时要做好充分准备，完全发挥出自己的正常水平，即排除运动员自身及外界环境的影响。3. 假设每个队员的成绩互相独立，互不影响。四 符号说明及定义符号定义i第i个队员，i=1，2，3，4，5j第j种泳姿，j=1，2，3，4cij第i个队员的第j种泳姿的百米最好成绩xij第i个 队员是否选择第j种泳姿z=j=14i=15cijxij接力队的成绩五 模型建立与求解 5.1问题一解决5.1.1建立0-1规划模型记甲、乙、丙、丁、戊分别为队员i=1，2，3，4，5；记蝶泳、仰泳、蛙泳、自由泳分别为泳姿j=1，2，3，4。记第i
5、个队员的第j种泳姿的百米最好成绩为cij（s），即有ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4引入0-1规划xij，若选择第i个队员参加第j种泳姿的比赛，记xij=1，否则记xij=0。根据组成接力队的要求，xij应该满足两个约束条件：第一，每个人最多只能入选4种泳姿之一，即对于i=1，2，3，4，5，应有j=14xij1；第二，每种泳姿必须有1人而且只能有1人入选，即对于j=1，2，3，4，应有i=15xij=1。当第i个队员入选第j种泳姿
6、时，cijxij表示他（她）的成绩，否则cijxij=0。于是接力队的成绩可表示为z=j=14i=15cijxij，这就是该问题的目标函数。综上，这个问题的0-1规划模型可写为 min z=j=14i=15cijxij s.t. j=14xij1，i=1，2，3，4，5 i=15xij=1，j=1，2，3，4 xij=0，15.1.2求解已知目标函数：min z =两矩阵相乘s.t. j=14x1j1，即x11 + x12 + x13 + x14 1j=14x2j1，即x21 + x22 + x23 + x24 1 j=14x3j1，即x31 + x32 + x33 + x34 1j=14x4
7、j1，即x41 + x42 + x43 + x44 1 j=14x5j1，即x51 + x52 + x53 + x54 1i=15xi1=1，即x11 + x21 + x31 + x41 + x51 = 1i=15xi2=1，即x12 + x22 + x32 + x42 + x52 = 1i=15xi3=1，即x13 + x23 + x33 + x43 + x53 = 1 i=15xi4=1，即x14 + x24 + x34 + x44 + x54 = 1xij = 0，1 （ i=1，2，3，4，5； j=1，2，3，4）用LINGO软件来解决：利用题目所给数据，将这一模型输入LINGO：m
8、odel:sets:person/1.5/;position/1.4/;link(person,position):c,x;endsetsdata:c = 66.8,75.6,87,58.6, 57.2,66,66.4,53, 78,67.8,84.6,59.4, 70,74.2,69.6,57.2, 67.4,71,83.8,62.4;enddatamin =sum(link:c*x);for(person(i):sum(position(j):x(i,j)=1;);for(position(i):sum(person(j):x(j,i)=1;);for(link:bin(x);end求解得
9、到结果为：x14=x21=x32=x43=1，其他变量为0，成绩为253.2s=4132。即应当甲、乙、丙、丁4人组成接力队，分别参加自由泳、蝶泳、仰泳、蛙泳的比赛。（程序输出结果见附录一）5.2问题二解决问题二考虑到丁、戊最近的状态，c43由原来的69.6s变为75.2s，c54由原来的62.4s变为57.5s，此时LINGO中所输出的敏感性分析结果通常是没有意义的。于是我们只好用c43，c54的新数据重新输入模型，为：model:sets:person/1.5/;position/1.4/;link(person,position):c,x;endsetsdata:c = 66.8,75.
10、6,87,58.6, 57.2,66,66.4,53, 78,67.8,84.6,59.4, 70,74.2,75.2,57.2, 67.4,71,83.8,57.5;enddatamin =sum(link:c*x);for(person(i):sum(position(j):x(i,j)=1;);for(position(i):sum(person(j):x(j,i)=1;);for(link:bin(x);end运用LINGO求解得： x21 = x32 = x43 = x51 = 1 ，其他变量为0，成绩为257.7s=4177。即应当乙、丙、丁、戊4人组成接力队，分别参加蝶泳、仰泳、
11、蛙泳、自由泳的比赛。（程序输出结果见附录二）六 模型的评价与推广6.1模型的评价本文中队员的选拔方案具有简单，实用，快捷等优点，避免了穷举法的大量繁琐计算，对各种大型体育赛事中大量队员的合理选拔等具有实际参考价值。 但在假设中忽略了运动员本身的情况与外界坏境对运动员发挥水平的影响，对模型运算结果的准确性也会造成一定的影响。6.2模型的推广这题属于指派问题，所以“对于有若干个任务，每项任务必须有一人且只能有一人承担，每人也只能承担其中一项，不同人员承担不同任务的收益（或成本）不同，问题是怎么样分派各项任务使总收益最大（或总成本最小）”的问题，可以建立0-1规划模型来解决这类问题。即使数据多，规模
12、大，用0-1规划模型且结合LINGO软件都能很方便很快地解决问题。参考文献1姜启，谢金星，叶俊. 数学模型（第四版）.北京：北京高等教育出版社，2011.2胡运权 运筹学习题集. 清华大学出版社，2002.3杨光亭，邱哲勇. 数学建模 .北京：高等教育出版社，2010.4杨启帆.数学建模. 北京：高等教育出版社，2011.附录一：问题一求解数据Global optimal solution found. Objective value: 253.2000 Objective bound: 253.2000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0 Model Class: PILP Total variables: 20 Nonlinear variables: 0 Integer variables: 20 Total constraints: 10 Nonlinear constraints: 0 Total nonzeros: 60 Nonlinear nonzeros: 0 Variable Value Reduced Cost C( 1, 1) 66.80000 0.000000 C( 1, 2) 75.60000 0.000000
