最佳組隊(duì)問題

最佳組隊(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ù)水平最高的最佳組隊(duì)。針對(duì)問題三，本文通過非線性規(guī)劃模型，得出以下組隊(duì)方案:第一隊(duì)第二隊(duì)第三隊(duì)第四隊(duì)第五隊(duì)第六隊(duì)AEDKGCBFJMOPLNSRQT經(jīng)過模型的誤差分析，重新建立1模型四，得：應(yīng)淘汰A、O隊(duì)員。最強(qiáng)隊(duì)組合人員應(yīng)為G,H,L最佳組隊(duì)方案應(yīng)如下所示：第一隊(duì)第二隊(duì)第三隊(duì)第四隊(duì)第五隊(duì)第六隊(duì)EIBCDHFJGNMISKPRQT關(guān)鍵詞層次分析法權(quán)重優(yōu)化模型非線性規(guī)劃模型一、問題重述1.1問題背景在一年一度的我國(guó)和美國(guó)大學(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)選拔及組合。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)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-隊(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ì)員中組合出一組最佳組合使得其競(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)指標(biāo)來衡量，各隊(duì)的各單項(xiàng)競(jìng)賽水平由此項(xiàng)最優(yōu)隊(duì)員水平為準(zhǔn)。（5） 所有被選擇隊(duì)員參賽時(shí)無不參賽的情況或厭賽心理（6） 問題二和問題三中各組成隊(duì)伍里的各隊(duì)員相處寫作融洽四、 符號(hào)說明x.依次為學(xué)科成績(jī)、智力水平、動(dòng)手能力、寫作能力、外語水平、協(xié)作能力和I其他特長(zhǎng)氣表示第i個(gè)隊(duì)員在第j個(gè)基本條件下的成績(jī)七表示第j個(gè)條件在選隊(duì)員時(shí)所占的權(quán)重aj表示第i個(gè)因素比第j個(gè)因素對(duì)目標(biāo)層的影響程度xi表示每個(gè)隊(duì)員的編號(hào)乂疝表示第k個(gè)隊(duì)的第i個(gè)隊(duì)員七第i個(gè)隊(duì)員的競(jìng)賽技術(shù)水平k第k個(gè)隊(duì)的總體競(jìng)賽技術(shù)水平/V五、模型建立與求解5.1問題一由于題目要求在20進(jìn)18的選隊(duì)員過程中首先看學(xué)科成績(jī)，其次看智力水平，再看動(dòng)手能力、寫作能力、外語能力、協(xié)作能力和其他特長(zhǎng)。因此我們先建立成對(duì)比較矩陣再使用層次分析結(jié)構(gòu)模型進(jìn)行問題一的求解。5.1.1利用層次分析法建立層次結(jié)構(gòu)模型圖1-層次結(jié)構(gòu)模型■t..ll圖1-層次結(jié)構(gòu)模型■t..ll;4t5.1.2建立成對(duì)比較矩陣設(shè)A為因素層次的成對(duì)比較矩陣，為了便于構(gòu)造，假設(shè)每?jī)蓚€(gè)相鄰因素的比較值相同，即aii+1=常數(shù)。因此引進(jìn)比較尺（表2）尺度 含義1 第i個(gè)因素與第j個(gè)因素影響相同3 第i個(gè)因素與第j個(gè)因素影響稍強(qiáng)5 第i個(gè)因素與第j個(gè)因素影響強(qiáng)7 第i個(gè)因素與第j個(gè)因素影響較強(qiáng)9 第i個(gè)因素與第j個(gè)因素影響很強(qiáng)2，4，6，8為位于1，3，5，7，9中間的值另Li1=1.5，并建立成對(duì)比較陣: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確定各項(xiàng)權(quán)重及一致性檢驗(yàn)1）計(jì)算成對(duì)比較矩陣A的最大特征值入=7.0870（附件一）其對(duì)應(yīng)特征向量為：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的值依次表示下一個(gè)元素對(duì)上一個(gè)元素的影響程度2）一致性檢驗(yàn)由于一致性指標(biāo)所以C=n—n=言=。0145由下表（表3）可知，RI=1.32隨機(jī)一致性指標(biāo)n1234567891011RI000.580.901.121.241.321.411.451.491.51表3-隨機(jī)一致性指標(biāo)ri數(shù)值表一致性比率:CR=C=^01^5=0.0110<0.1RI1.32所以A不一致度在容許范圍內(nèi)，可用其歸一化特征向量3作為其權(quán)重5.1.4根據(jù)權(quán)重計(jì)算個(gè)人競(jìng)賽水平定義每位隊(duì)員競(jìng)賽技術(shù)水平：P.=di.*o. i=A,B，…,T

