数学建模讲座08Sep河北大学.ppt

数学建模讲座（2008年9月 河北大学） 数学建模竞赛评阅标准 - 模型创新与论文写作,谢金星 100084北京清华大学数学科学系 Tel:Fax:Email: /jxie,简要提纲,应用数学与数学建模 - 建模及建模竞赛的意义 竞赛评阅标准 - 一般原则及主要问题 创新能力培养 -几个例子,数学的重要性：众所周知？,E. E. David Jr.: (Notices of AMS, v31, n2, 1984, P142) 现今被如此称颂的“高技术”本质上是数学技术。,马克思： 一门科学只有成功地运用数学时,才算达到了完善的地步。,资深评估小组对美国数学科学的国际评估报告: (NSF Report, March 1998) 现如今的数学科学对科学的所有的三个方面： 观察、理论和模拟来说都是必不可少的。 数盲和文盲一样是极其有害的。,既要学好“算数学”, 更要培养“用数学”的能力,利用计算机和数学软件, 培养分析、思考能力,感受“用数学”的酸甜苦辣, 激发学好数学的愿望,数学的重要性：似是而非？,不少同学（甚至社会）的反映： - 无用 - 难学,原因：很少用；用不好,最常用的大学数学内容有哪些?,纯粹数学(Pure Math) 基础/核心(Core)数学？ 应用数学(Applied Math) 计算数学(Computational Math) 概率论与数理统计 随机/统计数学？ 运筹学(OR)与控制论 运筹数学？,数学的二级学科(研究生专业),应用数学,Core,具体应用学科,具体应用学科,应用数学,应用数学,数学建模：数学与实际问题的桥梁,数学建模: 应用数学知识解决实际问题的第一步 数学建模: 通常有本质性的困难和原始性的创新(关键一步) Pure Math vs Applied Math: Logic vs Problem Driving “源”（Motivation）远“流”（Impact）长,实际问题,数学,Mathematical Modeling,数学模型 (Mathematical Model) 和 数学建模（Mathematical Modeling),数学模型: 对于一个现实对象，为了一个特定目的, 作出必要的简化假设，根据对象的内在规律， 运用适当的数学工具，得到的一个数学结构。,现实对象的信息,数学模型,现实对象的解答,数学模型的解答,(归纳),(演绎),数学建模的全过程,数学知识 数学技巧, 随机数学 代数与几何 微积分,数学：几个层次的理解,（美国大学生）数学建模竞赛(MCM),1985年开始举办，每年一次(2月)；“国际竞赛”,我国(清华等校) 1989年开始每年参加，英文答卷,MCM-2006有10个国家(地区)748队参赛，其中我国占62%; ICM-2006有224队参赛，其中我国占87%,每年赛题和优秀答卷刊登于同年 UMAP杂志,1999年起又同时推出交叉学科竞赛（Interdisciplinary Contest in Modeling ICM),网址：,美国MCM+ICM竞赛规模,中国大学生数学建模竞赛（CUMCM）,1992年中国工业与应用数学学会(CSIAM)开始组织,1994年起教育部高教司和CSIAM共同举办(每年9月),2007年有30省/市/区的969所学校11742队参加,赛题和优秀答卷刊登于次年“数学的实践与认识”（2001年起刊登于当年“工程数学学报”）,网址：,奖励：证书 （“一次参赛，终身受益”）,等级：全国一等2%、二等 7%；赛区奖1/3,我国CUMCM竞赛规模,学生欢迎：“一次参赛，终身受益” 研究生导师们的认同 企业界的认同赞助 教育改革同行的认同：“成功范例” 国际同行的认同,竞赛的反响,IBM 中国研究中心- 招聘条件 Position title: Business Optimization(BJ) 1Background in industrial engineering, operations research, mathematics, Artificial Intelligence, management science etc. 2. Knowledge in network design, job scheduling, data analysis, simulation and optimization 3. Award in mathematical contest in modeling is a plus 4. Experience in industry is a plus 5. Experience in eclipse or programming model / architecture design is a plus -Feb. 18, 2006, /cn/ibm/crl/careers/condition.shtml,竞赛的反响（一例）,竞赛内容与形式,内容,赛题：工程、管理中经过简化的实际问题,答卷：一篇包含问题分析、模型假设、建立、求解(通常用计算机)、结果分析和检验等的论文,形式,3名大学生组队，在3天内完成的通讯比赛,可使用任何“死”材料(图书/互联网/软件等), 但不得与队外任何人讨论（包括上网讨论）,宗旨,创新意识 团队精神 重在参与 公平竞争,标准,假设的合理性，建模的创造性，结果的正确性，表述的清晰性。,选修或自学数学模型课, 或参加赛前培训 2. 了解和掌握常用数学软件的基本用法 （Matlab / Mathematica, Lingo, ） 3. 了解竞赛基本信息 （竞赛章程，特别是纪律；论文写作规范；) 4. 参加各种类型的数学建模竞赛或模拟赛 （校内赛，地区赛，全国赛，美国赛,),建议：参赛前的准备,简要提纲,应用数学与数学建模 - 建模及建模竞赛的意义 竞赛评阅标准 - 一般原则及主要问题 创新能力培养 -几个例子（结合优化模型）,A Joke,http:/haha.nu/funny/funny-math/,Another Joke,http:/haha.nu/funny/funny-math/,CUMCM评阅标准,清晰性：摘要应理解为详细摘要，提纲挈领 表达严谨、简捷，思路清新 格式符合规范，严禁暴露身份,创造性：特别欣赏独树一帜、标新立异，但要合理,假设的合理性，建模的创造性， 结果的正确性，表述的清晰性。,正确性：不强调与“参考答案”的一致性和结果的精度； 好方法的结果一般比较好；但不一定是最好的,合理性：关键假设；不欣赏罗列大量无关紧要的假设,CUMCM评阅标准: 一些常见问题,有的论文过于简单，该交代的内容省略了，难以看懂,有的队罗列一系列假设或模型，又不作比较、评价， 希望碰上“参考答案”或“评阅思路”，弄巧成拙,数学模型最好明确、合理、简洁： 有些论文不给出明确的模型，只是根据赛题的情况， 实际上是用“凑”的方法给出结果，虽然结果大致是对 的，没有一般性，不是数学建模的正确思路。,有的论文参考文献不全，或引用他人结果不作交代,从论文评阅看学生参加竞赛中的问题,吃透题意方面不足，没有抓住和解决主要问题； 就事论事，形成数学模型的意识和能力欠缺； 对所用方法一知半解，不管具体条件，套用现成的方法，导致错误； 对结果的分析不够，怎样符合实际考虑不周； 写作方面的问题(摘要、简明、优缺点、参考文献); 队员之间合作精神差，孤军奋战； 依赖心理重，甚至违纪（指导教师、 网络）。,简要提纲,应用数学与数学建模 - 建模及建模竞赛的意义 竞赛评阅标准 - 一般原则及主要问题 创新能力培养 -几个例子,A Joke: “Find x”,“I cant believe the teacher marked him wrong, he found it.”,http:/haha.nu/funny/funny-math/,Another Joke: “Find x”,“Smart enough!”,http:/haha.nu/funny/funny-math/,0,y,x,VOR2 x=629, y=375,309.00 (1.30),864.3(2.0),飞机 x=?, y=?,VOR1 x=764, y=1393,161.20 (0.80),VOR3 x=1571, y=259,45.10 (0.60),北,DME x=155, y=987,图中坐标和测量距离 的单位是“公里”,案例: 飞机的精确定位问题,参考资料谢金星、薛毅编著， 优化建模与lindo/lingo软件，请华大学出版社, 2005,飞机的精确定位模型,飞机的精确定位模型,第1类模型: 不考虑误差因素,超定方程组-非线性最小二乘！,量纲不符！,or,？,？,飞机的精确定位模型,第2类模型: 考虑误差因素(作为硬约束),Min x; Min y; Max x; Max y.,非线性规划！,？,？ 仅部分考虑误差! 角度与距离的“地位”为何不同！,其他：,误差非均匀分布！,不等式组？,飞机的精确定位模型,误差一般服从什么分布？,正态分布！,不同的量纲如何处理？,无约束非线性最小二乘模型,归一化处理！,shili0702.m,飞机坐标(978.31，723.98), 误差平方和0.6685 ( 4),角度需要进行预处理，如利用 Matlab的atan2函数, 值域(-pi, pi),第3类模型: 考虑误差因素(作为软约束); 且归一化,飞机的精确定位模型,小技巧: LINGO中没有atan2函数, 怎么办？,可以直接利用tan函数！,exam0507c.lg4,同前面的模型/结果,飞机坐标(980.21，727.30 ), 误差平方和2.6 与前面的结果有所不同, 为什么? 哪个模型合理些?,最后: 思考以下模型:,exam0507d.lg4,例 CUMCM-2000B 钢管订购和运输,钢厂的产量和销价（1单位钢管=1km管道钢管）,钢厂产量的下限：500单位钢管,1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计）,601 = 300 + 301 44 20 + 23 ?,（1）制定钢管的订购和运输计划，使总费用最小.,（2）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？,（3）讨论管道为树形图的情形,问题1的基本模型和解法,总费用最小的优化问题,总费用：订购，运输（由各厂Si经铁路、公路至各点Aj, i=1,7; j=1, 15 ），铺设管道Aj Aj+1 （j=1, 14),由Si至Aj的最小购运费用路线及最小费用cij 由Si至Aj的最优运量xij 由Aj向Aj Aj-1段铺设的长度yj及向Aj Aj+1段铺设的长度zj,最优购运计划,约束条件,钢厂产量约束：上限和下限（如果生产的话） 运量约束：xij对i求和等于zj 加yj； zj与 yj+1之和等于Aj Aj+1段的长度lj,yj zj,Aj,基本模型,由Aj向Aj Aj-1段铺设的运量为 1+ +yj= yj( yj+1)/2由Aj向Aj Aj+1段铺设的运量为 1+ +zj= zj( zj+1)/2,二次规划？,求解步骤,1）求由Si至Aj的最小购运费用路线及最小费用cij,难点：公路运费是里程的线性函数，而铁路运费是里程的分段阶跃函数，故总运费不具可加性。因而计算最短路常用的Dijkstra算法、Floyd算法失效。,A1,需要对铁路网和公路网进行预处理，才能使用常用算法，得到最小购运费用路线。- 至少求3次最短路,如S7至A10的最小费用路线,先铁路1130km，再公路70km, 运费为77（万元）,先公路（经A15）40km, 再铁路1100km，再公路70km, 运费为76（万元）,实际上只有S4和S7需要分解成子问题求解,每个子问题是标准的二次规划，决策变量为xij,yj,zj, 不超过135个 。,fi表示钢厂i是否使用；xij是从钢厂i运到节点j的钢管量 yj是从节点j向左铺设的钢管量；zj是向右铺设的钢管量,c) 比较好的方法：引入0-1变量,LINDO/LINGO得到的结果比matlab得到的好,yj zj,j,问题1的其它模型和解法,1）运输问题的0-1规划模型,将全长5171km的管道按公里分段，共5171个需求点，钢厂为7个供应点，构成如下的运输问题,cij为从供应点i到需求点j的最小购运费,xij=1表示从点i到点j购运1单位钢管,求解时要针对规模问题寻求改进算法,2）最小费用网络流模型,线性费用网络(只有产量上限),非线性费用网络(只有产量上限),边的标记（流量上限，单位费用）,用标准算法(如最小费用路算法)求解,无单位费用概念(f(f+1)/2), 需修改最小费用路算法,2）最小费用网络流模型,产量有下限ri时的修正,注：该模型获当年的惟一最高奖（网易杯）,3) 最小面积模型,作图：Si到管道x单位钢管的最小购运费用c,由各条Si首尾相连(横坐标)组成的一条折线对应一个购运方案，折线下面的面积对应方案的费用,在产量约束下找面积最小的折线,问题2: 分析对购运计划和总费用影响(哪个钢厂销价变化影响最大；哪个钢厂产量上限变化影响最大),规划问题的灵敏度分析,问题3：管道为树形图,(jk)是连接Aj