協(xié)作比賽的組隊問題數(shù)學(xué)建模競賽論文

1、第2題 最佳組隊方案問題 在一年一度的我國和美國大學(xué)生數(shù)學(xué)建模競賽活動中,任何一個參賽院校都會遇到如何選拔最優(yōu)秀的隊員和科學(xué)合理地組隊問題這是一個最實際的,而且首先需要解決的數(shù)學(xué)模型問題.現(xiàn)假設(shè)有20名隊員準(zhǔn)備參加競賽,根據(jù)隊員的能力和水平要選出18名優(yōu)秀隊員分別組成6個隊,每個隊3名隊員去參加比賽,選拔隊員主要考慮的條件依次為有關(guān)學(xué)科成績(平均成績)、智力水平(反映思維能力、分析問題能力和解決問題能力等)、動手能力(計算機(jī)的使用和其他方面實際操作能力) 寫作能力、外語能力、協(xié)作能力(團(tuán)結(jié)協(xié)作能力)和其他特長.每個隊員的基本條件量化后如表.假設(shè)所有隊員接受了同樣的培訓(xùn),外部條件相同,競賽中不考

2、慮其他的隨機(jī)因素,競賽水平的發(fā)揮只取決于表中所給的各項條件,并且參賽隊員都能正常發(fā)揮自己的水平.現(xiàn)在的問題是:1) 在20名隊員中選擇18名優(yōu)秀隊員參加競賽;2) 確定一個最佳的組隊使競賽技術(shù)水平最高；3) 給出由18名隊員組成6個隊的組隊方案，使整體競賽技術(shù)水平最高，并給出每個隊的競賽技術(shù)水平。隊員學(xué)科成績（1）智力水平（2）動手能力（3）寫作能力（4）外語水平（5）協(xié)作能力（6）其它特長（7）abcdefghijklmnopqrst8.68.28.08.68.89.29.27.07.78.39.09.69.58.69.19.38.48.77.89.09.08.88.68.98.49.29.

3、68.08.28.18.29.19.68.38.78.48.08.38.18.88.28.18.58.38.58.29.09.88.48.68.08.18.38.28.88.69.49.29.69.58.06.58.59.67.77.97.26.26.56.97.89.98.18.18.48.89.29.17.67.97.97.79.29.78.69.09.18.79.68.59.08.79.09.08.88.68.48.79.07.79.59.19.69.79.29.09.29.79.3.9.49.59.79.3.9.09.49.59.19.29.69.0628896965456755678

4、96一、 問題的提出在一年一度的國際數(shù)學(xué)建模競賽中，各個單位都會遇到如何組隊問題?，F(xiàn)由20名隊員。根據(jù)其能力選拔18名參加競賽，選拔隊員主要考慮的條件依次為學(xué)習(xí)成績，智力水平（反映思維能力，分析問題、解決問題的能力，分析問題，解決問題的能力），動手能力（計算機(jī)的使用和其它方面的實際操作能力），寫作能力，外語能力，協(xié)作能力（相互協(xié)作能力），其他特長（如身體素質(zhì)等）每個隊員的基本條件如下表（滿分10分記）： 條件隊員學(xué)習(xí)成績智力水平動手能力寫作能力外語能力協(xié)作能力其他特長18.69.08.28.07.99.5628.28.88.16.57.79.2238.08.68.58.59.29.6848.6

5、8.98.39.69.79.7858.88.48.57.78.69.2969.29.28.27.99.09.0679.29.69.07.29.19.2987.08.09.86.28.79.7697.78.28.46.59.69.35108.38.18.66.98.59.44119.08.28.07.89.09.55129.69.28.19.98.79.76139.59.68.38.19.09.37148.68.38.28.19.09.05159.18.78.88.48.89.45169.38.48.68.88.69.56178.48.09.49.28.49.17188.78.39.29.18.

6、79.28197.88.19.67.69.09.69209.08.89.57.97.79.06現(xiàn)在要解決的問題是：1.在20名隊員中選擇18名優(yōu)秀隊員，參加競賽。2.給出18名隊員組成6個隊的組隊方案是整體競賽水平最高，并給出每隊的競賽水平。3.給出一個最高水平的參賽隊。4.如果學(xué)習(xí)的權(quán)重為0.2，智力水平權(quán)重為0.2，動手能力的權(quán)重為0.2，寫作能力的權(quán)重為0.1，外語能力的權(quán)重為0.1 ，協(xié)作能力的權(quán)重為0.15，其他權(quán)重為0.05，則應(yīng)如何考慮？5.如果每個隊員在競賽時，受某種原因干擾，在某一方面發(fā)揮不好，但在另一方面發(fā)揮很好，應(yīng)如何考慮？ 二、問題的分析協(xié)作比賽的組隊問題是要從眾多備選

