学生建模报告：建模论文.doc

赛程安排的公平性问题程宁巧(20031090047)刘敏茜(20031090017)张洪杰(20031090066)本文对于单循环赛赛程安排的公平性问题进行的讨论，提出了公 平性的衡量标准：相邻两场比赛之间的相隔场次数首先对问题进行 初步分析，得到可建立起以各参赛队为顶点的完全图将问题转化为 给完全图赋权的的问题，采用轮转赋权法但是，随着〃的增多，用 图论解决困难对问题进行简化，用梯形转圈法和梯-矩形交替转圈 法构造了赛程表，并且给出了公平性指标叫，的一个上限号，其中 1叫为n支球队的赛程中的各队的每相邻两场比赛间的场次数最小值 最后提出了另外几个公平性指标关键字：完全图公平性指标一、 问题的提出:有n支球队在同一块场地上进行单循环赛，如何安排赛程使对各队来说尽量 公平呢？下面是随便安排的一个赛程：记5支球队为A, B, C, D, E,在下表左半部分的右上三角的10个空格中, 随手填上1,2,...10,就得到一个赛程，即第1场A对B,第2场B对C,第 10场C对EABCDE每两场比赛间相隔场次 数AX19361, 2, 2B1X2580, 2, 2C92X7104, 1, 0D357X40, 0, 1E68104X1, 1, 1我们仅观察每两场比赛相隔场次数，易见，这个赛程对A, E有利，对D则 不公平。

以下将以比赛相隔场数作为指标讨论单循环赛赛程安排的公平性问题模型的假设和符号说明:1、 每个参赛队按赛程准时参加比赛，无中途调整赛程的情况2、 赛程不考虑种子队等其他因素符号说明：n：参赛队的总数:参赛队编码(7=1, 2,…刀)w..：与第，队和第丿队所在的顶点相连的边的权:第i队在第丿场与第沖场比赛的间隔场次数(戶,2,…(/t-2))G：兼顾公平，平均每两场间隔的场次数，即平均间隔"—2G,：第丫支队总的间隔次数，且G严工gj.j 丿=i 叫:每相邻两场比赛间相隔的场次数的最小值每相邻两场比赛间相隔的场次数的最大值三、问题的初步分析：图一一个循环赛小，任何一个参赛队均须与其它 参赛队比赛由此，可建立赛程安排的完全图(如图一(n=5) )o其中顶点表示各个参赛队，边表示参赛队之 间的比赛，边的权表示赛程中的比赛场次边的 总数为C；问题需要完成对完备欧拉图进行权值 为1至C；的赋权，并且要求每个顶点的各个关联 边的权之间存在一定的差值，这些差值反映了该顶点代表的参寒队每两场比赛小相隔的场次数我们首先定义在由门支球队参赛的赛程中的各队的每相邻两场比赛间相隔 的场次数的最小值和最大值分别记为：叫训％｝, 妙严呼％｝(zjj J2 =1,2<--,h；71 J2 ^0显然，叫越大，公平性越好，在叫达到上限的情况下，越小，公平性越好。

我们要求出各队每两场比赛中间相隔的场次数的上限，即需解决如下模型:max{min{g. .}} = max {minn i、j " i ・/|可2H 叱J ”1,2…呼V J = 12"；且i H j）若两个相邻边的权的差值是r,则表示该队有两场比赛之间间隔（广1）场比 赛因此问题的实质是对所作的完全图的各边进行恰当的赋权，找出对边的赋 权的一种规律，便可得到问题的可行解但是，随着门的增加，边数将很快增大，给赋权带来不利我们结合赛程安 排表，改进算法，表格小作业，根据要求进行调试模型的建立:模型一、首先，我们安排五支球队的赛程，要求各队每两场比赛小间都至少相隔一场, 建立网络图：顶点集Y = ｛y｝,儿，儿，儿O5｝ = ｛人,B, C,D, E｝表示；边集 = ｛（”•, = 1,2,3,4,5; i < J 5 4｝表示参赛队进行比赛；权值W = ｛1,2,3,4,5,6,7,8,9,10｝表示循环赛的场次该网络如下所示： 则网络中顶点的相邻边的权满足：赋权的方法：（1） 对该网络图的外囤边按照逆吋针方向相间标记从而可得5条边的权值：（X，）2） i，（儿，儿）=2,（儿,y J = 3, （_y2 ,y3） = 4,（儿，儿）=5（2） 对相间一个顶点的边沿逆吋针方向按顶点顺序连续标记。

从而可得另外5 个权值：（Vi，儿）=6,（儿，儿）=7,（儿，y5） = & （儿，>i） = 9, （y5, y2）=10我们称这种赋权的方法为轮转赋权法：对相邻的边的权，按照一定的间隔和 一定的方向（逆时钟或顺时钟）标号；对于同等地位的边（相间顶点个数相同的 边）按照一定方向的顶点次序进行有序的标号由于标号按顶点有序进行，则不 会出现边的权相差1的情况最终得到当n二5时，赋权的网络图如图所少：对应的赛程安排如下表所示：y>y-2y-sY4*每两场比赛 间相隔次数YiX16931, 2, 2y21X47102, 2, 2y-s64X281, 1, 1*972X52, 1, 1Y531085X1, 2, 1表-可见，建立完全图，将问题转化为给完全图赋权，能得出可行解模型二、其次，对n个球队的情形建立模型:1、当n = 2k时，可以用梯形转圈法來构造赛程表构造法如下：设以k场比赛 为一轮，总比赛场数为C；,因此共有2k—1轮比赛，用2行k列矩阵Aj表示第 i轮赛程表，i=l,2,・・・,2k・l；令1 2 3 .・・ k-2 k-\ k2k 2—1 2—2 ... k + 3 k + 2 k + \A】中的第j列的两个元素表示参加本轮第j场比赛的两支参赛队的编号 (j=l,2,…,k)。

第二轮赛程表人2的排法是在Al的基础上，采用梯形转圈法确定 即A】中的左下角元素(2k)不动，其余的2k・l个元素看成—•个梯形圈，按逆吋针 方向转圈，每个元素移动一位，得到下一轮的赛程表A? 2 3 4 ... k_\ k k + \~Ao=-2k 1 2k... R+4 R+3 k + 2A3,A4,A5,-,A2k_2和A21都是由前一轮赛程表经梯形转圈法获得最后一轮赛 程农A2k-1为：「2—1 1 2 ... k-\ k k + \An_,=2k 2k-2 2k-3 ・・・ R+4 k + 3 k + 2(1) A|, A2, A3,…,A21确实是一个赛程表，即满足任意两队相遇一次且仅一次2) 各队的每相邻两场比赛间相隔的场次数的最小值mn满足：mn^[(n-3)/2]这是因为，对于V2k来说，从赛程表上看，它的每相邻两场都是相隔k・l场 对于其余的旳來说，由于它在每轮赛程表里面仅出现一次，并且在每轮移动中位 置仅移动一位，所以，在相邻的两轮中勺位置相隔k或k・2场，因此，mn=k-2 W[(n-3)/2]成立2、当n = 2k- 1时，可以用梯■矩形交替转圈法来构造赛程表。

