《数学建模讲座2007B题课件》由会员分享，可在线阅读，更多相关《数学建模讲座2007B题课件（45页珍藏版）》请在金锄头文库上搜索。
1、数学建模竞赛案例选讲,重庆邮电大学 主讲：鲜思东 ,CUMCM-2007B 赛题分析,应用数学与数学建模 - 建模及建模竞赛的意义 竞赛评阅标准 - 一般原则及主要问题 优化模型的创新 - 2007B题分析,数学知识 数学技巧, 随机数学 代数与几何 微积分,数学：几个层次的理解,应用数学与数学建模 - 建模及建模竞赛的意义,数学建模：实际与数学之间的桥梁,实际问题,数学,Mathematical Modeling,现实对象的信息,数学模型,现实对象的解答,数学模型的解答,(归纳),(演绎),数学建模的全过程,美国MCM+ICM竞赛规模,我国CUMCM竞赛规模,学生欢迎：“一次参赛，终身受益”
2、 研究生导师们的认同 企业界的认同赞助 教育改革同行的认同：“成功范例” 国际同行的认同,竞赛的反响,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, simula
3、tion 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, ,竞赛的反响（一例）,CUMCM评阅标准,清晰性：摘要应理解为详细摘要，提纲挈领 表达严谨、简捷，思路清新 格式符合规范，严禁暴露身份,创造性：特别欣赏独树一帜、标新立异，但要合理,假设
4、的合理性，建模的创造性， 结果的正确性，表述的清晰性。,正确性：不强调与“参考答案”的一致性和结果的精度； 好方法的结果一般比较好；但不一定是最好的,合理性：关键假设；不欣赏罗列大量无关紧要的假设,竞赛评阅标准 - 一般原则及主要问题,CUMCM评阅标准: 一些常见问题,有的论文过于简单，该交代的内容省略了，难以看懂,有的队罗列一系列假设或模型，又不作比较、评价， 希望碰上“参考答案”或“评阅思路”，弄巧成拙,数学模型最好明确、合理、简洁： 有些论文不给出明确的模型，只是根据赛题的情况， 实际上是用“凑”的方法给出结果，虽然结果大致是对 的，没有一般性，不是数学建模的正确思路。,有的论文参考文
5、献不全，或引用他人结果不作交代,从论文评阅看学生参加竞赛中的问题,吃透题意方面不足，没有抓住和解决主要问题； 就事论事，形成数学模型的意识和能力欠缺； 对所用方法一知半解，不管具体条件，套用现成的方法，导致错误； 对结果的分析不够，怎样符合实际考虑不周； 写作方面的问题(摘要、简明、优缺点、参考文献); 队员之间合作精神差，孤军奋战； 依赖心理重，甚至违纪（指导教师、 网络）。,参加竞赛前的准备,了解竞赛章程等相关信息； 掌握数学建模的基本方法（学过“数学模型”或“数学实验”课最好，自学一些基本内容也可以）； 掌握基本的数学软件（Matlab/Mathematica；LINGO；如能掌握SAS
6、统计软件更好）； 训练规范的科技论文写作/表达能力 (摘要、正文、优缺点、参考文献及引用等); 试做几道以前的赛题； 培养合作精神。,优化问题三要素：决策变量；目标函数；约束条件,优化问题的一般形式,有人统计： 优化问题占CUMCM赛题的一半以上（1/32/3）,创新能力培养 - 2007B分析,建模时需要注意的几个基本问题,1、尽量使用实数优化，减少整数约束和整数变量 2、尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等 3、尽量使用线性模型，减少非线性约束和非线性变量的个数 （如x/y 5 改为x5y） 4、合理设定变量上
7、下界，尽可能给出变量初始值 5、模型中使用的参数数量级要适当 (如小于103),优化建模如何创新？,方法1：大胆创新，别出心裁 - 采用有特色的目标函数、约束条件等 - 你用非线性规划，我用线性规划 - 你用整数/离散规划，我用连续规划/网络优化 - 方法2：细致入微，滴水不漏 - 对目标函数、约束条件处理特别细致 - 有算法设计和分析，不仅仅是简单套用软件 - 敏感性分析详细 / 全面 - ,2007B命题背景,奥运相关的题目：(时代特性, 社会关注） 让运动员及时到达场馆（车辆调度，路径安排等） 应急管理（紧急疏散，应急调度等） 赛程安排（单一项目，多个项目） 成绩排名（如循环赛，体操或跳
8、水等） 技术类，如“刘翔的运动鞋” 乘公交，看奥运：原名“自动问路机” 方沛辰（吉大），吴孟达（国防科大）提出 原拟作乙组题，似乎难度太大,命题背景,定位：公交路线选择（查询）模型与算法 如何给数据？ 抽象数据实际数据？（减小规模，不给地理信息） 貌似简单，实则不然 数据处理（转换）方面有一定难度 换乘次数多时简单搜索不易（计算复杂度高） 换乘时间步行时间等需要考虑周全 标准的最短路算法（如Dijkstra算法）并不适用,乘公交，看奥运,公交线路选择问题的自主查询计算机系统：核心是线路选择的模型与算法 应该从实际情况出发考虑，满足查询者的各种不同需求 1: 仅考虑公汽线路，给出任意两公汽站点之
9、间线路选择问题的一般数学模型与算法 2: 同时考虑公汽与地铁线路，解决以上问题 3: 假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型,【附录1】基本参数设定 相邻公汽站平均行驶时间(包括停站时间)： 3分钟 相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟 公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟) 地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟) 地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟) 公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟) 公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；21
10、40站：2元；40站以上：3元 地铁票价：3元（无论地铁线路间是否换乘） 推论：换乘公汽等待分钟，换乘地铁等待分钟 【附录2】公交线路及相关信息 （见数据文件）,线路数据中的问题,线路数据中的异常或不明确之处，同学可根据自己的理解作出假设和处理，一般不会影响实例的计算结果 个别线路相邻站点名相同，可去掉其中一点或不作处理等 L406未标明是环线，是否将其当作环线处理均可 L290标明是环线，但首尾站点分别为1477与1479，可将所有线路中1477与1479统一为1477后计算。同学也可以按照各自认为合理的方式处理，包括不当作环线，或将1479改为1477，或在1479后增加1477，等等 如
11、果在假设中有明确约定，则环线单向或双向发车均应认可（按单向发车作假设，计算结果可能差些）,对通过地铁换乘的理解,“假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)” 步行：公汽站地铁站（通道）公汽站 换乘耗时11min：步行4+4=8min; 等车3min 第问（只考虑公汽）：可不考虑以上换乘 有同学也考虑了如上换乘，只是不坐地铁，应该也可以 此样处理时，第问和第问的难度相近,模型的目标,多目标优化问题（至少考虑三方面） 换乘次数最少(N)、费用最省(M)、时间最短(T) 从该问题的实际背景来看，加权太合适 不少同学用层次分析法确定权 不少同学计算时间的价值（平均收入
12、工作时间） 不同目标组合的模型 三个目标按优先级排序，组合成六个模型 也可将某些目标作为约束,多数队仅采用搜索法（70-80%?）,直达； 一次换乘； 二次换乘；,s t,s t,s t,求出所有线路；评价其目标(容易计算)；选优,多数队仅采用搜索法,总体来看，技术含量较低（基本上是枚举） 几乎没有建模，完全只有算法实现，算法也没什么创新 一般只考虑不超过两次换乘 不少文章引用参考文献作为依据，实用中似乎够用 题目难度大大降低，模型不够一般 换乘作为了第一目标，或作为一个最重要的约束 任意次换乘时算法复杂度提高，难以处理 结果不佳（如：从省时考虑，有些需次换乘）,图论模型与最短路算法,用图论做
13、的队也不少，但往往考虑不周 弧上赋权方式交代不清 套用Dijkstra或Floyd-Warshall算法，却不清楚其原理及适用的问题 需要建立一个带权有向图，节点表示站点，有向弧表示前一站点能够直达后一站点，弧上的权表示前一站点直达后一站点所需付出的代价(时间或费用) 图（网络）如何描述和表示？ 基本要素：节点，有向弧（边），弧上赋权 邻接矩阵；关联矩阵（数学上处理方便，存储量较大） 链表（存储量较小，计算机上处理方便）,关联矩阵(Incidence Matrix)表示法,在线路选择问题中，当从i可直达j时，定义弧(i,j)；其上的权可为或成本(时间或费用)；多重弧可只保留一条（弧上的权可取最
14、小的成本，如时间或费用）,G=(V，A)是一个简单有向图；|V|=n，|A|=m,重要数学性质：关联矩阵是全幺模矩阵,图G=(V，A)的邻接矩阵C是如下定义的：C是一个 的矩阵，即,邻接矩阵(Adjacency Matrix)表示法,图G=(V，A)的邻接矩阵C是如下定义的：C是一个 的0-1矩阵，即,在线路选择问题中，当从i可直达j时，定义弧(i,j)；其上的权可为或成本(时间或费用),G=(V，A)是一个简单有向图；|V|=n，|A|=m,有向图的“传递闭包算法”(可用于一般二元关系) 权取0-1时，C(0)=C可称为直达矩阵 ；C(1)=C*C 为次可达矩阵；C(2)=C(1)*C 为2
15、次可达矩阵；,链表（邻接表）表示法,单向链表(指针数组),A(1)=2,3,A(2)=4,A(3)=2,A(4)=3,5,A(5)=3,4,Dijkstra算法（标号算法，1959）,STEP1. 如果S=V, 则uj为节点s到节点j的最短路路长(最短路可以通过数组pred所记录的信息反向追踪获得), 结束.否则继续.,STEP0. (初始化) 令S= ，=V， ；对V 中的顶点j(j s)令初始距离标号 .,STEP2. 从 中找到距离标号最小的节点i，把它从 删除，加入S. 对于所有从i出发的弧 , 若 ，则令 转STEP1.,特点：1. 算法求出从源点s到所有点的最短路长 2. 每点给一
16、对标号 (uj, predj)，uj是从s到j的最短路长；predj是从s到j的最短路中j点的前一点,Example,Dijkstra算法（标号设定算法）,适用于正费用网络：“分层”设定标号 永久标号：S中的点，uj是最短路长 临时标号；其他点， uj是只通过S中的点的最短路长,对于稠密网络，这是求解最短路问题可能达到的最小的复杂度,因为任何算法都至少必须对每条弧考虑一次. 对于稀疏网络，利用各种形式的堆（Heap），其复杂度可降为 或 等,特点：求所有点对间最短路 基本思想：逐步逼近，迭代求解最短路方程: O(n3),Floyd-Warshall算法 （标号修正算法，1962),临时标号 是不通过k，k+1，,n 节点(i,j 除外)时从节点i到节点j的最短路路长.,Floyd-Warshall算法的具体实现: O(n3),