7、隊員中按照給定的量化標(biāo)準(zhǔn)，選出綜合素質(zhì)較高的若干名隊員，以保證參賽隊員的整體水平（即本題問題1）。通過分析我們知道這是一個多條件多方案的選擇問題，屬于層次分析問題，需要建立層次結(jié)構(gòu)模型。為了盡可能體現(xiàn)參賽單位整體水平我們要對選出的這些優(yōu)秀隊員作出適當(dāng)?shù)拇钆浣M合。使各組隊員之間起到優(yōu)勢互補(bǔ)作用，這樣就可以提高該組合的水平。通過隊員間的搭配組合，組合出來的隊伍的整體綜合素質(zhì)就會提高。這樣這個單位派出的所有參賽隊伍就都具有一定的水平，奪獎的機(jī)率會增加許多（即本題問題2）。但是，為了盡可能體現(xiàn)參賽單位的最高水平，并且提高獲大獎的概率，就需要組合出一個“最佳陣容”，即該組合的各項水平幾乎都是參賽單位的最

8、高水平（即本題問題3）。我們知道以上兩個問題都屬于動態(tài)規(guī)劃問題，需要我們建立動態(tài)規(guī)劃模型。由于體現(xiàn)參賽隊員水平的量化指標(biāo)很多，但各量化指標(biāo)的重要程度不盡相同，這就需要對量化指標(biāo)加入一個可以代表“重要程度”的衡量方式。本題是對各項量化指標(biāo)進(jìn)行加權(quán)，用權(quán)重來表示該項量化指標(biāo)體現(xiàn)學(xué)生綜合水平的程度。在此基礎(chǔ)上來考慮參賽隊員的選擇以及組隊問題（即本題問題4）。我們可以在題目所給權(quán)重的條件下，結(jié)合所建立的兩個模型來解決問題。實際參賽時還有一個臨場發(fā)揮問題，在比賽時受某種條件干擾隊員的實際水平有可能超常發(fā)揮也可能失常發(fā)揮（即本題問題5）。怎樣可以表示出隊員水平的變化狀態(tài)？我們可以借助矩陣來解決這一問題。三

9、、模型假設(shè)（1） 假設(shè)題目中所給的每個隊員的各項信息都能真實地體現(xiàn)隊員的各項能力和水平。（2） 假設(shè)每個隊員在比賽能不受外界原因干擾，將自己的單項水平都發(fā)揮到正常水平（問題5除外）。（3） 假設(shè)一個參賽隊單項能力或水平是由該隊中水平最高的隊員體現(xiàn)的。（即組合中的單項水平取三名隊員中該項水平最高的）。（4） 假設(shè)問題3中選擇一個體現(xiàn)參賽單位最高水平的組合是在問題1選出的18名隊員中挑選。但它不受問題2中組隊方案的影響（即不是直接在問題2已經(jīng)組好6個隊伍的基礎(chǔ)上選取水平最高的）。（5） 假設(shè)題目中所給出的衡量學(xué)生綜合素質(zhì)的7項指標(biāo)從左往右“重要程度”是依次降低的。四、符號說明表示準(zhǔn)則i與準(zhǔn)則j對目

10、標(biāo)決策的重要程度之比r.i表示隨機(jī)一致性指標(biāo)ak =()20*20 表示方案層對準(zhǔn)則層的比較矩陣c.r(1) 表示準(zhǔn)則層（c）對目標(biāo)層（o）一致性比例指標(biāo)五、模型的建立及求解對問題1： 從20名隊員中選擇18名優(yōu)秀隊員。1.利用層次分析法首先建立該問題的層次結(jié)構(gòu)模型圖，如下：選擇優(yōu)秀隊員其它特長協(xié)作能力外語能力寫作能力動手能力智力水平學(xué)習(xí)成績隊員1隊員2隊員3隊員4隊員5隊員6隊員7隊員8隊員9隊員10隊員11隊員12隊員13隊員14隊員15隊員16隊員17隊員18隊員19隊員20（層次結(jié)構(gòu)模型圖）根據(jù)層次分析法，我們可以知道第一層是目標(biāo)層（記為o），是要解決的問題（即要從20名隊員之中挑選1

