比赛项目排序的优化模型.doc

第一页答卷编号：论文题目：比赛项目排序的优化模型参赛队员： 吴波 梁二伟 李素贤指导教师： 肖华勇参赛学校：西北工业大学报名序号： 1254第二页答卷编号：18比赛项目排序的优化模型摘要本文针对比赛项目的排序问题采用如下模型和算法，使每位运动员尽可能不连续参加两项比赛。针对只有14个项目、40名队员参赛的小型运动会的比赛项目排序问题，我们定义了两项目之间的距离，把排序问题看作是对所有比赛项目的一次遍历。由于我们考虑的是不需要返回起始点的排序问题，所以，文中论述了此问题可看成有种返回起始点的TSP问题，通过上面的构造，该问题便转化为经典的TSP问题。对此问题建立混合整数线性规划模型，目标就是保证连续参加两场比赛的人次为最小。利用lingo编程对原问题进行遍历搜索，求解得到一组最优次序。根据转化的定义和模型的约束可知，得到的搜索结果必为一环路，需要在假设条件下进行手工处理，在项目间距不为零，即有运动员连续参加两项比赛的地方选取一处断开。最后可得只有第11号运动员连续参加第4，13两场比赛，39号运动员连续参加第8，9两场比赛、项目顺序为：对于问题2，沿用以上思路，给出了算法及其框图，编程求解得到最优排列顺序。经调整后得到此大型运动的比赛项目顺序为：其中，有6名运动员需要连续参加两场比赛：872号运动员会连续参加第16，51两场比赛；736号运动员会连续参加第49，46两场比赛；606号运动员会连续参加第10，3 两场比赛；594号运动员会连续参加第45，7 两场比赛；883号运动员会连续参加第41，14两场比赛；317号运动员会连续参加第40，33两场比赛；考虑到各种实际情况及所用模型和算法本身的优缺点，对本算法的合理性和结果的可行性进行分析评议。针对问题2的排序结果，以整体满意度最高为双目标给出了解决运动员连续参加比赛问题的建议和调整方案。最后考虑到不同比赛项目的实际强度、场地限制、运动员身体条件以及天气等因素，我们对所建模型加以改进，使所得排序结果更加合理，更符合实际，模型的可行性得到很大提高。关键字：项目排序 TSP算法 整数线性规划 一、 问题重述在国务院领导下，由国家体委会同有关部门、各群众组织和社会团体共同推行的一项依托社会、全民参与的体育健身计划，是与实现社会主义现代化目标相配套的社会系统工程和跨世纪的发展战略规划。现在，以全民健身为主要内容的群众性体育活动蓬勃开展，举国上下形成了全民健身的热潮，人民群众健康水平不断提高，同时也扩大了竞技体育的社会影响，提高了竞技体育水平。现在各级、各类、各种运动比赛比比皆是，这不但提高了全民的身体素质，而且使一批运动员脱颖而出，成为运动健将，为国家争得了荣誉。 在各类运动比赛中，为使比赛公平、公正、合理的举行，在比赛项目的排序过程中，一个基本要求是应当尽可能使每位运动员不连续参加两项比赛，以便运动员恢复体力，发挥正常水平。由此提出以下问题：1、 对于14个比赛项目，40名运动员参赛的问题（见附表1），建立数学模型，并且合理安排比赛项目顺序，使连续参加两项比赛的运动员人次尽可能少；2、 文件“运动员报名表”给出了61个比赛项目、1050人参加比赛的报名情况，要求给出算法及其框图，同时给出合理的比赛项目排序表，使连续参加两项比赛的运动员人次尽可能的少；3、 说明上述算法的合理性；4 、对于问题2的排序结果，给出解决“运动员连续参加比赛”问题的建议及方案。二、 问题分析对于个比赛项目的排序问题，我们希望连续参加两场比赛的运动员人次尽可能的少。由于运动会比赛项目排序是一个很现实的问题，排序过程要考虑很多实际因素，为了使模型清晰，目的明确易于求解，我们排除意外以及人为等因素的影响把问题转化为纯数学问题求解。把每项比赛看作一个节点，连续参加两项比赛的运动员人次看作这两个节点之间路径的权值，并设初始进行项目和最终进行项目间的权值为零，需要把所有比赛项目进行顺序排序，目的是使“遍历”所得的权值总和为最小。于是我们把此问题转化为旅行销售员问题（TSP）求解。考虑到以不同的项目作为初始项目得到的排序结果必不相同，所以对于个比赛项目的排序问题，实际上是转化为了个TSP问题，可以利用计算机编程搜索选取最优解。可以用多种方法把TSP表示为整数规划模型。这里采用混合整数规划模型，引入变量增加约束条件，目的是消除在一次排序中可能出现多于一个互不连通的子环路的情况，可以对该约束条件起到的作用进行推证，以确保其能起到严格保证所得结果不出现“子遍历”的作用。由于在TSP问题中售货员最终回到出发点，所以由以上转化过程可知，采用模拟为TSP建立模型求解用计算机编程搜索得到的结果必为一环路。由于最优结果必为有限个，我们可以对所得结果进行手工处理。考虑到在所得环路中存在连续参加两项比赛的运动员可能并不唯一，所以在假设条件下，任意选择一个有运动员连续参加两项比赛的地方断开，就可以得到一个项目的排列次序。再通过查表进一步可得连续参加两场比赛的运动员序号。至于此算法的适应性，我们从TSP本身的特点出发，结合本问题的规模及所作假设对现实情况的忽略，给出所建模型的合理性分析。由于求解问题的最终结果时采用了手工处理，所以在解决“运动员连续参加比赛”的问题时，我们应该从实际情况出发，选取有运动员连续参加的相邻两项目强度较大的地方断开，使所排项目顺序对每一位运动员都尽量的公平，争取整体满意度为最大。由此，结合求得的问题2的比赛排序结果，我们给出解决连续参赛问题的建议和基本方案。由于在运动会的实际举行中，不可能完全按照我们所作的假设排列比赛项目，所以我们可以对所建模型进行改进，把不同比赛项目的剧烈程度、运动员身体条件和其他因素考虑在内，增加约束条件，使模型更加实际化、可行化。三、 模型假设1、 各比赛项目之间相互独立，不存在发生的先后次序关系，且所有比赛项目顺序进行，发生时间互不重合；2、 各比赛项目剧烈程度相同，即运动员参加不同项目所需的运动强度相同；3、 运动员参加全部比赛均不会出现导致无法参赛的意外情况发生；4、 比赛进行不受意外因素（如天气）的影响，避免过程中产生中断；5、 只要不连续参加比赛，运动员休息时间长短对体力恢复没有影响。四、 符号说明14个比赛项目间的距离， 61个比赛项目间的距离，14个比赛项目距离的邻接矩阵61个比赛项目的距离的邻接矩阵 小型运动会报名表的生成矩阵大型运动会报名表的生成矩阵小型运动会中第个比赛项目，； 大型运动会中第个比赛项目，参见小型运动会的人数参加大型运动会的人数五、 模型的建立及求解从所要解决的问题和基本假设出发，我们把项目排序问题转化为经典的旅行售货员问题（TSP）,建立混合整数线性规划模型求解，目标即为使连续参加两场比赛的运动员人次尽量少。1、 模型的建立 首先对所给问题的数据进行预处理。对于问题1 ,把题目所给小型运动会的比赛报名表看作一个4014的矩阵，表中有“#”的位置设为1，其他位置设为0。即： 进一步作出n个比赛项目之间的距离定义,定义如下： 若两个比赛项目连续安排的话，则到的距离 为连续参加这两个比赛项目的人数总和,第i个项目到自己的距离为一个充分大的数M。得到n个比赛项目之间距离的邻接矩阵分析矩阵知：矩阵的第列表示参加第个比赛项目的所有运动员情况，矩阵的任意两列其对应元素成绩之和，就是连续参加i，j两个比赛项目的人数之和，即为据矩阵乘法的意义，可知：则原问题转化为含有14个接点的图，比赛项目为图的节点端点，为图的边；求解连续比赛项目最少就是图的最小流问题（一笔画问题）。我们利用求解TSP问题的思想求解。在原图中任意选取两个点作为最短路的首点和尾点，则有种情况；改变点的距离，使其值为最小值0，以保证在的得到的回路中他们是相连的，断开弧i，j，就是我们想要的排序结果。 但是种情况，不需要一一求解，我们可以求解TSP问题，找到图的最短回路，剪断回路中的最长边。下面我们利用此思想来进行求解：可以用多种方法求解TSP问题，这里我们把该问题的解看作是对所有比赛项目的一次遍历，建立整数线性规划模型，编程搜索最优路径。对每个比赛项目，制定一个0-1变量，令其目标为使为最小。每个比赛项目前只能安排一个项目所以存在以下约束： ；每个项目之后也只能安排一个比赛项目，所以有以下约束： ；但仅以上约束条件不能避免在一次遍历中产生多于一个互不连通回路。为此我们引入额外变量，附加以下充分约束条件： ；于是我们可以得到如下的模型：我们通过lingo8.0（lingo程序间附录）求解得到TSP问题的回路： 此回路中有三条边的值为1（回路中边的最大值），我们可以在中任意选择一条边剪开。（一） 当剪开（8，9）时我们得到比赛项目的排列顺序：参赛顺序1234567实际比赛项目81571136参赛顺序891011121314实际比赛项目21412101349通过我们的验证程序（见附录）可以知道，在此方案下出现连续的场次为： 11号运动员连续参加第2，14两场比赛，11号运动员连续参加第13，4两场比赛:（二）当剪开（4，13）边的时候，我们得到比赛项目的排列顺序：参赛顺序1234567实际比赛项目26311751参赛顺序891011121314实际比赛项目89413101214通过我们的验证程序知，在此方案下出现连续的场次为： 11号运动员连续参加第4，13两场比赛， 39号运动员连续参加第8，9两场比赛；（三）当剪开（14，12）边时，参赛顺序1234567实际比赛项赛顺序891011121314实际比赛项目15711362通过我们的验证程序知，在此方案下出现连续的场次为：39号运动员连续参加第13，4两场比赛，11号运动员连续参加第9，8两场比赛；综合分析这三种方案，可以看出方案一会使11号参加的比赛都是连续的，不可取，我们可以选择方案二或三，我们选择了方案二作为结果，作出了小型运动会的赛程安排表（见附录）。问题二的求解:在大型运动会中,比赛的项目为61种无法采用遍历的方法,我们也用问题一的求解思想把问题抽象成图的问题,利用求解TSP问题的思想求解。参考问题一的求解思路我们也把运动员的报名表抽象成矩阵， 同样作出比赛项目间的距离和比赛距离的邻接矩阵 则有 同样解决TSP问题来找出最优解。对每个比赛项目，制定一个0-1变量，令其目标为使为最小。每个比赛项目前只能安排一个项目,所以存在以下约束： ；每个项目之后也只能安排一个比赛项目，所以有以下约束： ；但仅以上约束条件不能避免在一次遍历中产生多于一个互不连通回路。为此我们引入额外变量，附加以下充分约束条件： ；于是我们可以得到如下的模型：我们通过lingo8.0（lingo程序见附录）求解得到一条回路: 此回路中有7条边的值为1（回路中边的最大值），分别为（41，14），（40，33） ，（12，31），（16，51），（49，46），（10，3），（45，7）我们选择了，边（12，31）处剪开，我们得到了下面的排列顺序：参赛顺序123456789实际比赛项目3139532544426158参赛顺序101112131415161718实际比赛项目303757165124292713参赛顺序192021222324252627实际比赛项目325611544338494635参赛顺序282930313233343536实际比赛项目918522615620555参赛顺序373839404142434445实际比赛项目2110350364574222参赛顺序464748495051525354实际比赛项目1728598601914114参赛顺序55565758596061实际比赛项目23344840334712在这个方案下，872号运动员会连续参加第16，51两场比赛；736号运动员会连续参加第49，46两场比赛；606号运动员会连续参加第10，3 两场比赛；594号运动员会连续参加第45，7 两场比赛；883号运动员会连续参加第41，14两场比赛；317号运动员会连续参加第40，33两场比赛；因此，有六个运动员连续参加比赛。 我们采用这种方法给出了大型运动会的比赛安排表（运动员参赛日程表.xls）。 六、 结果和算法分析问题一的结果分析： 我们对小型运动会的运动员报名表进行了统计分析，统计出此次运动会总的比赛场次： ；我们解决方案中有连续的场次： ；则连续场次出现的比例： ；参加此次运动会总的运动员： ；我们方案中会连续参加比赛的运动员： ；则连续参加比赛的运动员的比例： 通过上面的分析可以看出我们的方案很好解决了此次运动会赛程的安排问题问题二结果的分析： 我们对此次大型运动会的运动员报名表进行了统计分析，统计出此次运动会总的比赛场次 ；我们解决方案中有连续的场次 ；则连续场次出现的几率： ；参加此次运动会总的运动员： ；我们方案中会连续参加比赛的运动员： ；则连续参加比赛的运动员的比例： 通过上面的分析可以看出我们的方案很好解决了此次运动会赛程的安排问题。问题3、算法的合理性分析：该比赛项目排序问题经我们处理已转化为经典的TSP,并建立了混合整数规划模型，应用lingo编程搜索最优排序方案。其算法思路清晰，适应性强。当问题规模较小时，例如问题1的仅有14个项目的排序问题，在所有可行的排序方案中能很快的搜索到最优结果。唯一不足之处在于当问题规模较大，即比赛项目较多时，算法效率降低，求解时间延长。七、 模型的改进方案我们再处理本问题中，假定所有比赛的强度是一样的，但实际中比赛项目间的强度差距是很大的，比若在短跑比赛中100米和400米的强度是有差别的，长跑比赛中10000米和马拉松的比赛强度也是不一样的，而参加短跑或长跑运动员的比赛项目一般不少于 ，基于此考虑我们可以给出描述比赛强度的量，在实际安排比赛赛程时，在保证每位运动员不连续参加两项比赛的前提下，我们使相邻的比赛项目强度有所差异。在此思想下，对模型二进行了进一步的规划。 设定每个比赛项目的强度为了使相邻的比赛项目强度有所差异，建立目标函数 在原模型的基础上，做出双目标规划：处理所得结果时我们可以选取任意一个的地方断开，但考虑到各种实际情况，对断开位置的选择我们给出以下建议： 该在相邻强度为最大的两个比赛项目之间断开，以求尽量使所有运动员的整体满意度最高；对于连续参加过两个比赛项目的运动员来说，使其尽量休息更长的时间以后再参加下一个项目。从管理上加以改进：现代运动会参加的人越来越多，可以限制运动员参赛的项目，减少运动员参赛的数目可以在一定程度上解决运动员连续参加比赛，参赛项目的减少还可以使参赛人数的增加，从而还提高了比赛的观赏性. 可以安排不同类型的比赛间隔进行，比如田径中的短跑和长跑，运动员一般不会同时参加这两个项目，则可以安排短跑和长跑间隔进行。可以增长比赛的间隔时间，以便运动员充分休息，但在现代运动会中比赛项目很多的情况下不很可取。修改一定的规则减少比赛的时间或增加比赛时的暂停时间以便运动员充分休息。八、 参考文献1 姜启源 谢金星 叶 俊 数学建模(第三版) 北京 高等教育出版社出版 2 苏今明 张莲花 刘 波 工具箱应用 北京 电子工业出版社出版 3 梅长林 周家良 实用统计方法 北京 科学出版社出版4 刁在筠 郑汗鼎 刘家壮 运筹学 北京 高等教育出版社5 孙惠泉 图论及其应用 北京 科学出版社出版附录一：第一个问题的求解的程序：!比赛项目排序问题;model:sets: city / 1. 14/: u; link( city, city): dist, ! 邻接矩阵; x;endsets n = size( city);data: !邻接矩阵，它是对称的，当然也可以不是对称的; dist=6 2 1 2 0 0 1 0 1 2 1 1 1 1 2 8 1 4 1 0 1 1 1 3 1 0 2 1 1 1 6 1 0 0 0 3 1 1 0 2 2 1 2 4 1 9 1 1 2 1 0 2 1 0 1 1 0 1 0 1 7 2 0 1 1 1 0 1 1 2 0 0 0 1 2 8 1 2 1 1 1 2 1 2 1 1 0 2 0 1 7 1 1 1 0 2 2 1 0 1 3 1 1 2 1 10 1 2 1 4 2 2 1 1 1 0 1 1 1 1 6 1 1 1 3 1 2 3 1 2 1 1 1 2 1 10 1 0 0 3 1 1 0 1 0 1 0 1 1 1 6 3 1 1 1 0 2 0 1 2 2 4 1 0 3 10 1 0 1 2 2 1 1 1 2 2 3 0 1 1 8 4 1 1 1 1 2 2 1 2 1 3 1 0 4 10;!这里可改为需要解决的问题的数据，故此程序对61阶层矩阵亦可行;enddata !目标函数; min = sum( link: dist * x); FOR( city( K): !进行比赛项目K; sum( city( I)| I #ne# K: x( I, K) = 1; !完成比赛项目K; sum( city( J)| J #ne# K: x( K, J) = 1; ); !保证不出现子圈; for(city(I)|I #gt# 1: for( city( J)| J#gt#1 #and# I #ne# J: u(I)-u(J)+n*x(I,J)=n-1); ); !限制u的范围以加速模型的求解，保证所加限制并不排除掉本问题的最优解; for(city(I) | I #gt# 1: u(I)=n-2 ); !定义X为01变量; for( link: bin( x);end附录二：%Matlab验证程序；load table2.txt; %当调用的是tabel1是,就写成咯load table.txt;a=table2; %tabel1.txt和tabel2.txt存放的是原问题的邻接矩阵; m,n=size(a);d=zeros(n,n); %定义距离矩阵; for i=1:nfor j=1:n if(i=j) for k=1:m if(a(k,i)=1&a(k,j)=1) d(i,j)=d(i,j)+1; endend endendend p1=26311751 89413101214; %p1为原问题第一步的的比赛项目举行比赛顺序,有多组数据;%p1=2,6,3,7,11,5,1,8,9,4,13,10,12,14; %p1=81571136 2