搜索
简要提纲•应用数学与数学建模-----建模及建模竞赛的意义•竞赛评阅标准-----一般原则及主要问题•优化模型的创新-----2007B题分析数学知识数学技巧数学应用数学发现……应用数学数学技术数学实验……随机数学代数与几何微积分……数学美学数学哲学数学精神数学素质数学文化数学：几个层次的理解数学建模：实际与数学之间的桥梁实际问题数学MathematicalModeling现实对象的信息数学模型现实对象的解答数学模型的解答表述求解解释验证(归纳)(演绎)数学建模的全过程美国MCM+ICM竞赛规模美国大学生数学建模竞赛参赛队数01002003004005006007008009001000198919901991199219931994199519961997199819992000200120022003200420052006年份参赛队数总数中国我国CUMCM竞赛规模中国大学生数学建模竞赛02004006008001000199219931994199519961997199819992000200120022003200420052006年份校数020004000600080001000012000队数校数队数•学生欢迎：“一次参赛，终身受益”•研究生导师们的认同•企业界的认同／赞助•教育改革同行的认同：“成功范例”•国际同行的认同竞赛的反响IBM中国研究中心-招聘条件Positiontitle:BusinessOptimization(BJ)1．Backgroundinindustrialengineering,operationsresearch,mathematics,ArtificialIntelligence,managementscienceetc.2.Knowledgeinnetworkdesign,jobscheduling,dataanalysis,simulationandoptimization3.Awardinmathematicalcontestinmodelingisaplus4.Experienceinindustryisaplus5.Experienceineclipseorprogrammingmodel/architecturedesignisaplus--Feb.18,2006,竞赛的反响（一例）简要提纲•应用数学与数学建模-----建模及建模竞赛的意义•竞赛评阅标准-----一般原则及主要问题•创新能力培养-----几个例子（结合优化模型）CUMCM评阅标准清晰性：摘要应理解为详细摘要，提纲挈领表达严谨、简捷，思路清新格式符合规范，严禁暴露身份创造性：特别欣赏独树一帜、标新立异，但要合理假设的合理性，建模的创造性，结果的正确性，表述的清晰性。正确性：不强调与“参考答案”的一致性和结果的精度；好方法的结果一般比较好；但不一定是最好的合理性：关键假设；不欣赏罗列大量无关紧要的假设CUMCM评阅标准:一些常见问题有的论文过于简单，该交代的内容省略了，难以看懂有的队罗列一系列假设或模型，又不作比较、评价，希望碰上“参考答案”或“评阅思路”，弄巧成拙数学模型最好明确、合理、简洁：有些论文不给出明确的模型，只是根据赛题的情况，实际上是用“凑”的方法给出结果，虽然结果大致是对的，没有一般性，不是数学建模的正确思路。有的论文参考文献不全，或引用他人结果不作交代从论文评阅看学生参加竞赛中的问题•吃透题意方面不足，没有抓住和解决主要问题；•就事论事，形成数学模型的意识和能力欠缺；•对所用方法一知半解，不管具体条件，套用现成的方法，导致错误；•对结果的分析不够，怎样符合实际考虑不周；•写作方面的问题(摘要、简明、优缺点、参考文献);•队员之间合作精神差，孤军奋战；•依赖心理重，甚至违纪（指导教师、网络）。简要提纲•应用数学与数学建模-----建模及建模竞赛的意义•竞赛评阅标准-----一般原则及主要问题•创新能力培养-----2007B分析2020/11/1414•优化问题三要素：决策变量；目标函数；约束条件约束条件决策变量优化问题的一般形式njiDxljxgmixhtsxf,...,1,0)(,...,1,0)(..)(min目标函数•有人统计：优化问题占CUMCM赛题的一半以上（1/3~2/3）建模时需要注意的几个基本问题1、尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量的个数（如x/y5改为x5y）4、合理设定变量上下界，尽可能给出变量初始值5、模型中使用的参数数量级要适当(如小于103)优化建模如何创新？•方法1：大胆创新，别出心裁----采用有特色的目标函数、约束条件等----你用非线性规划，我用线性规划----你用整数/离散规划，我用连续规划/网络优化----……•方法2：细致入微，滴水不漏----对目标函数、约束条件处理特别细致----有算法设计和分析，不仅仅是简单套用软件----敏感性分析详细/全面----……2007B命题背景奥运相关的题目：(时代特性,社会关注）让运动员及时到达场馆（车辆调度，路径安排等）应急管理（紧急疏散，应急调度等）赛程安排（单一项目，多个项目）成绩排名（如循环赛，体操或跳水等）技术类，如“刘翔的运动鞋”乘公交，看奥运：原名“自动问路机”方沛辰（吉大），吴孟达（国防科大）提出原拟作乙组题，似乎难度太大命题背景定位：公交路线选择（查询）模型与算法如何给数据？抽象数据／实际数据？（减小规模，不给地理信息）貌似简单，实则不然数据处理（转换）方面有一定难度换乘次数多时简单搜索不易（计算复杂度高）换乘时间／步行时间等需要考虑周全标准的最短路算法（如Dijkstra算法）并不适用B题：乘公交，看奥运第29届奥运会08年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。应该从实际情况出发考虑，满足查询者的各种不同需求。07-B题解题分析为了设计这样一个系统，其核心是线路选择的模型与算法。07-B题解题分析请解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间,请你给出任意两站点之间线路选择问题的数学模型。07-B题解题分析【附录1】基本参数设定相邻公汽站平均行驶时间(包括停站时间)：3分钟相邻地铁站平均行驶时间(包括停站时间)：2.5分钟公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）【附录2】公交线路及相关信息（见数据文件B2007data.rar）线路数据中的问题线路数据中的异常或不明确之处，同学可根据自己的理解作出假设和处理，一般不会影响实例的计算结果个别线路相邻站点名相同，可去掉其中一点或不作处理等L406未标明是环线，是否将其当作环线处理均可L290标明是环线，但首尾站点分别为1477与1479，可将所有线路中1477与1479统一为1477后计算。同学也可以按照各自认为合理的方式处理，包括不当作环线，或将1479改为1477，或在1479后增加1477，等等如果在假设中有明确约定，则环线单向或双向发车均应认可（按单向发车作假设，计算结果可能差些）对通过地铁换乘的理解“假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)”步行：公汽站地铁站（通道）公汽站换乘耗时11min：步行4+4=8min;等车3min第１问（只考虑公汽）：可不考虑以上换乘有同学也考虑了如上换乘，只是不坐地铁，应该也可以此样处理时，第１问和第２问的难度相近07-B题解题分析题目特点1、本题根据公交线路查询系统研制的实际需求简化改编而成；2、问题容易理解，相关参考文献较多；3、相关知识点：（1）图论（最短路径）；（2）多目标规划。4、题目开放度不够，可发挥余地不多。关于数据的预处理：1、对于原始数据中出现的一些异常数据，可根据自己的理解作出假设和处理。如：（1）对于个别线路相邻点名相同，可以采取去掉其中1点或不作处理等方式，一般不会影响实例计算中线路选择的结果。（2）对于L406未标明是环行线的问题，无论学生是否将其当作环线处理，一般不会影响到实例的计算结果。（3）对于L290标明是环线，但首尾站点分别为1477与1479的问题，可将所有线路中1477与1479统一为1477后计算。也可以按照各自认为合理的方式处理，包括不当作环线，实例计算用到的是该线路中部的几个站点，一般不会影响实例计算结果。07-B题解题分析2、关于环行线路，可以假设为单向或双向。3、线路数据格式需编程进行转换。模型的目标多目标优化问题（至少考虑三方面）换乘次数最少(N)、费用最省(M)、时间最短(T)从该问题的实际背景来看，加权不太合适不少同学用层次分析法确定权不少同学计算时间的价值（平均收入／工作时间）不同目标组合的模型三个目标按优先级排序，组合成六个模型也可将某些目标作为约束多数队仅采用搜索法（70-80%?）直达；一次换乘；二次换乘；…ststst求出所有线路；评价其目标(容易计算)；选优多数队仅采用搜索法总体来看，技术含量较低（基本上是枚举）几乎没有建模，完全只有算法实现，算法也没什么创新一般只考虑不超过两次换乘不少文章引用参考文献作为依据，实用中似乎够用题目难度大大降低，模型不够一般换乘作为了第一目标，或作为一个最重要的约束任意次换乘时算法复杂度提高，难以处理结果不佳（如：从省时考虑，有些需３－４次换乘）图论模型与最短路算法用图论做的队也不少，但往往考虑不周弧上赋权方式交代不清套用Dijkstra或Floyd-Warshall算法，却不清楚其原理及适用的问题需要建立一个带权有向图，节点表示站点，有向弧表示前一站点能够直达后一站点，弧上的权表示前一站点直达后一站点所需付出的代价(时间或费用)图（网络）如何描述和表示？基本要素：节点，有向弧（边），弧上赋权邻接矩阵；关联矩阵（数学上处理方便，存储量较大）链表（存储量较小，计算机上处理方便）关联矩阵(IncidenceMatrix)表示法在线路选择问题中，当从i可直达j时，定义弧(i,j)；其上的权可为１或成本(时间或费用)；多重弧可只保留一条（弧上的权可取最小的成本，如时间或费用）G=(V，A)是一个简单有向图；|V|=n，|A|=m重要数学性质：关联矩阵是全幺模矩阵图G=(V，A)的邻接矩阵C是如下定义的：C是一个的矩阵，即mn,}1,0,1{)(mnmnikbB其他。，,0),(,,1,),(,,1AijkVjAjikVjbik邻接矩阵(Adjacen