最佳組隊問題

1、最佳組隊問題的求解與分析摘要參加重大比賽前，院校如何選拔最優(yōu)秀的隊員并科學合理地組隊是各院校取得優(yōu)秀名次的關鍵。本文就此通過層次分析法建立層次結構模型（模型一），結合模型比較得出參賽的18名隊員。根據(jù)所得18名成員建立優(yōu)化模型（模型二）求解最佳競賽技術隊。接著，使用非線性規(guī)劃模型（模型三）求解整體競賽技術水平最高問題，最后，通過誤差分析得到模型四推翻模型一，同時重解模型二、三，得出優(yōu)化后的組隊分配。針對問題一，本文通過建立成對比較矩陣確定各項權重及其一致性，并通過權重計算得出淘汰隊員應為I,H。針對問題二，本文通過問題一的權重以及優(yōu)化模型求解，得出G,L,S組成的隊伍是競賽技術水平最高的最佳組

2、隊。針對問題三，本文通過非線性規(guī)劃模型，得出以下組隊方案：第一隊第二隊第三隊第四隊第五隊第六隊AEDKGCBFJMOPLNSRQT經(jīng)過模型的誤差分析，重新建立模型四，得：1. 應淘汰A、O隊員。2. 最強隊組合人員應為G,H,L3. 最佳組隊方案應如下所示：第一隊第二隊第三隊第四隊第五隊第六隊EIBCDHFJGNMISKPRQT關鍵詞層次分析法 權重 優(yōu)化模型 非線性規(guī)劃模型 一、 問題重述1.1問題背景在一年一度的我國和美國大學生數(shù)學建模競賽活動中, 任何一個參賽院校都會遇到如何選拔最優(yōu)秀的隊員和科學合理地組隊問題，因此現(xiàn)假設有20名隊員準備參加競賽,請根據(jù)問題及所給參數(shù)進行相關選拔及組合。

3、1.2題目所給信息及參數(shù)根據(jù)隊員的能力和水平選出18名優(yōu)秀隊員分別組成6個隊, 每個隊3名隊員去參加比賽。其中選拔隊員主要考慮的條件按重要度依次為有關學科成績（平均成績）、智力水平（反映思維能力、分析問題和解決問題的能力等）、動手能力（計算機的使用和其它方面實際操行能力）、寫作能力、外語能力、協(xié)作能力（團結協(xié)作能力）和其它特長，相關數(shù)據(jù)如下表所示。隊員編號學科成績x1智力水平x2動手能力x3寫作能力x4外語水平x5協(xié)作能力x6其它特長x7A8.69.08.28.07.99.56B8.28.88.16.57.79.12C8.08.68.58.59.29.68D8.68.98.39.69.79.7

4、8E8.88.48.57.78.69.29F9.29.28.27.99.09.06G9.29.69.07.29.19.29H7.08.09.86.28.79.76I7.78.28.46.59.69.35J8.38.18.66.98.59.44K9.08.28.07.89.09.55L9.69.18.19.98.79.76M9.59.68.38.19.09.37N8.68.38.28.19.09.05O9.18.78.88.48.89.45P9.38.48.68.88.69.56Q8.48.09.49.28.49.17R8.78.39.29.18.79.28S7.78.19.67.69.09.6

5、9T9.08.89.57.97.79.06表 1-隊員各項能力匯總表1.3所需解決問題（1） 在20名隊員中選擇18名優(yōu)秀隊員參加競賽。（2） 確定一個最佳的組隊使競賽技術水平最高。（3） 給出由18名隊員組成6個隊的組隊方案, 使整體競賽技術水平最高, 并給出每個隊的競賽技術水平。二、問題分析2.1問題一分析由于題中已提及選拔隊員主要考慮的條件按重要度依次為有關學科成績、智力水平、動手能力、寫作能力、外語能力、協(xié)作能力和其它特長，因此通過比較確定表一中各項能力對隊員選拔的權重，繼而建立層次結構模型（模型一）進行隊員的篩選。2.2問題二分析由于題目要求在已選出的18名隊員中組合出一組最佳組合使

