浙大城院数学建模9

11:05:16MCM1第九章、随机模型§9.3拉丁方与正交设计§9.1几何概率模型§9.2计算机模拟11:05:16MCM2现实世界中充满了不确定性，我们所研究的对象往往受到诸多随机因素的影响，因此所建立的数学模型涉及到的变量往往并非确定型变量而是随机变量，甚至有时候变量之间的关系也不是确定的函数关系，我们将这类模型称为随机模型。§9.1几何概率模型一类涉及到“等可能性”的概率问题我们称之为几何概型或几何概率模型，我们先来观察一下下面的例子。11:05:16MCM3例9.1约会问题一位男生与一位女生约定晚饭后18时到19时之间在教学大楼后的左边第三棵柳树下会面。双方约定，先到者必须等候另一个人15分钟，过时如另一人仍未到达则可离去，问两人会面的机会有多大？显然，男生和女生到达约会地点的时间是随机的、不确定的，故所涉模型应为随机模型。根据题意，我们已经知道了男生和女生各自到达的时间范围，他们均可能在18时到19时之间的任何时刻到达约会地点。但是无法预知他们到达的确切时刻，那么等候另一人的15分钟自然也不确定，问题好像有点麻烦。11:05:16MCM4如果到达的时间只有有限多个时间点，那么所涉及的数学模型属于古典概型，我们只需列出男生和女生到达时间的所有可能组合，然后从中找出所有可以会面的组合，用可以会面的组合数去除以所有可能的组合数就可得到两人会面的概率。但现在到达时间可取自一个无限集合(区间)，这给我们的计算带来了一些困难。用古典概型的方法无法解决此问题，我们要另寻其它方法。几何概型讨论的是无限样本空间中的概率问题，在此空间中随机试验的每一结果都是等可能发生的。在几何概型中，随机试验的所有可能结果构成一个样本空间，样本空间通常是一个几何区域。11:05:16MCM5试验中可能发生的事件则为中的一个子区域，而随机事件发生的概率则是在对两者进行了比较之后计算出来的。比如我们在一个面积为的区域中，等可能地任意投点(如图9.1)。在区域中有一个小区域，它的面积为，投点落入A中的可能性大小只与A的面积成正比，图9－1而与的位置及形状无关。如果仍将“投点落入小区域A”这个随机事件记作A，并设(即投点必落在中)，可得事件A发生的概率为，这样的概率问题通常被称为”几何概型”。SASAS()1P()ASPAS11:05:16MCM6应当注意的是，这里的面积只是二维平面内某个区域的测度而已，如果是在一条线段上等可能地任意投点，公式里的面积应改为长度；如果在一个三维立方体内等可能地投点，则面积应该为体积。现在，我们来求解例9.1。设x和y分别表示男生和女生到达约会地点的时间(为计算方便，从18时开始计时)，建立平面直角坐标系如图9-2所示，所有可能到达时间的组合，即(x,y)的所有可能结果构成一个边长为60的正方形(以分钟为单位)。另外，由题意两人能够会面的充要条件是15xy11:05:16MCM7图9-201020304050600102030405060xyA11:05:16MCM8可能会面的时间组合由图中的阴影部分所表示。我们假设两人到达约会地点的时间在这一小时中均是等可能的，此时，例9.1就成为了一个几何概型问题。记二人会面的事件为A，由等可能性可知二人会面的可能性为22260457()6016ASPAS几何概型的用途十分广泛，其中最为著名的是利用它来求的近似值。在1777年出版的《或然性算术实验》一书中，法国科学家蒲丰（Buffon）提出了著名的蒲丰投针试验，并以该实验方法计算。11:05:16MCM9这个实验方法的操作很简单：在一张白纸上画出一组间距为的平行线，并找一根粗细均匀，长度为的细针，然后一次又一次地将小针任意投掷在白纸上。这样反复地投掷多次，记录下针与这组平行线中的任意一条相交的次数，就可以得到的近似值。例如，在某次实验中，他选取了，然后，共计投了2212次，其中针与平行线之一相交了704次，这样求得圆周率的近似值为2212/704=3.142。下面，我们来简单地介绍一下该试验的原理。a()lla/2la11:05:16MCM10如图9-3所示，用x表示针的中点与最近一条平行线间的距离，用表示针与此直线间的夹角，显然有020ax图9-311:05:16MCM11由这两个不等式可以确定平面上的一个矩形区域(见图9-4)，其面积为：x()2aS图9-4为使针与平行线相交，其充要条件是：sin20lx11:05:16MCM12这两个不等式确定的平面区域A的面积为由细针落纸的等可能性知，细针与平行线相交的概率0()sin2lSAdl()2()SAlpSa记N为投针试验中的试验次数，n为针与平行线相交的次数，则n/N为细针与平行线相交的频率。由概率论中的大数定理，当试验次数足够多(N足够大)时，可将事件发生的频率看作事件发生的概率的近似值，即于是得到。2lnaN2lNan11:05:16MCM13历史上有许多学者曾亲自做过这个试验，下表记录了他们的试验结果（把折算成单位长度1）:a表9.1试验者年份针长投掷次数相交次数得到的近似值Wolf18500.8500025323.1596Smith18550.632041218.53.1554DeMorgan,C.18601.0600382.53.137Fox18840.7510304893.1595Lazzerini19010.83340818083.1415929Reina19250.541925208593.179511:05:16MCM14蒙特卡罗(MonteCarlo)方法，也称为计算机随机模拟方法，是一种基于“随机数”的计算方法。这一方法源于美国在第一次世界大战期间研制原子弹的“曼哈顿计划”。该计划的主持人之一，数学家冯诺伊曼用驰名世界的赌城——摩纳哥的MonteCarlo来命名这种方法，使它蒙上了一层神秘的色彩。§9.2计算机模拟MonteCarlo方法的基本思想源于我们上节介绍过的蒲丰投针试验。早在17世纪，人们就已经知道用事件发生的“频率”作为事件的“概率”的近似值。只要设计一个随机试验，使一个事件的概率于某未知数有关，然后通过重复试验，以频率近似表示概率，即可求得该未知数的近似解。11:05:16MCM15显然，利用随机试验求近似解，试验次数要相当多才行，比如前述的各位学者为了求，都亲自重复投针达几千次之多，这显然既费时又费力，非常麻烦。随着本世纪40年代电子计算机的出现，人们便开始利用计算机来模拟所设计的随机试验，使得这种方法得到迅速的发展和广泛的应用。特别是近年来高速电子计算机的出现，使得用数学方法在计算机上大量、快速地模拟这样的试验成为可能。若对已知分布的随机变量进行模拟，需要产生一系列服从这种分布的随机数。其中最基本的模拟是区间上的均匀分布随机数的产生。产生均匀分布的随机数的常用方法很多，有平方取中法、线性同余法等，这里我们不作专门的介绍，因为很多软件均提供了生成随机数的专用命令，如MATLAB提供了rand函数来生成上的均匀分布随机数等。11:05:16MCM16计算机产生的随机数都是按照某种确定的算法产生的，它遵循了一定的规律，一旦初始值确定，所有随机数也就随之确定，这显然不满足真正随机数的要求，因此我们称这种随机数为伪随机数。但只要伪随机数能通过独立性检验、分布均匀性检验、参数检验等一系列的统计检验，就可以把它们当作真正的随机数那样放心地使用。上节中的约会问题我们也可以通过计算机模拟来解决。用x和y分别记男生和女生到达约会地点的时间(仍从18时开始计时，但以小时为单位计算)，由于二人均可能在18时到19时之间的任何时刻到达约会地点，且在这一小时之内的任何时刻到达的可能性均相同，所以x和y均服从区间(0,1)上的均匀分布。11:05:16MCM17取一个充分大的正整数n，重复n次，每次独立地从区间(0,1)中随机地取一对数x和y，分别检验|x-y|≤15/60是否成立。设n次试验中不等式成立的共有m次，则二人会面的可能性可近似地看成为m/n。图9.5为某次模拟时取1000个随机数对得到的散点图，并由此得到二人会面的可能性大约为0.4440，与实际数值7/16=0.4375的误差仅为0.0065，如果我们希望据此方法得到更为精确的结果，可令n取更大的数。00.20.40.60.8100.10.20.30.40.50.60.70.80.91图9.511:05:16MCM18蒲丰投针试验也可进行计算机模拟。但一般只能用来演示而不能真正用来求π的近似值，因为产生服从均匀分布的的随机数时，需要知道均匀分布的区间范围（），但既然范围已经知道，我们也就无需再求π了！那么能否利用计算机，用模拟的方法来求π呢？根据上节的几何概率我们也可以自行设计求π的方法。0,02或，比如我们可以采取下面的方法：如图9-6所示，取一个二维数组(x,y)，取一个充分大的正整数n，重复n次，每次独立地从区间(0,1)中随机地取一对数x和y，并分别检验是否成立。设n次试验中不等式成立的共有m次，则221xy4mn11:05:16MCM19图9-611:05:16MCM20大部分其它分布的随机数的产生均基于均匀的分布随机数，主要采用的方法有逆变换法等。逆变换法基于定理9.1。记随机变量X的分布函数为F(x)，定义它的逆函数,y的取值范围为0≤y≤1。1()inf:()FyxFxy定理9.1设随机变量Y服从区间(0,1)上的均匀分布，则随机变量的分布函数为F(x)。1()XFY证明由分布函数的定义及上述函数的定义，可以得到随机变量X的分布函数为1F1()(())(())PXxPFYxPYFx11:05:16MCM21因为Y服从区间(0,1)上的均匀分布，显然当0≤y≤1时总有，故，证毕。()PYyy()()PXxFx由定理9.1，要产生分布函数为F(x)的随机数，只要先产生区间(0,1)上的均匀分布的随机数y，然后计算，即为分布函数为F(x)的随机数。合成和筛选等方法也可以由均匀分布随机数产生其它分布的随机数。某些特殊分布如标准正态分布N(0,1)、指数分布的随机数的产生还有专门的定理(定理9.2为标准正态随机数的产生定理)。大部分数学软件均提供了专门的函数来产生常用分布随机数，给我们带来了很大的便利，其原理大体就是这样的。1()FY1()FY11:05:16MCM22定理9.2设、是独立同分布的服从区间(0,1)上的均匀分布的随机变量，令则随机变量与相互独立，且均服从标准正态分布。1X2X1211212212(2ln)cos(2)(2ln)sin(2)YXXYXX1Y2Y利用此定理可以同时产生两个服从标准正态分布的随机数，首先产生两个区间(0,1)上的均匀分布的随机数、，然后计算出，，则和均为标准正态随机数。1x2x1y2y12112(2ln)cos(2)yxx12212(2ln)sin(2)yxx11:05:16MCM23蒙特卡罗方法现已被成功地运用到诸如解微分方程、解积分方程、求特征值、矩阵转置等许多传统的数学问题中去，尤其是常被用于计算多重积分。让我们来看一下较为简单的数值积分——计算一元函数定积分的蒙特卡罗方法的主要思想。在区间(a,b)上随机选取n个点，用这n个点上的函数值的平均值来代替f(x)在区间(a,b)上的平均值。由此思想可以得到计算一元函数定积分近似值的公式()bafxdx11()()()nbiaifxdxbafxn(1,2,,)ixin其中是区间(a,b)上均匀分布的n个随机数。这个思想显然很容易推广到多重积分上去。11:05:16MCM24对于二重积分，有相应的公式1212121()()(,)(,)nbdiiacibadcfxxdxdxfxxn其中是区间(a,b)上均匀分布的n个随机数，是区间(c,d)