赛程安排模型

第13卷第2期Vo1．13No．2达县师范高等专科学校学报(自然科学版JJournalofDaxianTeachersCoUege(NaturalScienceEdition)2003年6月Jun．嬲赛程安排模型“钟发平廖从攀任晓梅(达县师范高等专科学校 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 系，四川达州635000)【摘要】本文主要讨论了Tt支球队在同一场地上进行单循环赛的赛程安排问题。文章用图的方法给出了特殊几支球队的一个较优赛程安排，并讨论了一般情形下，1支球队比赛赛程安排的问题。另外，文章给出了一些衡量赛程安排优劣的指标，并用给出的指标对赛程安排进行了检验，结果表明这种安排是较优的。【关键词】赛程安排；单循环赛；指标【中图分类号】O157．6【文献标识码】A【文章~]10o8一镐86(2003)o2—0117—051模型假设I．比赛只在同一个场地上进行；两场比赛问的休息时间很短；2．假设参赛队的实力可以大致知道，且水平发挥正常；·3．比赛制度为单循环，且参赛球队没有缺赛的情况；4．各队每两场比赛中间相隔的场次数的上限为每个队都能达到场问的间隔数。2符号说明n：参加比赛的球队数d：当n为奇数且比赛不允许轮空时，各队每两场比赛中间相隔的场次数的上限d一：当n为偶数时，各队每两场比赛中间相隔的场次数的最大值d：当n为偶数时，各队每两场比赛中间相隔的场次数的上限k：为大于等于3的自然数Ⅳ：n个球队共进行的比赛场数S：综合指标ml对各队的综合实力划分的m个等级cm：观赏性指数6：人气指数或观众对球队的看好系数嘞：表示第队的第．『次休息的间隔场数3问题的分析与模型的建立3．I对问题1)，我们把5支球队看着5个点。分别用A、、C、D、E来表示，用线将他们两两联结，建立了一个图(如图I)。两个点之间有连线，表示两个队之间有一场比赛。显然五个队之间共进行了1O场比赛，在安排赛程时我们可以把I到1O的数字随便填在图I的边上，就可以得到一个比赛赛程，但这样安排不一定很公平，因为各个队每两场比赛的休整时间不能大致均衡。为了使各个队每两场比赛的休整时间大致均衡，保证赛程对每个球队的相对公平性，我们制定如下两条规则：规则l：各球队应尽可能早的进行他们的第一场比赛，他们的最后一场比赛尽可能安排得靠后。规则2：在安排每一场比赛时，要优先安排累计场问休息时间已最长的球队。规则I是为了保证总的场问休息时间最长，规则2是为了保证每个球队场问休息时间大致均等。3．2对问题2)，因为n个球队进行单循环比赛共有的比赛场数：N=c。为了保证比赛的相对公平性，我们同样要让安排的赛程满足问题I)的规则。当参赛球队数n为奇数时，我们结合规则I和规贝q2，利用问题1)的方法可以求得赛程的安排。当参赛球队队数n为偶数时．按照规则l和规则2，应该尽可能的让最先比赛的球队先结束比赛，后比赛的球队后结束比赛(这里的先后是相对的)．且在安排每一场比赛·【收稿Et期】2O0_0l—06‘【作者简介】钟发平(198)．男．四川达县人；廖从攀(1)．男．四川宣汉县人；任晓梅(1982_)．女．四川达县人；三作者均系达县师范高等专科学校数学系2000级学生。“本文获2000年全国大学生数学建模竞赛国家二等奖。117一——■了————1r———————一4维普资讯http://www.cqvip.com2O03年第2期钟发平，廖从攀，任晓梅：赛程安排模型时，优先安排累计场间休息时间已最长的球队。为达到此目的，我们将这些比赛分为t／,一1轮，每轮有{场比赛。将所有球队用l、2、3等编号，前半号数由l号起，由上至下写在左边，后一半号数由A下至上写在右边，然后用横线把图(1)：5个球队的赛程图相x,t~j号数连接起来，就是首轮(字母表示球队；线上的数的比赛。第2轮到第t／,一l轮的排字表示两个球队第Jlv场比法是把l号队位置固定不动，其赛)余的号码在前一轮的基础上按逆时针方向移动一个位置，再用横线连接起来，就可得到各轮的比赛安排。这样排出的赛程对每个球队来说都较为公平。问题2：先给出定理定理l：至少存在一个赛程，使得整个比赛总的休息场数最多。证明从略。比如五支球队的总的休息场数最少是l4场。最多是22场。定理2：设参加比赛的球队为t／,，若当t／,为奇数时，允许球队轮空(场地轮空)。在满足规则的前提下，各队每两场比赛中间相隔的场次数的最大值d一和其上限d与参加比赛的队数t／,之间存在：f号，(n为偶数，n≥6)d：{‘。l里，(，l为奇数，，l≥5)d，=d一一2我们用数学归纳法证明如下：证明：1．当n为大于等于6的偶数时：①取n=6时，赛程顺序安排如下表：第1轮第2轮第3轮第4轮第5轮】．_+6l¨51．-．4l+÷31．_+22+÷56¨45+÷34+斗23．_+63．-．42+斗36+÷25+÷64H5用矩阵表如下：每两场比赛问每队总的相4(1：e(2：C(3：o(4：E(5：F(6相隔的场数隔场次数●A(1]l31074l2，2。2。28B(2：l36l1293，2，l，17C(3：l0638142，1，1，370(4：7l13】551，1，3，38E(5]I42815121，3，3，29F(6jl9145123，3，2，19由上矩阵可知，每两场比间相隔的场次数的上限的最大118值：d一=3={，上限的最小值：dn‘n=d一一2=1定理成立。②假设t／,=2k一2，(是大于等于3的自然数)时，定理成立，即有等式d：丝；d：d一一2：丝一2j~,-'r③那么当t／,=2k时，就是在t／,=2k一2的基础上增加了两个队，则每一轮都将增加一场比赛，对每一轮的每一个队来说，场间休息都多增加了一次，而每一个球队在进行比赛时，是按逆时针方向依次轮转的，所以每两场比赛间相隔的场次数上限也只能相应地增加一次。否则比赛’的顺序将会被打乱。即有：d：丝+：；d：d一一2：警一212m下+。；m一一综上所述可得t／,≥6的偶数时，定理成立。2．当t／,为大于等于5奇数时：虚设一个球队，用0来表示，使球队总数成为偶数。遇到0的球队就轮空一次(即场地轮空一次)，其它的证明就同n为偶数时一样。所以在允许球队比赛轮空时(场地轮空)，定理成立。当t／,为任意正整数时，我们利用这种思想。用Mat／ab编程得到比赛的情况(程序1和程序2的结果分别是两种不同的表示方法)。当t／,为奇数，且场地不允许空时，则不满足定理1。此时结合规则l、规则2和图论模型安排赛程的方法，易知首轮比赛的第堡一l场和生场的队中一定存在只有休息一场的情况，因此各队每两场比赛间相隔的场次数的上限d=l3．3对问题3)，我们利用问题2)的分析方法分别编出了t／,=8，t／,=9时赛程。A5IE图(2)：9个球队的比赛赛程图(字母表示球队：线上的数字表示两个球队第n场比赛)3．4对问题4)，我们认为可以用来衡量一个赛程的优劣指标有：(1)各队相邻两场比赛问相隔场次数；较优的赛程应维普资讯http://www.cqvip.com钟发平，廖从攀，任晓梅：赛程安排模型2{X13年第2期使比赛队至少休息一场。的休息时间。(2)各队的总休息场数以及所有休息场数总和；较优的赛程要使各队的总休息场数差距尽可能的小以及所有休息场数总和尽可能的大，即满足下列目标规划条件：^●一2目标函数：rnax∑∑‘tl·1约束条件：lI∑由一∑d(i+I)，-．2n一2-l，-l差值尽量小，且≥I一^2-一2一l∑一∑d(ml』-lJ·l的(3)人气指数：同一场比赛安排不同场次会影响比赛观看人数，如果是商业比赛的话，就会影响整个比赛的经济收入，一般应将观赏性(精彩程度)较好的比赛安排在比赛的开始和结束。我们认为每场球赛的观赏性cm与参赛的两支球队的实力大小有关，并将它赋予不同的值。比如我们定义观赏性指数如下：参赛两队实力差距10％以下l0％．2o％2o％以上观赏性指效l0．80．6场次的安排影响人气的权数我们定义如下：第三场至结结束前结束前场次第一场第二场最后一场束前三场一场一场权效l0．80．60．80．90．8我们定义整个比赛的综合人气指数为s：s=∑，∑；要使赛程相对较优，就要在满足I和2的条件下』-1．使这个综合指标达到较大，即S：∑∑c，但按照我们的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 ，对于参赛队队数为偶数时，由于第一轮的安排直接影响以后各轮的场次安排，因此我们只需考虑第一轮羔的综合指标：sI=∑，但对于奇数队只能计算s；再则，根据各场次权数大小不同，易知将两个实力相当的强队的比赛场次安排尽量靠前和尽量靠后，可以使综合指数达到较大。4模型的求解4．I问题I的求解：我们在图(I)中任选一个顶点比如J4，选定一条与之相邻接的边作为第一场比赛，且在边上标上I，然后先沿五边形的逆时针选与上一边不相邻的边为第二场比赛，依次类推，直至标完五场比赛；接着考虑五边形各对角线，仍先从J4出发，逆时针隔一个顶点即D相连，为第六场比赛，再是BE、DC、AE、BC，如图(3)所示。这样得出的赛程，参赛的每一队在每场比赛后至少有一场ACD2E图(3)5个队的赛程图(字母表示球队，边上的效字表示比赛顺序)由图(3)可得5个队的赛程安排表：表I由图(I)得到的赛程表每两场比间相每队总的相隔＼BCDE隔的场次效场次效l693l，2，25Bl47l02，2。26_C6428l。1．13D97252。1．14E3l085l。2。l4由表(1)可得出在比赛过程中各队每两场比赛中间都至少相隔了一场的赛程，总的休息场数为22场。4．2对问题3的求解当：8时，共有的比赛场数：N：c；：二：28。把分为n—I：8一I：7轮，每一轮有{：鲁：4场比赛，按照问题2)的方法编制每轮各队的对赛情况如表(2)表(2)：8个球队的每轮各队的对赛表第一轮第二轮第三轮第四轮第五轮第六轮第七轮l·8l·7l·6l·5lH4l·3l·22++78·67+÷565·34H23+÷83+÷62·58H47+36+÷35+÷841++74·53H42+÷38·27·86++75·6根据表(．2)得到的赛程表如表(3)所示：表3由表(2)得到的8个球队的矩阵赛程表每两场每队总：l：2C：3D：4E：5，：6C：7：8阃相陌的相陌的次散场次敷^：l252ll7l395l3,3，3，3，3，3l8B：225l2227l92l64，4，3，2．2，2l7C：32ll28l83l5264，3，2。2，2,4l7D：4l72284l427ll3,2，2，2，4，4l7E：5l37l8428l0232，2⋯244，4l8，：69l93l4282462,2，4，4．4。3l9C：752l527l024加2,4，4。4。3。2l9．I=，：8ll626ll236加4，4，4，3，2．2l9总的休息场数为144场。当n=9时，如果场地可以轮空时，按照n为偶数时的方法编制每轮各队的对赛情况如表(4)119维普资讯http://www.cqvip.com2OO3年第2期钟发平，廖从攀，任晓梅：赛程安排模型表(4)9个球队的每轮各队的对赛表第一轮第二轮第三轮第四轮第五轮第六轮第七轮第八轮第九轮l++0l++9l++8l++7l++6l++5l++4l一3l++22—90++89—78—67++56++45—34++23H03—82++70—69—58++47—36—25++04++94++73++62++5OH49—38—27—06—95++85—64++53++42—3O++29—08—97—86—7当r／,=9时，场地可以轮空时的赛程安排矩阵如表(5)表(5)：9个球队的场地可以轮空的矩阵赛程表每两场比间相每队总的相隔A：lB：2C：3D：4E：5F：6G：7日：8I：90隔的次数场次数A：l41363l2621l6l16l4，4，4，4，4，4，4，432B：241203714338292255,5，S，4，3，3，3，331C：33620l532928324425，5，4，3，3，3，3，53lD：43l37l5l02742343l95，4，3，3，3，3，53lE：52614321052244l8384，3，3，3，3，5，5，53lF：621339275451739l33，3，3，3，5，5，5，532G：7l6828422454012343，3，3，5，5，5，5，433日：8l1293234417403573，3，5，5，5，5，4，333，：9622443l8391235303，5，5，5，5，4，3。3330l2542l938l3347305，5，5，5，4，3，3，333当r／,=9时，如果场地不能轮空时，我们建立图论模型。在模型1的基础上，我们增加4个点F，G，日，，分别代表4个球队，比赛的先后顺序按问题的分析(见图(2)所示)，对阵矩阵为：当r／,=9时，场地不能轮空时的赛程安排矩阵表(6)表(6)：由图(2)得到9个球队的场地不可以轮空的矩阵赛程表每两场比间相每队总的相ABCDE，G日，隔的场次数隔场次数All0l52428l83253，4，4，2，5，3，324Bl6l1292533l9144，4，2，4，5，3，325Cl062l6203034233，3，5，3，2，6，323Dl5l1273521263l4，3，3，5，4，4，326E2429l6731222363，4，3，5，1，4，626，2825203538l3174，4，3，2，4。2，625Gl83330211284273，3，5，2，5．2，222日32l9342622l3494，3，5，2，3，5，123，514233l36172793，4，2，5，3，3，4244．4解决问题4时，首先我们假设各队的实力系数在60～100之间，用计算机模拟产生出8～9个60～i00之间的任意随机数作为各队的实力系数，如下表所示：对别ABCDE，G日，I实力927880698673988976然后将各队排序，实力强的排在前面，并分别用代号1，2，3，⋯⋯，8，9表示，其对应如下：对别ABCDE，G日，代号823647l59其对阵形式如前面表2所示，用Mat／ab编程(程序3)．当t／,=8时，按照上述方法求出S约为3，如果没有排序及按照我们的方法编排，即使比赛间隔大致相当，计算出的’●维普资讯http://www.cqvip.com钟发平，廖从攀，任晓梅：赛程安排模型20O3年第2期一个随机安排的赛程的综合人气指标值约为2．2，当n：9时，我们必须考虑所有比赛的综合人气指数，随机排列(没有排序)所得赛程的综合指数的是22、8，及按我们上述思想(即球队先按实力排序后按表6编制的赛程)计算出能达到的最大综合指标值为28．2。可见我们编制方法还是较优的。参考文献：[1]徐全智，杨晋浩．数学建模入门[M]．成都：电子科技大学出版社，1996．[2]p开澄．图论及其应用[M]．北京：清华大学出版社。1981．[3]马振洪．篮球一篮球比赛方法及规则简介[M]．北京：北京体育大学出版社，1998．[指导教师刘浏责任编辑何聪】(上接第5页)ResearchonPropertiesofHolohedralSymmetryRealMatrixYANNeng——zhong(Departmentofmath，DaxianTeachersCollege，DazhouSichuan635000，China)Abstract：Itisdiscussedaboutpropertiesofholohedralsymmetryrealmatrixinthispaper．Itbeingpositivedefinitematrix，itsfullandnecessaryconditionsareeduced，eigenvalueandeigenveetorofthematrixiscalculatedwiththeseproperties．Keywords：symmetrymatrix；orthogonalmatrix；eigenvaluel2l维普资讯http://www.cqvip.com