11、8名隊員）第二層是準(zhǔn)則層（記為c），是要解決問題時所要考慮的各種因素，即學(xué)科代表、智力水平、動手能力、寫作能力、外語能力、協(xié)作能力、其他特長7項因素。第三層是方案層（記為p），使該問題可以選擇的各種方案，即20名備選隊員。2.確定準(zhǔn)則層（c）對目標(biāo)層（o）的權(quán)重構(gòu)造比較矩陣根據(jù)假設(shè)，準(zhǔn)則層的7項因素從左到右的“重要程度”是依次減弱的。則1(1=ij=7),我們現(xiàn)在近似的認(rèn)為任意兩項因素的影響程度之差相等。因此，我們假設(shè)比較矩陣為 1 2 3 4 5 6 7 1/2 1 2 3 4 5 6 1/3 1/2 1 2 3 4 5a= 1/4 1/3 1/2 1 2 3 4 1/5 1/4 1/3 1

12、/2 1 2 3 1/6 1/5 1/4 1/3 1/2 1 2 1/7 1/6 1/5 1/4 1/3 1/2 1 計算比較矩陣a的特征值及特征向量由特征方程a-=0,利用matlab軟件可以求出（求解過程附后）最大的特征值；max7.1955，相應(yīng)的特征向量位w0=（0.3543，0.2399，0.1586，0.1036，0.0676，0.0448，0.0312）則該特征向量w0,即為準(zhǔn)則層（c）對目標(biāo)層（o）的權(quán)重 一致性檢驗由于比較矩陣a的階數(shù)為7，其隨機(jī)一致性指標(biāo)為r.i=1.32（注：見數(shù)學(xué)模型姜啟源p312表9-2）c.i(1)= (max -7)/(7-1)0.0326于是 一

13、致性比例指標(biāo)為c.r(1)= c.i(1)/ r.i0.0247，則對應(yīng)的（x,y,z）就可能是一個組隊；任取3名隊員組合，求出相應(yīng)的技術(shù)水平指標(biāo)，使6個技術(shù)水平指標(biāo)之和為最佳組隊方案。2.建立組隊模型通過以上的分析，我們可以清楚的知道這就是一個動態(tài)規(guī)劃問題。因而需要利用動態(tài)規(guī)劃模型解決這個問題。利用動態(tài)規(guī)劃的方法，分決策過程為6個階段，分步給出6個隊的組隊方案，每一個階段確定一個隊。決策變量：xk =（x,y,z）k (k=1,2,3,4,5,6),即任取三名隊員（x,y,z）所組成的一個組隊方案。 狀態(tài)變量：s k(k=1,2,3,4,5,6)，即從第k（1k6）個到第6個組隊的組隊方案所

14、包含的隊員，其中s 1 =隊員1，隊員2，隊員3，隊員20（不含隊員8，隊員9）。狀態(tài)轉(zhuǎn)移方程：s k+1 = s k -xk (k=1,2,3,4,5)允許決策集合：dk =（x,y,z）；x，y，zs k ，vk =（x,y,z）w (k=1,2,3,4,5,6) 指標(biāo)函數(shù)：vk （s k ，xk）表示決策xk （一個組隊）關(guān)于狀態(tài)s k的技術(shù)水平指標(biāo)，即vk （s k ，xk）=m* 最優(yōu)值函數(shù)：fk（s k）表示在狀態(tài)s k下確定的k（1k6）個組隊的技術(shù)水平指標(biāo)之和的最大值。則有逆序解法的基本方程：fk（s k）=max vk (s k ，xk)+ fk+1（s k+1） xk dk

15、k=6,5,4，3，2，1 f6（s 6）=max vk (s k ，xk)當(dāng) x6 = sn 其中s k+1 =s k -xk k=1,2,3,4,53.模型求解把18名隊員分成6個組共有816種分法,根據(jù)組隊原則,用計算機(jī)編程可算得：組隊xkx1x2x3x4x5x6隊員(x,y,z)(3,10,11)(1,14,15)(2,16,18)(4,6,20)(5,13,17)(7,12,19)水平vk （x,y,z）0.05160.05190.05330.05460.05530.0563其最優(yōu)值為f1（s 1）=0.32315對問題3：確定一個最佳的組隊使競賽水平最高模型的建立及求解：注意：由于

