活中的数学建模.ppt

数学数学数学数学建模建模建模建模从自然走向理性之路从自然走向理性之路从自然走向理性之路从自然走向理性之路 2/40 【本讲简介本讲简介】数学建模无处不在。在我们的生活中处处可以看到数学建模无处不在。在我们的生活中处处可以看到数学模型的影子，本讲介绍发生在我们身边的几个数学数学模型的影子，本讲介绍发生在我们身边的几个数学建模案例：人行走时步长多大最省力？雨中行走如何使建模案例：人行走时步长多大最省力？雨中行走如何使淋雨量最小？道路越多越通畅吗？有奖销售时的抽奖策淋雨量最小？道路越多越通畅吗？有奖销售时的抽奖策略问题，略问题，“非诚勿扰非诚勿扰”女生的最佳选择女生的最佳选择,网络文章流行网络文章流行度预测度预测,招聘时的稳定匹配等。招聘时的稳定匹配等。3/40 行走行走步长问题步长问题 问题问题 人在匀速行走时步长多大最省劲？人在匀速行走时步长多大最省劲？设设人的体重为人的体重为M，腿重，腿重为为 m，腿长，腿长为为 l，速度为，速度为v（固定），（固定），单位时间步数单位时间步数为为 n，步长，步长为为 x（v=nx）。4/405/40 考虑人考虑人行走行走时所消耗的能量的两个部分：时所消耗的能量的两个部分：一部分一部分抬高抬高人体重心人体重心，转化为势能，另一部分转化为两，转化为势能，另一部分转化为两腿转腿转动的动能动的动能 （全身（全身运动运动的平动的平动能是常数，与步长无关，能是常数，与步长无关，故不考虑）。故不考虑）。下面下面分别计算之。分别计算之。1 1.重心升高所需的能量重心升高所需的能量 记记一步中重心升高为一步中重心升高为，则，则 6/40 7/40 于是于是，单位时间重心升高所需做功为，单位时间重心升高所需做功为 2 2.腿运动腿运动所需的能量所需的能量 将将人行走时腿人行走时腿的运动的运动视为均匀直杆（腿）绕腰部的视为均匀直杆（腿）绕腰部的转动，则在单位时间内所需动能为转动，则在单位时间内所需动能为 8/40其中其中转动惯量转动惯量 ，角速度角速度 ,故故所以人行走时单位所以人行走时单位时间所做的功为时间所做的功为 9/40 令令 解得解得 为检验此结果的合理性，带入具体数值，假定为检验此结果的合理性，带入具体数值，假定 M/m=4，l=1 米米 ,g=9.89.8米米/秒秒2 2 ,v=1.5=1.5米米/秒秒计算得到计算得到 n=5.45.4步步/秒秒 x=0.28 0.28米米结果与实际情形差异太大结果与实际情形差异太大!10/40 有有人人将将腿腿的的转转动动改改为为脚脚的的直直线线运运动动，且且将将腿腿的的质质量量全全部部算算在在脚脚上上，这这样样得得到到的的结结果果大大约约是是每每秒秒步步，是是否否合理？合理？建建模模小小结结：本本问问题题的的关关键键点点在在于于腿腿部部运运动动的的合合理理描描述述，模型改进的方向来自于对结果的细致分析。模型改进的方向来自于对结果的细致分析。11/40 雨雨中行走问题中行走问题 问题问题 考虑人在雨中沿一直线行走，雨速已知，问人考虑人在雨中沿一直线行走，雨速已知，问人行走行走的速度多大才能使淋雨量最小？的速度多大才能使淋雨量最小？单位时间淋雨量最小：单位时间淋雨量最小：雨从头顶上落下。雨从头顶上落下。但这样做要付出时间代价，值不值就要看具体降雨量但这样做要付出时间代价，值不值就要看具体降雨量情况与风的情况而定了。情况与风的情况而定了。淋雨量单位时间淋雨量淋雨量单位时间淋雨量淋雨时间淋雨时间跑得越快淋雨量越小？跑得越快淋雨量越小？12/40 设设人行走速度人行走速度(U,0,0)(U0)(U,0,0)(U0)，雨速雨速(Vx,Vy,Vz)(Vx,Vy,Vz)，行走距离为，行走距离为S S，将人视为长方体，前、侧、顶的将人视为长方体，前、侧、顶的面积之比为面积之比为1:L:T1:L:T。13/40单位时间淋雨量单位时间淋雨量为为 C|C|U-Vx|,|0-Vy|,|0-Vz|1,L,T U-Vx|,|0-Vy|,|0-Vz|1,L,T C C（|U-Vx|+|Vy|L+|Vz|T U-Vx|+|Vy|L+|Vz|T）C C（|U-Vx|+A U-Vx|+A）(其中其中A=|Vy|L+|Vz|T)A=|Vy|L+|Vz|T)总淋雨量为总淋雨量为 R(U)=S/UC(|U-Vx|+A)R(U)=S/UC(|U-Vx|+A)为简便计，考虑为简便计，考虑 R(U)=S/U(|U-Vx|+A)R(U)=S/U(|U-Vx|+A)14/40 因此，雨中行走问题抽象成数学问题：因此，雨中行走问题抽象成数学问题：已知已知S,Vx,A,S,Vx,A,求求U U为何值时为何值时R(U)R(U)达最小值？达最小值？下面下面分几种情况讨论。分几种情况讨论。（1 1）Vx 0 Vx 0 Vx 0 时（即风从背面吹来）时（即风从背面吹来）16/40 结论结论 当当 A Vx 时，取时，取 U=Vx ，其他情况下，其他情况下，U应尽可能大。应尽可能大。建模小结：决定淋雨量大小有两个因素：淋雨时间建模小结：决定淋雨量大小有两个因素：淋雨时间及单位时间淋雨量及单位时间淋雨量,忽略后者将导致错误结论。忽略后者将导致错误结论。17/40 道路越多越通畅吗？道路越多越通畅吗？18/40布雷斯悖论布雷斯悖论(Braesss paradox)Braesss paradox)19/40 数学家研究结论：如果一个交通网络上每一条路的数学家研究结论：如果一个交通网络上每一条路的通行时间都与这条路上的车子数量成线性关系，这个交通行时间都与这条路上的车子数量成线性关系，这个交通网络就一定存在一个纳什均衡点。它可能导致全体不通网络就一定存在一个纳什均衡点。它可能导致全体不利的情况发生，即出现布雷斯悖论现象。利的情况发生，即出现布雷斯悖论现象。真实案例真实案例1 1：德国：德国,斯图加特市斯图加特市,1969,1969 年。年。真实案例真实案例2 2：美国，纽约，：美国，纽约，19901990年世界地球日。年世界地球日。真实案例真实案例3 3：韩国，清溪川。：韩国，清溪川。20/40 某人某人可获得一笔奖金可获得一笔奖金 x,x由他在区间由他在区间0,10,1中任中任意地抽取。如果他满意，可以领取意地抽取。如果他满意，可以领取 x 奖金而不再抽取；奖金而不再抽取；如果他不满意，可以放弃这个如果他不满意，可以放弃这个 x而重新抽取。这个抽而重新抽取。这个抽取过程可重复取过程可重复3 3 次次 ,第三次抽取后不得放弃。第三次抽取后不得放弃。问他问他应该采取何种策略以期获得最多奖金？应该采取何种策略以期获得最多奖金？有奖销售抽奖策略有奖销售抽奖策略21/40 设该抽奖人设该抽奖人采取的策略为：采取的策略为：其中其中 X1,X2,X3均为在均为在0,10,1上均匀分布的随机变上均匀分布的随机变量。该人目标为获得的量。该人目标为获得的奖金奖金H的的期望期望达最大值。达最大值。22/40 计算期望：令计算期望：令则则H=g(X1,X2,X3),根据期望计算公式有根据期望计算公式有23/40 以下我们换一种方法计算获利期望。以下我们换一种方法计算获利期望。条件期望方法条件期望方法 第一次抽奖的获奖期望为第一次抽奖的获奖期望为 第二次抽奖的获奖期望为第二次抽奖的获奖期望为 24/40 第三次抽奖的获奖期望为第三次抽奖的获奖期望为 所以所以 25/40 令令 解解得：得：a=a=5/8,5/8,b b=1/2=1/2 最大期望奖金为最大期望奖金为：最优停止问题，例如最优停止问题，例如“不可召回的秘书招聘问题不可召回的秘书招聘问题”。26/40非诚勿扰非诚勿扰女生女生的的”最最优选优选择择”总共面试总共面试n人，不选择前人，不选择前k人，从第人，从第k+1+1人起，一人起，一旦有比前面更优秀的男生，则选择。旦有比前面更优秀的男生，则选择。策策略略 如何确定如何确定K K，使选到最中意男生的概率最大？，使选到最中意男生的概率最大？对于对于某个固定的某个固定的 k，能选到最佳，能选到最佳男生的总男生的总概率为：概率为：27/40 1/1/e 大约大约等于等于37%37%，即，即k/n37%37%3737%法则！法则！按此策略，找到最中意男生的概率也是按此策略，找到最中意男生的概率也是37%37%！用用 x 来表示来表示 k/n 的值，并且假设的值，并且假设 n 充分大，则上述充分大，则上述公式公式可以近似表示为积分形式：可以近似表示为积分形式：建模小结：生活中处处有数学建模的身影。建模小结：生活中处处有数学建模的身影。28/40【问题问题】“如何在一篇文章被发出前就判断它会否流行如何在一篇文章被发出前就判断它会否流行”The Pulse of News in Social Media:Forecasting Popularity【基本思路基本思路】l确定文章内容的关键因素。确定文章内容的关键因素。l统计这些关键因素取不同值时对文章流行度的影响，并将各取值统计这些关键因素取不同值时对文章流行度的影响，并将各取值赋以不同分值。赋以不同分值。l利用统计方法建立并优化利用统计方法建立并优化“内容关键因素内容关键因素”对对“流行度流行度”影响程影响程度的数值模型。度的数值模型。l利用模型预测某篇文章在推特上的流行度。利用模型预测某篇文章在推特上的流行度。网络文章流行度预测网络文章流行度预测29/404 4个判断的关键要素：个判断的关键要素：1 1、信息类别、信息类别30/402 2、客观程度、客观程度 用软件判断样本标题及摘要的客观程度，并为其设定分用软件判断样本标题及摘要的客观程度，并为其设定分值值 0 0 或者或者 1 1。3 3、提及的人物和地名、提及的人物和地名4 4、新闻来源、新闻来源31/40 预测模型：预测模型：其中：其中：T T流行度（t-density）S信息来源的 t-density 分值C信息类别的 t-density 分值Ent max 文中提及的人名或地名中的最大t-density值 结论结论：来自可靠的信息源、提及名人并且谈论流行话题建模启示：对建立评价类模型具有典型意义。建模启示：对建立评价类模型具有典型意义。32/40 假设在一个假设在一个n n男男n n女的联谊会上配对跳舞，每个人都女的联谊会上配对跳舞，每个人都按自己的喜好程度对所有异性排一个顺序，没有并列，按自己的喜好程度对所有异性排一个顺序，没有并列，例如：例如：【问题问题】是否存在一个稳定的配对？是否存在一个稳定的配对？如果存在，是否唯一？如何求？如果存在，是否唯一？如何求？稳定匹配问题及算法稳定匹配问题及算法ABCDwxxyxzwxywyzzyzwwxyzDBDCCACBADBABCAD33/40 稳定匹配稳定匹配（Stable matching）：每个人当前的每个人当前的配对对象恰好是他（她）在当前现实中的最优选择。配对对象恰好是他（她）在当前现实中的最优选择。不稳定匹配不稳定匹配：存在这样的一个男生和一个女生，他：存在这样的一个男生和一个女生，他们都认为对方比自己当前的配对对象更优。们都认为对方比自己当前的配对对象更优。ABCDwxxyxzwxywyzzyzwwxyzDBDCCACBADBABCAD(A,(A,w w),(B,x),(),(B,x),(C C,y y),(D,),(D,z z)(A,z),(B,x),(C,w),(D,y)(A,z),(B,x),(C,w),(D,y)34/40罗伊德罗伊德沙普利沙普利(Lloyd Shapley)(Lloyd Shapley)美国著名数学家和经济学家美国著名数学家和经济学家20122012年因在稳定配对和市场年因在稳定配对和市场设计方面的贡献获诺贝尔经设计方面的贡献获诺贝尔经济学奖济学奖1923年年6月月2日日35/40 Gale-Shapley算法：算法：第一轮：每位男生向各自最中意的女生发出邀请，第一轮：每位男生向各自最中意的女生发出邀请，然后每个女生在向其发出邀请的男生中选择自己最中意然后每个女生在向其发出邀请的男生中选择自己最中意的；的；第二轮，尚未配对的男生向其第二喜欢的女生（不第二轮，尚未配对的男生向其第二喜欢的女生（不管该女生是否已配对）发出邀请，然后每个女生在向其管该女生是否已配对）发出邀请，然后每个女生在向其发出邀请的男生以及上一轮已选择的男生中选择一个最发出邀请的男生以及上一轮已选择的男生中选择一个最中意的；中意的；第三轮，第三轮，36/40第一轮：第一轮：(A,w)(B,x)(C,x)(D,y),x(A,w)(B,x)(C,x)(D,y),x拒绝拒绝C C第二轮：第二轮：(A,w)(B,x)(C,w)(D,y),w(A,w)(B,x)(C,w)(D,y),w拒绝拒绝A A第三轮：第三轮：(A,x)(B,x)(C,w)(D,y),x(A,x)(B,x)(C,w)(D,y),x拒绝拒绝A A第四轮：第四轮：(A,y)(B,x)(C,w)(D,y),y(A,y)(B,x)(C,w)(D,y),y拒绝拒绝A A第五轮：第五轮：(A,z)(B,x)(C,w)(D,y)(A,z)(B,x)(C,w)(D,y)ABCDwxxyxzwxywyzzyzwwxyzDBDCCACBADBABCAD37/40几个问题：几个问题：1 1、算法是否能在有限步结束？、算法是否能在有限步结束？是的。由于每一个男生最多发出是的。由于每一个男生最多发出n n次邀请，必然能够邀次邀请，必然能够邀请到女生，所以算法在有限轮后会结束。请到女生，所以算法在有限轮后会结束。2 2、选择先后对双方是否有区别？、选择先后对双方是否有区别？是的。对先选的一方有利。是的。对先选的一方有利。3 3、稳定配对是否唯一？、稳定配对是否唯一？未必。见上面例子。未必。见上面例子。4 4、算法得到的配对是否稳定？算法得到的配对是否稳定？是的。是的。ABCDwxwyxyyxyzzwzwxzwxyzAABDBCACCBDBDDCA38/405 5、算法在多对一时（例如：企业与求职者，研究生导师、算法在多对一时（例如：企业与求职者，研究生导师与研究生等）是否有效？与研究生等）是否有效？是的。是的。6 6、算法是否能够预防欺诈行为得逞？、算法是否能够预防欺诈行为得逞？否。否。思考题：思考题：2 2n n个男生分宿舍，每间宿舍住两人，每个人对其他人成个男生分宿舍，每间宿舍住两人，每个人对其他人成为自己的舍友有一个优先排序，能否应用为自己的舍友有一个优先排序，能否应用ShapleyShapley算法算法求稳定匹配？为什么？求稳定匹配？为什么？39/402.12.1、建立更合理的模型，改进、建立更合理的模型，改进“行走步长问题行走步长问题”模型。模型。2.22.2、教材、教材 P37 P37 第第3 3题。题。作业：作业：数学数学数学数学建模建模建模建模从自然走向理性之路从自然走向理性之路从自然走向理性之路从自然走向理性之路