協(xié)作比賽的組隊(duì)問(wèn)題數(shù)學(xué)建模競(jìng)賽論文

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

2、慮其他的隨機(jī)因素,競(jìng)賽水平的發(fā)揮只取決于表中所給的各項(xiàng)條件,并且參賽隊(duì)員都能正常發(fā)揮自己的水平.現(xiàn)在的問(wèn)題是: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ù)水平。隊(duì)員學(xué)科成績(jī)（1）智力水平（2）動(dòng)手能力（3）寫作能力（4）外語(yǔ)水平（5）協(xié)作能力（6）其它特長(zhǎng)（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一、 問(wèn)題的提出在一年一度的國(guó)際數(shù)學(xué)建模競(jìng)賽中，各個(gè)單位都會(huì)遇到如何組隊(duì)問(wèn)題?，F(xiàn)由20名隊(duì)員。根據(jù)其能力選拔18名參加競(jìng)賽，選拔隊(duì)員主要考慮的條件依次為學(xué)習(xí)成績(jī)，智力水平（反映思維能力，分析問(wèn)題、解決問(wèn)題的能力，分析問(wèn)題，解決問(wèn)題的能力），動(dòng)手能力（計(jì)算機(jī)的使用和其它方面的實(shí)際操作能力），寫作能力，外語(yǔ)能力，協(xié)作能力（相互協(xié)作能力），其他特長(zhǎng)（如身體素質(zhì)等）每個(gè)隊(duì)員的基本條件如下表（滿分10分記）： 條件隊(duì)員學(xué)習(xí)成績(jī)智力水平動(dòng)手能力寫作能力外語(yǔ)能力協(xié)作能力其他特長(zhǎng)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)在要解決的問(wèn)題是：1.在20名隊(duì)員中選擇18名優(yōu)秀隊(duì)員，參加競(jìng)賽。2.給出18名隊(duì)員組成6個(gè)隊(duì)的組隊(duì)方案是整體競(jìng)賽水平最高，并給出每隊(duì)的競(jìng)賽水平。3.給出一個(gè)最高水平的參賽隊(duì)。4.如果學(xué)習(xí)的權(quán)重為0.2，智力水平權(quán)重為0.2，動(dòng)手能力的權(quán)重為0.2，寫作能力的權(quán)重為0.1，外語(yǔ)能力的權(quán)重為0.1 ，協(xié)作能力的權(quán)重為0.15，其他權(quán)重為0.05，則應(yīng)如何考慮？5.如果每個(gè)隊(duì)員在競(jìng)賽時(shí)，受某種原因干擾，在某一方面發(fā)揮不好，但在另一方面發(fā)揮很好，應(yīng)如何考慮？ 二、問(wèn)題的分析協(xié)作比賽的組隊(duì)問(wèn)題是要從眾多備選

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

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

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

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

