賽程安排數(shù)學(xué)模型(共15頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上賽程安排數(shù)學(xué)模型徐龍(湖南科技學(xué)院數(shù)學(xué)與計(jì)算科學(xué)系 湖南 永州 )摘要: 本文對(duì)賽程安排問題進(jìn)行了分析，構(gòu)建了以“輪轉(zhuǎn)法”為基礎(chǔ)的數(shù)學(xué)模型，提供了如何編制賽程的方法利用“輪轉(zhuǎn)法”所編制的賽程的間隔場(chǎng)次數(shù)上、下限及其相應(yīng)的評(píng)價(jià)指標(biāo)分別就球隊(duì)數(shù)為偶數(shù)和奇數(shù)的情況進(jìn)行了討論最后證明了當(dāng)球隊(duì)數(shù)為偶數(shù)時(shí)，由“輪轉(zhuǎn)法”所編制的賽程是最優(yōu)的關(guān)鍵詞: 數(shù)學(xué)模型；賽程安排；輪轉(zhuǎn)法；賽場(chǎng)間隔 The Mathematical Model of Competition Schedule ArrangementXu Long (Department of Mathematics and Co

2、mputational Science，Hunan University ofScience and Engineering，Yongzhou，Hunan）Abstract: This article has carried on the analysis to the question of competition schedule arrangement and has constructed the mathematical model of “the law of rotates” . Moreover ,it also provided the method to establish

3、 the competition schedule. It also discussed about the situation respectively when the team number is even or odd through the upper limit and lower limit of the number of competition schedule that is established by the “the law of rotates” and the corresponding appraisal target. Finally, it proved t

4、hat the competition scheme is most superior established by “the law of rotates” when the team number is odd.Key word: mathematical model; competition schedule arrangement; the law of rotates; gap1 引言運(yùn)動(dòng)會(huì)作為一種體育賽事應(yīng)重視它的公平性，運(yùn)動(dòng)會(huì)的賽制包括：循環(huán)賽、排位賽和淘汰賽本文主要考慮循環(huán)賽中各隊(duì)賽程的間隔時(shí)間單循環(huán)球類比賽適用于參賽隊(duì)比較少的公平競(jìng)賽，通常采用的是“輪轉(zhuǎn)法”等手工編排，在編排

5、過程中可綜合考慮其它比賽因素本題解決的是單場(chǎng)地單循環(huán)的競(jìng)賽賽程安排，單循環(huán)是指所有參賽隊(duì)在競(jìng)賽中均能相遇一次，最后按各隊(duì)在競(jìng)賽中的得分多少、勝負(fù)場(chǎng)次來排列名次。 單循環(huán)一般在參賽隊(duì)不太多，又有足夠的競(jìng)賽時(shí)間才能采用。單循環(huán)由于參加競(jìng)賽的各隊(duì)都有相遇比賽的機(jī)會(huì)， 是一種比較公平合理的比賽制度。 體現(xiàn)這種比賽公平性的最大因素是某隊(duì)每?jī)蓤?chǎng)比賽的間隔場(chǎng)次數(shù)單循環(huán)的競(jìng)賽場(chǎng)數(shù)公式為:；2 模型2.1 問題的提出為簡(jiǎn)單起見設(shè)某運(yùn)動(dòng)會(huì)的某項(xiàng)目有5個(gè)代表隊(duì), 首先我們考慮所有的代表隊(duì)在同一場(chǎng)地上進(jìn)行單循環(huán)賽, 共要進(jìn)行10 場(chǎng)比賽, 那么如何安排賽程才公平呢? 下面是隨意安排的一個(gè)賽程, 記5個(gè)代表隊(duì)為在下表左

