建模部分专题.ppt

1、贵州民族学院数学与计算科学系索洪敏,数学建模方法及部分专题,玩具、照片,实物模型,风洞中的飞机,物理模型,地图、电路图,符号模型,模型是为了一定目的，对客观事物的一部分进行简缩、抽象、提炼出来的原型的替代物。,模型集中反映了原型中人们需要的那一部分特征。,我们常见的模型,什么是数学模型,如何建立数学模型,你碰到过的数学模型“航行问题”,用x表示船速，y表示水速，列出方程：,求解得到x=20,y=5,答：船速每小时20公里,航行问题建立数学模型的基本步骤,作出简化假设（船速、水速为常数）；,用符号表示有关量（x,y表示船速和水速）；,用物理定律（匀速运动的距离等于速度乘以时间）列出数学式子（二元

2、一次方程）；,求解得到数学解答（x=20,y=5）；,回答原问题（船速每小时20公里）。,数学模型(MathematicalModel)和数学建模（MathematicalModeling),数学模型:对于一个现实对象，为了一个特定目的，根据其内在规律，作出必要的简化假设，运用适当的数学工具，得到的一个数学结构。,数学建模：建立数学模型的全过程（包括建立、求解、分析、检验）。,数学建模的重要意义,电子计算机的出现及飞速发展,数学以空前的广度和深度向一切领域渗透，,数学建模作为用数学方法解决实际问题的第一步，越来越受到人们的重视。,数学建模,计算机技术,知识经济,建模示例商人们怎样安全过河,问题

3、(智力游戏),随从们密约,在河的任一岸,一旦随从的人数比商人多,就杀人越货.,但是乘船渡河的方案由商人决定.商人们怎样才能安全过河?,问题分析,多步决策过程,决策每一步(此岸到彼岸或彼岸到此岸)船上的人员,要求在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河,模型构成,xk第k次渡河前此岸的商人数,yk第k次渡河前此岸的随从数,xk,yk=0,1,2,3;k=1,2,sk=(xk,yk)过程的状态,S=(x,y)x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2,S允许状态集合,uk第k次渡船上的商人数,vk第k次渡船上的随从数,dk=(uk,vk)决策,D

4、=(u,v)u+v=1,2允许决策集合,uk,vk=0,1,2;k=1,2,sk+1=skdk,+(-1)k,状态转移律,求dkD(k=1,2,n),使skS按转移律由s1=(3,3)到达sn+1=(0,0).,多步决策问题,模型求解,穷举法编程上机,图解法,状态s=(x,y)16个格点,允许决策D移动1或2格;k奇,左下移;k偶,右上移.,s1,sn+1,d1,d11给出安全渡河方案,评注和思考,规格化方法,易于推广,考虑4名商人各带一随从的情况,允许状态S,S=(x,y)x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2,D=(u,v)u+v=1,2,基本方法,机理分析

5、,测试分析,根据对客观事物特性的认识，找出反映内部机理的数量规律,将研究对象看作“黑箱”,通过对量测数据的统计分析，找出与数据拟合最好的模型,机理分析没有统一的方法，主要通过实例研究(CaseStudies)来学习。以下建模主要指机理分析,二者结合,机理分析建立模型结构,测试分析确定模型参数,数学建模的方法和步骤,数学建模的一般步骤,怎样学习数学建模,数学建模与其说是一门技术，不如说是一门艺术,技术大致有章可循,艺术无法归纳成普遍适用的准则,想象力,洞察力,判断力,学习、分析、评价、改进别人作过的模型,亲自动手，认真作几个实际题目,创新意识,录象机计数器的用途,问题,经试验，一盘录象带从头走到

6、尾，时间用了183分30秒，计数器读数从0000变到6152。,在一次使用中录象带已经转过大半，计数器读数为4580，问剩下的一段还能否录下1小时的节目？,要求,不仅回答问题，而且建立计数器读数与录象带转过时间的关系。,初等模型例子,问题分析,录象机计数器的工作原理,录象带运动,观察,计数器读数增长越来越慢！,模型假设,录象带的运动速度是常数v；,计数器读数n与右轮转数m成正比，记m=kn；,录象带厚度（加两圈间空隙）为常数w；,空右轮盘半径记作r；,时间t=0时读数n=0.,建模目的,建立时间t与读数n之间的关系,（设V，k，w，r为已知参数）,模型建立,建立t与n的函数关系有多种方法,1.

