2009年北京物资学院第三届数学建模竞赛试题.doc

2009年北京物资学院第三届数学建模竞赛参赛说明1. 北京物资学院数学建模竞赛试题共有三道（A、B、C），请选择一道与熟悉的题目回答，不必做其他题目。2. 请按规定的时间内 ( 5月15号下午5：00以前) 上交论文，过期无效。试卷要在用A4纸打印完成，手写无效。3. 论文请交到南实验楼403，交论文时间：5月15号上午9：00下午5：00。4. 由于竞赛题目有一定的难度，因此不必做完上一个问题，才能回答下一个问题，而是需要完整地把解题的思想表达出来。由于有些题目中的问题较多，很可能在竞赛期间做不完，你可以对某些问题不作回答，有兴趣的同学可以在竞赛后再作深入研究。5. 由于题目难度不可能完全相同，评审中将向难度较大的题目倾斜，请参赛选手在选题时加以考虑。A题：阅卷方案的确定在确定数学建模竞赛的优胜者时，常常需要评阅大量的论文。某次竞赛有两个题目，组委会共收到744个队完成的竞赛论文，其中A题有343份论文，由12位阅卷人组成的小组来完成评阅任务；B题有401份论文，由14位阅卷人组成的小组来完成评阅任务。最理想的评阅方法是每位阅卷人评阅所有的论文，并且最终给所有论文排序，不过，这种评阅方法工作量太大，花费时间过长。目前评阅论文是采用筛选方式，在一次筛选中，每位阅卷人只评阅一定数量的论文，并给出分数，论文满分为100分；阅卷人的任务是从中选出1/3的优胜者；每份论文最多有3个阅卷人评阅。在这次数学建模竞赛中，A题和B题采用以下两种不同的评阅方案：（1）A题评阅方案第一轮：阅卷人随机抽取论文进行评阅，当每份论文都由两位不同的阅卷人进行过评阅后，阅卷结束。对每份论文，当两位阅卷人给分相近时，将两个评阅成绩累加作为该答卷的总分；当两位阅卷人给分相差大于10分时，进入第二轮。第二轮：对进入第二轮的论文，阅卷人随机抽取自己没有评阅过的论文进行评阅；从每份论文的三个评阅成绩中取两个相近的分数之和作为该论文的总分。另外，因为竞赛规则规定，只需要选出1/3的优胜者，所以为了减少工作量，第一轮评阅得分之和排在后40%的论文不再进入第二轮处理。两轮评阅结束后，将论文按总分排序，确定优胜者。（2）B题评阅方案每份论文由三位不同阅卷人随机抽取评阅，将三个评阅成绩累加作为该卷的总分，将论文按总分排序，确定优胜者。附件1中的数据是一次竞赛评阅后的实际统计数据。请利用所给的数据完成下面的工作：（1）分析比较两种评阅方案，可以从工作量大小、误判的概率大小等方面进行比较。（2）附件1(评阅成绩.xls)是8位评委评阅181份试卷的评分结果，参照此数据进行分析，并分别给出采用以上两种评阅方案获得的排名。（3）对A题评阅方案，请再给出2种以上计算总分的方法，并比较其优劣；在第一轮评阅结束后，你认为可以淘汰掉多少论文后，再进行第二轮的评阅，说明理由。（4）对B题评阅方案，请再给出2种以上计算总分的方法，并比较其优劣。（5）在现有条件下，25位阅卷人在3天时间内评阅744份答卷，你们能否提供一个更公平合理的评阅方案。B题：地震问题下图为四川大地震一截图，主要是地震灾区县（市）公路网示意图，两地距离以实际距离为准（自行收集）。2008年5月12日发生大地震，该地区遭受地震。为考察灾情、组织自救，成都领导决定，带领有关部门负责人到受灾地区各县（市）巡视。巡视路线指从成都所在地出发，走遍各受灾县（市），又回到成都政府所在地的路线。路上合理考虑阻抗。问题1、假定巡视人员在各县停留时间t=1.5小时，市停留时间T=2.5小时，汽车行驶一般公路（国道）速度v=60公里/小时，行驶高速速度V=89公里/小时。若分一组巡视地图上的方框地区，如何设计巡视线路，最短时间为多少？若要在18小时内完成巡视，至少应分几组？请给出这种分组下你认为最佳的巡视路线。问题2、在上述关于t、v、T 和V的假定下，若分三组（路）巡视方框地区，试设计总路程最短且各组在巡视时间上尽可能均衡的巡视路线。问题3、考虑更为具体的受灾地区，如附表1所示（与问题1和问题2比较需要巡视的地区数增多），分2组考虑最佳巡视路线。 问题4、进一步考虑通用模型。已知有M个受灾地点，给定各点之间的距离和路况，在给定t、v、T 和V的假定下，若分2组（路）巡视受灾地点，试设计巡视时间最短的巡视路线。同学有兴趣的话，可以进一步考虑若分N组（路）巡视受灾地点，试设计巡视时间最短的巡视路线。附表1：四川主要受灾地区汶川县北川县绵竹市都江堰市广元市青川县成 都什邡市安 县平武县彭州市茂 县江油市理 县雅 安眉 山巴 中南 充遂 宁乐 山甘 孜广 安泸 州凉 山自 贡资 阳内 江说明：两地间的距离可以通过INTERNET网查询，路况可做一个大致估计，路上的行驶不需要很精确，但要大致合理。四川大地震一截图 C题：徽章问题在1994年的“机器学习与计算学习理论”的国际会议上，参加会议的280名代表都收到会议组织者发给的一枚徽章，徽章的标记为“”或“”（参加会议的名单及得到的徽章见附表）。会议的组织者声明：每位代表得到徽章“”或“”的标记只与他们的姓名有关，并希望代表们能够找出徽章“”与“”的分类方法。1. 请你帮助参加会议的代表找出徽章的分类方法；2. 对你的分类方法进行分析，如分类的理由、分类的正确与错误率等；3. 由于客观原因，有名代表（见附表）没能参加此次会议。按照你的方法，如果他们参加会议，他们将得到什么类型的徽章？附表：参加会议的名单及得到的徽章+ Naoki Abe - Myriam Abramson + David W. Aha+ Kamal M. Ali - Eric Allender + Dana Angluin- Chidanand Apte + Minoru Asada + Lars Asker+ Javed Aslam + Haralabos Athanassiou + Jose L. Balcazar+ Timothy P. Barber + Michael W. Barley - Cristina Baroglio+ Peter Bartlett - Eric Baum + Welton Becket- Shai Ben-David + George Berg + Neil Berkman+ Malini Bhandaru + Bir Bhanu + Reinhard Blasig- Avrim Blum - Anselm Blumer + Justin Boyan+ Carla E. Brodley + Nader Bshouty - Wray Buntine- Andrey Burago + Tom Bylander + Bill Byrne- Claire Cardie + Richard A. Caruana + John Case+ Jason Catlett + Nicolo Cesa-Bianchi - Philip Chan+ Mark Changizi + Pang-Chieh Chen - Zhixiang Chen+ Wan P. Chiang - Steve A. Chien + Jeffery Clouse+ William Cohen + David Cohn - Clare Bates Congdon- Antoine Cornuejols + Mark W. Craven + Robert P. Daley+ Lindley Darden - Chris Darken - Bhaskar Dasgupta- Brian D. Davidson + Michael de la Maza - Olivier De Vel- Scott E. Decatur + Gerald F. DeJong + Kan Deng- Thomas G. Dietterich + Michael J. Donahue + George A. Drastal+ Harris Drucker - Chris Drummond + Hal Duncan- Thomas Ellman + Tapio Elomaa + Susan L. Epstein+ Bob Evans - Claudio Facchinetti + Tom Fawcett- Usama Fayyad + Aaron Feigelson + Nicolas Fiechter+ David Finton + John Fischer + Paul Fischer+ Seth Flanders + Lance Fortnow - Ameur Foued+ Judy A. Franklin + Yoav Freund + Johannes Furnkranz+ Leslie Grate + William A. Greene + Russell Greiner+ Marko Grobelnik + Tal Grossman + Margo Guertin+ Tom Hancock + Earl S. Harris Jr. + David Haussler+ Matthias Heger + Lisa Hellerstein + David Helmbold+ Daniel Hennessy + Haym Hirsh + Jonathan Hodgson+ Robert C. Holte + Jiarong Hong - Chun-Nan Hsu+ Kazushi Ikeda + Masayuki Inaba - Drago Indjic+ Nitin Indurkhya + Jeff Jackson + Sanjay Jain+ Wolfgang Janko - Klaus P. Jantke + Nathalie Japkowicz+ George H. John + Randolph Jones + Michael I. Jordan+ Leslie Pack Kaelbling + Bala Kalyanasundaram - Thomas E. Kammeyer- Grigoris Karakoulas + Michael Kearns + Neela Khan+ Roni Khardon + Dennis F. Kibler + Jorg-Uwe Kietz- Efim Kinber - Jyrki Kivinen - Emanuel Knill- Craig Knoblock + Ron Kohavi + Pascal Koiran+ Moshe Koppel + Daniel Kortenkamp + Matevz Kovacic- Stefan Kramer + Martinch Krikis + Martin Kummer- Eyal Kushilevitz - Stephen Kwek + Wai Lam+ Ken Lang - Steffen Lange + Pat Langley+ Mary Soon Lee + Wee Sun Lee + Moshe Leshno+ Long-Ji Lin - Charles X. Ling + Michael Littman+ David Loewenstern - Phil Long + Wolfgang Maass- Bruce A. MacDonald + Rich Maclin - Sridhar Mahadevan- J. Jeffrey Mahoney + Yishay Mansour + Mario Marchand- Shaul Markovitch - Oded Maron + Maja Mataric+ David Mathias + Toshiyasu Matsushima - Stan Matwin- Eddy Mayoraz - R. Andrew McCallum - L. Thorne McCarty- Alexander M. Meystel + Michael A. Meystel - Steven Minton+ Nina Mishra + Tom M. Mitchell + Dunja Mladenic+ David Montgomery - Andrew W. Moore + Johanne Morin+ Hiroshi Motoda - Stephen Muggleton + Patrick M. Murphy- Sreerama K. Murthy + Filippo Neri - Craig Nevill-Manning- Andrew Y. Ng + Nikolay Nikolaev - Steven W. Norton+ Joseph OSullivan + Dan Oblinger + Jong-Hoon Oh- Arlindo Oliveira + David W. Opitz + Sandra Panizza+ Barak A. Pearlmutter - Ed Pednault + Jing Peng+ Fernando Pereira + Aurora Perez + Bernhard Pfahringer+ David Pierce - Krishnan Pillaipakkamnatt + Roberto Piola+ Leonard Pitt + Lorien Y. Pratt - Armand Prieditis+ Foster J. Provost - J. R. Quinlan + John Rachlin+ Vijay Raghavan - R. Bharat Rao - Priscilla Rasmussen+ Joel Ratsaby + Michael Redmond + Patricia J. Riddle+ Lance Riley + Ronald L. Rivest + Huw Roberts+ Dana Ron + Robert S. Roos + Justinian Rosca+ John R. Rose + Dan Roth + James S. Royer+ Ronitt Rubinfeld - Stuart Russell + Lorenza Saitta+ Yoshifumi Sakai + William Sakas + Marcos Salganicoff- Steven Salzberg - Claude Sammut + Cullen Schaffer+ Robert Schapire + Mark Schwabacher + Michele Sebag+ Gary M. Selzer + Sebastian Seung - Arun Sharma+ Jude Shavlik + Daniel L. Silver - Glenn Silverstein+ Yoram Singer + Mona Singh + Satinder Pal Singh+ Kimmen Sjolander + David B. Skalak + Sean Slattery+ Robert Sloan + Donna Slonim + Carl H. Smith+ Sonya Snedecor + Von-Wun Soo - Thomas G. Spalthoff+ Mark Staley - Frank Steph