混合泳接力隊(duì)的選拔

1、例1：混合泳接力隊(duì)的選拔 問題：某班準(zhǔn)備從5名游泳隊(duì)員中選擇四人組成接力隊(duì)，參加學(xué)校的混合泳接力隊(duì)比賽。5名隊(duì)員4種泳姿的百米平均成績?nèi)绫?所示，現(xiàn)問如何選拔隊(duì)員組成接力隊(duì)？ 甲乙丙丁戊蝶泳66.857.2787067.4仰泳75.66667.874.271蛙泳8766.484.669.683.8自由泳58.65359.457.262.4問題分析：從5名隊(duì)員中選出4人組成接力隊(duì)，每人一種泳姿，且4人的泳姿各不同，使得接力隊(duì)的成績最好。容易想到的一個(gè)辦法是窮舉法，組成接力隊(duì)的方案共有120種，逐一計(jì)算并作比較，即可找出最優(yōu)方案。顯然這不是解決這類問題的好辦法，隨著問題規(guī)模的變大，窮舉法的計(jì)算量將

2、是無法接受的?？梢杂?1變量表示一個(gè)隊(duì)員是否入選接力隊(duì)，從而建立這個(gè)問題的01規(guī)劃模型，借助于LINDO軟件求解。模型的建立與求解：記甲乙丙丁分別為隊(duì)員i=1,2,3,4,5;記蝶泳，仰泳，蛙泳，自由泳分別為泳姿j=1,2,3,4;記隊(duì)員i的第j種泳姿的百米最好成績?yōu)閏ij（s）,即有：12345166.857.2787067.4275.66667.874.27138766.484.669.683.8458.65359.457.262.4引入01變量，若選擇隊(duì)員參加泳姿的比賽，記1，否則記0.根據(jù)組成接力隊(duì)的要求，應(yīng)該滿足兩個(gè)約束條件：第一：每人最多入選4種泳姿之一，即對(duì)于1，2，3，4，5，

3、應(yīng)有第二：每種泳姿必須有1人而且只能有1人入選，即對(duì)于1，2，3，4，應(yīng)有綜上，這個(gè)問題的01規(guī)劃模型為：將題目所給數(shù)據(jù)代入這一模型，并輸入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

4、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.000000 66.800003 X12 0.000000 75.599998 X13 0.000000 87.000000 X14 1.000000 58.599998 X21 1.000000 57.200001 X22

5、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

6、.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 DETER

7、M.= 1.000E 0最后求解得到的結(jié)果為：1，其他變量為0，成績?yōu)?53.2000，即應(yīng)當(dāng)選派甲乙丙丁4人組成接力隊(duì)，分別參加自由泳，蝶泳，仰泳，蛙泳的比賽。討論：考慮到丁戊最近的狀態(tài)，由原來的69.4變?yōu)?5.2，由原來的62.4變?yōu)?7.5，討論對(duì)結(jié)果的影響?，F(xiàn)在我們用新數(shù)據(jù)重新輸入模型在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

8、.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.000000 66.800003 X12 0.000000 7

9、5.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.00