7、右轮盘转第i圈的半径为r+wi,m圈的总长度等于录象带在时间t内移动的长度vt,所以,模型建立,2.考察右轮盘面积的变化，等于录象带厚度乘以转过的长度，即,3.考察t到t+dt录象带在右轮盘缠绕的长度，有,思考,1.3种建模方法得到同一结果,但仔细推算会发现稍有差别，请解释。,2.模型中有待定参数,确定参数的一种办法是测量或调查，试设计测量方法。,参数估计,确定参数的另一种方法测试分析,将模型改记作,只需估计,理论上，已知t=183.5,n=6152,再有一组(t,n)数据即可；,实际上，由于测试有误差，最好用足够多的数据作拟合。,现有一批测试数据：,用最小二乘法可得,模型检验,应该另外测试一

8、批数据检验模型：,模型应用,1.回答提出的问题：由模型算得n=4580时t=118.5分，剩下的录象带能录183.5-118.5=65分钟的节目。,2.揭示了“t与n之间呈二次函数关系”这一普遍规律，当录象带的状态改变时，只需重新估计a,b即可。,存贮模型,某厂生产若干种产品。轮换生产时因更换设备要付准备费;产量大于需求时因积压资金要付贮存费。,今已知某产品的日需求量为100件，生产准备费5000元，贮存费每日每件1元。试安排该产品的生产计划，即多少天生产一次(生产周期)，每次产量多少，使总费用最小。设该厂生产能力非常大，即所需数量可在很短时间内产出。,不只是回答问题，而且要建立生产周期、产量

9、与需求量、准备费、贮存费之间的关系。,问题,要求,微分法建模,问题分析与思考,每天生产一次，每次100件，无贮存费，准备费5000元，故每天费用为5000元。,日需求100件，生产准备费5000元，贮存费每日每件1元。,10天生产一次，每次1000件，贮存费900+800+100=4500元，准备费5000元，总计9500元。,50天生产一次，每次5000件，贮存费4900+4800+100=122500元，准备费5000元，总计127500元。,平均每天费用为950元,平均每天费用为2550元,这是一个优化问题，关键在建立目标函数。,显然不能用一个周期的总费用作为目标函数,目标函数每天总费用

10、的平均值,周期短，产量小,周期长，产量大,模型假设,1.产品每天的需求量为常数r；,2.每次生产准备费为c1,每天每件产品贮存费为c2；,3.T天生产一次(周期为T),每次生产Q件，且当贮存量降到零时，Q件产品立即生产出来(生产时间不计)；,建模目的,设r,c1,c2已知，求T,Q,使每天总费用的平均值最小。,4.为方便起见，时间和产量都作为连续量处理。,模型建立,将贮存量表示为时间的函数q(t),t=0生产Q件，贮存量q(0)=Q,q(t)以需求r的速率递减，直到q(T)=0.,一周期总费用,每天总费用平均值（目标函数）,离散问题连续化,一周期贮存费,A,模型求解,求T使,模型分析,模型应用

