最佳組隊問題

最佳組隊問題的求解與分析摘要參加重大比賽前，院校如何選拔最優(yōu)秀的隊員并科學合理地組隊是各院校取得優(yōu)秀名次的關鍵。本文就此通過層次分析法建立層次結構模型（模型一），結合模型比較得出參賽的18名隊員。根據(jù)所得18名成員建立優(yōu)化模型（模型二）求解最佳競賽技術隊。接著，使用非線性規(guī)劃模型（模型三）求解整體競賽技術水平最高問題，最后，通過誤差分析得到模型四推翻模型一，同時重解模型二、三，得出優(yōu)化后的組隊分配。針對問題一，本文通過建立成對比較矩陣確定各項權重及其一致性，并通過權重計算得出淘汰隊員應為I,H。針對問題二，本文通過問題一的權重以及優(yōu)化模型求解，得出G,L,S組成的隊伍是競賽技術水平最高的最佳組隊。針對問題三，本文通過非線性規(guī)劃模型，得出以下組隊方案:第一隊第二隊第三隊第四隊第五隊第六隊AEDKGCBFJMOPLNSRQT經(jīng)過模型的誤差分析，重新建立1模型四，得：應淘汰A、O隊員。最強隊組合人員應為G,H,L最佳組隊方案應如下所示：第一隊第二隊第三隊第四隊第五隊第六隊EIBCDHFJGNMISKPRQT關鍵詞層次分析法權重優(yōu)化模型非線性規(guī)劃模型一、問題重述1.1問題背景在一年一度的我國和美國大學生數(shù)學建模競賽活動中，任何一個參賽院校都會遇到如何選拔最優(yōu)秀的隊員和科學合理地組隊問題，因此現(xiàn)假設有20名隊員準備參加競賽，請根據(jù)問題及所給參數(shù)進行相關選拔及組合。1.2題目所給信息及參數(shù)根據(jù)隊員的能力和水平選出18名優(yōu)秀隊員分別組成6個隊，每個隊3名隊員去參加比賽。其中選拔隊員主要考慮的條件按重要度依次為有關學科成績（平均成績）、智力水平（反映思維能力、分析問題和解決問題的能力等）、動手能力（計算機的使用和其它方面實際操行能力）、寫作能力、外語能力、協(xié)作能力（團結協(xié)作能力）和其它特長，相關數(shù)據(jù)如下表所示。隊員編號學科成績x1智力水平x2動手能力x3寫作能力x4外語水平x5協(xié)作能力x6其它特長x7A869082807.9956B82888165 7.7912C808685859.2968D868983969.7978E888485778.6929F929282799.0906G929690729.1929H70809862 8.7976I| 778284659.6935ji838186698.5944K90828078 9.0955L969181998.7976M959683819.0937N868382819.0905O918788848.8945P938486888.6956Q848094928.4917R8 _____78392-1918.791-28S 778196769.0969T9.08.89.5797.7906表1-隊員各項能力匯總表1.3所需解決問題（1） 在20名隊員中選擇18名優(yōu)秀隊員參加競賽。（2） 確定一個最佳的組隊使競賽技術水平最高。（3） 給出由18名隊員組成6個隊的組隊方案，使整體競賽技術水平最高，并給出每個隊的競賽技術水平。二、 問題分析2.1問題一分析由于題中已提及選拔隊員主要考慮的條件按重要度依次為有關學科成績、智力水平、動手能力、寫作能力、外語能力、協(xié)作能力和其它特長，因此通過比較確定表一中各項能力對隊員選拔的權重，繼而建立層次結構模型（模型一）進行隊員的篩選。2.2問題二分析由于題目要求在已選出的18名隊員中組合出一組最佳組合使得其競賽技術水平最高，因此本文采用優(yōu)化模型（模型二）來求解。2.3問題三分析問題要求尋求各隊整體競賽水平最高的分隊方法，首先應該給每一對的整體競賽水平一個精確標準，根據(jù)經(jīng)濟學原理，在社會中總是從事自己最有優(yōu)勢的工作，即最擅長的工作。因此在組隊的過程中，每隊的三名選手至少有兩項能力在整體平均能力以上，根據(jù)這一原則以及三人綜合水平盡可能高進行組隊。因此本文通過非線性規(guī)劃模型（模型三）來解決問題。三、 模型假設（1） 題目所給各項指標真實客觀反映選手水平。（2） 競賽過程中不考慮其他各類因素影響，競賽水平的展現(xiàn)只取決于表1中數(shù)據(jù)（3） 選拔過程遵循本文標準公平公正公開。（4） 各競賽水平由各個單項指標來衡量，各隊的各單項競賽水平由此項最優(yōu)隊員水平為準。（5） 所有被選擇隊員參賽時無不參賽的情況或厭賽心理（6） 問題二和問題三中各組成隊伍里的各隊員相處寫作融洽四、 符號說明x.依次為學科成績、智力水平、動手能力、寫作能力、外語水平、協(xié)作能力和I其他特長氣表示第i個隊員在第j個基本條件下的成績七表示第j個條件在選隊員時所占的權重aj表示第i個因素比第j個因素對目標層的影響程度xi表示每個隊員的編號乂疝表示第k個隊的第i個隊員七第i個隊員的競賽技術水平k第k個隊的總體競賽技術水平/V五、模型建立與求解5.1問題一由于題目要求在20進18的選隊員過程中首先看學科成績，其次看智力水平，再看動手能力、寫作能力、外語能力、協(xié)作能力和其他特長。因此我們先建立成對比較矩陣再使用層次分析結構模型進行問題一的求解。5.1.1利用層次分析法建立層次結構模型圖1-層次結構模型■t..ll圖1-層次結構模型■t..ll;4t5.1.2建立成對比較矩陣設A為因素層次的成對比較矩陣，為了便于構造，假設每兩個相鄰因素的比較值相同，即aii+1=常數(shù)。因此引進比較尺（表2）尺度 含義1 第i個因素與第j個因素影響相同3 第i個因素與第j個因素影響稍強5 第i個因素與第j個因素影響強7 第i個因素與第j個因素影響較強9 第i個因素與第j個因素影響很強2，4，6，8為位于1，3，5，7，9中間的值另Li1=1.5，并建立成對比較陣:4.567.59)r11.531/1.511.534.567.51/31/1.511.534.56A=1/4.51/31/1.511.534.51/61/4.51/31/1.511.531/7.51/61/4.51/31/1.511.5[1/91/7.51/61/4.51/31/1.51J5.1.3確定各項權重及一致性檢驗1）計算成對比較矩陣A的最大特征值入=7.0870（附件一）其對應特征向量為：w'=(0.7508,0.5102,0.3277,0.2055,0.1280,0.0818,0.0573”歸一化得：w=（0.3649,0.2479,0.1593,0.0999,0.0622,0.0398,0.0261”w的值依次表示下一個元素對上一個元素的影響程度2）一致性檢驗由于一致性指標所以C=n—n=言=。0145由下表（表3）可知，RI=1.32隨機一致性指標n1234567891011RI000.580.901.121.241.321.411.451.491.51表3-隨機一致性指標ri數(shù)值表一致性比率:CR=C=^01^5=0.0110<0.1RI1.32所以A不一致度在容許范圍內(nèi)，可用其歸一化特征向量3作為其權重5.1.4根據(jù)權重計算個人競賽水平定義每位隊員競賽技術水平：P.=di.*o. i=A,B，…,T

將表1中各項數(shù)據(jù)代入上式，計算得出各人競賽水平排序（表4）隊員編號學科成績x1智力水平x2動手能力x3寫作能力x4外語水平x5協(xié)作能力x6其它特長x7競賽技術水平七L9.69.18.19.98.79.769.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.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)化模型以解決此問。5.2.1對18名優(yōu)秀隊員及其基本條件進行編號隊員ABCDEFGHIJ編號12345678910隊員KLMNOPQRST編號11121314151617181920表5-優(yōu)秀隊員編號條件學科成績x1智力水平x2動手能力x3寫作能力x4外語水平x5協(xié)作能力x6其它特長x7編號1234567表6-個人各項能力編號評價一個隊的競賽技術水平高低，取決于所選隊員的每個基本條件。因此一個隊的競賽技術水平高低使用整體法加以說明，即給一組JJj=1,2,L,7來表示這個隊的各基本條件的值，然后再分別乘以權值，最后加和就用這個值來表示一個隊的競賽技術水平u，即u二￡p*.j=1 .接下來我們確定p.，由于競賽水平的發(fā)揮只取決于表一中所給的各項條件，并且，參賽隊員都能正常發(fā)揮自己的水平，所以應采取優(yōu)勢互補的辦法來定義?；谌缟峡紤]我們讓Pj取三個隊員在第j個基本條件下的值中的最大值，即：

