NBA赛程安排的数学模型与分析.doc

赛程安排的数学模型与分析 1前言 n支球队在同一场地上进行单循环赛有多种赛程安排，问题是如何编制符合公平性的赛程，数学上这是一个满足一定指标要求的配对排序问题。 本文在合理假设的基础上，由问题的数学实质，建立出问题的线性规划模型；由问题的特殊性将n分为偶数与奇数分别研究，获得关于各队每两场比赛之间相隔场次数上限的一般公式，用构造性方法加以证明；运用归纳的方法发现了这种特殊排序中的对称规律，由此设计出符合上限要求的计算机算法与实际人工编制法。文中对赛程优劣的评价指标也作了较多的探讨。 本文一个特点是，分析研究迄今体育界实际使用的赛程“循环编制法”，发现其对n为奇数时编制的赛程公平性差，给出了一种n 为奇数时编制简便、结果合理的人工编制法。 2问题的提出你所在的年级有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) 中给出的赛程达到这些指标的程度.赛程安排直接影响比赛的公平性，如何建立衡量一个赛程的优劣的指标，建立编制公平合理的排列问题的数学研究，也有数学意义。3基本假设（1）设n支参赛队在同一场地上进行单循环赛。（2）假设赛程的公平性只与赛程安排有关，而与裁判等其它因素无关。（3）在假设（2）下赛程的公平性就是指各队每两场比赛中间得到休整时间均等性，其中“每队每两场比赛”限定为指“每队每相邻两场比赛”。（4）假设任相邻两场比赛之间间隔时间相同。4建立模型 4.1符号说明n参赛队数N比赛场数M赛程总共安排数j队与k队比赛场次序号数t队与j队及k队两场比赛间最小相隔场次数(I,j)第i队与第j队比赛e各队在全部赛程中间隔场次数d各队每两场比赛中间相隔场次数的上限di第i赛程各队每两场比赛间相隔最小场次数4.2 问题分析 在假设（1）下，即n个队在同场地进何单循环赛共有M=场比赛，有M=（）！种赛程安排，通常M是较大的数字。M种赛程中各队比赛间隔情况不同，因而对各队的比赛有影响。题目中4个问题相互联系，基本的题是赛程安排公平性及其编排法。赛程的公平性而对所有参赛队而言，同时问题（2）中“各队每两场比赛中间隔的场次数的上限” 应指每个队都满足的间隔上限，其数学 表达：d=max didi=min i=1,2,3,. ! j,k,t=1,2,3,n4.3 建模思想d的数学实质是一个最大值，因此可用一个线性规划模型来描述。具体考虑满足上限d要求的赛程编排法，则由于问题的特殊性，可将n分为偶数与奇数分别考虑；当n=2k,我们建立一种称为循环规则”的赛程编制法, 并得到d的公式，作出证明；当n=2k+1，建立一种称为“移位规则”的赛程编制法, 并得到d的公式，作出证明；两种证明的思路方法一样，都属于“构造证明法”。最后将n为偶数与奇数的上限公式统一起来。4.4 一般模型d=max didi=min5. 模型求解5.1 问题（1）的解表1ABCDE每两场比赛间相隔场次数总间隔场次数AX174102，2，26B1X9631，2，25C79X252，1，14D462X81，1，13E10358X1，2，14其中d=1,具体编排法见下面问题3）解中n为奇数的方法。5.2 问题（2）的解当参赛队n=2k或2k-1(k=3,4,5),各队每两场比赛中间相隔的场次数的上限为d= ,n=5,6,7. 当n=8时：见表2表2A1A2A3A4A5A6A7A8每两场比赛间相隔场次数总间隔场次数A1X125521917133，3，3，3，3，318A21X162026611234，4，4，3，2，219A32516X212192274，4，3，2，2，217A45202X152427102，4，4，4，3，219A521261215X38184，3，2，2，2，417A69619243X14282，2，4，4，4，319A717112227814X43，2，2，2，4，417A8132371018284X2，2，2，4，4，418当n=9时：见表3表3A1A2A3A4A5A6A7A8A9每两场比赛间相隔场次数总间隔场次数A1X131626112116364，4，4，4，4，4，428A21X35103015252053，4，4，4，4，4，427A33135X22271712274，4，4，4，4，3，326A46102X34192924143，3，3，4，4，4，425A526302234X3138184，4，4，3，3，3，324A611157193X3328233，3，3，3，3，4，423A7212517291333X494，3，3，3，3，3，322A8162012248284X323，3，3，3，3，3，321A936527141823932X3，4，3，4，3，4，324为方便起见，设i表示n队中第i 个队(i=1,2,3.n)5.2.1 n=8的编制过程：循环规则八个队排成一个42矩阵，同一行两数表示这两队比赛（称为比赛矩阵），此矩阵表示第一轮比赛安排，如图1下面的安排中将某队（如1队）固定不移动，余下的队逆时针循环移动1位（上、下相邻两数的位置叫“1位”），得第二轮比赛安排，如图2 图1 图2按此规则移动6次，既得8队比赛28场的一个赛程，此赛程满足各队每两场比赛中间相隔场次数，达到上限d=(8-3)/2=2,此赛程见表2。一般n=2k，一个赛程有M=场比赛，按此规则需移动（n-2）次，得满足d的赛程。由“循环规则”编程得一上结果。5.2.2 n=9的编制过程：移位规则考虑一般n=2k+1，先建立一个2k(2k+1)矩阵称之为“生成矩阵”，由此矩阵即可生成赛程。下面是此矩阵的生成规则：（1） 将任一队（如2k+1队）先占第2k+1列的各行，余下各队占第一行的余下位置，不妨设1，2，2k队分别占第一行的1，2，2k列。（2） 将第一行前2k个数按下述规则向下移动得第二行，依次类似得其余各行；a. 将奇数行从第一行算起的第奇数个数右移1位到下一行；b. 将奇数行的第偶数个数左移1位到下一行；c. 将偶数行的第奇数个数左移1位到下一行；d. 将偶数行的第偶数个数右移1位到下一行；e. 不能移动（指移出矩阵外）的数垂直下移到下一行，如此移动n-2次则生成矩阵，由生成矩阵从第一行生起依次相邻两数表示一场比赛。此赛程满足各队每两场比赛中间相隔场次数达到上限d=(n-3)/2.当n=9时，d=(9-3)/2=3生成矩阵如图3。由此矩阵可生成比赛日程，依次为（1，2），（3，4），（5，6），（7，8），（9，2），1，4），.即得表3。由“生成规则”编程同样这一结果。5.4问题（4）的解衡量一个赛程优劣，除各队每两场比赛间相隔场次数上限d这个指标外，各队在整个赛程中总间隔场次数e的差异程度E也是一个重要的指标。可设E=Emax-Emin，E越大说明各队总体休整间隔数的差异大。见表2、表3，分别是n=8,n=9的满足d=(n-3)/2的赛程，n=8的此赛程E=19-17=2；n=9的赛程E=28-21=7。这里n=8的赛程中差异度较小，表现出各队总体休整时间较为均匀，因而此赛程就指标而言，也较为公平的，n=9的赛程中差异度较大，因而此赛程仍有不公平性。此外，除了每两场比赛间相隔场次数外，各队比赛之前的休息时间，即首轮比赛的出场次序，对比赛的成绩仍有一定的影响，（如在首轮中靠后面比赛可减少旅途劳累，可先观察各队情况等等）。如表2中，4队、5队首轮最后比赛，表3中，9队首轮最后比赛。实际中此因素无法解决，常采取抽签的方法来决定首轮的出场次序。关于赛程的优劣，除考虑公平性外，还有效率性问题，即考虑如何合理紧凑地安排赛程，使赛程的从时间较短。6模型评价6.1 本模型的结果成功地给出了同一场地单循环赛各队每两场比赛中间相隔场次数上限的计算公式，有一定的理论意义与实际意义。6.2关于同一场地单循环赛赛程编派法，至今实际中都采用“循环规则”，（见上文n为偶数编派法），通过我们的研究发现此规则虽然简易、对于n为偶数的赛程，符合d=(n-3)/2,从而有公平性，对于n为奇数，编派的赛程d(n-3)/2,有失公平性。表4是用实际方法对n=7编制的赛程（首轮1队轮空，1队不动）。其弊端是此赛程d=1，而按公式d=(n-3)/2=2。说明各队每两场比赛中间极不均等，如有间隔6场，有间隔1场，具体到一个队（如5队比赛与休整时间极不均等）。从比赛与休整的节奏，第一队最有利，第五队最不利，另外从各队总间隔场次数看，也有较大差异，说明实际赛程编制法有待改进。而本模型算法提出的“生成规则”（见上文n为奇数编派法）既简便又公平。表41234567每两场比赛间相隔场次数总间隔场次数1X19161310742，2，2，2，210219X91751513，3，5，1，1133169X6142123，2，2，1，19413176X311202，4，1，3，2125105143X2181，2，1，3，613671521121X184，3，3，2，2147411220818X2，3，3，5，1146.3 方法推广为解决n为奇数是实际编制赛程的弊端，将“生成规则”简化为便于手工编制赛程的方法，此方法可推广实际运用（具体方法见附录）。6.4方法程序时间复杂度分析本问题的线性规划模型表示的算法，其时间复杂度为O（！）。经定性分析，上限d的实际意义含有“先休息先比赛”之意，将此规则引入线性规划之中，建立“优化穷举法”，其时间复杂度为O（）。进一步，由于