11、,c1=5000(元),c2=1(元/天件),r=100(件/天）,回答问题,经济批量订货公式（EOQ公式）,每天需求量r，每次订货费为c1,每天每件贮存费为c2，T天订货一次(周期T),每次订货Q件，且当贮存量降到零时，Q件立即到货。,用于订货、供应、存贮情形,不允许缺货的存贮模型,允许缺货的存贮模型,A,B,当贮存量降到零时仍有需求r,出现缺货，造成损失,原模型假设：贮存量降到零时Q件立即生产出来(或立即到货),现假设：允许缺货,每天每件缺货损失费c3,缺货需补足,一周期贮存费,一周期缺货费,周期T,t=T1贮存量降到零,一周期总费用,每天总费用平均值（目标函数）,一周期总费用,求T,Q使

12、,为与不允许缺货的存贮模型相比，T记作T,Q记作Q,不允许缺货模型,记,允许缺货模型,允许缺货模型,注意：缺货需补足,Q是每周期初的存贮量,每周期的生产量（或订货量）为,Q不允许缺货时的产量(或订货量),例：一鞋店平均每天卖出鞋110双，批发手续费每次200元，每双鞋存储一天的保管费为0.01元。问该商店多少天批发一次最好，进货量为多少？,本例中，R=100，C1=200，C2=0.01,于是最优进货周期,线性规划模型,在许多领域中，常常会遇到对有限的资源（如人力、财力、物力）如何合理安排，使预期目标达到最优。这类问题大都可以建立线性规划模型，并利用已有的算法和计算机软件得到解答。线性规划理论

13、是运筹学的理论分支中是最完善的，它已成为现代科学管理的一种重要方法和手段。,先看一个例子：,例：某小型工厂要安排甲、乙两种产品的生产。已知生产甲、乙两种产品每吨所需的原材料A、B、C数量如下：,原材料A,原材料B40160,原材料C25200,甲,乙,资源数量,1,1,50,甲、乙两种产品每吨利润分别为300元和200元。试问应如何安排生产可获得最大利润？,建立线性规划模型的步骤如同建立一般数学模型，有“问题的归结”、“假设”、“建立模型”、“模型求解”、“讨论与验证”几个过程。建立线性规划模型有三个特殊的过程：第一，设立决策变量。上例中设甲、乙两种产品分别生产x和y吨。第二，明确决策目标。利

14、润函数Z=3x+2y，即是要求它的最大值。第三，寻找限制条件：,还再加上变量x,y满足非负限制，即,这样该模型可归结为：,一般的线性规划模型：,求解线性规划问题一般有：图解法（二元）、单纯形法等。现在已有大型软件能很精确的求解更复杂的规划问题。,线性规划问题的图解法,用图解法求解：,解：1.作出可行解区域，并求出顶点。O（0，0），A（40，0），B（40，10），C（50/3，100/3），D（0，40）。,O,x,y,A,B,C,D,2x+5y=200,2.作出函数的等值线：z=3x+2y.即可得解为：B（40，10）,与线性规划类似但特殊的规划问题：如整数规划、0-1规划、运输问题等等，

15、这些都是实际运用相当广泛又有很成熟的算法的一类问题。,图论建模,1、思想图是由平面上的一些点及这些点之间的连线（称为边）构成的。用点表示要研究的离散对象，用边表示对象之间的关系来建立模型，并且用图的性质和算法求解模型，它是研究离散问题的重要手段。主要研究：图的连通、覆盖、色数、同构、有向图、邻接等。图论与网络分析中的典型的模型有：最小生成树、最短路、最大流、最小费用最大流、匹配模型等。一个图代表了某些对象集合之间的关系，而图论是主要研究这些对象在上述表示法中的许多可能的性质中的某些性质。,哥尼斯堡七桥问题,在离普格尔河入海口不远的地方，有一座古老的城市-哥尼斯堡，普格尔河的两条支流在这里汇成一

16、股，奔向蓝色的波罗的海，河心小岛矗立着著名的哥尼斯堡大教堂，整个城市被河水分隔成4块。于是修造了7座各具特色的桥。于是有人提出了：谁能够找出一条路线，经过所有这7座桥而每座桥都只经过一次最后返回出发地？,1736年，Euler用图论方法完美的解决了该问题。从而开创了图论的先河。他把该问题转化为一笔画的问题。他发现凡是能用一笔画出的图形，都有这样一个特点：每当你用笔画出一条线进入中间的一个点时，你还必须画一条线离开这个点。否则整个图形就不可能用一笔画出。于是任何一点顶点必与偶数条边相连。,中国邮路问题,邮递员从邮局中取出邮件，递送到不同地点，然后再返回邮局。假设要求他至少一次走过他投递范围内的每

17、条街道，我们希望选出一条尽可能短的路线。这个问题称为中国邮递员问题，是我国数学家管梅谷最先研究的。,3,2,4,2,1,A,B,C,D,图G,在邮递员服务范围的街道图上标明各条街的路长，就构成一连通赋权图G。,若G无奇次顶点，G就是欧拉图，因每边仅过一次，故总权是最小的。若G有奇次顶点，则它就不是欧拉图，然而要求是每边至少经过一次，但并未限制只许一次，故可在这些奇次顶点上添加一些与原图的边相重复的边，使这些奇次顶点成为偶次顶点，从而得到一个将重复边看成是另一条新边的欧拉图。问题是怎么加使总权最小？,人、狼、羊、菜渡河问题,一个摆渡人F希望用一条小船把一只狼W、一头羊S和一篮白菜V从一条河的左岸渡到右岸去，而船小只能容纳F、W、S、V中的两个，绝不能在无人看守的情况下，留下狼和羊在一起，羊和白菜在一起，应怎么渡河才能将狼、羊、白菜都运过河去？,在研究状态或位置发生变更的问题时，常构造有向图来解决。,首先对两岸上允许的组合加以分类，比如用（FWS/V）表示F、W和S在左岸上，而V在右岸上。O意味着在相应的岸上均无。,将