混合泳接力队的选拔的答案

P108页答案

例1 混合泳接力队的选拔

问题 某班准备从5名游泳队员中选择4人组成接力队，参加学校的4×100m混合泳接力比赛。5名队员4种泳姿的百米平均成绩如表6所示，问应如何选拔队员组成接力队？ 如果最近队员丁的蛙泳成绩有较大退步，只有1’15’’2;而队员戊经过艰苦训练自由泳成绩有所进步,达到57’5,组成接力队的方案是否应该调整? 蝶泳 仰泳 蛙泳 自由泳 甲 1’06’’8 1’15’’6 1’27’’ 58’’6 乙 57’2 1’06’’ 1’06’’4 53’’ 丙 1’18’’ 1’07’’8 1’24’’6 59’’4 丁 1’10’’ 1’14’’2 1’09’’6 57’’2 戊 1’07’’4 1’11’’ 1’23’’8 1’02’’4 模型的建立 记甲乙丙丁戊分别为队员i=1,2,3,4,5;记蝶泳`仰泳`蛙泳`自由泳分别为泳姿j=1,2,3,4.记队员i的第j种泳姿的百米最好成绩为cij(s),即有 cij j=1 j=2 j=3 i=1 66.8 75.6 87 i=2 57.2 66 66.4 i=3 78 67.8 84.6 i=4 70 74.2 69.6 i=5 67.4 71 83.8 j=4 58.6 53 59.4 57.2 62.4 引入0-1变量xij，若选择队员i参加泳姿j的比赛，记xij=1,否则记xij=0。根据组成接力队的要求，ij应该满足两个约束条件：

4（1）、每人最多只能入选4种泳姿之一，即对于i=1,2,3,4,5,应有?xij??1；

j?15（2）、每种泳姿必须有1人而且只能有1人入选，即对于j=1,2,3,4,应有?xij?1

i?1当队员i入选泳姿j时，cijxij表示他（她）的成绩，否则cijxij=0。

45目标函数：Z=??cijxij

j?1i?1综上，0-1规划模型为：

45Min Z=?4?cijxij

j?1i?1S.t.

?xijj?15??1,i=1,2,3,4,5

?xij?1,j=1,2,3,4

i?1 Xij={0,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 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 X11 0.000000 X12 0.000000 X13 0.000000 X14 1.000000 X21 1.000000 X22 0.000000

X23

0.000000 X24 0.000000 X31 0.000000 X32 1.000000 X33 0.000000 X34 0.000000 X41 0.000000 X42 0.000000 X43 1.000000 X44 0.000000 X51 0.000000 X52 0.000000 X53 0.000000 X54 0.000000

ROW SLACK OR SURPLUS 2) 0.000000 3) 0.000000 4) 0.000000 REDUCED COST 66.800003 75.599998 87.000000 58.599998 57.200001 66.000000 66.400002

53.000000 78.000000 67.800003 84.599998 59.400002 70.000000 74.199997 69.599998 57.200001 67.400002 71.000000 83.800003 62.400002 DUAL PRICES 0.000000 0.000000 0.000000

5) 0.000000 0.000000

NO. ITERATIONS= 12

BRANCHES= 0 DETERM.= 1.000E 0

问题解决：考虑丁、戊最近的状况，c43由原来的69.6s变为75.2s，c54由原来的62.4s变为57.5s,则 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 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

6) 7) 8) 9)

0.000000 0.000000 0.000000 0.000000

0.000000 0.000000 0.000000 0.000000

X44 0.000000 57.200001

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

NO. ITERATIONS= 11

BRANCHES= 0 DETERM.= 1.000E 0 例2 选课策略 某学校规定，运筹学专业的学生毕业时必须至少学习过两门数学课、三门运筹学课和两门计算机课。这些课程的编号、名称、学分、所属类别和先修课要求如表7所示。那么，毕业时学生最少可以学习这些课程中的那些课程.

如果某学生既希望选修课的数量少，又希望所获得的学分多，他可以选修那些课程？ 课程编号 1 2 3 4 5 6 7 8 9 模型的建立 课程名称 微积分 线性代数 最优化方法 数据结构 应用统计 计算机模拟 计算机编程 预测理论 数学实验 学分 5 4 4 3 4 3 2 2 3 所属类别 数学 数学 数学；运筹学 数学；计算机 数学；运筹学 先修课要求 微积分；线性代数 计算机编程 微积分；线性代数 X51 X52 X53 X54

0.000000 0.000000 0.000000 1.000000

67.400002 71.000000 83.800003 57.500000

计算机；运筹学 计算机编程 计算机 运筹学 应用统计 运筹学；计算机 微积分；线性代数 9目标函数：Min Z=?xi

i?1每人最少要学习2门数学课、3门运筹学课和2门计算机课；某些课程有先修课程的要求，则约束条件：

x1+x2+x3+x4+x5>=2 x3+x5+x6+x8+x9>=3 x4+x6+x7+x9>=2 2x3-x1-x2<=0

x4-x7<=0

2x5-x1-x2<=0 x6-x7<=0 x8-x5<=0 2x9-x1-x2<=0

LINDO输入软件：

Min x1+x2+x3+x4+x5+x6+x7+x8+x9 st

-x1-x2-x3-x4-x5<=-2 -x3-x5-x6-x8-x9<=-3 -x4-x6-x7-x9<=-2 2x3-x1-x2<=0 x4-x7<=0 2x5-x1-x2<=0 x6-x7<=0 x8-x5<=0 2x9-x1-x2<=0 end int 9

输出结果：

LP OPTIMUM FOUND AT STEP 10

OBJECTIVE VALUE = 4.85714293

NEW INTEGER SOLUTION OF 6.00000000 AT BRANCH 10

RE-INSTALLING BEST SOLUTION...

OBJECTIVE FUNCTION VALUE

1) 6.000000

VARIABLE VALUE REDUCED COST X1 1.000000 1.000000 X2 1.000000 1.000000 X3 1.000000 1.000000 X4 0.000000 1.000000 X5 0.000000 1.000000 X6 1.000000 1.000000 X7 1.000000 1.000000 X8 0.000000 1.000000 X9 1.000000 1.000000

0 PIVOT

ROW SLACK OR SURPLUS DUAL PRICES 2) 1.000000 0.000000 3) 0.000000 0.000000 4) 1.000000 0.000000

5)

0.000000

0.000000

6) 1.000000 0.000000 7) 2.000000 0.000000 8) 0.000000 0.000000 9) 0.000000 0.000000 10) 0.000000 0.000000

NO. ITERATIONS= 10

BRANCHES= 0 DETERM.= 1.000E 0 问题

如果只考虑获得尽可能多的学分，而不管所修课程得多少，则 目标函数：Max W= 5x1+4x2+4x3+3x4+4x5+3x6+2x7+2x8+3x9 约束条件不变

LINDO输入软件：

MAX 5x1+4x2+4x3+3x4+4x5+3x6+2x7+2x8+3x9 st

-x1-x2-x3-x4-x5<=-2 -x3-x5-x6-x8-x9<=-3 -x4-x6-x7-x9<=-2 2x3-x1-x2<=0 x4-x7<=0 2x5-x1-x2<=0 x6-x7<=0 x8-x5<=0 2x9-x1-x2<=0 end int 9

输出结果：

LP OPTIMUM FOUND AT STEP 9 OBJECTIVE VALUE = 30.0000000

NEW INTEGER SOLUTION OF 30.0000000 AT BRANCH 9

RE-INSTALLING BEST SOLUTION...

OBJECTIVE FUNCTION VALUE

1) 30.00000

0 PIVOT VARIABLE VALUE REDUCED COST

X1 X2 X3 X4

1.000000 -5.000000 1.000000 -4.000000 1.000000 -4.000000 1.000000 -3.000000

X5 1.000000 -4.000000 X6 1.000000 -3.000000 X7 1.000000 -2.000000 X8 1.000000 -2.000000 X9 1.000000 -3.000000

ROW SLACK OR SURPLUS DUAL PRICES 2) 3.000000 0.000000 3) 2.000000 0.000000 4) 2.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= 9

BRANCHES= 0 DETERM.= 1.000E 0

如果是以选修课程数最少为基本的前提，目标函数不变，增加约束条件：

9?xij?1?6

LINDO输入软件：

MAX 5x1+4x2+4x3+3x4+4x5+3x6+2x7+2x8+3x9 st

-x1-x2-x3-x4-x5<=-2 -x3-x5-x6-x8-x9<=-3 -x4-x6-x7-x9<=-2 2x3-x1-x2<=0 x4-x7<=0 2x5-x1-x2<=0 x6-x7<=0 x8-x5<=0 2x9-x1-x2<=0

x1+x2+x3+x4+x5+x6+x7+x8+x9=6 end int 9

输出结果：

LP OPTIMUM FOUND AT STEP 9 OBJECTIVE VALUE = 22.6666660

NEW INTEGER SOLUTION OF 22.0000000 AT BRANCH 0 PIVOT 9

RE-INSTALLING BEST SOLUTION...

OBJECTIVE FUNCTION VALUE

1) 22.00000

VARIABLE VALUE REDUCED COST X1 1.000000 -5.000000 X2 1.000000 -4.000000 X3 1.000000 -4.000000 X4 0.000000 -3.000000 X5 1.000000 -4.000000 X6 1.000000 -3.000000 X7 1.000000 -2.000000 X8 0.000000 -2.000000 X9 0.000000 -3.000000

ROW SLACK OR SURPLUS DUAL PRICES 2) 2.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) 1.000000 0.000000 10) 2.000000 0.000000 11) 0.000000 0.000000

NO. ITERATIONS= 9

BRANCHES= 0 DETERM.= 1.000E 0 如果只考虑学分最多或以课程最少为前提，而是觉得学分数和课程数这两个目标大致上应该三七开，则此时目标函数为：

Min Y=0.7Z-0.3W

=-0.8x1-0.5x2-0.5x3-0.2x4-0.5x5-0.2x6+0.1x7+0.1x8-0.2x9

LINDO输入软件：

MIN -0.8x1-0.5x2-0.5x3-0.2x4-0.5x5-0.2x6+0.1x7+0.1x8-0.2x9 st

-x1-x2-x3-x4-x5<=-2 -x3-x5-x6-x8-x9<=-3 -x4-x6-x7-x9<=-2 2x3-x1-x2<=0 x4-x7<=0 2x5-x1-x2<=0 x6-x7<=0 x8-x5<=0 2x9-x1-x2<=0 end int 9

输出结果：

LP OPTIMUM FOUND AT STEP 9 OBJECTIVE VALUE = -2.79999995

NEW INTEGER SOLUTION OF -2.80000019 AT BRANCH RE-INSTALLING BEST SOLUTION...

OBJECTIVE FUNCTION VALUE

1) -2.800000

VARIABLE VALUE REDUCED COST X1 1.000000 -0.800000 X2 1.000000 -0.500000 X3 1.000000 -0.500000 X4 1.000000 -0.200000 X5 1.000000 -0.500000 X6 1.000000 -0.200000 X7 1.000000 0.100000 X8 0.000000 0.100000 X9 1.000000 -0.200000

ROW SLACK OR SURPLUS DUAL PRICES 2) 3.000000 0.000000 3) 1.000000 0.000000 4) 2.000000 0.000000 5) 0.000000 0.000000 6) 0.000000 0.000000

0 PIVOT 9 7) 0.000000 0.000000 8) 0.000000 0.000000 9) 1.000000 0.000000 10) 0.000000 0.000000

NO. ITERATIONS= 9

BRANCHES= 0 DETERM.= 1.000E 0 在上面那个问题中，如果把其写为： Min Y=a1Z-a2W

当我们取a1=0.2,a2=0.78时输入目标函数

输入软件：

输出结果：

本文来源：https://www.bwwdw.com/article/i1ua.html