混合泳接力队的选拔

例1：混合泳接力队的选拔 问题：某班准备从5名游泳队员中选择四人组成接力队，参加学校的混合泳接力队比赛。5名队员4种泳姿的百米平均成绩如表6所示，现问如何选拔队员组成接力队？ 甲乙丙丁戊蝶泳66.857.2787067.4仰泳75.66667.874.271蛙泳8766.484.669.683.8自由泳58.65359.457.262.4问题分析：从5名队员中选出4人组成接力队，每人一种泳姿，且4人的泳姿各不同，使得接力队的成绩最好。容易想到的一个办法是穷举法，组成接力队的方案共有120种，逐一计算并作比较，即可找出最优方案。显然这不是解决这类问题的好办法，随着问题规模的变大，穷举法的计算量将是无法接受的。可以用01变量表示一个队员是否入选接力队，从而建立这个问题的01规划模型，借助于LINDO软件求解。模型的建立与求解：记甲乙丙丁分别为队员i=1,2,3,4,5;记蝶泳，仰泳，蛙泳，自由泳分别为泳姿j=1,2,3,4;记队员i的第j种泳姿的百米最好成绩为cij（s）,即有：12345166.857.2787067.4275.66667.874.27138766.484.669.683.8458.65359.457.262.4引入01变量，若选择队员参加泳姿的比赛，记1，否则记0.根据组成接力队的要求，应该满足两个约束条件：第一：每人最多入选4种泳姿之一，即对于1，2，3，4，5，应有第二：每种泳姿必须有1人而且只能有1人入选，即对于1，2，3，4，应有综上，这个问题的01规划模型为：将题目所给数据代入这一模型，并输入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.4x54st 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=1endint 20 1) 253.2000 VARIABLE VALUE REDUCED COST X11 0. 66. X12 0. 75. X13 0. 87. X14 1. 58. X21 1. 57. X22 0. 66. X23 0. 66. X24 0. 53. X31 0. 78. X32 1. 67. X33 0. 84. X34 0. 59. X41 0. 70. X42 0. 74. X43 1. 69. X44 0. 57. X51 0. 67. X52 0. 71. X53 0. 83. X54 0. 62. ROW SLACK OR SURPLUS DUAL PRICES 2) 0. 0. 3) 0. 0. 4) 0. 0. 5) 0. 0. 6) 1. 0. 7) 0. 0. 8) 0. 0. 9) 0. 0. 10) 0. 0. NO. ITERATIONS= 20 BRANCHES= 0 DETERM.= 1.000E 0最后求解得到的结果为：1，其他变量为0，成绩为253.2000，即应当选派甲乙丙丁4人组成接力队，分别参加自由泳，蝶泳，仰泳，蛙泳的比赛。讨论：考虑到丁戊最近的状态，由原来的69.4变为75.2，由原来的62.4变为57.5，讨论对结果的影响。现在我们用新数据重新输入模型在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.5x54st 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=1endint 20 1) 257.7000 VARIABLE VALUE REDUCED COST X11 0. 66. X12 0. 75. X13 0. 87. X14 0. 58. X21 1. 57. X22 0. 66. X23 0. 66. X24 0. 53. X31 0. 78. X32 1. 67. X33 0. 84. X34 0. 59. X41 0. 70. X42 0. 74. X43 1. 75. X44 0. 57. X51 0. 67. X52 0. 71. X53 0. 83. X54 1. 57. ROW SLACK OR SURPLUS DUAL PRICES 2) 1. 0. 3) 0. 0. 4) 0. 0. 5) 0. 0. 6) 0. 0. 7) 0. 0. 8) 0. 0.