p=max^xd,xd,L,xd}j=1,2,3,4,5,6,7j 11j22j1818j由于要從18名隊員中選出3名組為一隊，所以要求ZX〔只能等于3（x,表示第i個i=1隊員是否被選中：1選中，0不選中），即ZX〔=3i=15.2.2模型二的數(shù)學建立目標函數(shù)：maxu=￡p*wj=1p=max^xd,xd,L,xd}j=1,2,L,7j 11j22j1818j約束條件:凌8Xj=3i=1x〔i為0，1變量5.2.3模型二求解當x7=x10=x17=1時目標達到最大值u=9.588150，同時p=9.6,p=9.6,p=9.6,p=9.9,p=9.1,p=9.7,p=91 2 3 4 5 6 7即G,L,S三個隊員組成一隊時競賽技術水平最高，競賽技術水平值為:9.5881505.3問題三結合問題二可知若18名隊員組成6個隊，要使得整體競賽技術水平人最高Z七需達到最大值。k=1模型的目標函數(shù)為R=ZUKK=1由問題二可知U=Tp*①k=1p=max立*d,x*U=Tp*①k=1p=max立*d,x*d,L,xkij kl 1jk22j k18*d18jIj=1,2,...,7k=1,2,...,6每一個人只能被一個隊選中，所以￡xki=1k=1且每隊只能有三個人，因此：￡x^.=3i=15.3.1模型的的數(shù)學建立i=1,2,...,18k=1,2,...,6目標函數(shù):maxR=寸U

