资源描述：
《【5A版】学生建模报告-建模论文.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、7A版优质实用文档赛程安排的公平性问题程宁巧（20GG1090047）刘敏茜（20GG1090017）张洪杰（20GG1090066）摘要本文对于单循环赛赛程安排的公平性问题进行的讨论，提出了公平性的衡量标准：相邻两场比赛之间的相隔场次数。首先对问题进行初步分析，得到可建立起以各参赛队为顶点的完全图。将问题转化为给完全图赋权的的问题，采用轮转赋权法。但是，随着的增多，用图论解决困难。对问题进行简化，用梯形转圈法和梯-矩形交替转圈法构造了赛程表，并且给出了公平性指标mn的一个上限，其中mn为n支球队的赛程中的各队的每相邻两场比赛间的
2、场次数最小值。最后提出了另外几个公平性指标。关键字：完全图公平性指标一、问题的提出：有n支球队在同一块场地上进行单循环赛，如何安排赛程使对各队来说尽量公平呢？下面是随便安排的一个赛程:97A版优质实用文档7A版优质实用文档记5支球队为A,B,C,D,E，在下表左半部分的右上三角的10个空格中,随手填上1,2,¼10,就得到一个赛程,即第1场A对B,第2场B对C,¼,第10场C对EABCDE每两场比赛间相隔场次数AG19361，2，2B1G2580，2，2C92G7104，1，0D357G40，0，1E68104G1，1，1我们仅观
3、察每两场比赛相隔场次数，易见，这个赛程对A，E有利，对D则不公平。以下将以比赛相隔场数作为指标讨论单循环赛赛程安排的公平性问题。一、模型的假设和符号说明：1、每个参赛队按赛程准时参加比赛，无中途调整赛程的情况。2、赛程不考虑种子队等其他因素。符号说明：：参赛队的总数：参赛队编码(i=1,2,…n)：与第i队和第j队所在的顶点相连的边的权：第i队在第j场与第j+1场比赛的间隔场次数(j=1,2,…(n-2))：兼顾公平，平均每两场间隔的场次数，即平均间隔：第i支队总的间隔次数，且：每相邻两场比赛间相隔的场次数的最小值。97A版优质实
4、用文档7A版优质实用文档：每相邻两场比赛间相隔的场次数的最大值。一、问题的初步分析：101254310310987106y1y2y3y4y5一个循环赛中，任何一个参赛队均须与其它参赛队比赛。由此，可建立赛程安排的完全图（如图一(n=5)）。其中顶点表示各个参赛队，边表示参赛队之间的比赛，边的权表示赛程中的比赛场次。边的总数为。问题需要完成对完备欧拉图进行权值为1至的赋权，并且要求每个顶点的各个关联边的权之间存在一定的差值，这些差值反映了该图一顶点代表的参寒队每两场比赛中相隔的场次数。我们首先定义在由n支球队参赛的赛程中的各队的每相
5、邻两场比赛间相隔的场次数的最小值和最大值分别记为：，显然，越大，公平性越好，在达到上限的情况下，越小，公平性越好。我们要求出各队每两场比赛中间相隔的场次数的上限，即需解决如下模型：，若两个相邻边的权的差值是r，则表示该队有两场比赛之间间隔(r-1)场比赛。因此，问题的实质是对所作的完全图的各边进行恰当的赋权，找出对边的赋权的一种规律，便可得到问题的可行解。但是，随着n的增加，边数将很快增大，给赋权带来不利。我们结合赛程安排表，改进算法，表格中作业，根据要求进行调试。二、模型的建立：97A版优质实用文档7A版优质实用文档模型一、首先
6、，我们安排五支球队的赛程，要求各队每两场比赛中间都至少相隔一场，建立网络图：顶点集表示；边集表示参赛队进行比赛；权值表示循环赛的场次。该网络如下所示：则网络中顶点的相邻边的权满足：，赋权的方法：（1）对该网络图的外围边按照逆时针方向相间标记。从而可得5条边的权值：（2）对相间一个顶点的边沿逆时针方向按顶点顺序连续标记。从而可得另外5个权值：我们称这种赋权的方法为轮转赋权法：对相邻的边的权，按照一定的间隔和一定的方向（逆时钟或顺时钟）标号；对于同等地位的边（相间顶点个数相同的边）按照一定方向的顶点次序进行有序的标号。由于标号按顶点有
7、序进行，则不会出现边的权相差1的情况。最终得到当n=5时，赋权的网络图如图所示：对应的赛程安排如下表所示：y1y2y3y4y513425109876y1y2y3y4y5每两场比赛间相隔次数y1G16931，2，297A版优质实用文档7A版优质实用文档y21G47102，2，2y364G281，1，1y4972G52，1，1y531085G1，2，1表一图二可见，建立完全图，将问题转化为给完全图赋权，能得出可行解。模型二、其次，对n个球队的情形建立模型：1、当n＝2k时，可以用梯形转圈法来构造赛程表。构造法如下：设以k场比赛为一轮，
8、总比赛场数为，因此共有2k－1轮比赛，用2行k列矩阵Ａi表示第i轮赛程表，i=1,2,…,2k-1；令Ａ1中的第j列的两个元素表示参加本轮第j场比赛的两支参赛队的编号(j=1,2,…,k)。第二轮赛程表Ａ2的排法是在Ａ1的基础上，采用梯形转圈法确定