6、半部分的右上三角的10個(gè)空格中, 隨手填上1, 2,. . . , 10, 就得到一個(gè)賽程即第一場(chǎng)對(duì), 第二場(chǎng) 對(duì),. . . , 第十場(chǎng)對(duì)為方便起見, 將這些數(shù)字沿著對(duì)角線對(duì)稱地填入左下角這個(gè)賽程的公平性如何呢？不妨看看各代表隊(duì)每?jī)蓤?chǎng)比賽中間得到的休整時(shí)間是否均等, 表的右半部分是各隊(duì)每?jī)蓤?chǎng)比賽間相隔的場(chǎng)次數(shù), 顯然這個(gè)賽程對(duì)，有利, 對(duì)則不公平.每?jī)蓤?chǎng)比賽間相隔場(chǎng)次數(shù)X19361221X25802292X710410357X400168104X111表從上面的例子出發(fā)引發(fā)了我們對(duì)以下問題的討論:問題(1):對(duì)于5代表隊(duì)的比賽, 給出一個(gè)各隊(duì)每?jī)蓤?chǎng)比賽中間都至少相隔一場(chǎng)的賽程問題(2):當(dāng)有

7、N個(gè)代表隊(duì)比賽時(shí), 各隊(duì)每?jī)蓤?chǎng)比賽中間相隔的場(chǎng)次數(shù)的上限是多少?在達(dá)到(2) 的上限的條件下, 給出N = 8,N = 9,N=n()的賽程2.2 模型假設(shè)（1）假設(shè)在賽程安排中, 各隊(duì)的地位都是平等的，任何一個(gè)隊(duì)都沒有優(yōu)先權(quán)（2）假設(shè)比賽是連續(xù)的, 不間斷, 不受場(chǎng)地, 天氣等因素的影響（3）假設(shè)在比賽中任何一個(gè)隊(duì)都不得棄權(quán), 不能因隊(duì)員受傷或意外事故影響賽程（4）假設(shè)每天進(jìn)行一場(chǎng)比賽2.3 符號(hào)的說明:第k支球隊(duì)：球隊(duì)和進(jìn)行的比賽：第k支球隊(duì)在第i輪的位號(hào)g()：第i輪中位于號(hào)位上的球隊(duì)h()：第i輪中位于號(hào)位上的球隊(duì)所進(jìn)行的比賽在全賽程中的場(chǎng)次dmax：全賽程的間隔場(chǎng)次數(shù)上限dmin：全

8、賽程的間隔場(chǎng)次數(shù)下限V(dmax,dmin) ：全賽程的間隔場(chǎng)次數(shù)上限與下限之差2.4 模型的建立和求解2.4.1 對(duì)于問題（1）的求解對(duì)5支球隊(duì)的比賽,給出一個(gè)各隊(duì)每?jī)蓤?chǎng)比賽中間都至少相隔一場(chǎng)的賽程，其上限為2每?jī)蓤?chǎng)比賽間相隔場(chǎng)次數(shù)X24681112X79521147X110222691X312285103X121表2.4.2對(duì)于問題（2）的求解（一）當(dāng)參賽球隊(duì)數(shù)為偶數(shù)時(shí)賽程的編制步驟1將所要進(jìn)行的場(chǎng)比賽平均分為N-1輪，每輪為場(chǎng)比賽,并且要求每支球隊(duì)在該輪比賽中有且僅有一場(chǎng)比賽步驟2在第一輪中將位號(hào)1,2,N和球隊(duì)按左邊由上而下，右邊由下而上(逆時(shí)針方向)排成完整的兩列，并記錄輪場(chǎng)次和總場(chǎng)

9、次如下:位號(hào)第1輪位號(hào)輪場(chǎng)次總場(chǎng)次1N112N-1223N-233iN-i+1ii+1表3步驟3由第1輪的位號(hào)和比賽場(chǎng)次的安排用以下方法生成第2輪的位號(hào)和比賽場(chǎng)次的安排將固定N在號(hào)位不變, , 均按逆時(shí)針方向依次轉(zhuǎn)移一個(gè)位置，由原來的N-1號(hào)位轉(zhuǎn)移到1號(hào)位如下表：位號(hào)第1輪位號(hào)輪場(chǎng)次總場(chǎng)次1N112N-1223N-233iN-i+1ii+1表4重復(fù)步驟3的過程,由第2輪的賽程生成第3輪的賽程，依次類推，由第i輪的賽程生成第i+1輪的賽程步驟4由上述步驟1、2、3可依次得出第1,2,N-1輪的場(chǎng)次安排,然后按總場(chǎng)次的順序排列即可得到一個(gè)完整的賽程表我們將由上面4個(gè)步驟所得到的賽程編制方法稱為“輪

