学生建模报告：建模论文

《学生建模报告：建模论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、赛程安排的公平性问题程宁巧(20031090047)刘敏茜(20031090017)张洪杰(20031090066)本文对于单循环赛赛程安排的公平性问题进行的讨论，提出了公平性的衡量标准：相邻两场比赛之间的相隔场次数。首先对问题进行初步分析，得到可建立起以各参赛队为顶点的完全图。将问题转化为给完全图赋权的的问题，采用轮转赋权法。但是，随着〃的增多，用图论解决困难。对问题进行简化，用梯形转圈法和梯-矩形交替转圈法构造了赛程表，并且给出了公平性指标nin的一个上限耳，其中为n支球队的赛程中的各队的每相邻两场

2、比赛间的场次数最小值。最后提出了另外几个公平性指标。关键字：完全图公平性指标一、问题的提出：有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我们仅观察

3、每两场比赛相隔场次数，易见，这个赛程对A,E有利，对D则不公平。以下将以比赛相隔场数作为指标讨论单循环赛赛程安排的公平性问题。二、模型的假设和符号说明:1、每个参赛队按赛程准时参加比赛，无屮途调整赛程的情况。2、赛程不考虑种子队等其他因素。符号说明：料：参赛队的总数:参赛队编码(7=1,2,*••77)W,.:与第丫队和第丿队所在的顶点相连的边的权gitJ:第，队在第丿场与第冲场比赛的间隔场次数(户1,2,…(才2))G：兼顾公平，平均每两场间隔的场次数，即平均间隔G,：第7支队总的间隔次数，且G产工阴

4、j=mn:每相邻两场比赛间相隔的场次数的最小值。Mn:每相邻两场比赛间相隔的场次数的最人值。三、问题的初步分析:图一一个循环赛小，任何一个参赛队均须与其它参赛队比赛。由此，可建立赛程安排的完全图(如图一(n=5))<>其中顶点表示各个参赛队，边表示参赛队之间的比赛，边的权表示赛程中的比赛场次。边的总数为C；。问题需要完成对完备欧拉图进行权值为1至的赋权，并且耍求每个顶点的各个关联边的权Z间存在一定的弟值，这些弟值反映了该顶点代表的参寒队每两场比赛中相隔的场次数。我们首先定义在由n支球队参赛的赛程屮的各

5、队的每相邻两场比赛间相隔的场次数的最小值和最大值分别记为：mn=min{Sij},Mn=max{gij}丿（ij仏=1,2，・・・‘;久J?Hi）显然，®越大，公平性越好，在叫达到上限的情况下，越小，公平性越好。我们要求出各队每两场比赛中间相隔的场次数的上限，即需解决如下模型:max{min{g/.}}=max{minnij"i心2m叱j彳1,2…響}（门=12・・/1；且「丰j）若两个相邻边的权的差值是厂,则表示该队有两场比赛之间间隔（广1）场比赛。因此，问题的实质是对所作的完全图的各边进行恰当的赋权

6、，找出对边的赋权的一种规律，便可得到问题的可行解。但是，随着n的增加，边数将很快增大，给赋权带来不利。我们结合赛程安排表，改进算法，表格屮作业，根据要求进行调试。四、模型的建立：模型一、首先，我们安排五支球队的赛程，要求各队每两场比赛中间都至少相隔一场,建立网络图：顶点集Y={y[9儿，儿，儿，儿}={A，BCD®表示;边集E=仏,炒=123,4,5;i

7、vv.7]-wij2>2,（dJ,厶=1,2,・・"J,厶幻）丿1工丿？赋权的方法：（1）对该网络图的外围边按照逆时针方向相间标记。从而可得5条边的权值：（）“2）=1，（儿，儿）=2,（儿,），]）=3,（力,儿）=4,（九,儿）=5（2）对相间一个顶点的边沿逆时针方向按顶点顺序连续标记。从而可得另外5个权值：（风，儿）=6,（力,儿）=7,（旳,儿）=&（儿,必）=9,（兀』2）=10我们称这种赋权的方法为轮转赋权法：对相邻的边的权，按照-•定的间隔和一定的方向（逆时钟或顺时钟）标号；对于同等地位的

8、边（相间顶点个数相同的边）按照一定方向的顶点次序进行有序的标号。由于标号按顶点有序进行，则不会出现边的权相差1的情况。最终得到当n二5时，赋权的网络图如图所示：对应的赛程安排如下表所示：yiY2%Y4y.每两场比赛间相隔次数yiX16931,2,2y21X47102,2,2Y364X281,1,1Y4972X52,1,1Y531085X1,2,1表一v31082图二可见，建立完全图，将问题转化为给完全图赋权，能得岀可行解。模型二、其次，对n