6、得其競賽技術水平最高，因此本文采用優(yōu)化模型（模型二）來求解。2.3問題三分析問題要求尋求各隊整體競賽水平最高的分隊方法，首先應該給每一對的整體競賽水平一個精確標準，根據(jù)經(jīng)濟學原理，在社會中總是從事自己最有優(yōu)勢的工作，即最擅長的工作。因此在組隊的過程中，每隊的三名選手至少有兩項能力在整體平均能力以上，根據(jù)這一原則以及三人綜合水平盡可能高進行組隊。因此本文通過非線性規(guī)劃模型（模型三）來解決問題。三、模型假設（1） 題目所給各項指標真實客觀反映選手水平。（2） 競賽過程中不考慮其他各類因素影響，競賽水平的展現(xiàn)只取決于表 1中數(shù)據(jù)（3） 選拔過程遵循本文標準公平公正公開。（4） 各競賽水平由各個單項指

7、標來衡量，各隊的各單項競賽水平由此項最優(yōu)隊員 水平為準。（5） 所有被選擇隊員參賽時無不參賽的情況或厭賽心理（6） 問題二和問題三中各組成隊伍里的各隊員相處寫作融洽四、符號說明依次為學科成績、智力水平、動手能力、寫作能力、外語水平、協(xié)作能力和其他特長表示第個隊員在第個基本條件下的成績 表示第個條件在選隊員時所占的權重表示第個因素比第個因素對目標層的影響程度表示每個隊員的編號表示第個隊的第個隊員第個隊員的競賽技術水平第個隊的總體競賽技術水平五、模型建立與求解5.1問題一由于題目要求在20進18的選隊員過程中首先看學科成績，其次看智力水平，再看動手能力、寫作能力、外語能力、協(xié)作能力和其他特長。因此

8、我們先建立成對比較矩陣再使用層次分析結構模型進行問題一的求解。5.1.1利用層次分析法建立層次結構模型圖 1-層次結構模型5.1.2建立成對比較矩陣設為因素層次的成對比較矩陣，為了便于構造，假設每兩個相鄰因素的比較值相同，即常數(shù)。因此引進比較尺（表 2）尺度含義1第個因素與第個因素影響相同3第個因素與第個因素影響稍強5第個因素與第個因素影響強7第個因素與第個因素影響較強9第個因素與第個因素影響很強2，4，6，8為位于1，3，5，7，9中間的值表 2-比較尺另1.5，并建立成對比較陣：5.1.3確定各項權重及一致性檢驗1) 計算成對比較矩陣A的最大特征值=7.0870（附件一）其對應特征向量為：

9、歸一化得：的值依次表示下一個元素對上一個元素的影響程度2) 一致性檢驗由于一致性指標所以由下表（表 3）可知，隨機一致性指標 1234567891011 000.580.901.121.241.321.411.451.491.51表 3-隨機一致性指標數(shù)值表一致性比率：所以A不一致度在容許范圍內(nèi)，可用其歸一化特征向量作為其權重5.1.4根據(jù)權重計算個人競賽水平定義每位隊員競賽技術水平： 將表 1中各項數(shù)據(jù)代入上式，計算得出各人競賽水平排序（表 4）隊員編號學科成績x1智力水平x2動手能力x3寫作能力x4外語水平x5協(xié)作能力x6其它特長x7競賽技術水平 L9.69.18.19.98.79.769

10、.1221M9.59.68.38.199.379.0904G9.29.697.29.19.299.0570D8.68.98.39.69.79.788.8239F9.29.28.27.99968.8078P9.38.48.68.88.69.568.7947O9.18.78.88.48.89.458.7703T98.89.57.97.7968.7619R8.78.39.29.18.79.288.7230E8.88.48.57.78.69.298.5527Q8.489.49.28.49.178.5322A8.698.287.99.568.5008K98.287.899.558.4389C88.68.

11、58.59.29.688.4175N8.68.38.28.19958.3597S7.78.19.67.699.698.3195J8.38.18.66.98.59.448.1032B8.28.88.16.57.79.128.0067I7.78.28.46.59.69.357.9277H789.86.28.79.767.8018表 4-各人競賽技術水平排序由表可知淘汰隊員為I,H。5.2問題二為從18名隊員中選取一組最佳組合使得其隊競賽水平最高采用優(yōu)化模型以解決此問。對18名優(yōu)秀隊員及其基本條件進行編號隊員ABCDEFGHIJ編號12345678910隊員KLMNOPQRST編號111213141