10、轉(zhuǎn)法”下面給出有 N = 8 支球隊(duì)參賽 ,由上述“輪轉(zhuǎn)法”所生成的賽程表：每?jī)蓤?chǎng)比賽間相隔場(chǎng)次數(shù)x17261123620144432217x12227192254432222612X8183152143222411228x4142717432244237184x28101322244461931428x24922444320215271024x524443212521171395x333333表5計(jì)算間隔場(chǎng)次數(shù)的上、下限對(duì)上述給出的“輪轉(zhuǎn)法”所得的賽程給出如下結(jié)論：結(jié)論1各隊(duì)在每一輪中有且僅有一場(chǎng)比賽，因此該球隊(duì)在第i輪的比賽即是該隊(duì)的第i場(chǎng)比賽結(jié)論2各隊(duì)的第i場(chǎng)比賽在全賽程的總場(chǎng)次=賽程的

11、前(i-1)輪所需比賽的場(chǎng)數(shù)+該隊(duì)第i場(chǎng)比賽在該輪(即第i輪)中的輪場(chǎng)次結(jié)論3各隊(duì)的第i場(chǎng)與第i+1場(chǎng)比賽的間隔數(shù)=該隊(duì)的第(i+1)場(chǎng)比賽在全賽程的總場(chǎng)次該隊(duì)的第i場(chǎng)比賽在全賽程的總場(chǎng)次1結(jié)論4當(dāng)參賽隊(duì)數(shù)N( 6)為偶數(shù)時(shí)，由上述輪轉(zhuǎn)法所編制的賽程球隊(duì)前后兩場(chǎng)比賽間隔數(shù)的上限為，下限為-2下面給出結(jié)論4的證明：構(gòu)造如下的位置轉(zhuǎn)移函數(shù)，用于刻劃第k支球隊(duì)由第i輪的號(hào)位轉(zhuǎn)移到第i+1輪的號(hào)位（）其中 i=1,2,N-2；顯然(1)所定義的位置轉(zhuǎn)移函數(shù)是定義在從位號(hào)集到自身上的一個(gè)1-1對(duì)應(yīng)由結(jié)論1可知，在第i輪中位于號(hào)位上的球隊(duì)所進(jìn)行的比賽在該輪中的場(chǎng)次為：（）（2）式子所定義的函數(shù)稱為輪場(chǎng)次函

12、數(shù),用于記錄球隊(duì)在第i輪位于號(hào)位上的比賽在該輪中的場(chǎng)次由結(jié)論2可知,在第i輪中位于號(hào)位上的球隊(duì)所進(jìn)行的比賽在全賽程中的場(chǎng)次為：（）（3）式子所定義的函數(shù)稱為全程場(chǎng)次函數(shù)，用于記錄球隊(duì)在第i輪位于號(hào)位上的比賽在全賽程中的場(chǎng)次由結(jié)論3得球隊(duì)在i輪中所進(jìn)行的i場(chǎng)與在i+1輪中所進(jìn)行的第i+1場(chǎng)比賽之間的間隔數(shù)為：（）（4）式子所定義的函數(shù)稱為間隔場(chǎng)次函數(shù)，用于刻劃球隊(duì)所進(jìn)行的第i場(chǎng)與第i+1場(chǎng)比賽之間的間隔數(shù)因此,從間隔場(chǎng)次函數(shù)我們得到結(jié)論4是正確的對(duì)于參賽隊(duì)數(shù)N為偶數(shù)的情形,由上述“輪轉(zhuǎn)法”可以得到一個(gè)可行的編制方案(滿足各隊(duì)每?jī)蓤?chǎng)比賽都至少間隔一場(chǎng))(二) 當(dāng)參賽球隊(duì)數(shù)N(7)為奇數(shù)時(shí)記這N支球

