数学建模讲座CUMCM-2007B赛题分析.ppt

数学建模讲座 CUMCM-2007B 赛题分析,谢金星 100084北京清华大学数学科学系 Tel: 010-62787812，Fax: 010-62785847 Email:jxiemath.tsinghua.edu.cn http:/faculty.math.tsinghua.edu.cn/jxie,简要提纲,应用数学与数学建模 - 建模及建模竞赛的意义 竞赛评阅标准 - 一般原则及主要问题 优化模型的创新 - 2007B题分析,数学知识 数学技巧, 随机数学 代数与几何 微积分,数学：几个层次的理解,数学建模：实际与数学之间的桥梁,实际问题,数学,Mathematical Modeling,现实对象的信息,数学模型,现实对象的解答,数学模型的解答,(归纳),(演绎),数学建模的全过程,美国MCM+ICM竞赛规模,我国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, http:/www-900.ibm.com/cn/ibm/crl/careers/condition.shtml,竞赛的反响（一例）,简要提纲,应用数学与数学建模 - 建模及建模竞赛的意义 竞赛评阅标准 - 一般原则及主要问题 创新能力培养 -几个例子（结合优化模型）,CUMCM评阅标准,清晰性：摘要应理解为详细摘要，提纲挈领 表达严谨、简捷，思路清新 格式符合规范，严禁暴露身份,创造性：特别欣赏独树一帜、标新立异，但要合理,假设的合理性，建模的创造性， 结果的正确性，表述的清晰性。,正确性：不强调与“参考答案”的一致性和结果的精度； 好方法的结果一般比较好；但不一定是最好的,合理性：关键假设；不欣赏罗列大量无关紧要的假设,CUMCM评阅标准: 一些常见问题,有的论文过于简单，该交代的内容省略了，难以看懂,有的队罗列一系列假设或模型，又不作比较、评价， 希望碰上“参考答案”或“评阅思路”，弄巧成拙,数学模型最好明确、合理、简洁： 有些论文不给出明确的模型，只是根据赛题的情况， 实际上是用“凑”的方法给出结果，虽然结果大致是对 的，没有一般性，不是数学建模的正确思路。,有的论文参考文献不全，或引用他人结果不作交代,从论文评阅看学生参加竞赛中的问题,吃透题意方面不足，没有抓住和解决主要问题； 就事论事，形成数学模型的意识和能力欠缺； 对所用方法一知半解，不管具体条件，套用现成的方法，导致错误； 对结果的分析不够，怎样符合实际考虑不周； 写作方面的问题(摘要、简明、优缺点、参考文献); 队员之间合作精神差，孤军奋战； 依赖心理重，甚至违纪（指导教师、 网络）。,参加竞赛前的准备,了解竞赛章程等相关信息； 掌握数学建模的基本方法（学过“数学模型”或“数学实验”课最好，自学一些基本内容也可以）； 掌握基本的数学软件（Matlab/Mathematica；LINGO；如能掌握SAS/JMP统计软件更好）； 训练规范的科技论文写作/表达能力 (摘要、正文、优缺点、参考文献及引用等); 试做几道以前的赛题； 培养合作精神。,简要提纲,应用数学与数学建模 - 建模及建模竞赛的意义 竞赛评阅标准 - 一般原则及主要问题 创新能力培养 - 2007B分析,优化问题三要素：决策变量；目标函数；约束条件,优化问题的一般形式,有人统计： 优化问题占CUMCM赛题的一半以上（1/32/3）,建模时需要注意的几个基本问题,1、尽量使用实数优化，减少整数约束和整数变量 2、尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等 3、尽量使用线性模型，减少非线性约束和非线性变量的个数 （如x/y 5 改为x5y） 4、合理设定变量上下界，尽可能给出变量初始值 5、模型中使用的参数数量级要适当 (如小于103),优化建模如何创新？,方法1：大胆创新，别出心裁 - 采用有特色的目标函数、约束条件等 - 你用非线性规划，我用线性规划 - 你用整数/离散规划，我用连续规划/网络优化 - 方法2：细致入微，滴水不漏 - 对目标函数、约束条件处理特别细致 - 有算法设计和分析，不仅仅是简单套用软件 - 敏感性分析详细 / 全面 - ,2007B命题背景,奥运相关的题目：(时代特性, 社会关注） 让运动员及时到达场馆（车辆调度，路径安排等） 应急管理（紧急疏散，应急调度等） 赛程安排（单一项目，多个项目） 成绩排名（如循环赛，体操或跳水等） 技术类，如“刘翔的运动鞋” 乘公交，看奥运：原名“自动问路机” 方沛辰（吉大），吴孟达（国防科大）提出 原拟作乙组题，似乎难度太大,命题背景,定位：公交路线选择（查询）模型与算法 如何给数据？ 抽象数据实际数据？（减小规模，不给地理信息） 貌似简单，实则不然 数据处理（转换）方面有一定难度 换乘次数多时简单搜索不易（计算复杂度高） 换乘时间步行时间等需要考虑周全 标准的最短路算法（如Dijkstra算法）并不适用,乘公交，看奥运,公交线路选择问题的自主查询计算机系统：核心是线路选择的模型与算法 应该从实际情况出发考虑，满足查询者的各种不同需求 1: 仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法 2: 同时考虑公汽与地铁线路，解决以上问题 3: 假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型,【附录1】基本参数设定 相邻公汽站平均行驶时间(包括停站时间)： 3分钟 相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟 公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟) 地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟) 地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟) 公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟) 公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元 地铁票价：3元（无论地铁线路间是否换乘） 推论：换乘公汽等待分钟，换乘地铁等待分钟 【附录2】公交线路及相关信息 （见数据文件）,线路数据中的问题,线路数据中的异常或不明确之处，同学可根据自己的理解作出假设和处理，一般不会影响实例的计算结果 个别线路相邻站点名相同，可去掉其中一点或不作处理等 L406未标明是环线，是否将其当作环线处理均可 L290标明是环线，但首尾站点分别为1477与1479，可将所有线路中1477与1479统一为1477后计算。同学也可以按照各自认为合理的方式处理，包括不当作环线，或将1479改为1477，或在1479后增加1477，等等 如果在假设中有明确约定，则环线单向或双向发车均应认可（按单向发车作假设，计算结果可能差些）,对通过地铁换乘的理解,“假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)” 步行：公汽站地铁站（通道）公汽站 换乘耗时11min：步行4+4=8min; 等车3min 第问（只考虑公汽）：可不考虑以上换乘 有同学也考虑了如上换乘，只是不坐地铁，应该也可以 此样处理时，第问和第问的难度相近,模型的目标,多目标优化问题（至少考虑三方面） 换乘次数最少(N)、费用最省(M)、时间最短(T) 从该问题的实际背景来看，加权太合适 不少同学用层次分析法确定权 不少同学计算时间的价值（平均收入工作时间） 不同目标组合的模型 三个目标按优先级排序，组合成六个模型 也可将某些目标作为约束,多数队仅采用搜索法（70-80%?）,直达； 一次换乘； 二次换乘； ,s t,s t,s t,求出所有线路；评价其目标(容易计算)；选优,多数队仅采用搜索法,总体来看，技术含量较低（基本上是枚举） 几乎没有建模，完全只有算法实现，算法也没什么创新 一般只考虑不超过两次换乘 不少文章引用参考文献作为依据，实用中似乎够用 题目难度大大降低，模型不够一般 换乘作为了第一目标，或作为一个最重要的约束 任意次换乘时算法复杂度提高，难以处理 结果不佳（如：从省时考虑，有些需次换乘）,图论模型与最短路算法,用图论做的队也不少，但往往考虑不周 弧上赋权方式交代不清 套用Dijkstra或Floyd-Warshall算法，却不清楚其原理及适用的问题 需要建立一个带权有向图，节点表示站点，有向弧表示前一站点能够直达后一站点，弧上的权表示前一站点直达后一站点所需付出的代价(时间或费用) 图（网络）如何描述和表示？ 基本要素：节点，有向弧（边），弧上赋权 邻接矩阵；关联矩阵（数学上处理方便，存储量较大） 链表（存储量较小，计算机上处理方便）,关联矩阵(Incidence Matrix)表示法,在线路选择问题中，当从i可直达j时，定义弧(i,j)；其上的权可为或成本(时间或费用)；多重弧可只保留一条（弧上的权可取最小的成本，如时间或费用）,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次可达矩阵；,链表（邻接表）表示法,单向链表(指针数组),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. 每点给一对标号 (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),由于要记录所有节点之间最短路的信息, 所以这里我们要用一个二维数组P； 可依据P, 采用“正向追踪”的方式得到最短路.,STEP2：如果k=n, 结束; 否则转STEP1.,STEP0: k=0. 对于所有节点i和j: 令 ， , ( ，若节点i和j之间没有弧, 认为 ) .,STEP1: k=k+1. 对于所有节点i和j: 若 , 令 , ; 否则令 , .,Floyd-Warshall算法的 矩阵迭代法实现：O(n4),令D为权矩阵(直达最短路长) Dm为正好经过m条弧从i到j的最短路长,问题1和2的一种具体建模方法(赋权),在线路选择问题中，当从i可直达j时（同为公汽或地铁站点），定义弧(i,j)；其上的权为,lij表示由i直达j付出的代价，可以为时间或费用 (不包括换乘代价；多条线路可达时只保留最小代价) 初始等车时间2(3)min也不包括在内，最后结果可加上 注意：D=D(0)不是对称矩阵(“直达矩阵”),dij(0)=dij,问题的一种具体建模方法,i站点是公汽站点，j站点为地铁站点：,（1）若j站点对应的所有换乘(公汽)站点k，均不能从i直达(不在i站点所在公汽线路L上)，则dij(0) =.,（2）若j站点对应的换乘站点(k), 可从i站点直达k，则费用为dij(0) = dik(0)；对于时间则需要加上k到j的步行时间. (若有多种选择，取最小成本者即可),i,k,j,问题的一种具体建模方法,j站点是公汽站点，i站点为地铁站点：,（1）若从i站点对应的任何换乘(公汽)站点k，均不能直达j站点，则dij(0) =.,（2）若从i站点对应的换乘(公汽)站点k，能直达j站点， 则费用为dij(0) = dkj(0)；对于时间则需要加上i到k的步行时间.,i,k,j,问题：最小费用或时间,定义矩阵算子“”如下：设A、B均为n阶方阵， C = A B (考虑换乘代价),D(k)= D(k-1) D 表示k次换乘的最低代价(费用或时间) 该算法大体相当于求最短路的Floyd-Warshall算法，但考虑了换乘因素，可称为改进Floyd-Warshall算法 类似地, 通过修改Dijkstra算法求解也可,问题：最小费用或时间,i,j,k表示换乘时间,i = j 或k = i，j时，i,j,k = 0 其他情形： 若不可换乘(当i ，j为公汽站点而k为地铁站点，或者i ，j为地铁站点而k为公汽站点时)，则 i,j,k = 0 若可换乘，则,k,这只是等待时间，因为步行时间已在D中考虑了,i,j,第问：已知所有站点间步行时间,多数队没有给出一般模型, 而只考虑最多一次换乘 多数队的想法：假设“起点步行”，“换乘步行”，“终点步行”三种模式，限定步行最大时间后搜索,i,k,j,其他：最短路问题的线性规划模型,xij表示弧（i，j）是否位于s-t路上：当xij =1时，表示弧（i，j）位于s-t路上，当xij =0时，表示弧（i，j）不在s-t路上.,关联矩阵是全么模矩阵，因此0-1变量可以松弛为区间0,1中的实数,不含负圈，变量直接松弛为所有非负实数,思考：为什么xij 可以不限定为0，1 (0-1规划) ?,最短路问题的线性规划模型,线性规划模型，应该可以计算到比较大规模的问题 有些队写出了上述模型，但并未用该模型求解 可能需要强大的优化软件，数据输入工作量也较大 换乘代价不易考虑（网络上的权不易定义，或不具可加性） 有些同学提到动态规划, 但要么与这里介绍的最短路算法等价, 要么处理有误, 或只是搜索法的变种,有些队讨论“交通阻抗”:“文不对题”,道路阻抗在交通流分配中可以通过路阻函数来描述 所谓路阻函数是指路段行驶时间与路段交通负荷，交叉口延误与交叉口负荷之间的关系 在具体分配过程中，由路段行驶时间及交叉口延误共同组成出行交通阻抗 交通网络上的路阻，应包含反映交通时间、交通安全、交通成本、舒适程度、便捷性和准时性等等许多因素,同学论文中存在的主要问题,2. 目标不当，或不完整,3. 换乘时间处理不当 尤其地铁站与公汽站之间，以及 通过地铁通道换乘的公汽站之间,1. 几乎没有模型，只有算法（一般是搜索法）,4. 算法使用不当，或滥用,5. 对第问，很少认真进行讨论和建模,6. 全文表达不清，思路混乱,Thats all. Any Questions?,Thank you for your attendance! 最后，祝大家 在数学建模活动中 取得更大的成绩！,谢金星, 清华大学数学科学系, 2007-2008.,