12、51617181920表 5-優(yōu)秀隊員編號條件學科成績x1智力水平x2動手能力x3寫作能力x4外語水平x5協(xié)作能力x6其它特長x7編號1234567表 6-個人各項能力編號評價一個隊的競賽技術水平高低，取決于所選隊員的每個基本條件。因此一個隊的競賽技術水平高低使用整體法加以說明，即給一組來表示這個隊的各基本條件的值，然后再分別乘以權值，最后加和就用這個值來表示一個隊的競賽技術水平，即接下來我們確定，由于競賽水平的發(fā)揮只取決于表一中所給的各項條件，并且，參賽隊員都能正常發(fā)揮自己的水平，所以應采取優(yōu)勢互補的辦法來定義?；谌缟峡紤]我們讓取三個隊員在第個基本條件下的值中的最大值，即：由于要從18名隊

13、員中選出3名組為一隊，所以要求只能等于3（表示第個隊員是否被選中：1選中，0不選中），即模型二的數(shù)學建立目標函數(shù)：模型二求解當時目標達到最大值，同時即三個隊員組成一隊時競賽技術水平最高，競賽技術水平值為：9.5881505.3問題三結合問題二可知若18名隊員組成6個隊，要使得整體競賽技術水平最高需達到最大值。模型的目標函數(shù)為由問題二可知每一個人只能被一個隊選中，所以且每隊只能有三個人，因此：模型的的數(shù)學建立目標函數(shù)：模型求解 求解得下兩表：123456數(shù)值9.1388.96189.057079.367749.328469.13068表 7-每個隊的競賽技術水平12345619.69.28.69

14、.59.29.329.19.28.99.69.68.838.28.59.69.29.49.549.98.19.69.19.28.858.79.09.79.09.19.269.79.29.79.59.49.376.09.09.08.09.08.0表 8-第個隊的基本條件值由表 7-每個隊的競賽技術水平和表 8-第個隊的基本條件值得出此學校整體競賽技術水平最高的組隊方案如下表（表 9）所示：第一隊第二隊第三隊第四隊第五隊第六隊AEDKGCBFJMOPLNSRQT表 9-組隊方案六、模型誤差分析由于模型一中只考慮每個隊員的競賽技術水平，而沒有考慮一個隊的競賽技術水平，但問題三希望的是每個隊參賽技術水

15、平最高，所以不能從個人的角度去選擇隊員，因此我們希望用類似模型三的解法來解決問題一選隊員的問題，即從20人中選擇18人組成6隊使得整體競賽技術水平最高。6.1模型四6.1.6模型四的數(shù)學建立目標函數(shù)：模型的解123456數(shù)值9.1338.5729.2658.8449.59.392表 10-每個隊的競賽技術水平 123456719.29.29.67.99.09.69.029.08.28.67.89.69.55.039.39.69.08.89.19.59.048.78.69.29.19.29.68.059.59.69.49.69.79.78.069.69.19.89.98.79.76.0表 11-

16、第個隊的基本條件值由表 10-每個隊的競賽技術水平和表 11-第個隊的基本條件值可得出最終的使整體競賽技術水平最高的組隊方案如下：第一隊第二隊第三隊第四隊第五隊第六隊EIBCDHFJGNMISKPRQT因此則被淘汰的隊員為：A和O重驗模型二求解在模型四的基礎上，通過模型二我們計算問題二的值，得到：當選擇G、H和L時目標達到最大值，同時。即當把G、H、L這三個隊員組成一隊時，其競賽技術水平最高，值為：9.62。七、模型評價通過比較模型一和模型四，會發(fā)現(xiàn)模型一淘汰了個人整體競賽技術水平最差的兩名隊員，而模型四淘汰了個人整體水平處于中間的兩名隊員，結合模型二和模型三的解得出模型四優(yōu)于模型一。原因是由于組隊時考慮因素不同，模型四采取的是優(yōu)勢互補的原則，而模型一考慮的是個人整體競賽技術水平。因此最佳組隊題條件下的三個問題應通過模型四、二、三進行求解。八、模型改進與推廣在實際應用中，應該采取優(yōu)勢互補的原則，這樣整個參賽隊的成績會更好。九、參考文獻1層次分析法-劉婷 E:建模2017年暑期數(shù)模培訓線上7.6層次分析法老師資料2常見得優(yōu)化模型 E:建模2017年暑期數(shù)模培訓線上第一次論文 王志鴻 十、附錄附件一（MATLAB R20116a）A=1.0,1.5,3.0,4.5,6.0,7.5,9.0 1/1.5,1.0,1.5,3.0,4.5,6.0,7.5 1