对美国大学生数学建模竞赛的一些认识及感受(2013.12.11).ppt

1 对美国大学生数学建模竞赛的一些对美国大学生数学建模竞赛的一些认识及感受认识及感受根据同行老师课件整理根据同行老师课件整理2大纲大纲o一、美国大学生数学建模一、美国大学生数学建模竞赛（MCM）介）介绍o二、美国大学生数学建模二、美国大学生数学建模竞赛赛前准前准备o三、三、为什么要参加美国大学生数学建模什么要参加美国大学生数学建模竞赛？3一、一、美国大学生数学建模竞赛介绍美国大学生数学建模竞赛介绍o美国大学生数学建模美国大学生数学建模竞赛的的历史史o美国大学生数学建模美国大学生数学建模竞赛的的宗旨宗旨o美国大学生数学建模美国大学生数学建模竞赛的的特点特点o美国大学生数学建模美国大学生数学建模竞赛的的内容与形式内容与形式o美国美国MCM/ICMMCM/ICM竞赛规模模o近年部分近年部分竞赛题目目美国大学生数学建模竞赛美国大学生数学建模竞赛的历史的历史oMathematical Contest in Modeling（MCM）是）是一一项由由美国数学及其美国数学及其应用用联合会合会(COMAP)发起起组织的国的国际级竞赛项目，自目，自1985年开始年开始举办，每年一，每年一次。次。由由美国自然基金美国自然基金协会会和和美国数学及其美国数学及其应用用联合会合会共同主共同主办，美国运筹学学会美国运筹学学会、工工业与与应用数学学会用数学学会、数学学会数学学会等多家机构等多家机构协办。o1999年起，年起，美国数学及其美国数学及其应用用联合会合会又同又同时推出推出交叉学科交叉学科竞赛（Interdisciplinary Contest in Modeling），），简称称 ICM（涉及数学、（涉及数学、环境科学、境科学、生物学、化学、生物学、化学、资源管理等交叉学科）。源管理等交叉学科）。美国大学生数学建模竞赛美国大学生数学建模竞赛的宗旨的宗旨oMCMMCM的宗旨：的宗旨：鼓励大学鼓励大学师生生对范范围并不固定的各并不固定的各种种实际问题予以予以阐明、分析并提出解法，通明、分析并提出解法，通过这样一种一种结构，鼓励构，鼓励师生生积极参与并极参与并强调实现完整的模型构造的完整的模型构造的过程。程。oMCMMCM是国是国际大学生各大学生各类竞赛中中级别最高最高的一的一项赛事，每年吸引世界著名高校参事，每年吸引世界著名高校参赛，很多国内外很多国内外著名科研机构和企著名科研机构和企业将其作将其作为衡量学生素衡量学生素质和和水平的重要依据。水平的重要依据。我国自我国自19891989年开始每年参加，年开始每年参加，历届均取得届均取得优异成异成绩。6美国大学生数学建模竞赛的美国大学生数学建模竞赛的特点特点oMCMMCM的要求与国内的要求与国内竞赛大致相同大致相同o英文英文题目，要求提交英文目，要求提交英文论文，文，语言的障碍言的障碍对中国学生来中国学生来说是一个非常大的挑是一个非常大的挑战。oMCMMCM的的问题涉及到的知涉及到的知识面非常广泛。没有面非常广泛。没有固定的模式，要求固定的模式，要求赛前准前准备的知的知识非常多，非常多，诸如微分方程及数如微分方程及数值解，运筹学，解，运筹学，图论，高，高级算法等。算法等。o题目中往往目中往往不提供数据不提供数据或或提供很多数据。提供很多数据。72012 MCM A:The Leaves of a TreeoHow much do the leaves on a tree weigh?How might one estimate the actual weight of the leaves(or for that matter any other parts of the tree)?How might one classify leaves?Build a mathematical model to describe and classify leaves.Consider and answer the following:oWhy do leaves have the various shapes that they have?oDo the shapes“minimize”overlapping individual shadows that are cast,so as to maximize exposure?Does the distribution of leaves within the“volume”of the tree and its branches effect the shape?oSpeaking of profiles,is leaf shape(general characteristics)related to tree profile/branching structure?oHow would you estimate the leaf mass of a tree?Is there a correlation between the leaf mass and the size characteristics of the tree(height,mass,volume defined by the profile)?oIn addition to your one page summary sheet prepare a one page letter to an editor of a scientific journal outlining your key findings.82012 MCM A:一棵树的叶子一棵树的叶子o树上的叶子有多重？如何估上的叶子有多重？如何估计叶子的叶子的实际重量（或重量（或树木其它部分木其它部分的重量）？如何把叶子分的重量）？如何把叶子分类？建立一个数学模型来描述和分？建立一个数学模型来描述和分类叶叶子。回答如下子。回答如下问题：o1.为什么叶子有不同的形状？什么叶子有不同的形状？o2.叶子的形状尽量减少投影的影子重叠的部分，来使其曝光最大叶子的形状尽量减少投影的影子重叠的部分，来使其曝光最大化？叶子的分布包括化？叶子的分布包括树和它的分支的体和它的分支的体积会影响叶子的形状会影响叶子的形状吗？o3.考考虑树的概况，叶子的形状与的概况，叶子的形状与树的的概况或其分支有关的的概况或其分支有关吗？o4.怎么估怎么估计一棵一棵树的叶子的的叶子的质量？叶子的量？叶子的质量与量与树的尺寸特征的尺寸特征（概况定（概况定义的高度，的高度，质量，体量，体积）有关）有关吗？o除了一除了一页摘要，摘要，还准准备一一页的信向科学的信向科学杂志的志的编辑，概述你，概述你们的的发现美国数学建模竞赛的内容与形式美国数学建模竞赛的内容与形式内容内容 赛题：简化的实际问题赛题：简化的实际问题 答卷：一篇包含问题分析、模型假设、建立、求答卷：一篇包含问题分析、模型假设、建立、求解解(通常用计算机通常用计算机)、结果分析等的、结果分析等的全英文全英文论文。论文。形式形式 3 3名大学名大学本科生本科生组队，在组队，在4 4天天内完成通讯比赛内完成通讯比赛可使用任何可使用任何“死死”材料材料(图书图书/互联网互联网/软件等软件等),),但不得与队外任何人讨论（包括上网讨论）但不得与队外任何人讨论（包括上网讨论）宗旨宗旨创新意识创新意识 团队精神团队精神 重在参与重在参与 公平竞争公平竞争标准标准假设的合理性，假设的合理性，建模的创造性建模的创造性，结果的正确性，表述的清晰性。结果的正确性，表述的清晰性。美国美国MCM+ICMMCM+ICM竞赛规模竞赛规模2010年，年，MCM约有约有14国国(地区地区)2254队参赛，其中我国占队参赛，其中我国占82%;ICM有有356队参赛，其中我国占队参赛，其中我国占93%。2011年美国大学生数学建模竞赛吸引了来年美国大学生数学建模竞赛吸引了来自美国、中国、英国、加拿大、芬兰等自美国、中国、英国、加拿大、芬兰等16个国家的个国家的3510个代表队参赛。来个代表队参赛。来自哈佛、麻省理工和我国的北京大学、清华大学等知名高校学生参与了此项赛自哈佛、麻省理工和我国的北京大学、清华大学等知名高校学生参与了此项赛事的角逐。事的角逐。2012年总有年总有3697队参加！其中美国占队参加！其中美国占9%（341队队）！）！美国大学生数学建模竞赛题美国大学生数学建模竞赛题1998-2001o98A MRI Scanners（核磁共振扫描）o98B Grade Inflation（等级扩张）o99A Deep Impact（强烈的冲击）o99B Unlawful Assemly（非法的集合）o00A Air Traffic Control（空中交通管制）o00B Radio Channel Assignments（无线电信道的 分配）o01A Choosing a Bicycle Wheel（选择自行车车轮）o01B Escaping a Hurricanes Wrath（逃避飓风）美国大学生数学建模竞赛题美国大学生数学建模竞赛题2002-2005o02A Wind and Water Spray（风和喷水池）o02B Airline Order Booking（航空公司超员订票）o03A The Stunt Person（特技演员）o03B Gamma Knife Treatment Planning（刀治疗方 案）o04A Are Fingerprints Unique?（指纹是独一无二的吗）o04B A Faster Quick Pass System（更快捷的快通系统）o05A Flood Planning（水灾计划）o05B Tollbooths（收费站）美国大学生数学建模竞赛题美国大学生数学建模竞赛题2006-2008o06A Positioning and Moving Sprinkler Systems for Irrigation（灌溉喷赛系统的布置与移动）o06B Wheel Chair Access at Airports（在机场使用 轮椅的问题）o07A Gerrymandering（不公正的选区划分）o07B The Airplane Seating Problem（飞机就坐问题）o08A Take a Bath（可能的严重后果）o08B Creating Sudoku Puzzles（创建数独智力游戏）美国大学生数学建模竞赛题美国大学生数学建模竞赛题2009-2011o09A Designing a Traffic Circle（交通环岛）o09B Energy and the Cell Phone（能源与手机）o10A The Sweet Spot（最佳击球点）o10B Criminology（犯罪学）o11A Snowboard Course(单板滑雪场地)o11B Repeater Coordination(中继站的协调)美国大学生数学建模竞赛题美国大学生数学建模竞赛题2012oB题：沿着“大长河”露营 游客在游客在“大长河大长河”(225英里英里)可以享受到秀丽的风光和令人兴奋的白色湍流。这可以享受到秀丽的风光和令人兴奋的白色湍流。这条河对于背包客来说是进不去的，条河对于背包客来说是进不去的，因此畅游这条长河的唯一办法就是在这条河因此畅游这条长河的唯一办法就是在这条河上露营上几天。这次旅行从开始的下水点到最终结束点，共上露营上几天。这次旅行从开始的下水点到最终结束点，共225英里，且是顺英里，且是顺流而下的。乘客可以选择平均流而下的。乘客可以选择平均4英里英里/小时的以浆作为动力的橡胶筏或者平均小时的以浆作为动力的橡胶筏或者平均8英英里里/小时的机动帆船旅行。整个旅行从开始到结束会经历小时的机动帆船旅行。整个旅行从开始到结束会经历6至至18个夜晚。负责管个夜晚。负责管理这条河的政府机构希望到这里的每一次旅行都能够享受到野外经历，理这条河的政府机构希望到这里的每一次旅行都能够享受到野外经历，以最少以最少的接触到在河上其它的船只的接触到在河上其它的船只。目前，。目前，每年在六个月期间每年在六个月期间(一年的其余部分的天气一年的其余部分的天气对于河流旅行来说太冷对于河流旅行来说太冷)，共有，共有X次旅行，有次旅行，有Y处露营地，露营地均匀的分布整个处露营地，露营地均匀的分布整个河道。由于漂流的受欢迎程度的上升，公园管理者已经被要求允许更多的旅行次河道。由于漂流的受欢迎程度的上升，公园管理者已经被要求允许更多的旅行次数。所以他们想数。所以他们想确定怎样可能安排一个最优的混合的旅行方案，不同的时间确定怎样可能安排一个最优的混合的旅行方案，不同的时间(单单位为夜位为夜)和推动方式和推动方式(马达或浆马达或浆)，最大限度的利用露营地最大限度的利用露营地。换句话说，在长河的换句话说，在长河的漂流季，将会有多少更多的乘船旅行可以加进来漂流季，将会有多少更多的乘船旅行可以加进来?河流的管理者现在雇佣你，为河流的管理者现在雇佣你，为他们提出他们提出最佳排程方式和河流承载能力的建议最佳排程方式和河流承载能力的建议，记住两个露营者不能在同一时间，记住两个露营者不能在同一时间内占据同一个露营地。除了你的一页摘要，准备一页备忘录，对河流的管理者描内占据同一个露营地。除了你的一页摘要，准备一页备忘录，对河流的管理者描述你的主要发现。述你的主要发现。16二、二、美国大学生数学建模竞赛美国大学生数学建模竞赛赛前准备赛前准备o美国大学生数学建模美国大学生数学建模竞赛的的组队分工分工o美国大学生数学建模美国大学生数学建模竞赛之之如何如何备战o美国大学生数学建模美国大学生数学建模竞赛之之十大算法十大算法17MCM/ICM组队分工与团队配合组队分工与团队配合o在参加美在参加美赛前每一名前每一名队友必友必须要考要考虑自己在自己在团队中扮演什么中扮演什么样的角色，承担什么的角色，承担什么责任。假如任。假如你是你是队长，需要找到两名，需要找到两名队友共同完成本次比友共同完成本次比赛任任务，必，必须把每个人的分工把每个人的分工进行明确。行明确。o很多参很多参赛队组队的的时候，基本上是一个院系或候，基本上是一个院系或者一个班甚至一个宿舍，者一个班甚至一个宿舍，这样的的组队分工分工违背背了数学建模了数学建模竞赛的精神，不是科学和合理的。的精神，不是科学和合理的。o一种一种较好的好的组合是合是理工理工结合、文理搭配。合、文理搭配。18组队分工组队分工-建模人建模人o其工作主要是建立模型其工作主要是建立模型o数学知数学知识的的应用能力。它涉及的数学知用能力。它涉及的数学知识面十分面十分地地宽广，涉及：广，涉及：1)、概率与数理、概率与数理统计，2)、运、运筹与筹与线性性规划，划，3)、微分方程、微分方程还有与有与计算机知算机知识相交叉的知相交叉的知识：计算机模算机模拟等等等等。上述的内容有。上述的内容有些同学完全没有学些同学完全没有学过，也有些同学只学，也有些同学只学过一点概一点概率与数理率与数理统计，微分方程的知，微分方程的知识怎么怎么办呢？我呢？我们采用集中培采用集中培训和学生自学和学生自学练习相相结合。合。19组队分工组队分工-程序员程序员o美国美国赛注重注重实际，往往都要求，往往都要求对实例例给出解决方出解决方案，并且案，并且编程量大，程量大，计算量大。要求算量大。要求队员能快速能快速编写程序，并能写程序，并能优化程序的效率。化程序的效率。o除了除了数数值计算算的基本功，最好有的基本功，最好有算法算法设计与分析与分析的基的基础。o掌握常用的科学掌握常用的科学计算算软件，如件，如Matlab、Lingo、Mathematica等，利用等，利用现有函数或工具箱有函数或工具箱。20组队分工组队分工-论文组织与撰写者论文组织与撰写者o参参赛队最最终以以论文的形式提交工作成果，不在文的形式提交工作成果，不在论文中表述，就不会文中表述，就不会对比比赛结果果产生任何作用。生任何作用。o论文必文必须要要书写清晰、写清晰、简练、准确，不要把事情、准确，不要把事情复复杂化。化。o避免避免语法法错误，注意科技英，注意科技英语的表达方式。的表达方式。o论文写作涉及到每一个文写作涉及到每一个队员，但必，但必须要有人起要有人起带头作用。作用。21备战备战-学会分析问题学会分析问题o很多学生拿到很多学生拿到问题后根本不知道如何去做，面后根本不知道如何去做，面对没有数据的没有数据的题目、或者数据一大堆的目、或者数据一大堆的题目，目，无从下手。无从下手。o为什么会什么会这样？n中国的基中国的基础教育是教育是灌灌输式式的。的。n建模教材通常将各种建模教材通常将各种问题分分门别类整理成体系，往整理成体系，往往先往先讲相关理相关理论，再，再结合案例，合案例，课题教学教学过程仍是程仍是灌灌输式式的。的。n很多学校在培很多学校在培训时，老，老师拿模型就拿模型就讲题，或拿，或拿题目目就就讲模型。作模型。作业通常是一些通常是一些简单的或者是的或者是别人已人已经出出过或者做或者做过的的题目，而且网上都有答案。目，而且网上都有答案。割裂了从分析问题割裂了从分析问题到建立模型这一最到建立模型这一最重要的环节重要的环节22备战备战-学会模型归纳学会模型归纳o数学建模要求碰到数学建模要求碰到实际问题选择模型模型优化模型化模型得出得出结论。o模型模型归纳：美：美赛的的题目一般按目一般按题型可分型可分为连续性性问题和和离散型离散型问题；按解；按解题思路可以分思路可以分为开放型开放型问题和和编程程类问题！o在平在平时训练期期间，首先要做的工作是，首先要做的工作是对模型模型进行行归纳整理！整理！23备战备战-学会模型归纳学会模型归纳o首先首先罗列出所有常列出所有常规的模型及算法的模型及算法o如蒙特卡如蒙特卡罗算法、算法、图论算法、算法、层次分析法、数次分析法、数据据拟合、参数估合、参数估计、最、最优化算法、数据化算法、数据结构算构算法等法等o这些模型些模型不要求全部掌握不要求全部掌握，但是，但是必必须知道知道这些些模型算法的基本概念、模型算法的基本概念、应用范用范围、源代、源代码等，等，特特别是是应用范用范围必必须归纳。o最好能将最好能将历年的年的赛题按模型按模型进行分行分类。一道。一道题目也可以用多种模型来解决。目也可以用多种模型来解决。24备战备战-学会系统学习，逐步深入学会系统学习，逐步深入o培培训的的实践那么短，那么多模型践那么短，那么多模型该怎么怎么样掌握呢掌握呢？o所以在所以在备战期期间，要做的工作，就是把常，要做的工作，就是把常规模型模型的算法及源程序深刻掌握，打好基本功。的算法及源程序深刻掌握，打好基本功。o先先选择一些一些简单的算法和常的算法和常规的模型，的模型，进行学行学习。o抓住模型的灵魂！模型是死的，模型的抓住模型的灵魂！模型是死的，模型的优化是活化是活的。的。很多情况下，特等很多情况下，特等奖的模型和你的模型是一的模型和你的模型是一样的，但是的，但是获奖等等级不一不一样就是就是这个道理！个道理！25备战备战-现学现卖现学现卖o最初，先有最初，先有实际问题，后有数学模型，后有数学模型o今天，先学模型，后套今天，先学模型，后套问题o碰到不知道的从来没有做碰到不知道的从来没有做过的的问题，就要，就要现学学现卖o有有较强的学的学习能力，能快速掌握知能力，能快速掌握知识o阅读相关的科技相关的科技论文，关心作者是怎么建立模文，关心作者是怎么建立模型的型的o针对比比赛题目中的具体目中的具体问题，对模型模型进行行调整整和和优化化26数学建模十大算法数学建模十大算法o1、蒙特卡、蒙特卡罗算法（通算法（通过计算机仿真来解决算机仿真来解决问题的算法，同的算法，同时可以通可以通过模模拟来来检验自己模型自己模型的正确性，是比的正确性，是比赛时经常用的方法）。常用的方法）。o2、数据、数据拟合、参数估合、参数估计、插、插值等数据等数据处理算理算法（比法（比赛中通常会遇到大量的数据需要中通常会遇到大量的数据需要处理，理，通常使用通常使用Matlab作作为工具）工具）o3、线性性规划、整数划、整数规划、二次划、二次规划等划等规划划类问题（建模的大多数（建模的大多数问题属于最属于最优化化问题，通，通常用常用Lingo软件件实现）27数学建模十大算法数学建模十大算法o4、图论算法（如最短路、网算法（如最短路、网络流、二分流、二分图等算法）等算法）o5、动态规划、回溯搜索、分治算法、分枝定界等划、回溯搜索、分治算法、分枝定界等计算机算法（算机算法（这些算法是算法些算法是算法设计中比中比较常用的方常用的方法，很多法，很多场合可以用到合可以用到竞赛中）中）o6、优化理化理论的三大非的三大非经典算法：模典算法：模拟退火法、神退火法、神经网网络、遗传算法（算法（这些些问题是用来解决一些是用来解决一些较困困难的的优化化问题的算法，的算法，对于有些于有些问题非常有帮助，非常有帮助，但是算法的但是算法的实现比比较困困难，需慎重使用），需慎重使用）n并不是使用越复并不是使用越复杂的模型越好！的模型越好！28数学建模十大算法数学建模十大算法o7、数、数值分析算法（数分析算法（数值分析中常用的算法分析中常用的算法比如方程比如方程组求解、矩求解、矩阵运算、函数运算、函数积分等）分等）o8、一些、一些连续离散化方法（很多离散化方法（很多实际问题要要用用计算机求解，必算机求解，必须将其离散化后才能将其离散化后才能计算）算）o9、网格算法和、网格算法和穷举法（网格算法和法（网格算法和穷举法法都是搜索最都是搜索最优点的算法，在很多点的算法，在很多竞赛题中有中有应用，用，当重点当重点讨论模型本身而模型本身而轻视算法的算法的时候，可以使用候，可以使用这种方案种方案）o10、图像像处理算法理算法29三、三、为什么要参加美国大学生数学建为什么要参加美国大学生数学建模？模？“一次参一次参赛，终身受益！身受益！”30为什么要参加美国数学建模？为什么要参加美国数学建模？o建模建模竞赛带给了我了我们什么？什么？o 自身能力的提高自身能力的提高 计算机水平（算机水平（编程、程、查找文献等）找文献等）团队合作精神合作精神 与人交流的能力与人交流的能力 知知识面的面的扩展展31为什么要参加美国数学建模？为什么要参加美国数学建模？o建模建模竞赛带给了我了我们什么？什么？o 美好前途的保美好前途的保证 考研考研 出国出国 好的工作好的工作32 最后，祝大家最后，祝大家在数学建模活在数学建模活动中中不断提高素不断提高素质和能力！和能力！Thank you for your attendance!