最佳組隊(duì)問題

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

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

3、1.2題目所給信息及參數(shù)根據(jù)隊(duì)員的能力和水平選出18名優(yōu)秀隊(duì)員分別組成6個(gè)隊(duì), 每個(gè)隊(duì)3名隊(duì)員去參加比賽。其中選拔隊(duì)員主要考慮的條件按重要度依次為有關(guān)學(xué)科成績(jī)（平均成績(jī)）、智力水平（反映思維能力、分析問題和解決問題的能力等）、動(dòng)手能力（計(jì)算機(jī)的使用和其它方面實(shí)際操行能力）、寫作能力、外語能力、協(xié)作能力（團(tuán)結(jié)協(xié)作能力）和其它特長(zhǎng)，相關(guān)數(shù)據(jù)如下表所示。隊(duì)員編號(hào)學(xué)科成績(jī)x1智力水平x2動(dòng)手能力x3寫作能力x4外語水平x5協(xié)作能力x6其它特長(zhǎng)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-隊(duì)員各項(xiàng)能力匯總表1.3所需解決問題（1） 在20名隊(duì)員中選擇18名優(yōu)秀隊(duì)員參加競(jìng)賽。（2） 確定一個(gè)最佳的組隊(duì)使競(jìng)賽技術(shù)水平最高。（3） 給出由18名隊(duì)員組成6個(gè)隊(duì)的組隊(duì)方案, 使整體競(jìng)賽技術(shù)水平最高, 并給出每個(gè)隊(duì)的競(jìng)賽技術(shù)水平。二、問題分析2.1問題一分析由于題中已提及選拔隊(duì)員主要考慮的條件按重要度依次為有關(guān)學(xué)科成績(jī)、智力水平、動(dòng)手能力、寫作能力、外語能力、協(xié)作能力和其它特長(zhǎng)，因此通過比較確定表一中各項(xiàng)能力對(duì)隊(duì)員選拔的權(quán)重，繼而建立層次結(jié)構(gòu)模型（模型一）進(jìn)行隊(duì)員的篩選。2.2問題二分析由于題目要求在已選出的18名隊(duì)員中組合出一組最佳組合使

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

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

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

9、歸一化得：的值依次表示下一個(gè)元素對(duì)上一個(gè)元素的影響程度2) 一致性檢驗(yàn)由于一致性指標(biāo)所以由下表（表 3）可知，隨機(jī)一致性指標(biāo) 1234567891011 000.580.901.121.241.321.411.451.491.51表 3-隨機(jī)一致性指標(biāo)數(shù)值表一致性比率：所以A不一致度在容許范圍內(nèi)，可用其歸一化特征向量作為其權(quán)重5.1.4根據(jù)權(quán)重計(jì)算個(gè)人競(jìng)賽水平定義每位隊(duì)員競(jìng)賽技術(shù)水平： 將表 1中各項(xiàng)數(shù)據(jù)代入上式，計(jì)算得出各人競(jìng)賽水平排序（表 4）隊(duì)員編號(hào)學(xué)科成績(jī)x1智力水平x2動(dòng)手能力x3寫作能力x4外語水平x5協(xié)作能力x6其它特長(zhǎng)x7競(jìng)賽技術(shù)水平 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-各人競(jìng)賽技術(shù)水平排序由表可知淘汰隊(duì)員為I,H。5.2問題二為從18名隊(duì)員中選取一組最佳組合使得其隊(duì)競(jìng)賽水平最高采用優(yōu)化模型以解決此問。對(duì)18名優(yōu)秀隊(duì)員及其基本條件進(jìn)行編號(hào)隊(duì)員ABCDEFGHIJ編號(hào)12345678910隊(duì)員KLMNOPQRST編號(hào)111213141

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

