《数学建模赛题分析(建模方法)ppt课件.ppt》由会员分享，可在线阅读，更多相关《数学建模赛题分析(建模方法)ppt课件.ppt（60页珍藏版）》请在三一办公上搜索。
1、07B题解题分析,简要提纲,应用数学与数学建模-建模及建模竞赛的意义 竞赛评阅标准-一般原则及主要问题 优化模型的创新-2007B题分析,数学知识数学技巧,随机数学代数与几何微积分,数学：几个层次的理解,数学建模：实际与数学之间的桥梁,实际问题,数学,Mathematical Modeling,现实对象的信息,数学模型,现实对象的解答,数学模型的解答,(归纳),(演绎),数学建模的全过程,美国MCM+ICM竞赛规模,我国CUMCM竞赛规模,学生欢迎：“一次参赛，终身受益”研究生导师们的认同企业界的认同赞助教育改革同行的认同：“成功范例”国际同行的认同,竞赛的反响,IBM 中国研究中心-招聘条件
2、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.
3、Experience in industry is a plus 5.Experience in eclipse or programming model/architecture design is a plus-Feb.18,2006,http:/,竞赛的反响（一例）,简要提纲,应用数学与数学建模-建模及建模竞赛的意义 竞赛评阅标准-一般原则及主要问题 创新能力培养-几个例子（结合优化模型）,CUMCM评阅标准,清晰性：摘要应理解为详细摘要，提纲挈领 表达严谨、简捷，思路清新 格式符合规范，严禁暴露身份,创造性：特别欣赏独树一帜、标新立异，但要合理,假设的合理性，建模的创造性，结果的正确性
4、，表述的清晰性。,正确性：不强调与“参考答案”的一致性和结果的精度；好方法的结果一般比较好；但不一定是最好的,合理性：关键假设；不欣赏罗列大量无关紧要的假设,CUMCM评阅标准:一些常见问题,有的论文过于简单，该交代的内容省略了，难以看懂,有的队罗列一系列假设或模型，又不作比较、评价，希望碰上“参考答案”或“评阅思路”，弄巧成拙,数学模型最好明确、合理、简洁：有些论文不给出明确的模型，只是根据赛题的情况，实际上是用“凑”的方法给出结果，虽然结果大致是对的，没有一般性，不是数学建模的正确思路。,有的论文参考文献不全，或引用他人结果不作交代,从论文评阅看学生参加竞赛中的问题,吃透题意方面不足，没有
5、抓住和解决主要问题；就事论事，形成数学模型的意识和能力欠缺；对所用方法一知半解，不管具体条件，套用现成的方法，导致错误；对结果的分析不够，怎样符合实际考虑不周；写作方面的问题(摘要、简明、优缺点、参考文献);队员之间合作精神差，孤军奋战；依赖心理重，甚至违纪（指导教师、网络）。,简要提纲,应用数学与数学建模-建模及建模竞赛的意义 竞赛评阅标准-一般原则及主要问题 创新能力培养-2007B分析,14,优化问题三要素：决策变量；目标函数；约束条件,优化问题的一般形式,有人统计：优化问题占CUMCM赛题的一半以上（1/32/3）,建模时需要注意的几个基本问题,1、尽量使用实数优化，减少整数约束和整数
6、变量2、尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量的个数（如x/y 5 改为x5y）4、合理设定变量上下界，尽可能给出变量初始值 5、模型中使用的参数数量级要适当(如小于103),优化建模如何创新？,方法1：大胆创新，别出心裁-采用有特色的目标函数、约束条件等-你用非线性规划，我用线性规划-你用整数/离散规划，我用连续规划/网络优化-方法2：细致入微，滴水不漏-对目标函数、约束条件处理特别细致-有算法设计和分析，不仅仅是简单套用软件-敏感性分析详细/全面-,2007B命题背
7、景,奥运相关的题目：(时代特性,社会关注）让运动员及时到达场馆（车辆调度，路径安排等）应急管理（紧急疏散，应急调度等）赛程安排（单一项目，多个项目）成绩排名（如循环赛，体操或跳水等）技术类，如“刘翔的运动鞋”乘公交，看奥运：原名“自动问路机”方沛辰（吉大），吴孟达（国防科大）提出原拟作乙组题，似乎难度太大,命题背景,定位：公交路线选择（查询）模型与算法如何给数据？抽象数据实际数据？（减小规模，不给地理信息）貌似简单，实则不然数据处理（转换）方面有一定难度换乘次数多时简单搜索不易（计算复杂度高）换乘时间步行时间等需要考虑周全标准的最短路算法（如Dijkstra算法）并不适用,B题：乘公交，看奥运
8、 第29届奥运会08年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。,应该从实际情况出发考虑，满足查询者的各种不同需求。,07-B 题 解 题 分 析,为了设计这样一个系统，其核心是线路选择的模型与算法。,07-B 题 解 题 分 析,请解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们
9、的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。(1)、S3359S1828(2)、S1557S0481(3)、S0971S0485(4)、S0008S0073(5)、S0148S0485(6)、S0087S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间,请你给出任意两站点之间线路选择问题的数学模型。,07-B 题 解 题 分 析,【附录1】基本参数设定相邻公汽站平均行驶时间(包括停站时间)：3分钟相邻地铁站平均行驶时间(包括停站时间)：2.5分钟公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时：4分钟(
10、其中步行时间2分钟)地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）,【附录2】公交线路及相关信息（见数据文件B2007data.rar）,线路数据中的问题,线路数据中的异常或不明确之处，同学可根据自己的理解作出假设和处理，一般不会影响实例的计算结果个别线路相邻站点名相同，可去掉其中一点或不作处理等L406未标明是环线，是否将其当作环线处理均可L290标明是环线，但首尾站点分别为1
11、477与1479，可将所有线路中1477与1479统一为1477后计算。同学也可以按照各自认为合理的方式处理，包括不当作环线，或将1479改为1477，或在1479后增加1477，等等如果在假设中有明确约定，则环线单向或双向发车均应认可（按单向发车作假设，计算结果可能差些）,对通过地铁换乘的理解,“假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)”步行：公汽站地铁站（通道）公汽站换乘耗时11min：步行4+4=8min;等车3min第问（只考虑公汽）：可不考虑以上换乘有同学也考虑了如上换乘，只是不坐地铁，应该也可以此样处理时，第问和第问的难度相近,07-B 题 解 题
12、 分 析,题目特点 1、本题根据公交线路查询系统研制的实际需求简 化改编而成；2、问题容易理解，相关参考文献较多；3、相关知识点：（1）图论（最短路径）；（2）多目标规划。4、题目开放度不够，可发挥余地不多。,关于数据的预处理：,1、对于原始数据中出现的一些异常数据，可根据自己的理解作出假设和处理。如：（1）对于个别线路相邻点名相同，可以采取去掉其中1点或不作处理等方式，一般不会影响实例计算中线路选择的结果。（2）对于L406未标明是环行线的问题，无论学生是否将其当作环线处理，一般不会影响到实例的计算结果。（3）对于L290标明是环线，但首尾站点分别为1477与1479的问题，可将所有线路中1
13、477与1479统一为1477后计算。也可以按照各自认为合理的方式处理，包括不当作环线，实例计算用到的是该线路中部的几个站点，一般不会影响实例计算结果。,07-B 题 解 题 分 析,2、关于环行线路，可以假设为单向或双向。,3、线路数据格式需编程进行转换。,模型的目标,多目标优化问题（至少考虑三方面）换乘次数最少(N)、费用最省(M)、时间最短(T)从该问题的实际背景来看，加权不太合适 不少同学用层次分析法确定权不少同学计算时间的价值（平均收入工作时间）不同目标组合的模型三个目标按优先级排序，组合成六个模型也可将某些目标作为约束,多数队仅采用搜索法（70-80%?）,直达；一次换乘；二次换乘
14、；,st,st,s t,求出所有线路；评价其目标(容易计算)；选优,多数队仅采用搜索法,总体来看，技术含量较低（基本上是枚举）几乎没有建模，完全只有算法实现，算法也没什么创新一般只考虑不超过两次换乘不少文章引用参考文献作为依据，实用中似乎够用 题目难度大大降低，模型不够一般换乘作为了第一目标，或作为一个最重要的约束任意次换乘时算法复杂度提高，难以处理结果不佳（如：从省时考虑，有些需次换乘）,图论模型与最短路算法,用图论做的队也不少，但往往考虑不周弧上赋权方式交代不清套用Dijkstra或Floyd-Warshall算法，却不清楚其原理及适用的问题需要建立一个带权有向图，节点表示站点，有向弧表示
15、前一站点能够直达后一站点，弧上的权表示前一站点直达后一站点所需付出的代价(时间或费用)图（网络）如何描述和表示？基本要素：节点，有向弧（边），弧上赋权邻接矩阵；关联矩阵（数学上处理方便，存储量较大）链表（存储量较小，计算机上处理方便）,关联矩阵(Incidence Matrix)表示法,在线路选择问题中，当从i可直达j时，定义弧(i,j)；其上的权可为或成本(时间或费用)；多重弧可只保留一条（弧上的权可取最小的成本，如时间或费用）,G=(V，A)是一个简单有向图；|V|=n，|A|=m,重要数学性质：关联矩阵是全幺模矩阵,图G=(V，A)的邻接矩阵C是如下定义的：C是一个 的矩阵，即,邻接矩阵
16、(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
17、.如果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是最短路长临时
18、标号；其他点，uj是只通过S中的点的最短路长,对于稠密网络，这是求解最短路问题可能达到的最小的复杂度,因为任何算法都至少必须对每条弧考虑一次.对于稀疏网络，利用各种形式的堆（Heap），其复杂度可降为 或 等,特点：求所有点对间最短路基本思想：逐步逼近，迭代求解最短路方程:O(n3),Floyd-Warshall算法（标号修正算法1962),临时标号 是不通过k，k+1，,n 节点(i,j 除外)时从节点i到节点j的最短路路长.,Floyd-Warshall算法的具体实现:O(n3),由于要记录所有节点之间最短路的信息,所以这里我们要用一个二维数组P；可依据P,采用“正向追踪”的方式得到最短路
19、.,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也不包括在内，最后
20、结果可加上注意：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站点对应的换乘(
21、公汽)站点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为地铁站点而
22、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(
23、0-1规划)?,最短路问题的线性规划模型,线性规划模型，应该可以计算到比较大规模的问题有些队写出了上述模型，但并未用该模型求解可能需要强大的优化软件，数据输入工作量也较大换乘代价不易考虑（网络上的权不易定义，或不具可加性）有些同学提到动态规划,但要么与这里介绍的最短路算法等价,要么处理有误,或只是搜索法的变种,有些队讨论“交通阻抗”:“文不对题”,道路阻抗在交通流分配中可以通过路阻函数来描述所谓路阻函数是指路段行驶时间与路段交通负荷，交叉口延误与交叉口负荷之间的关系在具体分配过程中，由路段行驶时间及交叉口延误共同组成出行交通阻抗交通网络上的路阻，应包含反映交通时间、交通安全、交通成本、舒适程度
24、、便捷性和准时性等等许多因素,同学论文中存在的主要问题,2.目标不当，或不完整,3.换乘时间处理不当 尤其地铁站与公汽站之间，以及 通过地铁通道换乘的公汽站之间,1.几乎没有模型，只有算法（一般是搜索法）,4.算法使用不当，或滥用,5.对第问，很少认真进行讨论和建模,6.全文表达不清，思路混乱,关于目标的考虑：,问题1、2：换乘次数最少、费用最省、时间最短。,07-B 题 解 题 分 析,问题3：换乘次数最少、乘车的总站数最少、步行的总时间最少、总车费最少等。,关于目标的处理：,从该问题的实际背景来看，采取加权合成将问题转化为单目标优化问题的解题思路不太合适。比较适当的方法是对每个目标寻求最佳
25、线路，然后让乘客按照自己的需要进行选择。,07-B 题 解 题 分 析,换乘次数与可达矩阵：,对于本问题，经计算可知，任何两站点最多经5次换乘可达。经三次换乘可达率大于99%。,07-B 题 解 题 分 析,问题1 不考虑地铁线路时的公交线路选择,图论模型：这可能是最常使用的方法，首先要考虑如何根据不同目标建立有向赋权图（如利用不同的矩阵表示），然后再求给定点对之间的最小换乘次数或最短路。求两点间最短路有Dijkstra算法与Floyd算法等，但并不能将这两种算法直接套用于本问题，还需要处理好换乘次数 和换乘时间问题。,07-B 题 解 题 分 析,其它方法,规划模型，包括01规划方法与动态规
26、划方法等。数据库模型，利用数据库技术直接对线路及站点数据进行搜索。,07-B 题 解 题 分 析,问题2 考虑地铁线路时的线路选择,本问可以有多种处理方法，关键是看合理性与可操作性。换乘时间的处理较第一问要复杂，需重点关注。,07-B 题 解 题 分 析,07-B 题 解 题 分 析,关于地铁与公汽联合的考虑：对于任一条地铁线路，我们将其虚拟为一条“双向公汽”线路，地铁沿线对应各个公汽站点均认为可通过该线路直达。如图所示:,其中 为地铁站 对应所有公交站点。这样就可以将原来无法直达的公交站通过地铁站将它们连接起来，如此得到新的连接网络。,Si1,Si2,Sj1,Sj2,Di,Dj,Tk,问题3
27、 已知站点间步行时间条件下的线路选择,这是比较一般的线路选择问题，更接近实际。由于增加了步行因素，每个站点的可换乘方案大大增加了，于是用图论方法处理的难度会有很大增加。最常用的目标有：换车次数最少、乘车的总站数最少、步行的总时间最少、总车费最少等等，应该针对不同的情况分别写出模型。,07-B 题 解 题 分 析,方法1、将步行理解为第三种交通方式，转换为问题1。这使得问题规模急剧膨胀，求解变得相当困难。,方法2、设置一个步行时间的上限。,07-B 题 解 题 分 析,Si,Sj,1、本题1、2问要求在不知道站点地理信息的条件下给出解决线路选择问题的模型与算法，并就题目给定的数据计算得到线路选择结果，此二问主要考核建模及编程能力。关键是最短时间线路的选择及换乘时间的处理。,07-B 题 解 题 分 析,本题需要注意的两点：,2、算法的运算时间问题不是本题的考察重点。因为若算法运算时间比较长，可事先计算出所有最佳线路，将结果存入数据库备查。,几点 启示多关注社会热点问题。数据量大且形式多样。对计算机基础知识的掌握要求更高。对分数比例的正确判断有助于确定建模时的力量分配。,07-B 题 解 题 分 析,谢 谢！,