將表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.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-各人競(jìng)賽技術(shù)水平排序由表可知淘汰隊(duì)員為I,H。5.2問題二為從18名隊(duì)員中選取一組最佳組合使得其隊(duì)競(jìng)賽水平最高采用優(yōu)化模型以解決此問。5.2.1對(duì)18名優(yōu)秀隊(duì)員及其基本條件進(jìn)行編號(hào)隊(duì)員ABCDEFGHIJ編號(hào)12345678910隊(duì)員KLMNOPQRST編號(hào)11121314151617181920表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ù)水平高低使用整體法加以說明，即給一組JJj=1,2,L,7來表示這個(gè)隊(duì)的各基本條件的值，然后再分別乘以權(quán)值，最后加和就用這個(gè)值來表示一個(gè)隊(duì)的競(jìng)賽技術(shù)水平u，即u二￡p*.j=1 .接下來我們確定p.，由于競(jìng)賽水平的發(fā)揮只取決于表一中所給的各項(xiàng)條件，并且，參賽隊(duì)員都能正常發(fā)揮自己的水平，所以應(yīng)采取優(yōu)勢(shì)互補(bǔ)的辦法來定義。基于如上考慮我們讓Pj取三個(gè)隊(duì)員在第j個(gè)基本條件下的值中的最大值，即：

p=max^xd,xd,L,xd}j=1,2,3,4,5,6,7j 11j22j1818j由于要從18名隊(duì)員中選出3名組為一隊(duì)，所以要求ZX〔只能等于3（x,表示第i個(gè)i=1隊(duì)員是否被選中：1選中，0不選中），即ZX〔=3i=15.2.2模型二的數(shù)學(xué)建立目標(biāo)函數(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模型二求解當(dāng)x7=x10=x17=1時(shí)目標(biāo)達(dá)到最大值u=9.588150，同時(shí)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三個(gè)隊(duì)員組成一隊(duì)時(shí)競(jìng)賽技術(shù)水平最高，競(jìng)賽技術(shù)水平值為:9.5881505.3問題三結(jié)合問題二可知若18名隊(duì)員組成6個(gè)隊(duì)，要使得整體競(jìng)賽技術(shù)水平人最高Z七需達(dá)到最大值。k=1模型的目標(biāo)函數(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每一個(gè)人只能被一個(gè)隊(duì)選中，所以￡xki=1k=1且每隊(duì)只能有三個(gè)人，因此：￡x^.=3i=15.3.1模型的的數(shù)學(xué)建立i=1,2,...,18k=1,2,...,6目標(biāo)函數(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-每個(gè)隊(duì)的競(jìng)賽技術(shù)水平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個(gè)隊(duì)的基本條件值pkj由表7-每個(gè)隊(duì)的競(jìng)賽技術(shù)水平U和表8-第k個(gè)隊(duì)的基本條件值p..得出此學(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ù)水平最高，所以不能從個(gè)人的角度去選擇隊(duì)員，因此我們希望用類似模型三的解法來解決問題一選隊(duì)員的問題，即從20人中選擇18人組成6隊(duì)使得整體競(jìng)賽技術(shù)水平最高。6.1模型四6.1.6模型四的數(shù)學(xué)建立maxR=寸U目標(biāo)函數(shù)： kmaxR=寸U目標(biāo)函數(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-每個(gè)隊(duì)的競(jìng)賽技術(shù)水平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個(gè)隊(duì)的基本條件值Pkj由表10-每個(gè)隊(duì)的競(jìng)賽技術(shù)水平U和表11-第k個(gè)隊(duì)的基本條件值Pk可得出最終的使整體競(jìng)賽技術(shù)水平最高的組隊(duì)方案如下：第一隊(duì)第二隊(duì)第三隊(duì)第四隊(duì)第五隊(duì)第六隊(duì)EIBCDHFJGNMISKPRQT因此則被淘汰的隊(duì)員為：A和O6.1.3重驗(yàn)?zāi)Ｐ投蠼庠谀Ｐ退牡幕A(chǔ)上，通過模型二我們計(jì)算問題二的值，得到：當(dāng)選擇G、H和L時(shí)目標(biāo)達(dá)到最大值u=9.62，同時(shí)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 。即當(dāng)把G、H、L這三個(gè)隊(duì)