13、隊(duì)為,可以虛擬一個(gè)參賽隊(duì)，記為：,使之成為N+1(偶數(shù))支球隊(duì),然后按照隊(duì)數(shù)為偶數(shù)的情形進(jìn)行討論具體步驟如下：步驟1 將所要進(jìn)行的場(chǎng)比賽平均分為(N+1)-1輪，每輪為場(chǎng)比賽(其中有1場(chǎng)是虛擬賽)，并且要求每支球隊(duì)在該輪比賽中有且僅有一場(chǎng)比賽 步驟2 在第一輪中將位號(hào)1,2,N+1和球隊(duì),按左邊由上而下,右邊由下而上(逆時(shí)針方向)排成完整的兩列,并記錄輪場(chǎng)次和總場(chǎng)次如下：位號(hào)第1輪位號(hào)輪場(chǎng)次1N+112N23N-13表6步驟3由第1輪的位號(hào)和比賽場(chǎng)次的安排用以下方法生成第2輪的位號(hào)和比賽場(chǎng)次的安排將固定在N+1號(hào)位不變, 均按逆時(shí)針方向依次轉(zhuǎn)移一個(gè)位置，由原來的N號(hào)位轉(zhuǎn)移到1號(hào)位如下表：位號(hào)第

14、2輪位號(hào)輪場(chǎng)次1N+112N23N-13表7重復(fù)步驟3，可依次得出第1,2,N輪的賽程,然后將含有的虛擬賽剔除，按順序即可排出滿足要求(滿足各隊(duì)每?jī)蓤?chǎng)比賽都至少間隔一場(chǎng))的一個(gè)賽程下面給出用上述“輪轉(zhuǎn)法”所編制的 N=9 支球隊(duì)的一個(gè)賽程：每?jī)蓤?chǎng)比賽間相隔場(chǎng)次數(shù)X16301127624133444722216X12267232202944332223012X8223193425436224311268X4183515213232248277224X36143117262443462331836X321013232348324219351432X28964443321203415311028X5

15、344472233292521171395X3333333表8由上述編制過程,可以得出如下結(jié)論：結(jié)論8 當(dāng)參賽隊(duì)數(shù)N(7)為奇數(shù)時(shí)，由上述“輪轉(zhuǎn)法”所編制的賽程球隊(duì)前后兩場(chǎng)比賽間隔數(shù)的上限為N-1，下限為對(duì)結(jié)論8我們作如下解釋:設(shè)在第k輪中與虛擬球隊(duì)比賽的球隊(duì)是 (即是輪空的)，那么球隊(duì)在第k-1輪的輪場(chǎng)次到第k+1輪的輪場(chǎng)次之間的最大間隔為:dmax=(N+12+1)-2+(N+12-1)=N-1，且dmax=N-1就是該賽程的最大間隔場(chǎng)次數(shù)用同樣的方法考察第k-1輪和第k輪中球隊(duì)沒有出現(xiàn)輪空的間隔場(chǎng)次數(shù),可以得到球隊(duì)的間隔場(chǎng)次數(shù)下限dmin=,且dmin=就是該賽程的最小間隔場(chǎng)次數(shù)結(jié)論9

16、單數(shù)隊(duì)在5個(gè)隊(duì)以上時(shí)倒數(shù)的第二數(shù)字隊(duì)則在第四輪開始每輪均同上輪輪空隊(duì)進(jìn)行比賽,如上述代表隊(duì)由此產(chǎn)生了球類比賽中的不公平競(jìng)爭(zhēng)現(xiàn)象。為了解決結(jié)論9這一問題,目前的比賽大多采用“貝格爾輪轉(zhuǎn)法” ，其優(yōu)點(diǎn)是單數(shù)隊(duì)參加時(shí)可避免第二輪的輪空隊(duì)從第四輪起每場(chǎng)都與前一輪的輪空隊(duì)比賽的不合理現(xiàn)象貝格爾輪轉(zhuǎn)法：貝格爾輪轉(zhuǎn)法是國際上采用的一種編排方法。表(9)為7個(gè)隊(duì)參賽輪次表。其輪轉(zhuǎn)方法是：（1）最大號(hào)數(shù)（尾數(shù)或0）左右擺，右下號(hào)數(shù)提上來，先擺后轉(zhuǎn)，按逆時(shí)針方向轉(zhuǎn)移。（2）也可根據(jù)參賽隊(duì)數(shù)的多少來確定輪轉(zhuǎn)位置的數(shù)目。即3或4個(gè)隊(duì)，依次輪轉(zhuǎn)一個(gè)位置，5或6個(gè)隊(duì)，依次輪轉(zhuǎn)兩個(gè)位置，7或8個(gè)隊(duì)，依次輪轉(zhuǎn)三個(gè)位置等，每增

