数学建模赛题分析(建模方法)资料

1、07B题解题(ji t)分析 共六十一页简要(jinyo)提纲 应用数学与数学建模 - 建模及建模竞赛的意义(yy) 竞赛评阅标准 - 一般原则及主要问题 优化模型的创新 - 2007B题分析共六十一页数学知识数学(shxu)技巧数学应用数学发现应用数学数学技术数学实验随机数学代数(dish)与几何微积分数学美学数学哲学数学精神数学素质数学文化数学：几个层次的理解共六十一页数学建模：实际(shj)与数学之间的桥梁实际(shj)问题数学Mathematical Modeling 现实对象的信息数学模型现实对象的解答数学模型的解答表述求解解释验证(归纳)(演绎)数学建模的全过程共六十一页美国MCM

2、+ICM竞赛(jngsi)规模共六十一页我国CUMCM竞赛(jngsi)规模共六十一页学生欢迎：“一次参赛，终身受益”研究生导师们的认同企业界的认同赞助教育改革(gig)同行的认同：“成功范例”国际同行的认同竞赛(jngsi)的反响共六十一页IBM 中国研究中心(zhngxn)- 招聘条件Position title: Business Optimization(BJ)1Background in industrial engineering, operations research, mathematics, Artificial Intelligence, management scien

3、ce 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/care

4、ers/condition.shtml竞赛的反响(fnxing)（一例）共六十一页简要(jinyo)提纲 应用数学与数学建模 - 建模及建模竞赛的意义 竞赛评阅标准 - 一般原则及主要问题 创新能力培养 -几个例子（结合(jih)优化模型）共六十一页CUMCM评阅(pngyu)标准清晰性：摘要应理解为详细摘要，提纲挈领 表达严谨、简捷，思路(sl)清新 格式符合规范，严禁暴露身份创造性：特别欣赏独树一帜、标新立异，但要合理假设的合理性，建模的创造性，结果的正确性，表述的清晰性。正确性：不强调与“参考答案”的一致性和结果的精度； 好方法的结果一般比较好；但不一定是最好的合理性：关键假设；不欣赏罗

5、列大量无关紧要的假设 共六十一页CUMCM评阅(pngyu)标准: 一些常见问题有的论文过于简单，该交代的内容(nirng)省略了，难以看懂有的队罗列一系列假设或模型，又不作比较、评价，希望碰上“参考答案”或“评阅思路”，弄巧成拙数学模型最好明确、合理、简洁：有些论文不给出明确的模型，只是根据赛题的情况，实际上是用“凑”的方法给出结果，虽然结果大致是对的，没有一般性，不是数学建模的正确思路。有的论文参考文献不全，或引用他人结果不作交代共六十一页从论文评阅看学生参加(cnji)竞赛中的问题 吃透题意方面不足(bz)，没有抓住和解决主要问题； 就事论事，形成数学模型的意识和能力欠缺； 对所用方法一

6、知半解，不管具体条件，套用现成的方法，导致错误； 对结果的分析不够，怎样符合实际考虑不周； 写作方面的问题(摘要、简明、优缺点、参考文献); 队员之间合作精神差，孤军奋战； 依赖心理重，甚至违纪（指导教师、 网络）。共六十一页简要(jinyo)提纲 应用数学与数学建模 - 建模及建模竞赛的意义 竞赛评阅标准 - 一般原则及主要问题 创新能力培养(piyng) - 2007B分析共六十一页2022/7/2714 优化问题(wnt)三要素：决策变量；目标函数；约束条件约束条件决策变量优化问题(wnt)的一般形式目标函数有人统计： 优化问题占CUMCM赛题的一半以上（1/32/3）共六十一页 建模时

7、需要(xyo)注意的几个基本问题 1、尽量使用实数优化，减少(jinsho)整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量的个数 （如x/y 5 改为x5y）4、合理设定变量上下界，尽可能给出变量初始值 5、模型中使用的参数数量级要适当 (如小于103)共六十一页优化建模如何(rh)创新？ 方法1：大胆创新，别出心裁 - 采用有特色的目标(mbio)函数、约束条件等 - 你用非线性规划，我用线性规划 - 你用整数/离散规划，我用连续规划/网络优化 - 方法

