《[数学]数学建模竞赛算法讲座》由会员分享，可在线阅读，更多相关《[数学]数学建模竞赛算法讲座（41页珍藏版）》请在金锄头文库上搜索。
1、数学建模竞赛 常用方法,哈尔滨工业大学数学系 王希连,前言,在数学建模竞赛的评卷过程中, 首重摘要, 其次是所建立的数学模型的创新性和正确性, 第三要看求解计算结果的应用结果(是否能够完全回答题目的问题)及强健性(结果的主要优缺点和结果的敏感性分析等), 第四看文章的整体结构和格式表述的规范性, 简洁性, 最后再考评算法的实用性和正确性(只有竞争力较强的文章算法才可能被评委审评), 因此一定不要本末倒置.,一篇mcm官方正式出版的对一份Outstanding论文评审文章中节录的关于评审过程的一段:,广义来看, 算法是指求解一个问题的高效方法, 如等比数列的求和方法, 一元二次方程的求解方法,
2、求一元函数零点的牛顿迭代法, 信号频谱分析中的快速傅立叶变换法, 常微分方程求解的龙格-库塔法等等, 目前特指所有利用计算机程序求解问题的各种有效算法 在数学建模中, 针对各种各样的问题, 人们已经建立了各种算法,特别是很多问题的优秀算法都已经商业化了成熟的软件包, 使用者只要根据相应软件的语法要求正确地描述问题,然后运行程序即可得到结果,而不需要关心算法的具体原理和数据结构的组织安排和计算精度及收敛性的控制等, 如数据的统计分析、相关分析、回归分析、聚类分析、数据简化、生存分析、时间序列分析、多重响应等数据处理和挖掘工作可以用SAS或SPSS软件进行求解分析; 曲线拟合与插值,常微分方程和偏
3、微分方程的求解等数值求解问题可以使用Matlab完成, 线性规划、非线性规划、整数规划问题可以用lingo软件求解等,算法概述,蒙特卡洛(Monte-Carlo)算法,蒙特卡罗方法又称随机抽样技巧或统计试验方法，与一般数值计算方法有很大区别。它是以概率统计理论为基础的一种方法。 当所求问题的解是某个事件的概率，或者是某个随机变量的数学期望，或者是与之有关的量时，通过某种试验的方法，得出该事件发生的频率，再通过它得到问题的解。这就是蒙特卡罗方法的基本思想。 基本示例: 圆周率的计算,蒙特卡罗投点法(蒲丰投针实验的推广)： 在一个边长为a的正方形内随机投点， 该点落在此正方形的内切圆中的概率 应为
4、该内切圆与正方形的面积比值， 即 n=10000; a=2; m=0; for i=1:n x=rand(1)*a; y=rand(1)*a; if ( (x-a/2)2+(y-a/2)2 = (a/2)2 ) m=m+1; end end disp(投点法近似计算的为: ,num2str(4*m/n);,o,(a/2,a/2),蒙特卡罗方法的关键步骤在于随机数的产生，计算机产生的随机数都不是真正的随机数(由算法确定的缘故)，如果伪随机数能够通过一系列统计检验，我们也可以将其当作真正的随机数使用。 rand(state,sum(100*clock)*rand); rand(1) %重新启动ma
5、tlab时，输出的随机数不一样 常用Matlab随机数生成方法: 1rand() 生成（0,1）区间上均匀分布的随机变量。基本语法： rand(M,N,P .) 生成排列成M*N*P. 多维向量的随机数。如果只写M，则生成M*M矩阵；如果参数为M,N可以省略掉方括号,2randn() 生成服从标准正态分布（均值为0，方差为1）的随机数。基本语法和rand()类似。randn(M,N,P .) 生成排列成M*N*P. 多维向量的随机数。如果只写M，则生成M*M矩阵；如果参数为M,N可以省略掉方括号 3unifrnd() 和rand()类似，这个函数生成某个区间内均匀分布的随机数。基本语法 uni
6、frnd(a,b,M,N,P,.) 4normrnd() 和randn()类似，此函数生成指定均值、标准差的正态分布的随机数。基本语法normrnd(mu,sigma,M,N,P,.) 生成的随机数服从均值为mu，标准差为sigma（注意标准差是正数）正态分布，,5chi2rnd() 此函数生成服从卡方（Chi-square)分布的随机数。卡方分布只有一个参数：自由度v。基本语法 chi2rnd(v,M,N,P,.) 生成的随机数服从自由度为v的卡方分布，这些随机数排列成M*N*P. 多维向量 6frnd() 此函数生成服从F分布的随机数。F分布有2个参数：v1, v2。基本语法 frnd(v
7、1,v2,M,N,P,.) 生成的随机数服从参数为(v1,v2)的卡方分布 7trnd() 此函数生成服从t(Students t Distribution，这里是Cosset.W.S.的笔名)分布的随机数。t分布有1个参数：自由度v。基本语法trnd(v,M,N,P,.) 生成的随机数服从参数为v的t分布,8betarnd() 此函数生成服从Beta分布的随机数。Beta分布有两个参数分别是A和B。生成beta分布随机数的语法是： betarnd(A,B,M,N,P,.) 9exprnd() 此函数生成服从指数分布的随机数。指数分布只有一个参数: mu, 生成指数分布随机数的语法是： bet
8、arnd(mu,M,N,P,.) 10gamrnd() 生成服从Gamma分布的随机数。Gamma分布有两个参数：A和B。 生成Gamma分布随机数的语法是： gamrnd(A,B,M,N,P,.),11lognrnd() 生成服从对数正态分布的随机数。其有两个参数：mu和sigma，服从这个这样的随机数取对数后就服从均值为mu，标准差为sigma的正态分布。 lognrnd(mu,sigma,M,N,P,.) 12raylrnd() 生成服从瑞利（Rayleigh）分布的随机数。其分布有1个参数：B。 raylrnd(B,M,N,P,.) 13wblrnd() 生成服从威布尔（Weibull
9、）分布的随机数。其分布有2个参数：scale 参数 A和shape 参数 B。 wblrnd(A,B,M,N,P,.),14unidrnd() 生成服从离散均匀分布的随机数。Unifrnd是在某个区间内均匀选取实数（可为小数或整数），Unidrnd是均匀选取整数随机数。离散均匀分布随机数有1个参数：n, 表示从1, 2, 3, . N这n个整数中以相同的概率抽样。基本语法：unidrnd(n,M,N,P,.) 15. binornd() 生成服从二项分布的随机数。二项分布有2个参数：n,p。考虑一个打靶的例子，每枪命中率为p，共射击N枪，那么一共击中的次数就服从参数为（N,p）的二项分布。注意
10、p要小于等于1且非负，N要为整数。基本语法：binornd(n,p,M,N,P,.),16. geornd() 生成服从几何分布的随机数。几何分布的参数只有一个：p。几何分布的现实意义可以解释为，打靶命中率为p，不断地打靶，直到第一次命中目标时没有击中次数之和。注意p是概率，所以要小于等于1且非负。 基本语法：geornd(p,M,N,P,.) 17poissrnd() 生成服从泊松(Poisson)分布的随机数。泊松分布的参数只有一个：lambda。此参数要大于零。 基本语法：poissrnd (lambda,M,N,P,.) 附: 概率分布函数(Probability Distributi
11、on Function)直方图绘制语句: hist,例1 掷两枚不均匀硬币，每枚正面出现概率为批p，记录前mm次掷硬币试验中两枚都为正面频率的波动情况，并画图。 function test1(p,mm) pro=zeros(1,mm); randnum = binornd(1,p,2,mm)；a=0; for i=1:mm a=a+randnum(1,i)*randnum(2,i); pro(i)=a/i; end num=1:mm;plot(num,pro),例2 两盒火柴，每盒n根。每次随机在任一盒中取出一根火柴。问其中一盒中火柴被取完而另一盒中至少还有k根火柴的概率有多大？（用频率估计概
12、率） function proguji=test2(n,k,mm) frq=0; randnum=binornd(1,0.5,mm,2*n);proguji=0; for i=1:mm a1=0;a2=0;j=1; while (a1=k , frq=frq+1; end end; proguji=frq/mm,例3 在我方某前沿防守地域，敌人以一个炮排（含两门火炮）为单位对我方进行干扰和破坏为躲避我方打击，敌方对其阵地进行了伪装并经常变换射击地点经过长期观察发现，我方指挥所对敌方目标的指示有50是准确的，而我方火力单位，在指示正确时，有1/3的概率能毁伤敌人一门火炮，有1/6的概率能全部消灭
13、敌人现在希望能用某种方式把我方将要对敌人实施的1次打击结果显现出来，利用频率稳定性，确定有效射击(毁伤一门炮或全部消灭)的概率. 分析：这是一个复杂概率问题，可以通过理论计算得到相应的概率.为了直观地显示我方射击的过程，现采用模拟的方式。,需要模拟出以下两件事： 1 观察所对目标的指示正确与否 模拟试验有两种结果，每一种结果出现的概率都是1/2因此，可用投掷一枚硬币的方式予以确定,当硬币出现正面时为指示正确，反之为不正确 2 当指示正确时，我方火力单位的射击结果情况 模拟试验有三种结果：毁伤一门火炮的可能性为1/3(即2/6)，毁伤两门的可能性为1/6，没能毁伤敌火炮的可能性为1/2(即3/6
14、)这时可用投掷骰子的方法来确定： 如果出现的是、三个点：则认为没能击中敌人； 如果出现的是、点：则认为毁伤敌人一门火炮； 若出现的是点：则认为毁伤敌人两门火炮,i：要模拟的打击次数； k1：没击中敌人火炮的射击总数； k2：击中敌人一门火炮的射击总数； k3：击中敌人两门火炮的射击总数 E：有效射击(毁伤一门炮或两门炮)的概率,符号假设,模拟框图,function test(p, mm) efreq=zeros(1,mm); randnum1 = binornd(1,p,1,mm); randnum2 = unidrnd(6,1,mm);k1=0;k2=0;k3=0; for i=1:mm i
15、f randnum1(i)=0 k1=k1+1; else if randnum2(i)=3 k1=k1+1; elseif randnum2(i)=6 k3=k3+1; else k2=k2+1; end end efreq(i)=(k2+k3)/i; end num=1:mm;plot(num,efreq),蒙特卡洛方法的特点 Monte Carlo方法及其程序结构简单 产生随机数，计算相应的值。即通过大量的简单重复抽样和简单计算实现该方法。 2. 收敛速度与问题维数无关 Monte Carlo方法的收敛速度为O(n -1/2)，与一般数值方法相比很慢。因此，用Monte Carlo方法不
16、能解决精确度要求很高的问题 Monte Carlo方法的误差只与标准差和样本容量n有关，而与样本所在空间无关，即Monte Carlo方法的收敛速度与问题维数无关。而其他数值方法则不然。因此，这就决定了Monte Carlo方法对多维问题的适用性。,3. Monte Carlo方法的适用性强 在解题时受问题条线限制的影响较小，例如要计算s维空间中的任一区域Ds上的积分 时，无论区域Ds的形状多么特殊，只要能给出描述 Ds的几何特征的条件，就可以从Ds中均匀产生n个 点 , 得到积分的近似值 其中Ds为区域Ds的体积。这是数值方法难以作到的,数据处理方法,数据拟合方法 给出一系列的点，要求得到反映点列变化规律的函数，不要求曲线或曲面通过所有数据点，而是要求它反映对象的整体变化趋势。注意在进行数据拟
