比赛项目排序的研究27629.docx
( 4.5 )《比赛项目排序的研究27629.docx》由会员分享，可在线阅读，更多相关《比赛项目排序的研究27629.docx（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、比赛项目排序的研究（马元 陈陈三磊 刘刘世家）摘 要：本论文研研究了比赛赛中经常碰碰到的问题题，即如何何合理安排排赛程，使使得连续参参加两项比比赛的运动员人数达到最少，达达到公平的的目的。通通过对题目目的分析并并结合实际际，提出合合理假设，把把参赛表转转化为0-1矩阵，运用有关矩阵的知识，结合运筹学中图与网络分析原理，利用Matlab和WinQSB软件分析并计算出结果，最终给出合理的比赛项目顺序，并提出优化的建议和方案。关键词： 0-1矩矩阵 WinnQSB Mattlab 图与网网络分析 Hannmiltton回路路一、问题的的提出在各种运动动比赛中，为为了使比赛赛公平、公公正、合理理的举行
2、，一一个基本要要求是：在在比赛项目目排序过程程中，尽可可能使每个个运动员不不连续参加加两项比赛赛，以便运运动员恢复复体力，发发挥正常水水平。1表1是是某个小型型运动会的的比赛报名名表。有114个比赛赛项目，440名运动动员参加比比赛。表中中第1行表表示14个个比赛项目目，第1列列表示400名运动员员，表中“”号位置表表示运动员员参加此项项比赛。建建立此问题题的数学模模型，并且且合理安排排比赛项目目顺序，使使连续参加加两项比赛赛的运动员员人次尽可可能的少；2说明上上述算法的的合理性；3对“问问题2”的比赛排排序结果，给给出解决“运动员连连续参加比比赛”问题的建建议及方案案。二、问题的的分析思路1
3、：把把表1看成成是一个440*144的0-11矩阵，00表示运动动员没有参参加了这个个项目，11表示参加加，设此00-1矩阵阵为矩阵AA，那么问问题中安排排合理的比比赛顺序用用数学语言言表示为调调整A的列列向量使之之成为矩阵阵B，若BB满足一定定的条件后后，会使BB中行向量量连续出现现1的次数数最少，那那么B就是是最终要排排出的比赛赛项目矩阵阵。在这个个过程中，我我们使用了了Hanmmiltoon回路、MMatlaab 、WWinQSSB软件等等来求解BB。三 、模型型的建立 1 模型型假设：（1）每个个运动员都都能按时参参加比赛；（2）天气气情况良好好，不出现现因天气原原因中断比比赛项目；（
4、3）单纯纯比赛项目目的早与迟迟不影响运运动员的技技能发挥；（4）两项项比赛不会会同时进行行；（5）运动动员在一夜夜休息后，体体力可以得得到充分恢恢复；（6）比赛赛中不考虑虑个人因素素（如裁判判不公等）影影响比赛的的公平性。2 符号说说明 A:初始矩阵阵 B:最优矩阵阵 i :运动员员序号 （ii=1,22,m） j: 项目序序号 (j=1,2,n) bjj:第j个个项目 (j=1,2,n) pii:初始矩阵阵A的列向向量 xiij:第i个个运动员参参加的第jj项项目，xij=1表示参参加，xiij=0表表示不参加加。 wrrs:第r项比赛项目对对第s项的影响响度(r,s=1,2n)，即连续续参
5、加r项项目和s项项目的运动动员人数。W：表示影影响力矩阵阵，即任意意两个项目目连续进行行，导致连连续参加两两个比赛项项目的运动动员人数的的组合而形形成的144*14矩矩阵,wrs为W矩矩阵的元素素 3 模模型的建立立:（1）把附附录一变换换为0-11矩阵A，如如图附录二二所示。然后运用用Matllab软件件求出A矩矩阵的列矩矩阵AT（2）求出出影响力矩矩阵W 由符号说明明，可知wrs=xr1* xs1+ xr2* xs2+ + xrm* xsm 由矩阵阵相关知识识知W= AT *A,运用用Matllab软件件求得W矩矩阵如下b1b2b3b4b5b6b7b8b9b10b11b12b13b14b1
6、62120010121111b228141011131021b311610003110221b424191121021011b501017201110112b600012812111212b711020171110221b8013112110121422b911101111611131b10231211121101003b1111010101116311b12102012241031010b1312211122301184b14111122121310410从矩阵中可可以很清楚楚地看出任任意两个比比赛项目连连续进行，导导致连续参参加两个项项目的运动动员人数例例w12表示若若项目一与与项目二排排
7、在一起，共共有两个人人连续参加加了项目一一与项目二二，而w11表示项项目一与项项目一的重重复人数，这这与本题无无关，不予予考虑。此时问题题演变成如如何安排14个个项目的顺顺序，使得连续参参加比赛的的运动员人人数最少。即对矩阵阵W=bb1,b22,b3,b4,bb5,b66,b7,b8,bb9,b110,b111,b112,b113,b114的各各列重新排排序四、模型的的求解（1）“旅旅行推销商商”问题：一一个推销商商从n个城城市v1 v2 vn中某一个个城市出发发，到其他他n-1个个城市推销销商品，每每个城市都都必须访问问并只经过过一次，最最后回到出出发点，那那么如何安安排他的旅旅行路线使使其
8、总距离离最短。 我们发现现，所求的的问题与“旅行推销销商”问题很相相似，我们们可以将此此W矩阵问问题看作为为14个城城市，现在在就是要使使连接这114个城市市的路线最最短，只不不过“旅行推销销商”问题是一一个闭环的的回路，项项目排序问问题是一条条直线而已已，如果我们们运用Haamiltton回路路解法求出出最优解，再再在这个闭闭环回路中中找出距离离最长（即即影响力最最大的两个个相临项目目）的两个个项目，从从中把它割割段，使闭闭环回路变变成一条直直线，便可可得到我们们所要的模模型的解了了 定义：Hamiiltonn回路设设b1, b2, b3bn是图G中中的n个顶顶点，若有有一条从某某一顶点bb
9、j(1jn)出发发，经过各各节点一次次且仅一次次，最后返返回出发点点bj的回路，则则称此回路路为Hammiltoon回路。形成的圈称为H圈。（2）Haamiltton回路路求解原理理：1,任取初初始H圈：C0=v1 ,v2vi,vj,vn, v12,对所有有的i,jj,1ii+1jjn,若若w(vi,vj)+w(vi+11,vj+1) ww(vi,vi+1)+w(vj, vj+1) 则在C0删删去边(vvi,vi+1)和(vj, vj+1)而加入边边(vi,vj)和(vi+11,vj+1)，形成新新的H圈CC，即： C=v1,v2,vi ,vj ,vj-1 ,vi+1 ,vj+1 ,vn ,v
10、 1 3,对C重重复步骤（22），直到到条件不满满足为止，最最后得到的的C即为所所求。 （3）运用用WinQQSB软件件可以进行行对hammiltoon回路的的求解。运运行WinnQSB软软件，调用用子程序NNetwoork MModelling,进入主界界面后,选选择Traaveliing SSalessmen Probblem,设置144个项目。采采用三种近近似方法：最近城市市法（Neearesst Neeighbbor HHeuriisticc），两两两交换法（Cheapest Insertion Heuristic），逐步包围法（Tow-way Exchange Improvement
- 配套讲稿：
如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制：
部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词：
- 比赛项目 排序 研究 27629
淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
限制150内