数学建模竞赛获奖论文赛程安排数学模型.doc

《数学建模竞赛获奖论文赛程安排数学模型.doc》由会员分享，可在线阅读，更多相关《数学建模竞赛获奖论文赛程安排数学模型.doc（18页珍藏版）》请在沃文网上搜索。

1、 赛程安排数学模型摘要 队员：xxxxxx本文讨论的是对抗性比赛中的赛程安排问题。针对问题（1），当参赛球队为 5 支球队时，我们利用计算机进行枚举，共有 240 种满足条件的 编排方案。文中给出了一种具体的可行方案。当有 n 个队参加比赛时，对 n 为偶数和奇数时的情况分别讨论。 本文得到结论：当 n 为偶数时，每两场比赛中间至少相隔场数的上限为n - 3n - 42场；当 n 为奇数时，每两场比赛中间至少相隔场数的上限为场。并且对两个结论给予了详细的证明。2提供满足每两场相隔场次数上限条件的赛程编排方法是本文的关键。当参赛队数 n 为偶数时， 我们提供了“1”号固定左上角的逆时针“轮转法”

2、；当参赛队数 n 为奇数时，我们提供了“1”号固 定“填充编排法”。两种排法都能实现相隔场次数的达到上限条件。直接运用这两种方法就能够编排 参赛队数 n=8,9 的赛程。当运用“轮转法”，“填充法”排出一种赛程之后，将参赛队号任意选取两个对换，就能得到另 一种排法。根据这种思想，n 个队就有 n！种不同的排法。将最先排出的赛程顺序由后向前排列，得 到一种新的赛程，且这种赛程不能由前一种赛程对换得到。新的赛程对换后又有 n！种不同的排法。对于其他指标的提出，我们结合实际进行定性的分析给出 3 个附加指标：1）整个赛程中所有队 的间隔场次的波动性。2）最后一轮比赛的精彩程度。3）整个赛程各个队的平

3、均间隔场次。然后分 别对这三个指标进行定量的分析，给出衡量指标的数学表达式。最后，计算出第三问给出的 n=8 与 n=9 的竞赛次序达到的指标值。结果如下表：n=8n=9精彩程度激烈场次为 2激烈程度为 7激烈场次为 2激烈程度为 11波动性0.7867910.253968平均间隔3.0208333.507937赛程安排数学模型正文一问题的提出1背景 众所周知在竞技比赛中公平性是至关重要的。公平性表现在很多方面，比如，参赛队出 场的先后次序、比赛期间的休整情况等。对于对抗激烈、消耗体力大的竞技比赛，比赛期间的休整 尤其重要，休整时间的长短对参赛队竞技水平的发挥有很大的影响，因此一个好的赛程安排

4、应该使 每个参赛队在比赛期间的休整时间尽可能均等。为此我们研究以下问题。2问题一个年级有 5 个班，每班一支球队在同一块场地上进行单循环赛，共要进 10 场比赛， 如何安排赛程使对各队来说都尽量公平。比如说下面这个赛程的公平性如何呢，不妨只看看各队每 两场比赛中间得到的休整时间是否均等，表中 A,B,C,D,E 表示 5 支球队，表中数字表示出场的次序。 1为最先出场，10为最后出场，表的最后一列是各队每两场比赛间相隔的场次数，显然这个 赛程对 A，E 有利，对 D 则不公平。表1 ABCDE每两场比赛间相隔场次数AX19361，2，2B1X2580，2，2C92X7104，1，0D357X4

5、0，0，1E68104X1，1，1从上面例子出发讨论以下问题：1：对于 5 支球队的比赛，给出一个各队每两场比赛中间都至少相隔一场的赛程。2：当 N 支球队比赛时，各队每两场比赛中间间隔的场次数的上限是多少？3：在达到第 2 问的上限的条件下，给出 N=8,N=9 的赛程，并说明它们的编制过程。4：除了每两场比赛间的相隔场次数这一指标外，你还能给出哪些指标来衡量一个赛程的优劣，并 说明第 3 问中给出的赛程达到这些指标的程度。二模型的假设及符号说明假设：1每天有且仅有一场比赛，每天比赛的时间段固定并且每场比赛时间相同。2任两个球队在相等的休息时间里都能够得到同等程度休息。3比赛在一天中指定的时

6、间准时开始和结束并严格按照赛程的规定执行，不存在因为天气或 其他原因造成停赛的情况出现。4所建模型仅考虑开始比赛期间相邻两场比赛之间的休息时间对参赛队的影响，不考虑第一 场比赛之前与最后一场比赛之后的休息时间对参赛队的影响。5假定实力指数是衡量参赛方竞技水平的唯一参数。6赛程安排不考虑主客场的情况。符号说明：1N表示参赛队数；2m表示各队每两场比赛中间相隔的场次数的上限；3i,j表示参赛队的编号4a表示比赛的轮数5 xi 表示相邻两场比赛的间隔场数(i=1,2,3,.n)6 Ex 表示整个赛程各队相邻两场比赛的平均的间隔场次数7s 表示给定的一个赛程各组比赛间隔的方差三模型的建立与求解对于 n