构造法如下:设以2k—1场比赛为一•轮，而总比赛场数为C；,因此共有k轮比赛，用2行2k—l列矩阵Bi表示第i轮赛程表(i=l,2,...k),令1 2 3 k-2 Jt-1 k 2 3 4 k-\ k2—1 2k _2 2R-3 …k + 2 k + \ 2k1 2R-2 2—3 …k + 2 k +1 Bi中的第j列的两个元素表示参加本轮第j场比赛的两支参赛队的编号 (j=l,2,-,2k-l)o B)中的前k列小的元素l~2k・2形成一个梯形圈(上而l~k，下面 2k—2〜k+l),把这个梯形圈按逆时针方向转圈，转成一个矩形圈(上下两行都是 k-1个元素)，置于Bi的后k-1列，冗素2k-1始终固定不动B2的排法是将B]中的矩形圈按逆吋针转成梯形圈，置于B2 的前k列，再把此圈转为矩形圈，置于B2的后k・l歹U,元素2k・l的两个位置还 是原位不动本文称这样的转圈为梯■矩形交替转圈法因此，2 3 4 …k-{ k R + l 3 4 5 k k + \2k -1 1 2—2 … k+3 k + 2 2k-\ 2 1 2k-2 … + 3 R + 2B3、B4、B5、……Bi和Bk都是由前一个赛程表经梯■矩形交替转圈法获得。

最 后一轮赛程表Bk为：2k-22k-lI 2 …k-3 k-22k-3 2k-4 …k + 1 kk-\2k-1I 2 3 k-2 k-l2k-2 2k-3 2k-4 …k + 1 k同前而n=2k时的情形相似可得：(1) 按梯■矩形交替转圈法所作的B】、B2、B3 和Bk确是一种赛程表2) mn=k—2^[(n~3)/2]综上所述：对于任意的参赛队数n(n$2),至少存在一种赛程安排，使得 g达到上限[(n-3)/2]o依据上述方法，对于n二8及n=9的情形我们得到如下的赛程表:yiY2YaY4ysy6y?ys每两场比赛 间隔场次数总的间隔场次 数YiX252117139513, 3, 3, 3, 3, 318Y225X12227192164, 4, 3, 2, 2, 217丫32112X818315264, 3, 2, 2, 2,417Y417228X41427113,2, 2, 2, 4,417*137184X2810232, 2, 2, 4, 4, 418y691931428X2462, 2, 4, 4, 4, 319y?5215271024X202, 4, 4, 4, 3, 219ys116261123620X4, 4, 4, 3, 2,219表二yiy-zY3Y4ysyoy；yyy每两场比赛 间隔场次数总的间隔场次 数y>X332925211713953, 3, 3, 3, 3, 3, 321y-233X1630112762414, 4, 4, 7, 2, 2, 225y-s2916X12267232204,4, 3,3,2, 2,220Y4253012X822319344, 3, 6, 2, 2, 4, 324*2111268X41835153, 2, 3, 2, 2, 4, 824y617277224X3614312, 6, 2, 4, 4, 3, 425y?1362331836X32102, 3, 2,4,4, 8,326924219351432X286, 4, 4, 4, 3, 3, 226Y951203415311028X。