11、8名隊(duì)員）第二層是準(zhǔn)則層（記為c），是要解決問(wèn)題時(shí)所要考慮的各種因素，即學(xué)科代表、智力水平、動(dòng)手能力、寫作能力、外語(yǔ)能力、協(xié)作能力、其他特長(zhǎng)7項(xiàng)因素。第三層是方案層（記為p），使該問(wèn)題可以選擇的各種方案，即20名備選隊(duì)員。2.確定準(zhǔn)則層（c）對(duì)目標(biāo)層（o）的權(quán)重構(gòu)造比較矩陣根據(jù)假設(shè)，準(zhǔn)則層的7項(xiàng)因素從左到右的“重要程度”是依次減弱的。則1(1=ij=7),我們現(xiàn)在近似的認(rèn)為任意兩項(xiàng)因素的影響程度之差相等。因此，我們假設(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 計(jì)算比較矩陣a的特征值及特征向量由特征方程a-=0,利用matlab軟件可以求出（求解過(guò)程附后）最大的特征值；max7.1955，相應(yīng)的特征向量位w0=（0.3543，0.2399，0.1586，0.1036，0.0676，0.0448，0.0312）則該特征向量w0,即為準(zhǔn)則層（c）對(duì)目標(biāo)層（o）的權(quán)重 一致性檢驗(yà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，則對(duì)應(yīng)的（x,y,z）就可能是一個(gè)組隊(duì)；任取3名隊(duì)員組合，求出相應(yīng)的技術(shù)水平指標(biāo)，使6個(gè)技術(shù)水平指標(biāo)之和為最佳組隊(duì)方案。2.建立組隊(duì)模型通過(guò)以上的分析，我們可以清楚的知道這就是一個(gè)動(dòng)態(tài)規(guī)劃問(wèn)題。因而需要利用動(dòng)態(tài)規(guī)劃模型解決這個(gè)問(wèn)題。利用動(dòng)態(tài)規(guī)劃的方法，分決策過(guò)程為6個(gè)階段，分步給出6個(gè)隊(duì)的組隊(duì)方案，每一個(gè)階段確定一個(gè)隊(duì)。決策變量：xk =（x,y,z）k (k=1,2,3,4,5,6),即任取三名隊(duì)員（x,y,z）所組成的一個(gè)組隊(duì)方案。 狀態(tài)變量：s k(k=1,2,3,4,5,6)，即從第k（1k6）個(gè)到第6個(gè)組隊(duì)的組隊(duì)方案所

14、包含的隊(duì)員，其中s 1 =隊(duì)員1，隊(duì)員2，隊(duì)員3，隊(duì)員20（不含隊(duì)員8，隊(duì)員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 （一個(gè)組隊(duì)）關(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）個(gè)組隊(duì)的技術(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名隊(duì)員分成6個(gè)組共有816種分法,根據(jù)組隊(duì)原則,用計(jì)算機(jī)編程可算得：組隊(duì)xkx1x2x3x4x5x6隊(duì)員(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對(duì)問(wèn)題3：確定一個(gè)最佳的組隊(duì)使競(jìng)賽水平最高模型的建立及求解：注意：由于

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

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

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

19、如果學(xué)習(xí)的權(quán)重為0.2，智力水平權(quán)重為0.2，動(dòng)手能力的權(quán)重為0.2，寫作能力的權(quán)重為0.1，外語(yǔ)能力的權(quán)重為0.1 ，協(xié)作能力的權(quán)重為0.15，其他權(quán)重為0.05，則應(yīng)如何考慮？模型的建立及求解：利用準(zhǔn)則層（c）對(duì)目標(biāo)層（o）的權(quán)重（0.2 ，0.2， 0.2，0.1，0.1，0.15，0.05）以及方案層（p）對(duì)準(zhǔn)則層（c）的權(quán)重，可以計(jì)算方案層（p）對(duì)目標(biāo)層（o）的權(quán)重，根據(jù)公式得：w=（w1, w2, w3, w4, w20）t= w1, w2, ,w7* w0經(jīng)過(guò)matlab軟件計(jì)算（過(guò)程附后）得：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ù)計(jì)算出的這個(gè)權(quán)重,按我們模型的計(jì)算流程可以得出在(4)所給出的條件下每個(gè)問(wèn)題的答案。這說(shuō)明準(zhǔn)則層（c）對(duì)目標(biāo)層（o）的權(quán)重不同，方案層（p）對(duì)目標(biāo)層（o）的影響程度也不一樣；因此我們?cè)谶x擇參考條件時(shí)，一定要分清主要條件和次要條件。對(duì)問(wèn)題5：如果每個(gè)隊(duì)員在競(jìng)賽時(shí)，受某種原因干擾，在某一方面發(fā)揮不好，但在另一方面發(fā)揮很好，應(yīng)如何考慮？模型的建立為了避免這種情況的出現(xiàn)，應(yīng)該在計(jì)算時(shí)考慮這種因素。我們先設(shè)外界干擾對(duì)隊(duì)員的發(fā)揮影響程度為x每個(gè)隊(duì)員在某一方面發(fā)揮好則其水平數(shù)據(jù)為原來(lái)的（1+x）在某一方面發(fā)揮不好則其水平數(shù)據(jù)為原來(lái)的（1-x）發(fā)揮正常則其水平數(shù)據(jù)為原來(lái)的數(shù)據(jù)不妨設(shè)x取0.2，則：某一方面發(fā)揮好其水平數(shù)據(jù)為原來(lái)