【2017年整理】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则不公平. ? A B C D E 每两场比赛间相隔场次数 A X 1 9 3 6 1, 2, 2 B 1 X 2 5 8 0, 2, 2 C 9 2 X 7 10 4, 1, 0 D 3 5 7 X 4 0, 0, 1 E 6 8 10 4 X 1, 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赛程各队每两场比赛间相隔最小场次数 问题分析 在假设（1）下，即n个队在同～场地进何单循环赛共有M=场比赛，有M=（）！种赛程安排，通常M是较大的数字。M种赛程中各队比赛间隔情况不同，因而对各队的比赛有影响。题目中4个问题相互联系，基本的题是赛程安排公平性及其编排法。赛程的公平性而对所有参赛队而言，同时问题（2）中“各队每两场比赛中间隔的场次数的上限”‘ 应指每个队都满足的间隔上限，其数学 表达： d=max di di=min i=1,2,3,….. ! j,k,t=1,2,3,…n 建模思想 d的数学实质是一个最大值，因此可用一个线性规划模型来描述。具体考虑满足上限d要求的赛程编排法，则由于问题的特殊性，可将n分为偶数与奇数分别考虑； 当n=2k,我们建立一种称为‘循环规则”的赛程编制法, 并得到d的公式，作出证明； 当n=2k+1，建立一种称为“移位规则”的赛程编制法, 并得到d的公式，作出证明； 两种证明的思路方法一样，都属于“构造证明法”。最后将n为偶数与奇数的上限公式统一起来。 一般模型 d=max di di=min 5. 模型求解 5.1 问题（1）的解 表1 A B C D E 每两场比赛间相隔场次数 总间隔场次数 A X 1 7 4 10 2，2，2 6 B 1 X 9 6 3 1，2，2 5 C 7 9 X 2 5 2，1，1 4 D 4 6 2 X 8 1，1，1 3 E 10 3 5 8 X 1，2，1 4 其中