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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上賽程安排數(shù)學(xué)模型徐龍(湖南科技學(xué)院數(shù)學(xué)與計算科學(xué)系 湖南 永州 )摘要: 本文對賽程安排問題進(jìn)行了分析，構(gòu)建了以“輪轉(zhuǎn)法”為基礎(chǔ)的數(shù)學(xué)模型，提供了如何編制賽程的方法利用“輪轉(zhuǎn)法”所編制的賽程的間隔場次數(shù)上、下限及其相應(yīng)的評價指標(biāo)分別就球隊數(shù)為偶數(shù)和奇數(shù)的情況進(jìn)行了討論最后證明了當(dāng)球隊數(shù)為偶數(shù)時，由“輪轉(zhuǎn)法”所編制的賽程是最優(yōu)的關(guān)鍵詞: 數(shù)學(xué)模型；賽程安排；輪轉(zhuǎn)法；賽場間隔 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īng)重視它的公平性，運動會的賽制包括：循環(huán)賽、排位賽和淘汰賽本文主要考慮循環(huán)賽中各隊賽程的間隔時間單循環(huán)球類比賽適用于參賽隊比較少的公平競賽，通常采用的是“輪轉(zhuǎn)法”等手工編排，在編排

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

22、.北京:高等教育出版(第一版),2004：71-1094 動競賽方法研究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