7、=5 支球队的比赛，要求各队每两场比赛中间至少相隔一场的赛程，只需要手工编制或计 算机编制即可（算法和程序见附录 1），能够很容易地得到结果，见表 2 所示，而且满足这种条件的 编排方法共有 240 种之多。所以我们主要针对 n 支球队比赛的情况，从参队数为偶数和奇数两方面 展开讨论。表 2赛程及各队休整时间表（N=5）ABCDE每两场比赛间相隔场次数AX6183121B6X429112C14X107222D8210X5221E3975X1111参赛队为偶数的情形排法一：“1”固定左上角逆时针轮转法（简称：轮转法） “轮转法”的编排思路是：先将“1”号队确定在左上角，其他各队按号数大小顺序沿逆

8、时针方向依次逐队排列出第一轮次序；然后“1”号队固定左上角不动，其他各号每轮按逆时针方向转动一 个号位，从而排出以后各轮的全部次序（算法和程序见附录 3）。以 6 个参赛队为例，其竞赛次序及 编排方法如下：表 3轮转法及竞赛次序（N=6）第一轮第二轮第三轮第四轮第五轮161514131225645342363423625645定理 1：参赛队数 N 为大于 3 的偶数时，各队每两场比赛中间相隔的场次数的上限为m = N - 4 。2证明：分别证明各队每两场相隔场次数上限能够达到 m = N - 4 场，且仅为 m = N - 4 。22（1）存在性：首先证明当参赛队数 N = 2k 3 时，轮

9、转法可以使得各队每两场比赛之间都至少相隔 m = N - 4 = k - 2 场比赛。2依次把各队排号为“1”,“2k”，运用“轮转法”对赛程进行排列，每轮进行 k 场比赛，共进 行 2k-1 轮。我们只需考虑每相邻两轮中两场比赛的间隔。不妨设第 h 轮的第 i 场（1i k + 1) 号队自第 2k+1 轮 第 2k + 2 - j 场开始水平向左依次排 2 j - 2k - 2 场一直到 2 (2k + 2 - j) 轮的第 2k + 2 - j 场比 赛，若 2k + 2 - j 1 ，则第2 (2k + 2 - j) - 1轮第 (2k + 2 - j) - 1场比赛继续排 j 号队，

10、按阶 梯形依次向左上排列直到第 2k - j + 3 轮第 1 场比赛排 j 号队。之后的第 2k - j + 2 轮 j 号队轮空， 自第 2k - j + 1 轮第 k 场开始阶梯形依次向左上排列。即 j 号队继续排在第 2k - j 轮第 k-1 场比赛，第 2k - j - 1 轮第 k-2 场比赛，以此类推，直到第一轮结束（程序见附录 4）。以 7 个参赛队为例， 其竞赛次序及编排方法如下：表 4填充法及竞赛次序（N=7）第一轮第二轮第三轮第四轮第五轮第六轮第七轮（1）：14（4）：17（7）：67（10）：57（13）：47（16）：37（19）：27（2）：35（5）：34（8）

11、：13（11）：16（14）：56（17）：46（20）：36（3）：26（6）：25（9）：24（12）：23（15）：12（18）：15（21）：45注：表中（1）（21）表示比赛场次序号，数字 i 表示第 i 号球队。以后各表格中的符号含义相同。N=7 时，“填充法”具体编排步骤如下：第一步：第 1 轮，第 2 轮的第 1 场填入“1”，第 3 轮，第 4 轮的第 2 场填入“1”，第 5 轮，第 6 轮的第 3 场填入“1”，第 7 轮不填“1”第二步：第 15 轮的第 3 场填入“2”，第 6 轮不填“2”，第 7 轮的第 1 场填入“2”第三步：第 13 轮的第 2 场填入“3”，

12、第 4 轮的第 3 场填入“3”，第 5 轮不填“3”，第 6 轮的第 1场填入“3”，第 7 轮的第 2 场填入“3”第四步：第 1 轮的第 1 场填入“4”，第 2 轮的第 2 场填入“4”，第 3 轮的第 3 场填入“4”，第 4 轮不填“4”，第 5 轮的第 1 场填入“4”，第 6 轮的第 2 场填入“4”，第 7 轮的第 3 场填入“4”第五步：第 72 轮的第 1 场填入“7”，第 1 轮不填“7”第六步：第 74 轮的第 2 场填入“6”，第 3 轮的第 1 场填入“6”，第 2 轮不填“6”，第 1 轮的第 2场填入“6”第七步：第 76 轮的第 3 场填入“5”，第 5 轮

13、的第 2 场填入“5”，第 4 轮的第 1 场填入“5”，第 3轮不填“5”，第 2 轮的第 3 场填入“5”，第 1 轮的第 2 场填入“5”定理 2：参赛队数 N = 2k + 1 3 时，各队每两场比赛之间都相隔的上限为 m = N - 3 = k - 1 场2比赛。证明：分别证明各队每两场相隔场次数的上限为 m = N - 3 的存在性和最优性。2（1）存在性：首先证明当参赛队数 N = 2k + 1 3 时，填充法能够实现各队每两场比赛之间都至少相隔 m = N - 3 = k -1 场比赛的排法。2依次把各队排号为“1”,“2k”，“2k+1”，运用“填充法”对赛程进行排列，每轮进

