数学建模课件

数学建模数学建模雷涛雷涛 罗睿辞罗睿辞 王尧王尧 汪瑜婧汪瑜婧数学建模雷涛 罗睿辞 王尧 汪瑜婧1数学建模的定义目前还没有统一的定义数学模型是为一种特殊目的而建立的一个抽象的、简化的结构。描述现实世界的一部分特征表现事物之间的一部分客观联系数学建模的定义目前还没有统一的定义2数学模型的分类微分方程模型差分方程模型层次分析模型线性规划模型动态规划模型图论模型其它模型数学模型的分类微分方程模型3主要内容建模的方法和步骤 汪瑜婧图论模型的建立 罗睿辞图论模型的选择和关系的简化 雷涛其它数学模型举例 王尧主要内容建模的方法和步骤 汪瑜婧4建模的方法和步骤模型准备模型假设模型的建立模型求解与分析模型检验模型应用 建模的方法和步骤模型准备5问题的提出2007CUMCM B题 乘公交，看奥运给定若干条公交线路，以及在每条公交线路中任意相邻的两站之间所花费的时间。并且给定乘客在任意站点换乘的耗时要求给出任意两公汽站点之间线路选择问题的一般数学模型与算法，求出最佳的公交线路.问题的提出2007CUMCM B题 乘公交，看奥运6模型的假设对”最优”的理解有三个具有代表性的指标：时间最短花费最少最方便（换乘次数最少）不同的人群对最优的理解不同,需要根据实际定义.可以根据需要定义代价函数,三个指标的权重不同,代价值也不同。以时间最短为例模型的假设对”最优”的理解有三个具有代表性的指标：7模型的建立G=(V,E)每个车站：G的顶点每条公交线路相邻两点的连线：G的边边的权重：耗费时间 点的权重：换乘时间并不是一个简单图，两点间可能有多条边5937ac b(8)模型的建立G=(V,E)5937ac b(8)8考虑a经过b到c的最短路径由于有换乘的情况，只记录任意两点间的最短路径是不够的。并非一个标准的图论模型与经典最短路径问题比较567ac b(8)Min(a,b)=5Min(b,c)=3Min(a,c)=5+6=113与经典最短路径问题比较567ac b(8)Min(a,b9转化成标准的图论模型 每条公交线路抽象为一层层与层之间相连的顶点均代表同一个车站它们之间的边(虚线)的权值为换乘花费的时间 调用M*M次Dijkstra算法才能得到最优解 M为公交线路的总数转化成标准的图论模型 每条公交线路抽象为一层 10回顾上图导致无法使用标准算法原因:Min(a,b)和Min(b,c)之间需要计算附加耗时不用换车的线路成为最佳路径改进的想法:一次性地处理不用换车的情况567acMin(a,b)=5Min(b,c)=3Min(a,c)=5+6=113 b(8)回顾上图567acMin(a,b)=53 b(8)11模型的求解标准算法:每次选择一个新顶点进行扩展所有顶点扩展完毕即为最优解修改后的算法每次对一个顶点所能选择的所有公交线路扩展所有不用换乘就能到达的顶点均在一次中处理所有顶点扩展完毕即为最优解.模型的求解标准算法:12算法描述一次将扩展出多个顶点,用最小值堆保存初始:起点对应的节点S入堆；并赋予标志信息Time(S)=0取堆顶,对此定点,逐一枚举所有不用换乘就能到达的顶点,更新堆中对应点的标志信息.不断重复取堆顶的过程,直到取出的顶点为最终目标T Time(T)即为所求算法描述一次将扩展出多个顶点,用最小值堆保存13举例说明算法步骤abcdefg1298159206119225考虑顶点考虑顶点b到顶点到顶点g的路径的路径举例说明算法步骤abcdefg12981592061192214问题重述加入步行的因素,即任意两个车站之间人都可能通过步行到达,并给出步行的时间代价.问题重述加入步行的因素,即任意两个车站之间人都可能通过步行到15由于每两点之间均有步行路径,每次扩展都将涉及到所有顶点,复杂度增加不少改进的办法 预处理 找到两个相邻顶点之间路径的最小值,如果它加上两个顶点的权值之后后,仍然小于一些其它的路径,就可以将其它路径删除.这样至少可以删除不少步行路径考虑实际情况,可设定步行时间的上限.567ac加入步行的路径加入步行的路径并给定权值并给定权值20由于每两点之间均有步行路径,每次扩展都将涉及到所有顶点,复杂16算法的总结关键在于如何解决换乘的耗时扩展节点的策略与经典算法不同算法实际用到了分支界限法的思想类似于回溯法，但是求解的目标不同。目标：找到使目标函数取极值的解。算法的总结关键在于如何解决换乘的耗时17分支界限法思想以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树从一个点开始，每次以一定的策略扩展一些结点。每一个活结点一旦成为扩展结点，就一次性产生其所有子结点，并从活节点中移除。在产生 的子结点中，导致不可行解或导致非最优解的子结点被舍弃，其余的加入活结点表中。分支界限法思想以广度优先或以最小耗费（最大效益）优先的方式搜18选择扩展的节点从活结点表中选择下一扩展结点可能有不同的方式队列式分支限界法：先入先出的原则优先队列式分支限界法：选择优先级最高的节点进行扩展最大效益问题：最大值堆 最小耗费问题：最小值堆选择扩展的节点从活结点表中选择下一扩展结点可能有不同的方式19一个简单的例子印刷电路板将布线区域划分为nm个方格阵列精确的电路板布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。布线时电路只能沿直线或直角布线。为避免线路相交，已布线方格做上封闭标记，其他线路布线不允许穿过封闭区域。一个简单的例子印刷电路板将布线区域划分为nm个方格阵列20abab2111a11b11a11b222211a12212b22211a12212b22332211a12212b2332211a12212b232432211a12212b23432211a12212b2342532211a12212b234532211a12212b23452632211a12212b23456632211a12212b2345662732211a12212b2345676732211a12212b234567672832211a12212b2348567867832211a12212b2348567867829建模步骤的总结模型的准备提出问题，搜集数据。模型的假设根据实际情况，提出合理的假设简化问题。模型的建立根据所作的假设分析对象的因果关系，利用对象的内在规律和适当的数学工具，构造各个量间的等式关系或其它数学结构。建模步骤的总结模型的准备30建模步骤的总结模型的分析与求解已建立的模型是否有标准解法转化成标准模型对已有的标准解法修改，以适应模型的求解模型的检验灵敏性，鲁棒性模型的应用建模步骤的总结模型的分析与求解31图论模型的引入引例 现有6个人，任意两人之间或者相互认识，或者相互不认识，证明这6个人中，或者有3个人彼此都认识，或者有3个人彼此不认识图论模型的引入引例32思路一只有6个人，人数非常少，可以枚举任意两人之间的关系，然后判断每一种情况是否符合题意。如果所有情况都满足，则命题成立。虽然只有6个人，但是这样做的时间复杂度可不低，枚举次数为215 只能借助计算机了。有没有人可以直接证明的办法呢？思路一只有6个人，人数非常少，可以枚举任意两人之间的关系，然33思路二有了图论这个强大的工具我们还是像往常一样，以人为顶点，关系为边，建图但是为了以后的直观，这里图的建立有一点小小的不同：如果两个人之间相互认识，则在这两个人(顶点)间连一条红色边，如果两个人不认识，则在这两个人(顶点)间连一条蓝色边(下面会看到这样做的好处)那么这样我们就得到了一个由红边和蓝边组成的6阶完全图我们实际上要证明的就是这个图中或者存在一个红三角形(认识)，或者存在一个蓝三角形(不认识)思路二有了图论这个强大的工具34任取一个顶点v0，由它连出5条边到其它的顶点，这五条边只有红色和蓝色两种根据抽屉原理，肯定有一种颜色的边有3条或3条以上,不妨设为红色viv0vjvk如果vi,vj,vk之间的边都是蓝边，则图中存在一个蓝三角形如果至少有1条为红边，那么它总会与v0发出的两条红边组成一个红三角形。这样就证明了这个命题任取一个顶点v0，由它连出5条边到其它的顶点，这五条边只有红35现有n根长度不同的小木棍，每根木棍数量无限，取出一些小木棍可以拼出一根长度为这些小木棍长度之和的木棍。现在要求最小的整数k，使得长度大于等于k的木棍都能够被给出的n根小木棍拼出。例如，现在有3根小木棍，长度分别3,5,7它们可以拼出长度为3,5,6,7,8,9,10,11,12,13的木棍，看上去5就是答案，怎么证明呢？可以考虑把能够拼出来的木棍长度x根据模3的结果分成3类(0,1,2)对于x mod 3=0,3能够拼出来，那么6,9,12等等模3为0的数都可以被拼出来对于x mod 3=1，7能被拼出来，那么7,10,13等等都能被拼出来对于x mod 3=2，5能被拼出来，那么8,11,14等等都能被拼出来 也就是说，5确实是我们要求的答案这个题看上去似乎毫无头绪，那就先看看简单的情况吧！现有n根长度不同的小木棍，每根木棍数量无限，取出一些小木棍可36根据上面的证明，可以发现一种思路，不妨把上述结果推广一下：设n根木棍的长度为L1,L2,Ln,不妨设L1为所有木棍中最短的现在把能够拼出的木棍长度根据模L1的结果分为L1类(0,1L1-1),若某一类中的数模L1的结果为i,则它们组成的集合为Si显然，如果存在一个集合Si为空，则问题无解现在考虑所有集合都不为空的情况：设每个集合的最小元为b0,b1bl1-1(集合不为空，肯定存在最小元)那么如何去求题目要求的k呢？根据上面的证明，可以发现一种思路，不妨把上述结果推广一下：37考虑这样一个值：k=max bn-L1，1=n0.k不属于任何Si集合,否则与k是某个S中最小元。即k不能被小木棍拼出。对任意Lk,设L Sp，L+L1maxbn=bp 故Lbp-L1而L bp(mod p)所以 L=bp，所以L一定能够被拼出由以上两点可知，k一定是不能被拼出的木棍长度中的最大值那么k+1就是我们要求的答案！考虑这样一个值：k=max bn-L1，1=n38还剩下最后一步：求b0,b1,b2bl1-1,也就是每个集合中的最小元事实上，每一个能被拼出来的木棍长度x，都是从0开始，用已有的小木棍拼出来的。那么就可以把集合的编号看做顶点，小木棍的长度看边的长度，建立一个图。对于每个点i(集合i)，都连出n条边，长度为L1,L2Ln。对于长度为Lk的边，连向编号为(i+Lk)mod L1的顶点。对于从顶点i到j的一条长度为L的路径，表示集合i中的一个数加上L后得到的数属于集合j。对于任意一个能拼出来的数x(设x mod L1=p),根据上面的建图规则，x一定是点0到p的一条路径的长度。反过来，0到p的所有路径长度都属于Sp。所以，可以得出结论：Sp中的最小元其实就是顶点0到顶点p的最短路径长度。有了这个结论，我们就可以很容易的求出序列bn了至此，这个问题也就被完美的解决还剩下最后一步：求b0,b1,b2bl1-1,也就是每个集39数学建模模型的选择、关系的简化很多问题都是通过建立图论模型解决的图论中常见的模型有序列、树、各种图如何有效选择数学模型，简化原问题中元素之间的关系是数学建模的关键数学建模模型的选择、关系的简化很多问题都是通过建立图论模40题目坐船问题（改编自湖南省信息学省队选拔赛试题）北大有n个学生去公园划船：一只船最多坐2个人；出于娱乐目的，大家决定同船的2个人要么同姓要么同名；每个人都必须上船，且不能有脚踏多只船的情况问最少需要几只船。题目坐船问题（改编自湖南省信息学省队选拔赛试题）41例子6个同学：姚金宇，李金宇，姚峰宏，陈峰宏姚金宇 姚峰宏陈峰宏李金宇姚金宇 李金宇陈峰宏 姚峰宏例子6个同学：姚金宇，李金宇，姚峰宏，陈峰宏姚金宇 姚峰宏42例子4个同学：陈峰宏，囧峰宏，罗睿辞，廖叶子罗睿辞同学想和廖叶子同学坐同一船是不行的，因为他们不同名也不同姓陈峰宏 囧峰宏罗睿辞廖叶子陈峰宏 囧峰宏罗睿辞 廖叶子例子4个同学：陈峰宏，囧峰宏，罗睿辞，廖叶子陈峰宏 囧峰宏43将每一同学视为一元素，元素之间的关系为同名或者同姓构图是很自然的思路：2名同学同名或者同姓就连一条边一条边就代表了一种坐船的搭配方式用最少的边覆盖图中的点一般图的最小边覆盖问题一般图最大匹配问题，算法复杂，实现麻烦。建模姚金宇李金宇姚峰宏陈峰宏陈峰宏囧峰宏罗睿辞廖叶子将每一同学视为一元素，元素之间的关系为同名或者同姓建模姚金宇44建模图是本题信息最充分、最自然的模型，但其中数据关系存在很多冗余，没有充分利用原题的条件单独看同名、同姓这2种关系，它们都是等价关系，具有传递性那么换一种模型构造如何？把图转换成树来考虑建模图是本题信息最充分、最自然的模型，但其中数据关系存在很多45建模对于原图中的每一个连通分量，一定可以转换成一棵二叉树树中一个结点的左孩子跟其同姓；一个结点的右孩子跟其同名。证明用反证法罗睿辞罗贯中罗纳尔多廖睿辞罗睿辞罗贯中罗纳尔多廖睿辞建模对于原图中的每一个连通分量，一定可以转换成一棵二叉树罗睿46问题的解决含有n个点的连通分量，至少需要(n+1)div 2只船使用贪心法，一定可以构造出一个只需(n+1)div 2只船的解罗睿辞罗贯中罗纳尔多廖睿辞罗纳尔多是罗贯中的独生子，去掉他们2个，树依然连通罗睿辞廖睿辞廖睿辞依然是罗睿辞的独生子，将它们分成一组罗贯中罗纳尔多罗睿辞廖睿辞得到了一个最优解问题的解决含有n个点的连通分量，至少需要(n+1)div 47贪心构造1、若叶子结点是父亲的独生子，则删去它们2个，树依然保持性质2、若父亲结点有2个孩子重复以上步骤直至树为空或者只剩一个结点为止贪心构造1、若叶子结点是父亲的独生子，则删去它们2个，树依然48贪心举例陈峰宏贾 由陈 云王 云贾宝玉贾 云贪心举例陈峰宏贾 由陈 云王 云贾宝玉贾 云49贪心举例陈峰宏贾 由陈 云王 云贾宝玉贾 云贪心举例陈峰宏贾 由陈 云王 云贾宝玉贾 云50贪心举例陈峰宏贾 由陈 云王 云贾宝玉贾 云贪心举例陈峰宏贾 由陈 云王 云贾宝玉贾 云51陈峰宏贾 由陈 云王 云贾宝玉贾 云贪心举例陈峰宏贾 由陈 云王 云贾宝玉贾 云贪心举例52贪心举例陈峰宏贾 由陈 云王 云贾宝玉贾 云贪心举例陈峰宏贾 由陈 云王 云贾宝玉贾 云53贪心举例陈峰宏贾 由陈 云王 云贾宝玉贾 云贪心举例陈峰宏贾 由陈 云王 云贾宝玉贾 云54小结通过无向图到二叉树的转化，将一个复杂的匹配问题用简单贪心解决了建模是一个去粗取精的过程，要尽可能利用对我们有利的信息，而忽略那些与我们目标无关的信息LCA与RMQ问题之间相互转化，就是树形模型与序列模型相互辅助的经典例子希望本例会对同学们今后的解题有所帮助！小结通过无向图到二叉树的转化，将一个复杂的匹配问题用简单贪心55其它数学模型举例其它数学模型举例其它数学模型举例56数学建模课件57数学建模课件58E1E2E3棋棋盘盘多多项项式式E1E2E3棋59数学建模课件60数学建模课件61数学建模课件62AtAt63数学建模课件64另外，我们回到刚才的问题我们可以注意到白格主教和黑格主教是不会互相攻击的所以问题可以化简为白格放i(i=k)个棋子和黑格放k-i个棋子分别处理而且处理方法是一样的。为了直观，我们把白格从棋盘中抽出小方格和棋盘都顺时针旋转45度，再压缩，黑格同样最后都可以化建成左图情况我们希望知道的，就是在这样的一个棋盘上放置i(or k-i)各两两不同行不同列的象有多少种放法另外，我们回到刚才的问题65由于行列关系是相对的，所以行列顺序不重要，所以把宽度小的行放在宽度大的行之上，将图转换成这样的情况。然后，我们就可以继续编写算法来把这种有序的图形递归化简，然后利用棋盘多项式的规则化简最后我们可以从第x的k次方项的系数得知放置k个互不攻击的象的方法数有多少了由于行列关系是相对的，所以行列顺序不重要，所以把宽度小的行放66