混合泳接力队的选拔
例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
丙,分别为蝶泳,蛙泳,自由泳,仰泳。