17、加兩個(gè)隊(duì)，則增加一個(gè)輪轉(zhuǎn)位置. 第一輪 第二輪 第三輪 第四輪 第五輪 第六輪 第七輪 表9無論比賽隊(duì)是單數(shù)還是雙數(shù)，最后一輪時(shí)，必定是“0”或最大的一個(gè)代號(hào)在右上角，“1”在右下角.根據(jù)參賽隊(duì)的個(gè)數(shù)不同，“1”朝逆時(shí)針方向移動(dòng)一個(gè)位置時(shí)，應(yīng)按規(guī)定的間隔數(shù)移動(dòng)（見表10），“0”或最大代號(hào)數(shù)應(yīng)先于“1”移動(dòng)位置。 間隔移動(dòng)參賽隊(duì)數(shù)間隔移動(dòng)數(shù)4隊(duì)以下056隊(duì)178隊(duì)2910隊(duì)31112隊(duì)4“1”進(jìn)行間隔移動(dòng)時(shí)，凡遇到“0”或最大代號(hào)數(shù)時(shí)應(yīng)先越過，不作間隔計(jì)算.綜合（一）和（二），可以借助計(jì)算機(jī)實(shí)現(xiàn)賽程的編制賽程安排表2. 模型的優(yōu)化性探討下面說明利用輪轉(zhuǎn)法所編制的賽程是最優(yōu)化的利用整個(gè)賽程方差，

18、第i隊(duì)場(chǎng)次間隔的方差和整個(gè)賽程安排場(chǎng)次間隔的，來評(píng)價(jià)賽的優(yōu)劣，顯然當(dāng)越小的時(shí)候間隔場(chǎng)次數(shù)越集中，整個(gè)賽程方差和第i隊(duì)場(chǎng)次間隔的方差就越小，整個(gè)賽程的間隔場(chǎng)次數(shù)就越大，賽程的公平性就越好，反之則越差下面說明任何一個(gè)有偶數(shù)支球隊(duì)的單循環(huán)賽賽程用“輪轉(zhuǎn)法”所編制的賽程是最優(yōu)的假設(shè)有另外一個(gè)參賽球隊(duì)數(shù)相同的賽程用“輪轉(zhuǎn)法”所編制的賽程更優(yōu)，則將所要進(jìn)行的場(chǎng)比賽按照賽程比賽的次序平均分為 N - 1輪，每輪場(chǎng) 則一定存在某隊(duì)，其間隔場(chǎng)次數(shù)至多為，從而有如下結(jié)論：結(jié)論5 任何一個(gè)有 N 支球隊(duì)的單循環(huán)賽賽程的間隔場(chǎng)次數(shù)下限為其中 由結(jié)論 5 ,可以進(jìn)而得出以下結(jié)論：結(jié)論 6 任何一個(gè)有 N（）支球隊(duì)的單循

