數(shù)學(xué)建模模版之接力賽選拔及選課問題

分派問題4.4

接力隊選拔和選課策略若干項任務(wù)分給一些候選人來完成，每人的專長不同，完成每項任務(wù)取得的效益或需要的資源就不同，如何分派任務(wù)使獲得的總效益最大，或付出的總資源最少。若干種策略供選擇，不同的策略得到的收益或付出的成本不同，各個策略之間有相互制約關(guān)系，如何在滿足一定條件下作出決擇，使得收益最大或成本最小。丁的蛙泳成績退步到1’15”2；戊的自由泳成績進(jìn)步到57”5,組成接力隊的方案是否應(yīng)該調(diào)整？如何選拔隊員組成4100米混合泳接力隊?例1混合泳接力隊的選拔

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”45名候選人的百米成績窮舉法：組成接力隊的方案共有5!=120種。目標(biāo)函數(shù)若選擇隊員i參加泳姿j的比賽，記xij=1,否則記xij=0

0-1規(guī)劃模型

cij(秒)~隊員i

第j種泳姿的百米成績約束條件每人最多入選泳姿之一

ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每種泳姿有且只有1人模型求解

最優(yōu)解：x14=x21=x32=x43=1,其它變量為0;成績?yōu)?53.2(秒)=4’13”2MIN66.8x11+75.6x12+87x13+58.6x14+……+67.4x51+71x52+83.8x53+62.4x54SUBJECTTOx11+x12+x13+x14<=1

……x41+x42+x43+x44<=1x11+x21+x31+x41+x51=1

……x14+x24+x34+x44+x54=1ENDINT20

輸入LINDO求解

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”4甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.丁蛙泳c43

=69.675.2，戊自由泳c54=62.4

57.5,方案是否調(diào)整？敏感性分析？乙~蝶泳、丙~仰泳、丁~蛙泳、戊~自由泳IP規(guī)劃一般沒有與LP規(guī)劃相類似的理論，LINDO輸出的敏感性分析結(jié)果通常是沒有意義的。最優(yōu)解：x21=x32=x43=x51=1,成績?yōu)?’17”7c43,c54

的新數(shù)據(jù)重新輸入模型，用LINDO求解指派(Assignment)問題：每項任務(wù)有且只有一人承擔(dān)，每人只能承擔(dān)一項，效益不同，怎樣分派使總效益最大.討論甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.原方案為了選修課程門數(shù)最少，應(yīng)學(xué)習(xí)哪些課程？

例2選課策略要求至少選兩門數(shù)學(xué)課、三門運籌學(xué)課和兩門計算機課課號課名學(xué)分所屬類別先修課要求1微積分5數(shù)學(xué)

2線性代數(shù)4數(shù)學(xué)

3最優(yōu)化方法4數(shù)學(xué)；運籌學(xué)微積分；線性代數(shù)4數(shù)據(jù)結(jié)構(gòu)3數(shù)學(xué)；計算機計算機編程5應(yīng)用統(tǒng)計4數(shù)學(xué)；運籌學(xué)微積分；線性代數(shù)6計算機模擬3計算機；運籌學(xué)計算機編程7計算機編程2計算機

8預(yù)測理論2運籌學(xué)應(yīng)用統(tǒng)計9數(shù)學(xué)實驗3運籌學(xué)；計算機微積分；線性代數(shù)選修課程最少，且學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程？

0-1規(guī)劃模型

決策變量

目標(biāo)函數(shù)

xi=1~選修課號i的課程（xi=0~不選）

選修課程總數(shù)最少約束條件最少2門數(shù)學(xué)課，3門運籌學(xué)課，2門計算機課。

課號課名所屬類別1微積分?jǐn)?shù)學(xué)2線性代數(shù)數(shù)學(xué)3最優(yōu)化方法數(shù)學(xué)；運籌學(xué)4數(shù)據(jù)結(jié)構(gòu)數(shù)學(xué)；計算機5應(yīng)用統(tǒng)計數(shù)學(xué)；運籌學(xué)6計算機模擬計算機；運籌學(xué)7計算機編程計算機8預(yù)測理論運籌學(xué)9數(shù)學(xué)實驗運籌學(xué)；計算機先修課程要求最優(yōu)解：

x1=x2=x3=x6=x7=x9=1,其它為0；6門課程，總學(xué)分210-1規(guī)劃模型

約束條件x3=1必有x1=x2=1模型求解（LINDO）課號課名先修課要求1微積分

2線性代數(shù)

3最優(yōu)化方法微積分；線性代數(shù)4數(shù)據(jù)結(jié)構(gòu)計算機編程5應(yīng)用統(tǒng)計微積分；線性代數(shù)6計算機模擬計算機編程7計算機編程

8預(yù)測理論應(yīng)用統(tǒng)計9數(shù)學(xué)實驗微積分；線性代數(shù)學(xué)分最多多目標(biāo)優(yōu)化的處理方法：化成單目標(biāo)優(yōu)化。兩目標(biāo)(多目標(biāo))規(guī)劃

討論：選修課程最少，學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程？課程最少

以學(xué)分最多為目標(biāo)，不管課程多少。

以課程最少為目標(biāo)，不管學(xué)分多少。最優(yōu)解如上，6門課程，總學(xué)分21。最優(yōu)解顯然是選修所有9門課程。多目標(biāo)規(guī)劃

在課程最少的前提下以學(xué)分最多為目標(biāo)。最優(yōu)解：

x1=x2=x3=x5=x7=x9=1,其它為0；總學(xué)分由21增至22。注意：最優(yōu)解不唯一！課號課名學(xué)分1微積分52線性代數(shù)43最優(yōu)化方法44數(shù)據(jù)結(jié)構(gòu)35應(yīng)用統(tǒng)計46計算機模擬37計算機編程28預(yù)測理論29數(shù)學(xué)實驗3LINDO無法告訴優(yōu)化問題的解是否唯一?？蓪9=1易為x6=1增加約束，以學(xué)分最多為目標(biāo)求解。多目標(biāo)規(guī)劃

對學(xué)分?jǐn)?shù)和課程數(shù)加權(quán)形成一個目標(biāo)，如三七開。最優(yōu)解：

x1=x2=x3=x4=x5=x6=x7=x9=1，其它為0；總學(xué)分28。課號課名學(xué)分1微積分52線性代數(shù)43最優(yōu)化方法44數(shù)