赛程安排数学建模问题

1、题目赛程安排摘要赛程安排在体育活动中举足轻重，在很大程度上影响比赛的结果；本文主要 针对最优赛程安排方案建立相应的数学模型，给出最优赛程的安排方案。对于问题一，要给出一个各队每两场比赛中间都至少相隔一场的赛。因为参赛队伍只有5个，容易操作，所以可以利用排除-假设法可以得到一种满足条件 的赛程安排，即 AB,CD,EA,BC,DE, AC,BD, EC, AD,BE。对于问题二，考虑到各队每两场比赛中间至少相隔一场，我们用逆时针轮转 法对比赛队伍进行排序，并根据这种方法，用Matlab编出相应编程得出不同队伍比赛间隔的上限，再根据数据总结出规律，当N为偶数时各队每两场比赛中间相隔的场次数的上限为

2、N2_2场，用Matlab软件验证其准确性。用同样的方 法可知，当N为奇数时各队每两场比赛中间相隔的场次数的上限为 (N-3)2。对于问题三，在达到第二问上限的情况下，可通过轮换模型得到N =8,N =9 的赛程安排。N =8时一种赛程安排如下：(1.2) ,(3,5),(4,6),(8,7),(1,3),(4,2),(8,5),(7,6),(1,4),(8,3),(7,2),(6, 5),(1,8),(7,4),(6,3),(5,2),(1,7),(6,8),(5,4),(2,3),(1,6),(5,7),(2,8),(3,4),(1,5),(2,6),(3,7),(4,8)N =9时一种赛

3、程安排如下：(1.2) ,(3,4),(5,6),(7,8),(1,9),(2,4),(3,6),(5,8),(7,9),(1,4),(2,6),(3, 8),(5,9),(1,7),(4,6),(8,2),(9,3),(5,7),(1,6),(4,8),(2,9),(3,7),(1,5),(6,8) ,(4,9),(2,7),(3,5),(1,8),(6,9),(4,7),(2,5),(1,3),(8,9),(6,7),(4, 5),(2,3).对于问题四，我们可以用每个队的每两场比赛中间间隔的场次数之和SUM来衡量赛程的公平性。当SUM不同时，SUM大的队伍对其比赛结果越有利。 当SUM相

4、同时，用每次间隔场次的标准差来衡量赛程的公平性，其中标准差越 小的队对其比赛的结果越有利。当SUM相同且每次间隔场次的标准差也相同时， 两个队比赛时，我们用双方已参加比赛的次数来衡量比赛赛程的优劣，其中在双方比赛时，已参加比赛次数越少，其比赛的结果越有利。关键词：排除-假设法 逆时针轮转法 Matlab标准差问题重述1.1背景分析当今社会，随着经济的增长和科学技术的发展，人们的生活水平不断的提高， 体育竞赛也在日趋紧张的现代生活中被人们提到了越来越重要的位置。北京奥运会的成功更加提升了体育在人们生活中的份量，体育活动在生活中起着举足轻重 的作用。而这些体育运动中，公平性又显得尤其重要。特别是在

5、对抗性强的单循 环比赛中，赛程安排的不同，对比赛结果响很大。本文主要着手于最优赛程安排 方案，尽量给出赛程安排使得对每支球队来说都很公平。1.2问题重述假设你所在的年级有5个班，每班一支球队在同一块场地上进行单循环赛 （所谓单循环赛是所有参加比赛的队均能相遇一次，最后按各队在全部比赛 中的积分、得失分率排列名次）要进行10场比赛。如何安排赛程使对各队来说都尽量公平呢？下面是随便安排的一个赛程 ：记5支球队为A,B,C,D, E，在 下表左半部分的右上三角的10个空格中，随手填上1,2,3.10,就得到一个赛程， 即第1场A对B ,第2场B对C,第10场C对E .为方便起见将这些数字沿 对角线对

