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

分派問題4.4

接力隊選拔和選課策略若干項任務分給一些候選人來完成，每人的專長不同，完成每項任務取得的效益或需要的資源就不同，如何分派任務使獲得的總效益最大，或付出的總資源最少。若干種策略供選擇，不同的策略得到的收益或付出的成本不同，各個策略之間有相互制約關系，如何在滿足一定條件下作出決擇，使得收益最大或成本最小。丁的蛙泳成績退步到1’15”2；戊的自由泳成績進步到57”5,組成接力隊的方案是否應該調整？如何選拔隊員組成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種。目標函數(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,方案是否調整？敏感性分析？乙~蝶泳、丙~仰泳、丁~蛙泳、戊~自由泳IP規(guī)劃一般沒有與LP規(guī)劃相類似的理論，LINDO輸出的敏感性分析結果通常是沒有意義的。最優(yōu)解：x21=x32=x43=x51=1,成績?yōu)?’17”7c43,c54

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

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

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

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

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

0-1規(guī)劃模型

決策變量

目標函數(shù)

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

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

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

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

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

2線性代數(shù)

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

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

討論：選修課程最少，學分盡量多，應學習哪些課程？課程最少

以學分最多為目標，不管課程多少。

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

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

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

對學分數(shù)和課程數(shù)加權形成一個目標，如三七開。最優(yōu)解：

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