19、環(huán)賽賽程的間隔場(chǎng)次數(shù)不可能出現(xiàn)如下關(guān)系：假設(shè)有某 N 支球隊(duì)的單循環(huán)賽賽程的間隔場(chǎng)數(shù)上、下限均為，即：dmax = dmin =，則球隊(duì)的前后兩場(chǎng)的間隔數(shù)都是，這樣將會(huì)出現(xiàn)兩個(gè)隊(duì)在每一輪的比賽中都相遇，這種賽程是不符合競(jìng)賽規(guī)則的 ，從而結(jié)論 6 是成立的結(jié)論 6說明了這樣的理想賽程()是不存在的下面通過調(diào)整“理想賽程”的間隔場(chǎng)次數(shù)的上、下限，可得出符合實(shí)際的賽程.顯然，當(dāng)間隔場(chǎng)次數(shù)的上限增大時(shí)，必然使得間隔場(chǎng)次數(shù)的下限減少因?yàn)槟硞€(gè)隊(duì)的間隔場(chǎng)次數(shù)的增大這種利益是通過犧牲其他球隊(duì)的利益（間隔場(chǎng)次數(shù)的減少）來獲取的因此由這些變化關(guān)系和結(jié)論 6 可以知道若理想賽程的間隔場(chǎng)次數(shù)上限dmax 由增加1達(dá)到

20、時(shí)，下限dmin必定會(huì)減少，即有：，從而得到如下的結(jié)論7：結(jié)論 7 任何一個(gè)有偶數(shù)支球隊(duì)的單循環(huán)賽賽程用“輪轉(zhuǎn)法”所編制的賽程是最優(yōu)的2. 模型評(píng)價(jià)與改進(jìn)上述采用“輪轉(zhuǎn)法”所建立的模型實(shí)際操作性強(qiáng) ,方法簡(jiǎn)便 ,當(dāng)參賽隊(duì)數(shù)較多時(shí)，可以借助計(jì)算機(jī)實(shí)現(xiàn)賽程的編制這一模型在實(shí)際生活中有較強(qiáng)的推廣性和實(shí)用性改進(jìn)方向:（1）由于假設(shè)每天只賽一場(chǎng), 所以使問題得到了簡(jiǎn)化, 如果一天賽兩場(chǎng), 那么這樣的賽程難度將會(huì)加大, 還需進(jìn)一步改進(jìn)（2）由于是單循環(huán)賽, 所以在安排時(shí)不必考慮真實(shí)實(shí)力的差異, 但在實(shí)際中往往不是單循環(huán)賽, 這還有待進(jìn)一步改進(jìn).（3）當(dāng)N（7）為級(jí)數(shù)支球隊(duì)時(shí), 未能證明所建立的賽程優(yōu)劣指標(biāo)

21、下由“輪轉(zhuǎn)法”所到的賽程是最優(yōu)的因此應(yīng)對(duì)奇數(shù)的情況進(jìn)一步論證賽程的最優(yōu)性或者找出其他更能兼顧各隊(duì)平性的編制賽程的方法結(jié)束語本文對(duì)賽程安排問題進(jìn)行了分析，構(gòu)建了“輪轉(zhuǎn)法”的數(shù)學(xué)模型, 提供了如何編制賽程的方法利用“輪轉(zhuǎn)法”所編制的賽程的間隔場(chǎng)次數(shù)上、下限及其相應(yīng)的評(píng)價(jià)指標(biāo)分別就球隊(duì)數(shù)為偶數(shù)和奇數(shù)的情況進(jìn)行了討論最后證明了當(dāng)球隊(duì)數(shù)為偶數(shù)時(shí)，由“輪轉(zhuǎn)法”所編制的賽程是最優(yōu)的.參考文獻(xiàn)1 王向東數(shù)學(xué)實(shí)驗(yàn)M北京：高等教育出版社(第一版)，2004：5-10. 2 邊馥萍，侯文華，梁馮珍數(shù)學(xué)模型方法與算法M北京：高等教育出版(第一版)，2005：42-533 茆詩松，程依明，濮曉龍.概率論與數(shù)理統(tǒng)計(jì)教程M

22、.北京:高等教育出版(第一版),2004：71-1094 動(dòng)競(jìng)賽方法研究M.北京:人民體育出版社,2001：99-1085 育素養(yǎng)導(dǎo)論M.北京:科學(xué)出版社,2000：58-636 淑清.FORTRAN語言M.北京:清華大學(xué)出版社,2001：200-2567 Rbability，Random variables and stochastic processes AM.Papoulis,McGraw-Hill books Co，1965：136-162.8 Richard F.Bass，A Brief troduction to measure theory and integrationMSpringer Verleg，New