6、称地填入左下三角。这个赛程的公平性如何呢，不妨只看看各队每两场比赛中间得到的休整时 间是否均等。 表的右半部分是各队每两场比赛间相隔的场次数 ，显然这个赛程 对A,有利E,对D则不公平。表ABCDE每两场比赛间相隔场数AX19361,2,2B1X2580,2,2C92X7104,1,0D357X40,0,1E68104X1,1,1从上面的例子出发讨论以下问题问题一：对于5支球队的比赛，给出一个各队每两场比赛中间都至少相隔一 场的赛程。问题二：当n支球队比赛时，各队每两场比赛中间相隔的场次数的上限是多 少。问题三：在达到2）的上限的条件下，给出n =8, n=9的赛程，并说明它们 的编制过程。问

7、题四：除了每两场比赛间相隔场次数这一指标外，你还能给出哪些指标来 衡量一个赛程的优劣，并说明3）中给出的赛程达到这些指标的程度。模型假设结合本题实际，为确保模型求解的准确性和合理性， 我们排除了一些因素的 干扰，提出以下几点假设：1、比赛期间，比赛不受任何外界因素影响。2、每天比赛的时间段固定并且每场比赛时间相同。3、任两球队在相同的休息时间里都能够得到同等程度的休息。4、比赛在一天中指定的时间准时开始和结束并且严格按原赛程的规定执行，不 存在因为其他原因造成的停赛的出现。5、所建模型仅考虑开始比赛期间相邻两场比赛之间的休息时间队参赛队的影响， 不考虑第一场比赛之前和最后一场比赛之后的休息时间

8、对参赛队的影响。三、符号说明3.1符号说明为了便于问题的求解，我们给出以下符号说明:N表示参赛队伍的数量I1M表示各队每两场比赛中间隔的场次数的上限1a表示参赛队的轮数Xi表示相邻两场比赛的间隔场数（i =1,2,3n ）|S每个队的每两场比赛中间间隔的场次数的标准差r sum每个队的每两场比赛中间间隔的场次数之和d各队在全部赛程中间隔场次数|D在全部赛程中间隔场数的总次数|3.2名词解释:1、上限上限为每两场比赛中间相隔的场次数的最小值。2、单循环赛单循环赛是所有参加比赛的队均能相遇一次，最后按各队在全部比赛中 的积分、得失分率排列名次。3、排除一假设法当某一变因素的存在形式限定在有限种可能

9、（如某命题成立或不成立， 如a与b大小：有大于、小于和等于三种情况）时，假设该因素处于某种情 况（如命题成立，如 a>b），并以此为条件进行推理。四、问题分析4.1对问题一的分析对于问题一，假设这五支球队分别定义为 A,B,C,D,E队，那么这五支球队 比赛的总场次数为10。第一场出场队伍组合有C； 10种可能，要满足各队每两 场比赛中间都至少相隔一场这个条件，所以第二场比赛共有 C；种可能，以此类推共有10*3*2*2*2=240种可能。其中一种可能如下表二:表二、五支队伍参赛赛程安排表1 ABCDE每两场比赛间相隔场次数If AX16931,2, 2B1X4710P2, 2 ,21