k

k=1

=￡p*①i=1j=1,2,L,7Pk.=maxk*d,x*d,Lxk12jk18*d18jIj=1,2,L,7

k=1,L,6約束條件Ii=約束條件Ii=1,2,L,18k=1,2,L,6k=1如JX=3i=1x.=0或15.3.2模型求解求解得下兩表:k123456數(shù)值9.1388.96189.057079.367749.328469.13068表7-每個隊的競賽技術水平uij12345619.69.28.69.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-第k個隊的基本條件值pkj由表7-每個隊的競賽技術水平U和表8-第k個隊的基本條件值p..得出此學校整體競賽技術水平最高的組隊方案如下表（表9）所示：

第一隊第二隊第三隊第四隊第五隊第六隊AEDKGCBFJMOPLNSRQT表9-組隊方案六、模型誤差分析由于模型一中只考慮每個隊員的競賽技術水平，而沒有考慮一個隊的競賽技術水平，但問題三希望的是每個隊參賽技術水平最高，所以不能從個人的角度去選擇隊員，因此我們希望用類似模型三的解法來解決問題一選隊員的問題，即從20人中選擇18人組成6隊使得整體競賽技術水平最高。6.1模型四6.1.6模型四的數(shù)學建立maxR=寸U目標函數(shù)： kmaxR=寸U目標函數(shù)： k=1kU=￡p*oi=1Jp=maxu*d,x*d,L云尸1k=1JX=3i=1氣.=0或1約束條件」j=1,2,L,7ILd18jIk2*2ji=1,2,L,20k=1,2,L,6j=1,2,L,7;k=1,L,66.1.2模型的解k123456數(shù)值9.1338.5729.2658.8449.59.392表10-每個隊的競賽技術水平U.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-第k個隊的基本條件值Pkj由表10-每個隊的競賽技術水平U和表11-第k個隊的基本條件值Pk可得出最終的使整體競賽技術水平最高的組隊方案如下：第一隊第二隊第三隊第四隊第五隊第六隊EIBCDHFJGNMISKPRQT因此則被淘汰的隊員為：A和O6.1.3重驗模型二求解在模型四的基礎上，通過模型二我們計算問題二的值，得到：當選擇G、H和L時目標達到最大值u=9.62，同時p=9.6,p=9.6,p=9.8,p=9.9,p=9.1,p=9.7,p=9.01 2 3 4 5 6 7 。即當把G、H、L這三個隊