13、員中選出3名組為一隊(duì)，所以要求只能等于3（表示第個(gè)隊(duì)員是否被選中：1選中，0不選中），即模型二的數(shù)學(xué)建立目標(biāo)函數(shù)：模型二求解當(dāng)時(shí)目標(biāo)達(dá)到最大值，同時(shí)即三個(gè)隊(duì)員組成一隊(duì)時(shí)競(jìng)賽技術(shù)水平最高，競(jìng)賽技術(shù)水平值為：9.5881505.3問題三結(jié)合問題二可知若18名隊(duì)員組成6個(gè)隊(duì)，要使得整體競(jìng)賽技術(shù)水平最高需達(dá)到最大值。模型的目標(biāo)函數(shù)為由問題二可知每一個(gè)人只能被一個(gè)隊(duì)選中，所以且每隊(duì)只能有三個(gè)人，因此：模型的的數(shù)學(xué)建立目標(biāo)函數(shù)：模型求解 求解得下兩表：123456數(shù)值9.1388.96189.057079.367749.328469.13068表 7-每個(gè)隊(duì)的競(jìng)賽技術(shù)水平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-第個(gè)隊(duì)的基本條件值由表 7-每個(gè)隊(duì)的競(jìng)賽技術(shù)水平和表 8-第個(gè)隊(duì)的基本條件值得出此學(xué)校整體競(jìng)賽技術(shù)水平最高的組隊(duì)方案如下表（表 9）所示：第一隊(duì)第二隊(duì)第三隊(duì)第四隊(duì)第五隊(duì)第六隊(duì)AEDKGCBFJMOPLNSRQT表 9-組隊(duì)方案六、模型誤差分析由于模型一中只考慮每個(gè)隊(duì)員的競(jìng)賽技術(shù)水平，而沒有考慮一個(gè)隊(duì)的競(jìng)賽技術(shù)水平，但問題三希望的是每個(gè)隊(duì)參賽技術(shù)水

15、平最高，所以不能從個(gè)人的角度去選擇隊(duì)員，因此我們希望用類似模型三的解法來解決問題一選隊(duì)員的問題，即從20人中選擇18人組成6隊(duì)使得整體競(jìng)賽技術(shù)水平最高。6.1模型四6.1.6模型四的數(shù)學(xué)建立目標(biāo)函數(shù)：模型的解123456數(shù)值9.1338.5729.2658.8449.59.392表 10-每個(gè)隊(duì)的競(jìng)賽技術(shù)水平 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、第個(gè)隊(duì)的基本條件值由表 10-每個(gè)隊(duì)的競(jìng)賽技術(shù)水平和表 11-第個(gè)隊(duì)的基本條件值可得出最終的使整體競(jìng)賽技術(shù)水平最高的組隊(duì)方案如下：第一隊(duì)第二隊(duì)第三隊(duì)第四隊(duì)第五隊(duì)第六隊(duì)EIBCDHFJGNMISKPRQT因此則被淘汰的隊(duì)員為：A和O重驗(yàn)?zāi)Ｐ投蠼庠谀Ｐ退牡幕A(chǔ)上，通過模型二我們計(jì)算問題二的值，得到：當(dāng)選擇G、H和L時(shí)目標(biāo)達(dá)到最大值，同時(shí)。即當(dāng)把G、H、L這三個(gè)隊(duì)員組成一隊(duì)時(shí)，其競(jìng)賽技術(shù)水平最高，值為：9.62。七、模型評(píng)價(jià)通過比較模型一和模型四，會(huì)發(fā)現(xiàn)模型一淘汰了個(gè)人整體競(jìng)賽技術(shù)水平最差的兩名隊(duì)員，而模型四淘汰了個(gè)人整體水平處于中間的兩名隊(duì)員，結(jié)合模型二和模型三的解得出模型四優(yōu)于模型一。原因是由于組隊(duì)時(shí)考慮因素不同，模型四采取的是優(yōu)勢(shì)互補(bǔ)的原則，而模型一考慮的是個(gè)人整體競(jìng)賽技術(shù)水平。因此最佳組隊(duì)題條件下的三個(gè)問題應(yīng)通過模型四、二、三進(jìn)行求解。八、模型改進(jìn)與推廣在實(shí)際應(yīng)用中，應(yīng)該采取優(yōu)勢(shì)互補(bǔ)的原則，這樣整個(gè)參賽隊(duì)的成績(jī)會(huì)更好。九、參考文獻(xiàn)1層次分析法-劉婷 E:建模2017年暑期數(shù)模培訓(xùn)線上7.6層次分析法老師資料2常見得優(yōu)化模型 E:建模2017年暑期數(shù)模培訓(xùn)線上第一次論文 王志鴻 十、附錄附件一（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