内容发布更新时间 : 2024/11/16 15:34:09星期一 下面是文章的全部内容请认真阅读。

混合泳接力队的选拔

问题

某班准备从5名游泳员中选择人组成接力队，参加学校的4×100m混合泳接力比赛。5名队员4种泳姿的百米平均成绩如表6所示，问应如何选择队员组成接力对？

如果最近队员丁的蛙泳成绩有较大退步，只有1′15″2；而队员戊经过艰苦的训练自由泳成绩有所提高，达到57″5，组成接力队的方案是否应该调整？ 甲 乙 丙 丁 戊 蝶泳 1′06″8 57″2 1′18″ 1′10″ 1′07″4 仰泳 1′15″6 1′06″ 1′07″8 1′14″2 1′11″ 蛙泳 1′27″ 1′06″4 1′24″6 1′09″6 1′23″8 自由泳 58″6 53″ 59″4 57″2 1′02″4 表6 5名队员4种泳姿的百米平均成绩

问题分析

从5名队员中选出4名组成接力队，每人一种泳姿，且4人的泳姿各不相同，使接力队的成绩最好。容易想到的一个办法是穷举法，组成接力队的方案共5！=120种，逐一计算逼供内比较，即可以得到最优方案。显然这不是解决这类问题的好方法，随着问题规模的变大，穷举法的计算量是无法接受的。

可以用0-1变量表示一个队员是否入选接力对，从而建立这个问题的0-1规划模型，借助现成的数学软件求解。

模型的建立与求解

记甲乙丙丁戊分别为队员i?1,2,3,4,5；记蝶泳、仰泳、自由泳分别为泳姿

j?1,2,3,4。记队员i的第j种泳姿的百米最好成绩为，即有

cij i?1 66.8 75.6 87 58.6 i?2 57.2 66 66.4 53 i?3 78 67.8 84.6 59.4 i?4 70 74.2 69.6 57.2 i?5 67.4 71 83.8 62.3 j?1 j?2 j?3 j?4 引入0-1变量xij，若选择队员i参加泳姿j的比赛，记xij?1，否则记xij?0。根据组成接力队的要求，xij应满足两个约束条件：

第一，每个最多只能入选4种泳姿之一，即i?1,2,3,4,5，所以?xij?1；

j?14第二，每种泳姿必须有一人而且只能有一人入选，即对于j?1,2,3,4，应有

?xi?15ij?1。

当队员i当选泳姿j时，cijxij表示他（她）的成绩，否则cijxij?0。于是接力队的成绩可以表示为：Z???cijxij，即本题的目标函数。、

j?1i?145综上，这个问题的0-1规划模型可以表示为

MinZ???cijxijj?1i?145?4??xij?1,i?1,2,3,4,5j?1 ?

5??s.t.??xij?1,j?1,2,3,4?i?1?x??0,1??ij??运用Lingo8.0计算可以得到：x14?x21?x32?x43?1,即入选队员和对应参加的泳种如下表： 甲 蝶泳 仰泳 蛙泳 自由泳 √ 乙 √ 丙 √ 丁 √ 附录 程序

SETS: S/1..5/; B/1..4/; SS(S,B):X; ENDSETS

MIN=68.8*X11+75.6*X12+87*X13+58.6*X14

+57.2*X21+66*X22+66.4*X23+53*X24 +78*X31+67.8*X32+84.6*X33+59.4*X34 +70*X41+74.2*X42+69.6*X43+57.2*X44 +67.4*X51+71*X52+83.8*X53+62.4*X54;

X11+X12+X13+X14<=1; X21+X22+X23+X24<=1; X31+X32+X33+X34<=1; X41+X42+X43+X44<=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;

@FOR(SS(I,J):@BIN(X(i,j)));

运算结果

Global optimal solution found at iteration: 0 Objective value: 253.2000

Variable Value Reduced Cost X11 0.000000 1.400000 X12 0.000000 4.600000 X13 0.000000 16.00000 X14 1.000000 0.000000 X21 1.000000 0.000000 X22 0.000000 5.200000 X23 0.000000 5.600000 X24 0.000000 4.600000 X31 0.000000 13.80000 X32 1.000000 0.000000 X33 0.000000 16.80000 X34 0.000000 4.000000 X41 0.000000 4.000000 X42 0.000000 4.600000 X43 1.000000 0.000000 X44 0.000000 0.000000 X51 0.000000 0.000000 X52 0.000000 0.000000 X53 0.000000 12.80000 X54 0.000000 3.800000