赛程安排论文

赛程安排模型摘要：本文利用插空排列组合，数学归纳，1号位固定逆时针轮转等方法很好的解决了球类比赛的赛程编排问题。首先，在考虑每两场比赛间相隔场次数的前提下，结合查阅资料中的信息，建立赛程安排优化模型来解决赛程编排问题。对于问题一，在考虑每两场比赛间相隔场次数不能为零的情况下，运用插空排列组合，对比赛赛程进行编排，再通过对编排结果的分析得到：当参赛队伍n=5时，“各队每两场比赛中间都至少相隔一场”的每种赛程安排均具有相同的公平性。对于问题二，在问题一的基础上，考虑到n支球队的数量及球队的奇偶性，先采用数学归纳法求出n只球队的参赛场数的通项公式nS=321-nnn，然后巧妙地运用了“1号位固定逆时针轮转法”，将n只球队分为奇数和偶数两种情况进行讨论，并得出合理的结论。对于问题三，采用问题二中的排列方法，排出n=8,n=9时的比赛赛程，并通过对其结果的分析，使问题二中得到的结论得到进一步证实。对于问题四，在充分考虑到满足合理赛程的需求的前提下，给出在比赛中应需要考虑的其他因素，并通过对前几问的结论对比分析，对问题中的结论下一明确定义。本文所建立的赛程安排优化模型结构清晰、层次分明，图表能直观地表达其赛程安排情况，运用了一些常见的数学方法，并得到了相关资料中有力数据的支持，使其更具有推广价值。关键词：插空排列组合数学归纳法1号位固定逆时针轮转法一.问题提出你所在的年级有5个班，每班一支球队在同一块场地上进行单循环赛,共要进行10场比赛.如何安排赛程使对各队来说都尽量公平呢.下面是随便安排的一个赛程:记5支球队为A,B,C,D,E，在下表左半部分的右上三角的10个空格中,随手填上1,2,10,就得到一个赛程,即第1场A对B,第2场B对C,,第10场C对E.为方便起见将这些数字沿对角线对称地填入左下三角.这个赛程的公平性如何呢,不妨只看看各队每两场比赛中间得到的休整时间是否均等.表的右半部分是各队每两场比赛间相隔的场次数,显然这个赛程对A,E有利,对D则不公平.ABCDE每两场比赛间相隔场次数AX19361,2,2B1X2580,2,2C92X7104,1,0D357X40,0,1E68104X1,1,1从上面的例子出发讨论以下问题:1)对于5支球队的比赛,给出各队每两场比赛中间都至少相隔一场的赛程.2)当n支球队比赛时,各队每两场比赛中间相隔的场次数的上限是多少.3)在达到2)的上限的条件下,给出n=8,n=9的赛程,并说明它们的编制过程.4)除了每两场比赛间相隔场次数这一指标外,你还能给出哪些指标来衡量一个赛程的优劣,并说明3)中给出的赛程达到这些指标的程度二.问题分析2.1问题一比赛要求的是公平、公正，根据问题一，我们建立的模型需要解决的问题是：2.1.1满足每两场比赛中间都至少相隔一场的赛程一共有多少方案2.1.2建立一个最优且容易编排的赛程模型。赛程要求对于5支球队的比赛,给出一个各队每两场比赛中间都至少相隔一场的赛程。而公平性则通过每两场比赛间相隔场次数体现。2.2问题二、问题三各队每两场比赛中间相隔的场次数的上限,我们通过数学方法中的最优配备排列法解决。通过问题二的解决，问题三便可以迎刃而解。2.3问题四衡量一个赛程的优劣只通过每两场比赛间相隔场次数这一指标不能全面的体现比赛的公平性，问题四的提出、要求我们寻找其他指标，从而可以更好地体现比赛的公平性，使我们所建立的模型达到最优。符号说明：n表示参加比赛的球队的数量。ns表示一场赛事总共要进行比赛的次数。k假设每轮比赛的次数。j假设中间隔的场数。三.模型假设假设1：比赛时间充足，天气状况良好。假设2：假设3：为了尽量公平，假设每两场比赛间相隔场次数不能为零。四.模型建立与求解4.1问题一现有五只球队A,B,C,D,E要打小组赛，时间很充裕的可以采用循环制，即每支队伍分别跟其他4支队伍各进行一场比赛（如下）所示：EAEBDAECDBCAEDDCCBBA两两配对①；由①可得，一个赛程共打10场，但为了体现赛事的公平性，一个队每两场比赛中间都至少相隔一场的赛程。由此可以对①中的元素进行排列组合，以第一列元素为主族（如②所示）：)521(;54321为空位，AEADACAB②；从②中可以看出，有1,25个空位供剩余6个元素来插入，因此可以把①中第二列的三个元素插入②中，由于①中第二列元素中都含有B队，所以1号和2号位不能插入，由此得新的组合如下：)81,2(;87654321为空位BDAEBCADBEACAB③现③中共有8个空位供剩余三个元素插入，对剩余的三个元素和③中的元素分析，可得3，4，5，6，7中均不能插入剩余几种元素，2号位只能插入DE,8号位只能插入CE，1号位就只有CD了，由此可得出一个赛程如下：CEBDAEBCADBEACDEABCD表1赛程安排表ABCDE每两场比赛间相隔场次数AX2468111B2X795211C47X110222D691X3122E85103X121对于上述方案并不是唯一，A,B,C,D,E五只球队可任取五种间隔场数中的一种，共有5！种，而每种又有两种变化，故比赛场数共有240种。由此可得如下结论：①当参赛队伍n=5时，“各队每两场比赛中间都至少相隔一场”的每种赛程安排均具有相同的公平性。4.2问题二4.2.1nS的通项问题一中所给的球队较少，可以用简单的插空排列组合法来解决，由于此问中没有给定具体的参赛组数，且要在第一问的基础上来求n支球队比赛时,各队每两场比赛中间相隔的场次数的上限，因此我们首先要知道n支球队比赛时，一个赛事要进行多少场比赛，通过归纳得到规律如下：设n支球队比赛时，一个赛事要进行nS场比赛。当n=2时，无意义。当n=3时，nS=1+2=3；当n=4时，nS=1+2+3=6；当n=5时，nS=1+2+3+4=10；……当n=n时，nS=21-22-1-1-1-21nnnnnn；用数学归纳法得到通项公式nS=321-nnn；4.2.2分类讨论对于n支球队比赛的情况，讨论各队每两场比赛中间相隔的场次数的上限。我们把n支球队分为奇数和偶数来讨论。（1）n为偶数的情况通过查找资料，我们得到乒乓球单循环赛的赛程安排方法--逆时针论转法全称叫1号位固定逆时针论转法。它是各种单循环比赛中普遍采用的方法，先以阿拉伯数字作为代号,代替队名进行编排。以6人单循环赛为例，1号位固定逆时针论转法如下：表26队单循环赛赛程安排方法第一轮第二轮第三轮第四轮第五轮1--61--51--41--31--22--56--45--34--23--63--42--36--25--64--5其中各队每两场比赛中间隔分布如下：表3各队每两场比赛中间隔分布1参赛队123456间隔分布2,2,2,23,2,1,12,1,1,31,1,3,31,3,3,23,3,2,1由表2可知，1号位固定不变，其他元素逆时针旋转遇1跳过继续旋转，假设每轮比赛k场，间隔场数j；22kkn，由于所有对都要参加每一轮的比赛，所以我们只讨论两轮之间的变化情况，当k=3时，kjk2-；在变化时1号位固定不变，导致前一轮在1号位下边的哪一号和下一轮间隔为k；当k=n/2时，22-2njn；用1号位固定逆时针论转法推导，过程如下：1-22-223-24-3-1-2-121-2122-23-2-21-1122221-22-1-321nnnnnnnnnnnnnnnnnnnnnnnn；通过数学归纳法分析，发现每两轮之间1号位之间间隔始终是j=k-1，每轮左手边第k位旋转后和下一轮之间的间隔始终是j=k-1，介于1号位和左手第k位之间的元素，与下一轮的间隔始终是j=k，右上角第一位和下一轮的间隔始终是j=k，右手边从第二位开始到第k位与下一轮的间隔始终满足j=k-2。综上分析得出结论如下：②在满足逆时针论转法的前提下，当n只球队比赛22kkn时，各队每两场比赛中间至少相隔2-k场。（2）n为奇数的情况把队数按U型走向分成均等两边,n为奇数时,最后一位数字补为O成为偶数。第一轮只要在U形相对队数之间划横线,即为第一轮比赛秩序。第二轮开始固定左上角1数字,其余数字均按逆时针方向移动一个位置,即为第二轮比赛秩序,以后各轮比赛秩序以此类推。遇O队数即轮空队。以7对单循环赛为例，1号位固定逆时针论转法如下：表47队单循环赛赛程安排方法第一轮第二轮第三轮第四轮第五轮第六轮第七轮1--01--71--61--51--41--31--22--70--67--56--45--34--23--03--62--50--47--36--25--04--74--53--42--30--27--06--75--6表5各队每两场比赛中间隔分布2参赛队1234567间隔分布2,2,2,2,23,3,5,1,13,2,2,1,12,4,1,3,31,2,1,3,64,3,3,2,22,3,3,5,1方法同n为偶数时基本相同，从表4中可以看出，n为奇数时要考虑到每轮有一对轮空的情况，通过分析得出：③当212kkn时，各队每两场比赛中间至少相隔2-k场。综合上述两种情况，我们得出关于问题二的结论如下：④当n支球队比赛时,各队每两场比赛中间相隔的场次数的上限是2-k；4.3问题三结合问题二中的排列方法和结论，给出n=8,n=9的赛程如下表所示：表6n=8,n=9时单循环赛赛程安排第一轮第二轮第三轮第四轮第五轮第六轮第七轮第八轮第九轮轮场，共时，当728278,428nSnkn1--81--71--61--51--41--31--22--78--67--56--45--34--23--83--62--58--47--36--25--84--74--53--42--38--27--86--75--6轮场，共时，当936289,421-nSnkn101918171615141312290897867564534230382706958473625049473625049382706958564534230290897867表7各队每两场比赛中间隔分布3队数nn=8n=913,3,3,3,3,33,3,3,3,3,3,324,4,3,2,2,24,4,4,7,2,2,2343,2,2,2,44,4,3,3,3,2,543,2,2,2,4,44,3,6,2,2,4,352,2,2,4,4,43,2,3,2,2,4,762,2,4,4,4,33,6,2,4,4,3,472,4,4,4,3,22,3,2,4,4,8,384,4,4,3,2,26,4,4,4,3,3,293,4,4,4,7,2,2通过对表6、表7中数据的分析，证实了问题二中所得出的结论是相对合理的。4.4问题四就问题二中所选择的方案排法，经分析后发现有局部的不公平现象出现，且换种方式来说，假设参赛队有强到弱按序号一次往后排，如若1号队和2号队过早地相遇，那就对1号队和2号队明显不公平，用1号位固定逆时针论转法可得到解决，但如果是奇数队，就会使某队连续多轮总遇到上轮轮空的队，如表6中8号球队。循环赛的赛程安排存在多种编排方法。总的可归结为两类方法：一类是每轮转一个位置的方法，能够满足合理赛程的需求；另一种是每次轮转多个位置（n/2）-1的方法，能够满足“先后交替的需求”。问题三得到的结果符合第二种排法。五.模型评价5.1模型优点5.1.1赛程的编制能够推广到任意数n的情况。5.1.2合理恰当的使用了表格，使数据的体现和意思表达的更加清晰。5.1.3逆时针轮转法使各轮比赛搭配适合，每轮比赛都有势均力敌的比赛，使各轮比赛都保持紧张氛围。5.1.4逆时针轮转法使参赛各队比赛进度一致,编排方法简单,易操作、检查。5.2模型缺点5.2.1但当单数队在5个队以上时,抽签为倒数的第二数字队则在第四轮开始每轮均同上轮轮空队进行比赛,由此产生了球类比赛中的不公平竞争现象。为此我们采用了“贝格”“编排法予以解决。5.2.