《2011数学建模讲座计算机模拟》由会员分享，可在线阅读，更多相关《2011数学建模讲座计算机模拟（45页珍藏版）》请在金锄头文库上搜索。
1、2011 数学建模讲座,计算机模拟,主讲: 曹敦虔,2011-4-19,主要内容,计算机模拟概述 数学软件简介 建模竞赛使用软件情况 示例1 背包问题 示例2蒙特卡罗法 示例3钻井布局,计算机模拟概述,利用计算机来模拟系统的运行， 称为计算机模拟。 模拟分为静态模拟和动态模拟。 蒙特卡罗法就是典型的静态模拟。 动态模拟可分为连续系统模拟和离散事件系统模拟。,计算机模拟概述,连续系统模拟研究系统的状态随时间连续变化的情形。其模型一般为微分方程模型。 离散系统模拟讨论的是系统状态只在一些离散时间点上变化的情形。 模拟时间推进方式有两种：下次事件推进法和下个时刻推进法。,计算机模拟概述,模拟过程通常
2、是： 初始化系统状态。 进入下一时刻（事件），并按照系统演变规则计算当前状态。 重复（2）直到满足某个终止条件为止。,计算机模拟概述,使用计算机模拟能有效解决问题： 难以用数学公式表示或求解的系统 虽然可以用数学公式表示和求解但过程过于复杂的系统 某些参数对系统行为的影响难以直接判断, 需要使用计算机进行模拟的情形 难以在实际环境中进行实验的观察的情形 如需大量重复、高成本以及含随机过程等类型的实验,计算机模拟概述,计算机模拟环境 使用专门的模拟软件 使用高级程序设计语言编程 使用数学软件编程,数学软件简介,现在的计算机不仅可以进行数值计算，还可以进行符号运算。 数值计算就是处理的数据和处理后
3、的结果都是数值 符号计算则是处理的数据和处理后的结果都是符号。所谓符号，可以是字母、公式，也可以是数字。符号计算实际上就是数学演算、数学推理和数学证明。 专门用来完成这些演算、推理和证明的软件，通常称为数学软件。由于这类软件的功能覆盖了数学中相当广泛的领域，所以又称为通用数学软件。,数学软件简介,当今比较成熟的通用数学软件有Matlab、Maple和Mathematica。 Matlab主要是进行矩阵的运算，具有很强的数值运算能力； Maple和Mathematica则擅长符号运算，例如公式的推导、变形、方程的符号解、微积分运算等等； 它们各有自己的优点，并列为三大数学软件。,数学软件简介,另
4、外还有一些软件只用于求解数学中某一领域的问题，这类软件称为专用数学软件，如Lindo(线性规划), Lingo(非线性规划), Spss(统计)，Sas (统计)等.,数学建模竞赛现状,现在数学建模竞赛主要表现为数据量大，模型复杂，求解困难等特点，使用手工求解是不可能，必须借助于计算机和数学软件来处理数据和求解模型 通常需要使用多个软件来完成各个步骤的运算。如使用Excel处理数据，Maple推导公式，Matlab计算中间结果，Lingo求解最终模型,历年建模使用软件情况,历年建模使用软件情况,例1 背包问题,设有一个容积为S、最大承重量为G的背包，有k种物品，它们的体积、重量、数量和使用价值
5、分别为si、gi、ni、wi，i=1,2,k，问题应选择哪些物品装入背包，才能得到最大的使用价值？,建立的数学模型如下,目标函数,约束条件,价值最大化,容积约束,重量约束,数量约束,取值范围约束,取S=50, G=60, k=5, s=(3 4 7 8 9), g=(5 3 6 7 8), n=(3 3 5 4 6), w=(4 5 10 11 13). 在Lindo中输入如下模型： MAX 4X1 +5X2 +10X3 +11X4 +13X5 ST 3X1 +4X2 +7X3+8X4+9X565 5X1 +3X2 +6X3+7X4+8X553 X1 =3 X2 =3 X3 =5 X4 =4
6、X5 =6 END GIN 5,点击求解按纽即可求得最优解,OBJECTIVE FUNCTION VALUE 1) 87.00000 VARIABLE VALUE REDUCED COST X1 0.000000 -4.000000 X2 3.000000 -5.000000 X3 2.000000 -10.000000 X4 0.000000 -11.000000 X5 4.000000 -13.000000,在Lingo中输入如下模型：,model: sets: v5/15/:s,g,n,w,x; endsets data: s=3 4 7 8 9; g=5 3 6 7 8; n=3 3
7、5 4 6; w=4 5 10 11 13; enddata,max=sum(v5:w*x); sum(v5:s*x)=65; sum(v5:g*x)=53; for(v5:x=n); for(v5: GIN( x); End,点击求解按纽即可求得最优解,Objective value: 87.00000 Variable Value Reduced Cost X( 1) 0.000000 -4.000000 X( 2) 1.000000 -5.000000 X( 3) 3.000000 -10.00000 X( 4) 0.000000 -11.00000 X( 5) 4.000000 -13
8、.00000,Maple功能展示,Maple是一款综合型数学软件。由加拿大Waterloo大学符号计算小组于1980年开始研制，经过多年的应用和开发，至今发展到Maple12。由于枫树是加拿大的国树，Maple的开发者为了表示自己的爱国之情，所以把枫叶作为Maple的图标和标志。Maple是一个优秀的国际流行的数学软件系统，它提供了广泛的数学计算功能，可以进行符号计算、数值计算以及图形绘制。,Maple能解决如下问题：,初等数学中的有理数运算（精确计算和大有理数计算），代数式运算，初等函数变换，映射与集合运算，方程求根等。 复数运算，向量代数，平面和空间解析几何，线性代数中矩阵的各种运算和变换
9、，线性方程组求解 微积分中的函数的极限，导数，积分，泰勒级数、傅立叶级数展开，以及数列与级数求和，求积等 微分方程的解析解，数值解以及通过方向场图形得出近似解 图论、数论、群论、组合数学、概率统计、特殊函数（运算微积）以及其他应用数学（如金融数学）,Maple的数字运算 小数精度能力. evalf(Pi,10); evalf(Pi,100); evalf(Pi,1000); 大数运算能力. 10!; 100!; 1000!; ifactor(23353425325435234524352);,Maple的表达式处理 s:=sum(i2,i=1n); s1:=simjplify(s); s2:=
10、factor(s1); Maple求解方程（组） solve(a*x2+b*x+c=0,x); f:=a*x3+b*x2+c*x+d=0; solve(f,x);,微积分运算 limit(sin(x)/x,x=0); diff(sin(x),x); diff(sin(x*y),x); D(sin); int(sin(x),x); int(sin(x),x=0Pi);,Maple作图 二维图形. plot(sin(x),x=-PiPi); 三维图形 plot(x*y,x=-55,y=-55);,示例2 蒙特卡罗法,蒙特卡罗法是指利用计算机模拟随机过程，以频率近似概率的方法。 基本思想是：为了计算
11、某些量，先构造概率模型（如随机过程），利用概率模型的某些数学特征恰好等于所需要计算的量，而这些数学特征又可以通过实验，用统计的方法求出它们的近似值，这样就可以求出所需的量的近似值。,示例2 蒙特卡罗法,近似计算平面区域上某闭区域面积 设某闭区域可以表示为 其中 为闭区间a, b上的连续函数，且满足,示例2 蒙特卡罗法,a,b,f1(x),f2(x),x,y,示例2 蒙特卡罗法,步骤： 使用矩形区域=a,bc,d覆盖，c f1(x), d f2(x). 向中按均匀分布随机投入n个点pi=(xi,yi), i=1,2,n. 统计落入内的点的个数, 记为m. 当n较大时, 的面积,示例2 蒙特卡罗法
12、,a,b,f1(x),f2(x),x,y,示例2 蒙特卡罗法,思考: 如何取c和d? 如何按均匀分布随机投入n个点? 如何统计落入内的点的个数?,求由曲线y=1/x与直线y=x及x=2所围成图形的面积,% 蒙特卡罗法演示 % 计算平面闭区域面积 % 初始化 a=1; b=2; %设置定义域 %闭区域的边界 f1=(x) 1./x; f2=(x) x; c=0; d=2; %设置覆盖矩形 x=linspace(a,b,100); plot(x,f1(x),x,f2(x); %绘出闭区域 hold on %使得后面所绘图形在前面所绘图形的坐标系下 plot(a,b,b,a,a,c,c,d,d,c,
13、r); %绘出覆盖矩形S,% 随机投点 n=100; x=a+(b-a)*rand(1,n); y=c+(d-c)*rand(1,n); plot(x, y, .k); %绘出随机点 hold off % 统计落入闭区域内的点的个数 m=0; for i=1:n if y(i)=f1(x(i) end end S=(b-a)*(d-c)*m/n % 计算近似面积,99创维杯全国大学生数学建模竞赛题目 B题 钻井布局,勘探部门在某地区找矿。初步勘探时期已零散地在若干位置上钻井，取得了地质资料。进入系统勘探时期后，要在一个区域内按纵横等距的网格点来布置井位，进行“撒网式”全面钻探。由于钻一口井的费
14、用很高，如果新设计的井位与原有井位重合（或相当接近），便可利用旧井的地质资料，不必打这口新井。因此，应该尽量利用旧井，少打新井，以节约钻探费用。比如钻一口新井的费用为500万元，利用旧井资料的 费用为10万元，则利用一口旧井就节约费用490万元。,设平面上有n个点Pi，其坐标为(ai,bi),i=1,2,n，表示已有的n个井位。新布置的井位是一个正方形网格N的所有结点(所谓“正方形网格”是指每个格子都是正方形的网格；结点是指纵线和横线的交叉点)。假定每个格子的边长(井位的纵横间距)都是1单位(比如100米)。整个网格是可以在平面上任意移动的。若一个已知点Pi与某个网格结点Xi的距离不超过给定误
15、差(=0.05单位)，则认为Pi处的旧井资料可以利用，不必在结点Xi处打新井。,为进行辅助决策，勘探部门要求我们研究如下问题： 1)假定网格的横向和纵向是固定的(比如东西向和南北向)，并规定两点间的距离为其横向距离(横坐标之差绝对值)及纵向距离(纵坐标之差绝对值)的最大值。在平面上平行移动网格N，使可利用的旧井数尽可能大。试提供数值计算方法，并对下面的数值例子用计算机进行计算。 2)在欧氏距离的误差意义下，考虑网格的横向和纵向不固定(可以旋转)的情形，给出算法及计算结果。 3)如果有n口旧井，给出判定这些井均可利用的条件和算法(你可以任意选定一种距离)。,数值例子n=12个点的坐标如下表所示：,原井位(xi,yi)与点(xi+z1,yi+z2)是等价的, 其中z1 , z2是任意整数。,问题分析,将数据取小数部分后得到的数据及图形,再将满足ai 的点(ai,bi)复制为(1+ai,bi); 满足bi 的点(ai,bi)复制为(ai, 1+bi); 满足ai 且bi 的点(ai,bi)复制为(1+ai, 1+bi);,若存在某个网格的中心O，使得有m个点与O的距离都小于给定的 ，则这m个点就能够同时被利用。 此时，可以看成是这m个点被一个以O为中心为半径的正方形(或圆)覆盖。,这样，问题1就变为下面的问题： 1): 给定n个数据(ai,bi),i=1,2,n.