16、在問題2中，可以用計算機(jī)編程把18名隊員分成6個組，通過計算相應(yīng)的技術(shù)水平指標(biāo)，找出最高者的組隊，其結(jié)果為（12,7,19）下面我們通過分析法來說明其結(jié)果的正確性：由假設(shè)知，每個隊中的三名隊員具有互補(bǔ)性，即三個人中各單項水平指標(biāo)的最高者為該隊的單項水平指標(biāo)，最佳組隊主要體現(xiàn)全隊在各單項水平指標(biāo)水平最高,不應(yīng)有貌相述評指標(biāo)比其他的隊低.由問題(1)中的準(zhǔn)則c層對目標(biāo)o層的權(quán)重w0可知,七項準(zhǔn)則是按順序依次排列的,對目標(biāo)決策的影響是不同的,而且前四項對目標(biāo)決策起著決定性作用,即水平指標(biāo)主要體現(xiàn)在前四項上.(1) 最佳組隊原則設(shè)mi(x)表示隊員x的第i項水平指標(biāo)，mi(x,y,z)表示由隊員x,y

17、,z組隊(x,y,z)的第i項水平指標(biāo)，則mi(x,y,z)= max mi(x), mi(y), mi(z) ( i =1，2，3，7)(2)組隊方案根據(jù)組隊原則，最佳組隊中的隊員一定是前四項水平指標(biāo)的最高者。顯然由表13-2可得mi(12)=0.055 6為最高，于是mi= m1(12)= 0.055 619 9，則隊員12是首先入選的隊員。其次m2(7)= m2(13)= 0.055 7,而m2(7) m3(13)，故m2= m2(7)= 0.055 716 8，則隊員7是第二個入選的隊員。另外，m3(19)=0.055 395 3，于是m3 =m3(19) =0.055 395 3。而

18、且m4= m4(12)=0.061 913 7，則隊員19應(yīng)是第三個入選的隊員，并且注意到m5= m5(7)=0.052 029 7，m6= m6(12)=0.051 871 7，m7= m7(7)=0.070 866 1也都是相對的較高者，即m=（0.055 619 9，0.055 716 8，0.055 395 3，0.061 913 7，0.052 029 7，0.051 871 7，0.070 866 1）.因此，由隊員12,7,19組成（12,7,19）隊的技術(shù)水平指標(biāo)為:v（12,7,19）=m* w0 t=0.563 246是最高的,所以,最佳組隊為（12,7,19）對問題4：

19、如果學(xué)習(xí)的權(quán)重為0.2，智力水平權(quán)重為0.2，動手能力的權(quán)重為0.2，寫作能力的權(quán)重為0.1，外語能力的權(quán)重為0.1 ，協(xié)作能力的權(quán)重為0.15，其他權(quán)重為0.05，則應(yīng)如何考慮？模型的建立及求解：利用準(zhǔn)則層（c）對目標(biāo)層（o）的權(quán)重（0.2 ，0.2， 0.2，0.1，0.1，0.15，0.05）以及方案層（p）對準(zhǔn)則層（c）的權(quán)重，可以計算方案層（p）對目標(biāo)層（o）的權(quán)重，根據(jù)公式得：w=（w1, w2, w3, w4, w20）t= w1, w2, ,w7* w0經(jīng)過matlab軟件計算（過程附后）得：w = （ 0.0498，0.0464，0.0497，0.0520，0.05030.0

20、515，0.0531，0.0458，0.0464，0.04720.0494，0.0535， 0.0515， 0.0489，0.05120.0516，0.0502，0.0513，0.0491，0.0512）t根據(jù)計算出的這個權(quán)重,按我們模型的計算流程可以得出在(4)所給出的條件下每個問題的答案。這說明準(zhǔn)則層（c）對目標(biāo)層（o）的權(quán)重不同，方案層（p）對目標(biāo)層（o）的影響程度也不一樣；因此我們在選擇參考條件時，一定要分清主要條件和次要條件。對問題5：如果每個隊員在競賽時，受某種原因干擾，在某一方面發(fā)揮不好，但在另一方面發(fā)揮很好，應(yīng)如何考慮？模型的建立為了避免這種情況的出現(xiàn)，應(yīng)該在計算時考慮這種因素。我們先設(shè)外界干擾對隊員的發(fā)揮影響程度為x每個隊員在某一方面發(fā)揮好則其水平數(shù)據(jù)為原來的（1+x）在某一方面發(fā)揮不好則其水平數(shù)據(jù)為原來的（1-x）發(fā)揮正常則其水平數(shù)據(jù)為原來的數(shù)據(jù)不妨設(shè)x取0.2，則：某一方面發(fā)揮好其水平數(shù)據(jù)為原來