10、C(6P 4X2P 81, 1, 1D972X52, 1, 1E31085X1, 2, 1 1最后再用Matlab编程来验证此排除一假设法的准确性，发现结果相同即证 明针对参赛队伍较少的情况此种方法简易可行。4.2对问题二的分析为了方便计算、便于表示，我们将参加比赛的球队由编号分别为字母A、B、C、D,分别用数字1、2、3、4、，等代替表示，固定第 1队，按左边由上而 下、右边由下而上(即逆时针转动)排成完整的两列。再将比赛场地的顺序按轮转 法排出，分别讨论。根据这种逆时针轮转法，用Matlab编出相应软件得出不同队伍参赛时比赛间隔的上限，如当n =6,8,10,12时，算出各队每两场比赛中间

11、 相隔的场次数的上限分别为1, 2,3,4,，分析以上数据可以得到如下规律，当 N为偶数时，各队每两场比赛中间相隔的场次数的上限为N -2场；最后再用软2件验证得到这种逆时针轮转法的准确性。用同样的方法可知，当N为基数时各队每两场比赛中间相隔的场次数的上限为。24.3对问题三的分析在达到第二问上限的情况下，可通过轮换模型得到N=8,N=9的赛程安排。 当N =8时，把1固定在左上角不动，其余元素按逆时针轮转法轮换，一共轮换 了 N -2次。用Matlab编程得到一种赛程安排如下：(1.2) ,(3,5),(4,6),(8,7),(1,3),(4,2),(8,5),(7,6),(1,4),(8,

12、3),(7,2),(6, 5),(1,8),(7,4),(6,3),(5,2),(1,7),(6,8),(5,4),(2,3),(1,6),(5,7),(2,8), (3,4),(1,5),(2,6),(3,7),(4,8)其中每一个数代表一个队，括号里表示每两个队进行比赛。同样可以得到N =9的一种赛程安排：(1.2) ,(3,4),(5,6),(7,8),(1,9),(2,4),(3,6),(5,8),(7,9),(1,4),(2,6),(3,8),(5,9),(1,7),(4,6),(8,2),(9,3),(5,7),(1,6),(4,8),(2,9),(3,7),(1,5),(6,8)

13、 ,(4,9),(2,7),(3,5),(1,8),(6,9),(4,7),(2,5),(1,3),(8,9),(6,7),(4，5),(2,3)4.4对问题四的分析先用用每个队的每两场比赛中间间隔的场次数之和SUM来衡量赛程的公平性。当SUM不同时，SUM大的队伍对其比赛结果越有利。当 SUM相同时，用每次间隔场次的方差来衡量赛程的公平性， 其中方差越小的队对其比赛的结果越 有利。当SUM相同且每次间隔场次的方差也相同时，两个队比赛时，我们用双 方已参加比赛的次数来衡量比赛赛程的优劣， 其中在双方比赛时，已参加比赛次 数越少的队，对其比赛的结果就越有利。五、模型的建立与求解5.1问题一的模型

14、建立与求解根据对实际问题的分析可知，进行单循环赛时各队每两场比赛中间得到的休整时间是否均等，对于球赛的输赢起着决定性的作用，问题一需要我们对于5支球队的比赛，给出一个各队每两场比赛中间都至少相隔一场的赛程，因为队伍较少，所以利用排除-假设法可以得到一种理想的赛程安排。假设这五支球队分别 定义为A, B,C,D,E队，5支球队进行单循环赛比赛的总场次数 x = n(n1)，则五2支球队比赛的总场次数为X=5*(51)02五支球队进行比赛，因为五支球队没有明显的次序特征，所以第一场比赛出场队伍组合有C； =10种可能。假设 代B两支球队先进行比赛，要满足各队每两场比赛中间都至少相 隔一场这个条件，

15、因此第二场比赛只能从 C,D,E这三个球队中选择两支进行比赛， 共有Cs 种选择，即CD,CE,DE o假设第二场比赛队伍组合为 CD，在之前条件约束下，仅有A,B,E 可以参加第三场比赛， 即AB,AE,BE，可以设第三场比赛队伍组合为 EA。因为球队之间 进行的是单循环赛， 所以在任何两队之间只能进行一场比赛，对任何一队而言，曾经与其交战过的队，在以后的比赛中当不再相遇。以此类推，以后各场比赛赛程安排可以为BC,DE,AC,BD,EC,AD,BE。所以符合条件的比赛场数共有 10 3 2 2 2 = 240场。如图一所示：CBE图一、五个队伍参赛赛程安排图因为五个队伍比赛场次数较少可以将其

16、转化成如下形式的赛程表三，可以直观清晰的看出每两场比赛相隔场次数的特点。表三、五个队伍比赛间隔场次表ABCDE每两场比赛间相隔场次数IAX16931,2,2B1X47102,2,2C64X281,1,1D972X52,1,1E31085X1,2,1下面我们利用Matlab编程验证这种假设-排除法的准确性，编程能求出总的 240场次比赛情况，只要从中找出与上面对应的赛程安排就能证明此种方法准 确。下表四为Matlab软件求解出的相应结果，五个队伍参加五轮十场比赛满足 要求的赛程安排：表四、五个队伍参赛赛程安排I1-25-14-52-41-4I3-42-31-35-32-5从表格可以看出，结果与假

17、设-排除法得出的结果相同，证明针对参赛队伍 较少的情况此种方法简易可行。5.2问题二的模型建立与求解考虑到各队每两场比赛中间都至少相隔一场时让赛程尽可能公平的情况下，求每两场比赛中间相隔的场次数的上限。题目要求我们安排N支球队的单循环赛程，并使赛程对各队来说尽量做到公平。要想做到公平，其衡量的指标之一是： 考虑各队每两场比赛之间得到的休整时间是否均等、或是差距不大为此采用“逆 时针轮转法”对此问题进行处理，首先我们将参加比赛的球队由编号分别为字母 A B,C, D分别用数字1、2、3、4等代替表示，然后固定第1队，按左边由上而 下、右边由下而上（即逆时针转动）排成完整的两列。为了确定比赛顺序，

18、要先将比赛场次的顺序按轮转法排出。 仔细观察我们可 以发现，奇数会出现轮空的情况，而偶数则不会出现轮空的现象， 所以要将参赛 队伍的数量根据奇偶性进行讨论（当N=<4时，各队的每两场比赛中间相隔的场次 数的上限为0,在此不予讨论。）：（1）当N为偶数时，各队每两场比赛之间相隔的场次数的上限分析如下：当N =6时，根据附录中的程序算出总共的比赛次数为 15场，如下表所示：表五、6个参赛队的单循环赛比赛场次顺序轮转表I第一轮第二轮第三轮第四轮第五轮I1-65-11-41-31-22-5463-52-436462-3265645将其转化成如下形式的赛程表六，可以直观清晰的看出每两场比赛相隔场次

19、 数的特点。表六、赛程与相隔场次数表123456每两场比赛间隔场次数I1X13107412,2,2,2213Xr 6112P 9 :3,2,1,13106X38142,1,1,343113X155|542815X121,3,3,21 6 1914512X3,221nl由此表可得当N=6时，各队每两场比赛中间相隔的场次数的上限为 1。由 此我们通过编程得出当N=8,10, , 2n等偶数时重复当N =6时的算法并计算 他们的上限。得出参赛对数 N与队每两场比赛中间相隔的场次数的上限 M的关 系如下表七：表七、当N为偶数时的参赛队伍数与上限关系表参赛对数N6i81012J50J上限M1234J23

20、J因此，由上述图表可推测得出规律：当N为偶数时，各队每两场比赛之间相 隔的场次数的上限为：（N/2） 2场。当N=100时，经过编程得出各队每两场比 赛中间相隔的场次数的上限为 48，经由我们推导出来的公式计算得当 N =100 时，各队每两场比赛中间相隔的场次数的上限也为48，由此便可验证公式的正确性。（2）当N为奇数时各队每两场比赛之间相隔的场次数的上限分析如下：当N=5时，根据附录中的程序算出总共的比赛次数为 10场，如下表八所示：表八、五个队伍参赛赛程安排表第一轮第二轮第三轮第四轮第五轮1-2 d1-54-52-41-43-43-21-35-32-5将其转化成如下形式的赛程表九，可以直

21、观清晰的看出每两场比赛相隔场次 数的特点。表九、赛程与相隔场次数表12345每两场比赛间相隔场次数d1X16931,2, 221X47102, 2 ,2r 36 :4X281, 1, 14972X52, 1, 1| 531085X1,2, 1II由此表可得当N =5时，各队每两场比赛中间相隔的场次数的上限为1.由此我们通过编程得出当N =7,19, .2n，1等奇数时重复当N=5时的算法并计算 他们的上限。得出参赛对数N与队每两场比赛中间相隔的场次数的上限M的关系如下表十：表十、当N为奇数时的参赛队伍数与上限关系表I参赛对数N57911J49J|上限M1234J23J因此，由上述图表可推测得出

22、规律：当 N为奇数时，各队每两场比赛之间相隔的场次数的上限为：N 一3 /2。当N =99时，经过编程得出各队每两场比赛中间相隔的场次数的上限为48，经由我们推导出来的公式计算得当N =99时，各队每两场比赛中间相隔的场次数的上限也为48，由此便可验证公式的正确性。5.3问题三的模型建立与求解在达到第二问上限的情况下，可通过轮换模型得到N = 8和N = 9的赛程安排。当N =8时，把1固定在左上角不动，其余元素按逆时针轮换法轮换，一共 轮换了 (N -2)次。根据附录中的Matlab的编程得到当N = 8时的具体轮换过程可见下表十一：表一、八个队伍参赛赛程表第一轮1-23-54-68-7第二

23、轮1-34-28-57-6第三轮1-48-37-21-5第四轮1-87-46-35-2第五轮1-76-85-42-3第六轮1-65-72-83-4第七轮1-52-63-748由上表可知，具体赛程安排如下：(1,2),(3,5),(4,6),(8,7),(1,3),(4,2),(8,5),(7,6),(1,4),(8,3),(7,2),(6, 5),(1,8),(7,4),(6,3),(5,2),(1,7),(6,8),(5,4),(2,3),(1,6),(5,7),(2,8), (3,4),(1,5),(2,6),(3,7),(4,8)N =8时每两场比赛间隔相隔场次数如下表十二：表十二、各队

24、伍比赛相隔场次数表队相隔的场次数d相隔场次总数DI13， 3， 3， 3， 3， 31824, 4, 4, 3, 2, 219n1 32, 4, 4, 4, 3, 21942, 2, 4, 4, 4, 31954, 4, 3, 2, 2, 2171 64, 3, 2, 2, 2, 41773, 2, 2, 2, 4, 41782, 2, 2, 4, 4, 418 1当N =9时，采用逆时针轮转法.将队号数为1的队伍位子固定不变且遇到偶 数轮时在该轮中轮空，因要和上一轮轮空的队配成比赛，奇数轮中1则不能轮空 从奇数轮到偶数轮逆时针轮换。由偶数轮到奇数轮时第一列不变，第二列向上移一个位置,使得第一

25、组最后一组轮空.一共轮转N-2次.N =9时的具体轮换过程可见下表十三(轮空位用0替代)表十三、八个队伍参赛赛程表第一轮第二轮第三轮第四轮第五轮第六轮第七轮第八轮1-21-01-41-01-61-01-81-03-42-42-64-64-8：6-86-98-9|5-63-63-82-82-9：4-94-76-7|7-85-85-93-93-72-72-54-59-07-97-05-75-03-53-02-31根据逆时针轮转法，表中奇数轮末尾遇0轮空与相邻的偶数轮首位遇0轮空 的两支队搭配比赛。例如第三轮末尾第五场第七队轮空，第四轮首位第一场第一 队轮空，则十四场比赛队伍组合为第七队和第一队。由

26、上表可知，具体赛程安排如下：(1,2) ,(3,4),(5,6),(7,8),(1,9),(2,4),(3,6),(5,8),(7,9),(1,4),(2,6),(3,8),(5,9),(1,7),(4,6),(8,2),(9,3),(5,7),(1,6),(4,8),(2,9),(3,7),(1,5),(6,8) ,(4,9),(2,7),(3,5),(1,8),(6,9),(4,7),(2,5),(1,3),(8,9),(6,7),(4, 5),(2,3).N =9队每两场比赛间隔相隔场次数如下表十四：表十四、各队伍比赛相隔场次数表队:相隔的场次数d相隔场次总数D13 4 3 4 3 4

27、32424 4 4 4 4 4 42834 4 4 4 4 4 32743 3 4 4 4 4 42654 4 4 4 3 3 32563 3 3 3 4 4 42474 4 3 3 3 3 32383 3 3 3 3 3 42293 3 3 3 3 321通过验证这两种模型都是满足条件的.并且这两种模型都可以扩充到N为任偶数或是奇数的情况5.4问题四的模型的建立与求解前面三问都是在只考虑每两场比赛间相隔场次数这一指标下讨论赛程的公 平性，即赛程安排都是以各队休整时间是否均等作为最优目标。在这种情况下， 只能做到尽可能的均衡，而不可能使各队的总的间隔时间场次数完全相等。 由此, 我们想到可以用

28、每个队的每两场比赛中间间隔的场次数之和SUM来衡量赛程的公平性。很显然，对于SUM越大的队，他们休整时间比其他的队就长，对于他 们的比赛结果就越有利。当每个队的每两场比赛中间间隔的场次数之和SUM相等时，我们可以根据每次间隔场次的波动程度来衡量赛程的优劣，在此我们引入另一个指标一一标准差S来衡量赛程的优劣。由下面图二中的疲劳指数可知在休 整时间相同的两个队参赛队比赛时，一个队的标准差 S越大时对此对越不利。在实际比赛过程中还有一些客观的人为对已参加比赛队伍的比赛情况的分 析，这一因素也会对比赛的结果产生影响。 所以当每个队的每两场比赛中间间隔 的场次数之和SUM和每次间隔场次的标准差 S相等时

29、，我们可以比较两队在进 行比赛时双方已参加比赛的次数来衡量这次比赛的优劣。我们知道在这两个队进 行比赛时，哪一方已经参加的次数越多，被对方所掌握的信息就越多，就越易被 对方看出本队的优势与不足从而制定针对本队的方案。这样便会对参赛多的一方产生不利的影响。综合上述可得：我们可以先利用 SUM来衡量赛程安排的公平性，当各队的 SUM不同时，SUM大的队，对其比赛的结果就越有利。当 SUM相同时，我们用 每次间隔场次的方差来衡量赛程的公平性，其中标准差S越小的队，对其比赛的结果就越有利。当SUM相同且每次间隔场次的标准差 S也相同时，两个队比赛 时，我们用双方已参加比赛的次数来衡量比赛程的优劣，其中

30、在双方比赛时，已参加比赛次数越少的队，对其比赛的结果就越有利。当N =8时，1到8队比赛时的相隔场次总数分别 18,19,19,19,17,17,17,18 根据我们定义的赛程标准，我们首先可以看出这场比赛对第二、第三、第四队的比赛结果比较有利。在根据标准差可知这三队的标准差相等， 所以不存在不公平 因素。最后我们看他们互相比赛时各队已参加比赛次数。当第二队与第三队比赛时，双方均已参加四场比赛，所以不存在不公平因素；当第二队与第四队比赛时 双方均已参加一场比赛，所以不存在不公平因素；当第三队与第四队比赛时双方 均已参加五场比赛，所以不存在不公平因素。由此可见此场比赛对第二、第三、 第四队的比赛

31、结果比较有利。当 N =9时，1到9队比赛时的相隔场次总数分别 24，28，27，26，25，24，23，22，21。由此可知本次比赛对第二队有利。六、模型的评价与改进6.1模型的优点1、赛程的编制能够推广到任意数N的情况。2、合理恰当的使用了表格和图形，使数据的体现和意思的表达更加清晰3、用排除-假设法可以得到一种理想的赛程安排。4、用Matlab来检验结果是否准确，便于对结果的肯定。5、逆时针轮转法可以使各队每两场比赛中间有至少相隔一场的情况下使赛程尽 可能公平。6逆时针轮转法所建立的模型实际操作性强 ，方法简便，当参赛队数较多时， 可以借助计算机实现赛程的编制。7、逆时针轮转法使各轮比赛搭配合适，每轮比赛都有势均力敌的比赛，使各轮 比赛都保持紧张氛围。6.2模型的缺点1、排除-假设法只适用于参赛队伍较少的情况下，不具有普遍性。2、 由于是单循环赛，所以在安排时不必考虑真实实力的差异，但在实际中往往 不是单循环赛，这还有待进一步改进.3、当N （一 7）为级数支球队时，未能证明所建立的赛程优劣指标下由“轮转法” 所到的赛程是最优的.七、模型的推广在现实生活中，我们经常会遇到比赛赛程安排的问题，而且比赛赛程安排的是否 公平在一定程度上决定了双方两队的胜负。 为了解决此类问题，我们采用逆时针 旋转法来安排赛程。逆时针轮转法最精彩的、对决定