14、行 k 场比 赛，共进行 2k+1 轮。我们只需考虑每相邻两轮中两场比赛的间隔。根据上述填充法，对于每个参赛队，始终保证每轮至多参加 1 场比赛。且在该队参加的相邻两 轮比赛中，或者是同一场次的比赛，或者后一轮比赛场次比前一轮大 1，对于前一种情况，比赛间 隔为 k-1；对于后一种情况，比赛间隔为 k。综合上所述，当参赛队伍数 N 为大于 3 的奇数时，始终有各队每相邻两场比赛中间相隔场次数为 m = N - 3 = k -1 的排法。2（ 2 ）最优性：证明当参赛队数 N = 2k + 1 3 时，各队每相邻两场比赛的间隔至多为m = N - 3 = k - 1 场。2用反证法。假设当 N=

15、2k+1 的时候存在一个 m = k 的排法。要保证间隔 k 场比赛，显然在前 k+1 场比赛一个队不可能比赛两场。也就是说前 k+1 场比赛需要有 2k+2 个不同的队进行两两之间的比赛。 这与只有 2k+1 个参赛队矛盾，故定理 2 的最优性得证。根据“1固定左上角逆时针轮转法”容易得出：当 n=8 时符合上限 m=2 的一个竞赛次序：第一轮第二轮第三轮第四轮第五轮第六轮第七轮（1）：18（5）：17（9）：16（13）：15（17）：14（21）：13（25）：12（2）：27（6）：86（10）：75（14）：64（18）：53（22）：42（26）：38（3）：36（7）：25（11

16、）：84（15）：73（19）：62（23）：58（27）：47（4）：45（8）：34（12）：23（16）：82（20）：78（24）：67（28）：56根据“填充法”容易得出当 n=9 时的一个符合上限 m=3 的一个竞赛次序：第一轮第二轮第三轮第四轮第五轮第六轮第七轮第八轮第九轮151989796959493929464514187868584838373635341317675747282726252423121656轮空队987654321五指标的制定1、指标设计 整个赛程的公平程度，主要取决于各个队在每两场比赛间相隔的场次数是否大致均等。这一指标是问题中已经给出的，并且前面的讨论

17、我们都是围绕这一指标去研究的，这是所有指标中最重要 的一条指标。同时我们认为这一指标隐含了“整个赛程实力分布是否均匀”这一指标的实现，因为 强队与弱队先后两次出场的场次间隔是大致均等的，这样可以保证各轮比赛都有可能出现精彩场面。假设球队之间存在实力差距，实力最强的参赛方为“1”号，实力次强的为“2”号实力最 弱的参赛方为“n”号。竞技实力越强，其实力指数越小；竞技实力越弱，其实力指数越大。比赛场次的激烈程度，主要取决于参赛双方的实力对比，同时与参赛双方的实力强弱密切相关。 比如说竞赛次序中激烈程度最高的，是实力指数差为“1”的比赛场次，称其为“激烈场次“。依据 激烈场次中参赛双方的实力指数和，

18、进一步区分激烈场次的激烈程度。附加指标 1：根据竞赛过程应逐步推向高潮，比如理论上冠亚军决赛既“1-2”这场比赛须排在 最后一轮，所以我们可采用“最后一轮的比赛的精彩程度”这一指标。假设有 n 个球队参加比赛，总的比赛场次为 n*(n-1)/2。为了研究方便我们规定实力指数之差小n于或等于的场次为激烈场次，可以计算出最后一轮比赛的激烈场次的次数。另外，由比赛双方的实力指数之和可以进一步衡量一场比赛的激烈程度。依此类推还可以得出 最后一轮比赛中的激烈比赛的平均激烈程度。平均激烈程度的值越小，平均激烈程度越高。例如： 因为（1+2）0&C(e)n*(n-1)/2-1DelseA2(g+1,D);e

19、ndD(i,j)=100; D(j,i)=100;endend endend附录 3轮转算法(n 只能取偶数，此程序是解 n 支球队参加比赛的最优赛程) ：1. 对于 n 支球队参加比赛，B 为一个 n/2 行（n-1）列的矩阵, A 为一个 n/2 行（n-1）列的矩阵，给min 赋值为 100。2.对于i=1，n/2， A(i,1)=i ,A(i,2)=n+1-i.3.对于j=1，n ，矩阵A的两列值分别赋给矩阵B的2*j-1和2*j列。4 矩阵A左上角的1固定不变，其他数据逆时针变一格，j自行加1， 如果j大于n执行第三步，否则输出矩阵A,A为一种最优赛程且执行第五步。5 对于 i=1，n-1，j=1，n/2 ，c=1，n-1，d=1，n/2 如果 （i*n/2+j） 小于（c*n/2+d）且这两场比赛有两个队有一样，则w为(c-i)*(n/2-1)+(d-j)，如果 min 大于w，w