混合泳接力队的选拔

混合泳接力队的选拔 例1:混合泳接力队的选拔 问题:某班准备从5名游泳队员中选择四人组成接力队，参加学校的混合泳接力队比赛。5名队员4种泳姿的百米平均成绩如6所示，现问如何选拔队员组成接力队, 甲 乙 丙 丁 戊 蝶泳 66.8 57.2 78 70 67.4 仰泳 75.6 66 67.8 74.2 71 蛙泳 87 66.4 84.6 69.6 83.8 自由58.6 53 59.4 57.2 62.4 泳 问题分析:从5名队员中选出4人组成接力队，每人一种泳姿，且4人的泳姿各不同，使得接力队的成绩最好。容易想到的一个办法是穷举法，组成接力队的共有120种，逐一计算并作比较，即可找出最优方案。显然这不是解决这类问题的好办法，随着问题规模的变大，穷举法的计算量将是无法接受的。 可以用0,1变量表示一个队员是否入选接力队，从而建立这个问题的0,1规划模型，借助于LINDO软件求解。 模型的建立与求解:记甲乙丙丁分别为队员i=1,2,3,4,5;记蝶泳，仰泳，蛙泳，自由泳分别为泳姿j=1,2,3,4;记队员i的第j种泳姿的百米最好成绩为cij(s),即有: ,1 ,2 ,3 ,4 ,5 iiiiic ij j,66.8 57.2 78 70 67.4 1 j,2 75.6 66 67.8 74.2 71 j,3 87 66.4 84.6 69.6 83.8 j,4 58.6 53 59.4 57.2 62.4 j引入0,1变量x，若选择队员参加泳姿的比赛，记x,1，否则记x,0.根据组成接iijijij力队的要求，x应该满足两个约束条件: ij 4 x,,1;ij第一:每人最多入选4种泳姿之一，即对于,1，2，3，4，5，应有 i,j,1 5 j第二:每种泳姿必须有1人而且只能有1人入选，即对于,1，2，3，4，应有 x,1;ij,i,1 综上，这个问题的0,1规划模型为: 45 minz,cx;ijij,,j,i,11 5 s.tx,1;j,1,2,3,4ij,i,1 4 x,,1;i,1,2,3,4,5ij,i,1 将题目所给数据代入这一模型，并输入LINDO: min 66.8x11+75.6x12+87x13+58.6x14 +57.2x21+66x22+66.4x23+53x24 +78x31+67.8x32+84.6x33+59.4x34 +70x41+74.2x42+69.6x43+57.2x44 +67.4x51+71x52+83.8x53+62.4x54 st x11+x12+x13+x14<=1 x21+x22+x23+x24<=1 x31+x32+x33+x34<=1 x41+x42+x43+x44<=1 x51+x52+x53+x54<=1 x11+x21+x31+x41+x51=1 x12+x22+x32+x42+x52=1 x13+x23+x33+x43+x53=1 x14+x24+x34+x44+x54=1 end int 20 1) 253.2000 VARIABLE VALUE REDUCED COST X11 0.000000 66.800003 X12 0.000000 75.599998 X13 0.000000 87.000000 X14 1.000000 58.599998 X21 1.000000 57.200001 X22 0.000000 66.000000 X23 0.000000 66.400002 X24 0.000000 53.000000 X31 0.000000 78.000000 X32 1.000000 67.800003 X33 0.000000 84.599998 X34 0.000000 59.400002 X41 0.000000 70.000000 X42 0.000000 74.199997 X43 1.000000 69.599998 X44 0.000000 57.200001 X51 0.000000 67.400002 X52 0.000000 71.000000 X53 0.000000 83.800003 X54 0.000000 62.400002 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 0.000000 0.000000 4) 0.000000 0.000000 5) 0.000000 0.000000 6) 1.000000 0.000000 7) 0.000000 0.000000 8) 0.000000 0.000000 9) 0.000000 0.000000 10) 0.000000 0.000000 NO. ITERATIONS= 20 BRANCHES= 0 DETERM.= 1.000E 0 最后求解得到的结果为:,,,,1，其他变量为0，成绩为253.2000，即应xxxx32431421 当选派甲乙丙丁4人组成接力队，分别参加自由泳，蝶泳，仰泳，蛙泳的比赛。 讨论:考虑到丁戊最近的状态，由原来的69.4变为75.2，由原来的62.4变为57.5，cc4354 讨论对结果的影响。现在我们用新数据重新输入模型在LINDO中求解: min 66.8x11+75.6x12+87x13+58.6x14 +57.2x21+66x22+66.4x23+53x24 +78x31+67.8x32+84.6x33+59.4x34 +70x41+74.2x42+75.2x43+57.2x44 +67.4x51+71x52+83.8x53+57.5x54 st x11+x12+x13+x14<=1 x21+x22+x23+x24<=1 x31+x32+x33+x34<=1 x41+x42+x43+x44<=1 x51+x52+x53+x54<=1 x11+x21+x31+x41+x51=1 x12+x22+x32+x42+x52=1 x13+x23+x33+x43+x53=1 x14+x24+x34+x44+x54=1 end int 20 1) 257.7000 VARIABLE VALUE REDUCED COST X11 0.000000 66.800003 X12 0.000000 75.599998 X13 0.000000 87.000000 X14 0.000000 58.599998 X21 1.000000 57.200001 X22 0.000000 66.000000 X23 0.000000 66.400002 X24 0.000000 53.000000 X31 0.000000 78.000000 X32 1.000000 67.800003 X33 0.000000 84.599998 X34 0.000000 59.400002 X41 0.000000 70.000000 X42 0.000000 74.199997 X43 1.000000 75.199997 X44 0.000000 57.200001 X51 0.000000 67.400002 X52 0.000000 71.000000 X53 0.000000 83.800003 X54 1.000000 57.500000 ROW SLACK OR SURPLUS DUAL PRICES 2) 1.000000 0.000000 3) 0.000000 0.000000 4) 0.000000 0.000000 5) 0.000000 0.000000 6) 0.000000 0.000000 7) 0.000000 0.000000 8) 0.000000 0.000000 9) 0.000000 0.000000 10) 0.000000 0.000000 NO. ITERATIONS= 11 BRANCHES= 0 DETERM.= 1.000E 0 求解得到:,,,,1，其他变量为0，成绩为257.7000。即应当选派乙丁戊xxxx51324321 丙，分别为蝶泳，蛙泳，自由泳，仰泳。