单循环赛制安排的数学模型.doc

No.2 韶关学院学生数学建模论文集 第二期（2003年8月） 实用标准文案 PAGE 82 精彩文档 单循环赛制安排的数学模型 陈晔，祝文康，何荣坚 1．韶关学院2001级数学与应用数学本科1班,广东 韶关 512005; 2．韶关学院2002级计算机科学技术本科3班,广东 韶关 512005 [摘要]: 本文首先通过对５支足球队单场地单循环赛程安排的问题，考虑对各队公平的相隔场次的情况下用排除假设法给出至少相隔一场的赛程安排的方法，遵循小数先走的原则时恰好发现了击剑比赛时n＝５的赛程安排规律，并讨论其不合理性．分奇、偶参赛队的情况给出只考虑相隔场次时的最大均等时相隔场次次数的最小上限证明．在编制n=８，n=９支球队赛程的过程中进一步研究多种循环赛制安排的方法，还给出Matlab编制的一般性的赛程安排程序．同时通过引入对实力的排序、比赛的精彩度、各球队机会最大均等、奇数队参赛必然遇到不公平的情况等展开讨论一些赛程安排方法的不足之处． 关键词: 最大均等; 轮转法; 实力指数; 精彩度 １ 问题的提出 你所在的年级有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 从上面的例子出发讨论以下问题 对于5支球队的比赛，给出一个各队每两场比赛中间都至少相隔一场的赛程． 当n支球队比赛时，各队每两场比赛间相隔的场次数的上限是多少． 在达到2）的上限的条件下，给出n=8、n=9的赛程，并说明它们的编制过程． 除了每场间相隔场次数这一指标外，你还能给出哪些指标来衡量一个赛程的优劣， 并说明3）中给出的赛程达到这些指标的程度． 2 基本假设 1）单循环赛中，n为偶数队参赛时，所有队都安排参加一次后为一轮比赛，轮数为n-1，奇数队参赛时，n-1队安排参赛一次后为一轮比赛，轮数为n ． 2）参赛队A、B、C、D……通过以往比赛成绩的排名或社会评价的排名按 实力从大到小顺序记为1、2、3、……n队． 3 模型的分析、建立与求解 1）第一轮第一场比赛安排A对B，第二场比赛安排C对D，在各参赛队每两场比赛间至少相隔一场的前提下，第二轮第一场安排除C、D外的任意两支球队比赛，第二场安排前一场没有参赛的任意两队参赛，曾经比赛交战过的队不再安排对决，以此类推，共安排5轮共10场比赛，以下只给出安排过程的部分分支： BD CE AD AB （已对战过） BE BC（已对战过） AC CD（已对战过） DE BD…… BC AB（已对战过） AE AD…… AB—CD BD…… BE……