8、2：细致入微，滴水不漏 - 对目标函数、约束条件处理特别细致 - 有算法设计和分析，不仅仅是简单套用软件 - 敏感性分析详细 / 全面 - 共六十一页2007B命题(mng t)背景 奥运相关的题目：(时代特性, 社会关注(gunzh)）让运动员及时到达场馆（车辆调度，路径安排等） 应急管理（紧急疏散，应急调度等）赛程安排（单一项目，多个项目）成绩排名（如循环赛，体操或跳水等）技术类，如“刘翔的运动鞋”乘公交，看奥运：原名“自动问路机”方沛辰（吉大），吴孟达（国防科大）提出原拟作乙组题，似乎难度太大共六十一页命题(mng t)背景 定位：公交路线选择（查询）模型与算法如何给数据？抽象数据实际数

9、据？（减小规模，不给地理信息）貌似简单(jindn)，实则不然数据处理（转换）方面有一定难度换乘次数多时简单搜索不易（计算复杂度高）换乘时间步行时间等需要考虑周全标准的最短路算法（如Dijkstra算法）并不适用共六十一页 B题：乘公交，看奥运 第29届奥运会08年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择(xunz)问题。针对市场需求，某公司准备研制开发一个解决公交线路选择(xunz)问题的自主查询计算机系统。 应该(yngg

10、i)从实际情况出发考虑，满足查询者的各种不同需求。07-B 题 解 题 分 析 为了设计这样一个系统，其核心是线路选择的模型与算法。共六十一页07-B 题 解 题 分 析请解决如下问题： 1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价(pngji)说明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485 (4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同时考虑公汽与地铁线路，解决以上问题。

11、3、假设又知道所有站点之间的步行时间,请你给出任意两站点之间线路选择问题的数学模型。共六十一页07-B 题 解 题 分 析【附录1】基本参数设定相邻公汽站平均行驶时间(包括停站时间)： 3分钟相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记(bioj)于线路后；其中分段计价的票价为：020站：1元；2140站：2元； 40站以上：3元地铁票价：

12、3元（无论地铁线路间是否换乘）【附录(fl)2】公交线路及相关信息 （见数据文件B2007data.rar） 共六十一页线路(xinl)数据中的问题线路数据中的异常或不明确之处，同学可根据自己的理解作出假设和处理，一般不会影响实例的计算结果个别线路相邻站点名相同，可去掉其中一点或不作处理等L406未标明是环线，是否将其当作环线处理均可L290标明是环线，但首尾站点分别为1477与1479，可将所有线路中1477与1479统一为1477后计算。同学也可以按照各自认为合理的方式处理，包括不当作环线，或将1479改为1477，或在1479后增加1477，等等如果在假设中有明确约定，则环线单向(dn

13、xin)或双向发车均应认可（按单向(dn xin)发车作假设，计算结果可能差些） 共六十一页对通过(tnggu)地铁换乘的理解“假设同一地铁站对应的任意两个公汽站之间可以通过(tnggu)地铁站换乘(无需支付地铁费)”步行：公汽站地铁站（通道）公汽站换乘耗时11min：步行4+4=8min; 等车3min第问（只考虑公汽）：可不考虑以上换乘有同学也考虑了如上换乘，只是不坐地铁，应该也可以此样处理时，第问和第问的难度相近共六十一页07-B 题 解 题 分 析 题目特点 1、本题根据公交线路查询系统研制的实际需求简 化改编而成； 2、问题容易理解，相关参考文献较多； 3、相关知识点： （1）图论（

14、最短路径）； （2）多目标规划。 4、题目开放度不够(bgu)，可发挥余地不多。 共六十一页关于(guny)数据的预处理：1、对于原始数据中出现的一些异常数据，可根据自己的理解作出假设和处理。如：（1）对于个别线路相邻点名相同(xin tn)，可以采取去掉其中1点或不作处理等方式，一般不会影响实例计算中线路选择的结果。（2）对于L406未标明是环行线的问题，无论学生是否将其当作环线处理，一般不会影响到实例的计算结果。（3）对于L290标明是环线，但首尾站点分别为1477与1479的问题，可将所有线路中1477与1479统一为1477后计算。也可以按照各自认为合理的方式处理，包括不当作环线，实例

15、计算用到的是该线路中部的几个站点，一般不会影响实例计算结果。07-B 题 解 题 分 析2、关于环行线路，可以假设为单向或双向。3、线路数据格式需编程进行转换。共六十一页 模型(mxng)的目标多目标优化问题（至少考虑三方面）换乘次数最少(N)、费用最省(M)、时间最短(T)从该问题的实际背景来看，加权不太合适 不少同学用层次(cngc)分析法确定权不少同学计算时间的价值（平均收入工作时间）不同目标组合的模型三个目标按优先级排序，组合成六个模型也可将某些目标作为约束共六十一页 多数(dush)队仅采用搜索法（70-80%?）直达(zhd)； 一次换乘； 二次换乘；ststs t求出所有线路；评

16、价其目标(容易计算)；选优共六十一页 多数(dush)队仅采用搜索法总体来看，技术含量较低（基本上是枚举）几乎没有建模，完全只有算法实现，算法也没什么创新一般只考虑不超过两次换乘不少文章引用参考文献作为依据，实用中似乎够用 题目难度大大降低，模型不够一般换乘作为了第一目标，或作为一个(y )最重要的约束任意次换乘时算法复杂度提高，难以处理结果不佳（如：从省时考虑，有些需次换乘）共六十一页 图论(t ln)模型与最短路算法用图论做的队也不少，但往往考虑不周弧上赋权方式交代不清套用Dijkstra或Floyd-Warshall算法，却不清楚其原理及适用的问题需要建立一个带权有向图，节点表示站点，有

17、向弧表示前一站点能够直达后一站点，弧上的权表示前一站点直达后一站点所需付出的代价(时间或费用(fi yong)图（网络）如何描述和表示？基本要素：节点，有向弧（边），弧上赋权邻接矩阵；关联矩阵（数学上处理方便，存储量较大）链表（存储量较小，计算机上处理方便）共六十一页 关联矩阵(Incidence Matrix)表示法在线路选择问题中，当从i可直达j时，定义弧(i,j)；其上的权可为或成本(chngbn)(时间或费用)；多重弧可只保留一条（弧上的权可取最小的成本，如时间或费用）G=(V，A)是一个(y )简单有向图；|V|=n，|A|=m 重要数学性质：关联矩阵是全幺模矩阵图G=(V，A)的邻

18、接矩阵C是如下定义的：C是一个 的矩阵，即共六十一页 邻接矩阵(Adjacency Matrix)表示法图G=(V，A)的邻接矩阵C是如下定义(dngy)的：C是一个 的0-1矩阵，即在线路选择问题中，当从i可直达(zhd)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次可达矩阵；共六十一页链表（邻接(ln ji)表）表示法 122345283904602403053036470单

19、向(dn xin)链表(指针数组) A(1)=2,3A(2)=4A(3)=2A(4)=3,5A(5)=3,412345共六十一页 Dijkstra算法(sun f)（标号算法(sun f)，1959）STEP1. 如果S=V, 则uj为节点s到节点j的最短路路长(最短路可以通过(tnggu)数组pred所记录的信息反向追踪获得), 结束.否则继续. STEP0. (初始化) 令S= ，=V， ；对V 中的顶点j(j s)令初始距离标号 . STEP2. 从 中找到距离标号最小的节点i，把它从 删除，加入S. 对于所有从i出发的弧 , 若 ，则令 转STEP1. 特点：1. 算法求出从源点s到所

20、有点的最短路长 2. 每点给一对标号 (uj, predj)，uj是从s到j的最短路长；predj是从s到j的最短路中j点的前一点共六十一页Example共六十一页Dijkstra算法(sun f)（标号设定算法(sun f)）适用于正费用网络：“分层”设定标号永久标号：S中的点，uj是最短路(dunl)长临时标号；其他点， uj是只通过S中的点的最短路长对于稠密网络，这是求解最短路问题可能达到的最小的复杂度,因为任何算法都至少必须对每条弧考虑一次.对于稀疏网络，利用各种形式的堆（Heap），其复杂度可降为 或 等算法复杂度O( n2+m)：如链表或邻接矩阵实现找最小标号点修改标号共六十一页特

21、点：求所有点对间最短路基本思想(sxing)：逐步逼近，迭代求解最短路方程: O(n3) Floyd-Warshall算法(sun f)（标号修正算法1962)临时标号 是不通过k，k+1，,n 节点(i,j 除外)时从节点i到节点j的最短路路长. 共六十一页 Floyd-Warshall算法的具体(jt)实现: O(n3)由于要记录所有节点(ji din)之间最短路的信息, 所以这里我们要用一个二维数组P； 可依据P, 采用“正向追踪”的方式得到最短路. STEP2：如果k=n, 结束; 否则转STEP1. STEP0: k=0. 对于所有节点i和j: 令 ， , ( ，若节点i和j之间没有

22、弧, 认为 ) . STEP1: k=k+1. 对于所有节点i和j: 若 , 令 , ; 否则令 , . 共六十一页Floyd-Warshall算法(sun f)的矩阵迭代法实现：O(n4)令D为权矩阵(j zhn)(直达最短路长)Dm为正好经过m条弧从i到j的最短路长共六十一页 问题(wnt)1和2的一种具体建模方法(赋权)在线路选择问题中，当从i可直达(zhd)j时（同为公汽或地铁站点），定义弧(i,j)；其上的权为lij表示由i直达j付出的代价，可以为时间或费用 (不包括换乘代价；多条线路可达时只保留最小代价)初始等车时间2(3)min也不包括在内，最后结果可加上注意：D=D(0)不是对

23、称矩阵(“直达矩阵”)dij(0)=dij共六十一页 问题(wnt)的一种具体建模方法i站点是公汽站点，j站点为地铁站点：（1）若j站点对应(duyng)的所有换乘(公汽)站点k，均不能从i直达(不在i站点所在公汽线路L上)，则dij(0) =. （2）若j站点对应的换乘站点(k), 可从i站点直达k，则费用为dij(0) = dik(0)；对于时间则需要加上k到j的步行时间. (若有多种选择，取最小成本者即可)ikj共六十一页 问题的一种具体(jt)建模方法j站点是公汽站点，i站点为地铁站点：（1）若从i站点对应(duyng)的任何换乘(公汽)站点k，均不能直达j站点，则dij(0) =.

24、（2）若从i站点对应的换乘(公汽)站点k，能直达j站点， 则费用为dij(0) = dkj(0)；对于时间则需要加上i到k的步行时间. ikj共六十一页 问题：最小费用(fi yong)或时间 定义(dngy)矩阵算子“”如下：设A、B均为n阶方阵， C = A B (考虑换乘代价)当考虑费用矩阵之间的运算时，表示在k的换乘时间 当考虑时间矩阵之间的运算时， D(k)= D(k-1) D 表示k次换乘的最低代价(费用或时间) 该算法大体相当于求最短路的Floyd-Warshall算法，但考虑了换乘因素，可称为改进Floyd-Warshall算法 类似地,通过修改Dijkstra算法求解也可共六

25、十一页 问题(wnt)：最小费用或时间i,j,k表示(biosh)换乘时间 i = j 或k = i，j时，i,j,k = 0其他情形：若不可换乘(当i ，j为公汽站点而k为地铁站点，或者i ，j为地铁站点而k为公汽站点时)，则 i,j,k = 0若可换乘，则k这只是等待时间，因为步行时间已在D中考虑了ij共六十一页 第问：已知所有(suyu)站点间步行时间多数队没有给出一般模型, 而只考虑最多一次换乘多数队的想法：假设“起点步行”，“换乘步行”，“终点(zhngdin)步行”三种模式，限定步行最大时间后搜索ikj共六十一页 其他(qt)：最短路问题的线性规划模型xij表示(biosh)弧（i

26、，j）是否位于s-t路上：当xij =1时，表示弧（i，j）位于s-t路上，当xij =0时，表示弧（i，j）不在s-t路上. 关联矩阵是全么模矩阵，因此0-1变量可以松弛为区间0,1中的实数 不含负圈，变量直接松弛为所有非负实数思考：为什么xij 可以不限定为0，1 (0-1规划) ?共六十一页 最短路问题的线性规划(xin xn u hu)模型线性规划模型，应该可以计算到比较大规模的问题有些队写出了上述模型，但并未用该模型求解可能需要强大的优化软件，数据输入工作量也较大换乘代价不易考虑（网络(wnglu)上的权不易定义，或不具可加性） 有些同学提到动态规划, 但要么与这里介绍的最短路算法等

27、价, 要么处理有误, 或只是搜索法的变种共六十一页 有些队讨论“交通阻抗(zkng)”:“文不对题”道路阻抗在交通流分配中可以通过路阻函数来描述所谓路阻函数是指路段行驶时间与路段交通负荷，交叉口延误与交叉口负荷之间的关系在具体分配过程中，由路段行驶时间及交叉口延误共同组成出行交通阻抗交通网络上的路阻，应包含反映交通时间、交通安全、交通成本、舒适(shsh)程度、便捷性和准时性等等许多因素共六十一页 同学论文中存在的主要(zhyo)问题2. 目标(mbio)不当，或不完整 3. 换乘时间处理不当 尤其地铁站与公汽站之间，以及 通过地铁通道换乘的公汽站之间1. 几乎没有模型，只有算法（一般是搜索法

28、）4. 算法使用不当，或滥用5. 对第问，很少认真进行讨论和建模6. 全文表达不清，思路混乱共六十一页关于目标(mbio)的考虑：问题(wnt)1、2：换乘次数最少、费用最省、时间最短。 07-B 题 解 题 分 析问题3：换乘次数最少、乘车的总站数最少、步行的总时间最少、总车费最少等 。 共六十一页关于目标(mbio)的处理： 从该问题的实际背景来看，采取加权合成将问题转化为单目标优化问题的解题思路不太合适。比较适当的方法是对每个目标寻求最佳线路，然后让乘客按照(nzho)自己的需要进行选择。 07-B 题 解 题 分 析共六十一页换乘次数(csh)与可达矩阵：对于本问题，经计算(j sun

29、)可知，任何两站点最多经5次换乘可达。经三次换乘可达率大于99%。07-B 题 解 题 分 析共六十一页 问题(wnt)1 不考虑地铁线路时的公交线路选择 图论模型：这可能是最常使用的方法，首先要考虑如何根据不同目标建立有向赋权图（如利用不同的矩阵(j zhn)表示），然后再求给定点对之间的最小换乘次数或最短路。求两点间最短路有Dijkstra算法与Floyd算法等，但并不能将这两种算法直接套用于本问题，还需要处理好换乘次数 和换乘时间问题。07-B 题 解 题 分 析共六十一页其它(qt)方法规划模型，包括(boku)01规划方法与动态规划方法等。数据库模型，利用数据库技术直接对线路及站点数据进行搜索。07-B 题 解 题 分 析共六十一页问题2 考虑(kol)地铁线路时的线路选择 本问可以有多种处理方法，关键是看合理性与可操作性。换乘时间的处理较第一问要复杂，需重点(zhngdin)关注。 07-B 题 解 题 分 析共六十一页07-B 题 解 题 分 析关于地铁与公汽联合的考虑： 对于任一条(y tio)地铁线路，我们将其虚拟为一条(y tio)“双向公汽”线路，地铁沿线对应各个公汽站点均认为可通过该线路直达。如图所示: 其