马尔可夫链数学建模教程文件课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《马尔可夫链数学建模教程文件课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 马尔可夫链 数学 建模 教程 文件 课件
- 资源描述:
-
1、马尔可夫链建模法马尔可夫链建模法马尔可夫链基本理论和结论马尔可夫链基本理论和结论 服务网点的设置问题常染体隐性疾病模型常染体隐性疾病模型马尔可夫链的应用马尔可夫链的应用预备知识:马尔可夫链随机过程:设 是一族随机变量,T是一个实数集合,若对任意的 实数 ,是一个随机变量,则称 为随机过程。,TttTt t,Ttt例3:某商店每月考察一次经营情况,其结果用销路好或坏这两种状况中的一种表示。已知若果本月销路好,下月任保只这种状况的概率为0.5;如果本月销路坏,下月转变为销路好的概率为0.4,试分析假若开始时商店处于销路好的状态,过若干月后能保持销路好的概率有多大?如果开始是处于销路坏呢?E=1,2
2、,.m表示销路坏表示销路好,21nnXX,n=0,1,2,.nX称为这个经营系统的状态)|()2,1,2,1(),()(),2,1()(1iXjXPpjijipiXPnaiinnannijijnii即概率,下月转为状态的表示本月处于状态即的概率月处于状态表示第用无关和和只取决于这里称为转移概率称为状态概率.,)(211nnijnnijiXXpXXpna称为无后效性,由此,更椐全概率公式容易得到.,.2,1),(),(10)0(,1)0(6.015.01,4.0,5.0)()()1()()()1(212112221112211122212121221111nnanaaapppppppnapnan
3、apnapnana)立即可算出时,用式(当商店开始销路好,即所以显然有因为知道如表所示,由数字变化规律可以看出95)(,94)(21nanan时,当开始销路好时状态概率的变化n)()(21nana0 1 2 3 1 0.5 0.45 0.445 4/90 0.5 0.55 0.555 5/9表2 开始销路坏时的状态概率的变化)()(21nana0 1 2 3 n0 0.4 0.44 0.444 4/91 0.6 0.56 0.556 5/9马尔可夫链的定义:设,.2,1,nn是一个随机序列,状态空间E为有限或可列对于任意的正整数m,n,若i,j,有)1.,2,1(nkEik|,.,|1111i
4、jPiiijPnmnnnnmn则称,.2,1,nn为一个 马尔可夫链马氏链及其基本方程转移过程称为马氏链态按照离散时间的随机离散状的取值无关,那麽这种而与的取值及转移概率,的取值只取决于如果,即转移概率。的概率为到,即状态概率,从的概率记作且个离散值可以取表示,设机变量,系统的状态用一个随对于每一个离散化为按照系统的发展,时间.,)(,.2,1,.3,2,12111nnnnijnninnnnXXXXpjXiXnaiXkXkXXnn由状态转移的无后效性和全概率公式可以写出马氏链的基本方程)6,.(3,2,11)5,.(3,2,1,0)4(,.2,1,0,1)()()3(.,.2,1,)()1(1
5、11ipjipnnapnaipnanakjijijkiiijikjijji应满足和并且0NPNP使存在正整数正则链的充要条件是:,则它是移矩阵为定理一:若马氏链的转如果的状态称为吸收状态:转移概率定义,12iiP马氏链至少包括一个吸收状态,并且从每一个非吸收状态出发,能以正的概率经有限次转移达到某个吸收状态则称此马氏链为吸收链。定理2:正则链存在唯一的极限状态概率)11(1)()1()10(,)(),.,(1321kiikwpnanawwpwwnanwwwww两边同时取极限及得满足又称稳定概率与初始状态概率无关,时状态概率使得当引入状态概率向量和转移概率矩阵kkijkpPnanananana)
6、(.).(),(),()(221(7)则基本方程(3)可表为nPanaPnana)0()()()1(由此还可以得到(8)(9)6.04.05.05.0316)5(为的转移矩阵例,称为随机矩阵。对于的行和为)式表明是非负阵,(式表明转移矩阵PP因此对于马氏链模型最基本的问题是:构造状态xn及写出转移矩阵p,一旦有了P,则给定初始状态a(0)就可以用(9)或(8)计算任意时间n的状态概率a(n)定义1:一个有k个状态的马氏链,如果存在正整数N,使从任意状态i经N次转移,都以大于0的概率达到状态j(I,j=1,2,k)称此马氏链为正则链。正则链。马尔可夫链的应用模型六:服务网点的设置问题为适应日益扩
7、大的旅游事业的需要,某城市的甲乙丙三个照相馆组成一个联营部,联合经营出租相机的业务。游客可由甲乙丙三处任一处租出相机,用完后,还到三处中的任一处即可。估计其转移概率为:租相机处甲乙丙还 相 机 处甲乙丙0.2 0.8 00.8 0 0.20.1 0.3 0.6今欲选择其中之一附设相机维修点,请你设计一种方案。模型分析模型分析由于旅客还相机的情况只与该次租机地点有关,而与相机以前所处的点址无关。概率分布。这一马尔可夫链的极限设置问题实际上要计算点的由上表给出。考虑维修夫链,其转移矩阵是一个马尔可在甲乙丙馆。则用时分别表示相机第次被租次被租时所在的点址;表示相机第所以可用Pnnnnnnn.,.2,
8、1,3,2,1组解出存在,并可从下列方程的条件,极限概率满足定理对于所有的)3,2,1(,2,3,2,1,jpjij由(10)有,设极限概率为W11kiippwp即:16.02.03.08.01.08.02.03213233123211ppppppppppppp解上列方程组可得:418,4116,4117321ppp由计算看出,经过长期经营后,该联营部的每架照相机还到甲乙丙照相馆的概率为17/41,16/41,8/41。由于还到甲的照相机的概率最大,因此维修点设在甲馆较好。模型推广:生物基因遗传等方面的应用。模型推广:生物基因遗传等方面的应用。随着人类的进化,为了揭示生命的奥秘,人们越来越注重
9、随着人类的进化,为了揭示生命的奥秘,人们越来越注重遗传学的研究,特别是遗传特征的逐代传播,已引起人们遗传学的研究,特别是遗传特征的逐代传播,已引起人们广泛的注意。无论是人,还是动、植物都会将本身的特征广泛的注意。无论是人,还是动、植物都会将本身的特征遗传给下一代,这主要是因为后代继承了双亲的基因,形遗传给下一代,这主要是因为后代继承了双亲的基因,形成自己的基因对,由基因又确定了后代所表现的特征。本成自己的基因对,由基因又确定了后代所表现的特征。本节将利用数学的节将利用数学的 马氏链方法马氏链方法来建立相应的遗传模型等,并来建立相应的遗传模型等,并讨论几个简单而又有趣的实例。讨论几个简单而又有趣
10、的实例。马氏链(马尔柯夫链)马氏链(马尔柯夫链)研究的是一类重要的随机过程,研研究的是一类重要的随机过程,研究对象的状究对象的状 态态s(t)是不确定的,它可能是不确定的,它可能 取取K种种 状态状态si(i=1,k)之一,有时甚至可取无穷多种状态。在建模时,之一,有时甚至可取无穷多种状态。在建模时,时间变量也被离散化,我们希望通过建立两个相邻时刻研时间变量也被离散化,我们希望通过建立两个相邻时刻研究对象取各种状态的概率之间的联系来研究其变化规律,究对象取各种状态的概率之间的联系来研究其变化规律,故马氏链研究的也是一类状态转移问题。故马氏链研究的也是一类状态转移问题。例例4.6 设某商店经营情
11、况可能有三种状态:设某商店经营情况可能有三种状态:好(好(S1:利润丰厚)、一般(利润丰厚)、一般(S2)和不好和不好(S3:亏损)。根据统计资料,上月状态为亏损)。根据统计资料,上月状态为Si,下月状态为下月状态为Sj的概率为的概率为pij(i=1,2,3;j=1,2,3),),0pij1例例4.6中的关系既可用一转移矩阵表示中的关系既可用一转移矩阵表示 333231232221131211pppppppppA例例4.7 研究某一草原生态系统中物质磷的循环,考研究某一草原生态系统中物质磷的循环,考虑土壤中含磷、牧草含磷、牛羊体内含磷和流失于虑土壤中含磷、牧草含磷、牛羊体内含磷和流失于系统之外
12、四种状态,分别系统之外四种状态,分别 以以S1,S2,S3和和S4表示表示这四种状态。以年为时间参数,一年内如果土壤中这四种状态。以年为时间参数,一年内如果土壤中的磷以的磷以0.4的概率被牧草生长吸收,水土流失于系统的概率被牧草生长吸收,水土流失于系统外的概率为外的概率为 0.2;牧草中的含磷以;牧草中的含磷以 0.6的概率被牛的概率被牛羊吃掉而转换到牛羊体内,羊吃掉而转换到牛羊体内,0.1的概率随牧草枯死腐的概率随牧草枯死腐败归还土壤;牛羊体中的磷败归还土壤;牛羊体中的磷 以以0.7的概率因粪便排的概率因粪便排泄而还归土壤,又以自泄而还归土壤,又以自 身身0.1的比率因屠宰后投放的比率因屠宰
13、后投放市场而转移到系统外。我们可以建立一个马尔柯夫市场而转移到系统外。我们可以建立一个马尔柯夫链来研究此生态系统问题,其转移概率列表于下:链来研究此生态系统问题,其转移概率列表于下:1000S4流失系流失系统外统外0.10.200.7S3羊体含羊体含磷磷00.60.30.1S2牧草含牧草含磷磷0.200.40.4S1土壤含土壤含磷磷i时段状时段状态态S4S3S2S1i+1时段状态时段状态状态转移概率状态转移概率相应的转移矩阵相应的转移矩阵 为:为:10001.02.007.006.03.01.02.004.04.0M且且Sj+1=SjM马氏链模型的性质完全由其转移矩马氏链模型的性质完全由其转移
14、矩 阵决定,故研究马氏链的数学工阵决定,故研究马氏链的数学工 具是线性代数中有关矩阵的理论。具是线性代数中有关矩阵的理论。首先,任一转移矩阵的行向量均为概率向量,即有首先,任一转移矩阵的行向量均为概率向量,即有(1)(I,j=1,n)(2)(i=1,n)这样的矩阵被称为这样的矩阵被称为 随机矩阵随机矩阵。10 igP11 njigP 下面给出双亲体基因型的所有可能的结合,以及其后代形成下面给出双亲体基因型的所有可能的结合,以及其后代形成每种基因型的概率,如每种基因型的概率,如 表所示。表所示。在常染色体遗传中,后代从每个亲体的基因对中各继承一在常染色体遗传中,后代从每个亲体的基因对中各继承一个
15、基因,形成自己的基因时,基因对也称为基因型。如果个基因,形成自己的基因时,基因对也称为基因型。如果我们所考虑的遗传特征是由两个基我们所考虑的遗传特征是由两个基 因因A和和a控制的,(控制的,(A、a为表示两类基因的符号)那么就有三种基因对,记为为表示两类基因的符号)那么就有三种基因对,记为AA,Aa,aa。1000aa010Aa0001AA后后代代基基因因型型aaaaAaaaAaAaAAaaAAAaAAAA父体父体母体的基因型母体的基因型双亲随机结合的较一般模型相对比较复杂,这些我们仅研究双亲随机结合的较一般模型相对比较复杂,这些我们仅研究一个较简单的特例一个较简单的特例。例例4.8 农场的植
16、物园中某种植物的基因型农场的植物园中某种植物的基因型 为为AA,Aa和和aa。农场计划采用农场计划采用 AA型的植物与每种基因型植物型的植物与每种基因型植物相结合的方案培育植物后代。那么经过若干年后,相结合的方案培育植物后代。那么经过若干年后,这种植物的任一代的三种基因型分布情况如何?这种植物的任一代的三种基因型分布情况如何?(a)假设假设:令:令n=0,1,2,。(i)设设an,bn和和cn分别表示第分别表示第n代植物中,基因型代植物中,基因型 为为AA,Aa和和aa的植物占植物总数的百分比的植物占植物总数的百分比 。令。令x(n)为第为第n代植物的基因型分代植物的基因型分布:布:nnnnc
17、bax)(当当n=0时时 000)0(cbax表示植物基因型的表示植物基因型的初始分布(即培育初始分布(即培育开始时的分布)开始时的分布)例例4.8 农场的植物园中某种植物的基因型农场的植物园中某种植物的基因型 为为AA,Aa和和aa。农场计划采用农场计划采用 AA型的植物与每种基因型植物型的植物与每种基因型植物相结合的方案培育植物后代。那么经过若干年后,相结合的方案培育植物后代。那么经过若干年后,这种植物的任一代的三种基因型分布情况如何?这种植物的任一代的三种基因型分布情况如何?(b)建模建模根据假设根据假设(ii),先考虑第先考虑第n代中的代中的AA型。由于第型。由于第n1代的代的AA型与
18、型与AA型结合。后代全部是型结合。后代全部是AA型;第型;第n1代的代的Aa型与型与AA型结合,后代是型结合,后代是AA型的可能性为型的可能性为 1/2,而,而 第第n1代的代的aa型与型与AA型结合,后代不可能型结合,后代不可能 是是AA型。因此当型。因此当n=1,2时时1110211 nnnncbaa1121 nnnbaa即即类似可推出类似可推出1121 nnncbbcn=0 显然有显然有(ii)第第n代的分布与代的分布与 第第n1代的分布之间的关系是通过表代的分布之间的关系是通过表5.2确定的。确定的。1000 cba(4.2)(4.3)(4.4)将将(4.2)、()、(4.3)、()、
19、(4.4)式相加,得式相加,得111 nnnnnncbacba根据根据假设假设(I),可递推得出:可递推得出:1000 cbacbannn对于对于(4.2)式式.(4.3)式和式和(4.4)式,我们采用矩阵形式简记为式,我们采用矩阵形式简记为,2,1,)1()(nMxxnn其中其中 nnnncbaxM)(,00012100211(注:这里注:这里M为转移矩阵的位置)为转移矩阵的位置)(4.5)由由(4.5)式递推,得式递推,得)0()2(2)1()(xMxMMxxnnnn (4.6)(4.6)式给出第式给出第n代基因型的分布与初始分布的关系。代基因型的分布与初始分布的关系。为了计算出为了计算出
20、Mn,我们将我们将M对角化,即求出可逆矩对角化,即求出可逆矩 阵阵P和对角和对角库库D,使使 M=PDP-1因而有因而有 Mn=PDnP-1,n=1,2,其中其中 nnnnD321321000 这里这里 ,是矩是矩 阵阵M的三个特征值。对于的三个特征值。对于(4.5)式式中的中的M,易求得它的特征值和特征向量:易求得它的特征值和特征向量:=1,=1/2,=01 2 3 1 2 3 因此因此 121 011 001,0000210001321eeeD所以所以 100210111321eeeP通过计算,通过计算,P-1=P,因此有因此有)0(1)(xPPDxnn 000 100210111 000
21、0210001 100210111cban即即 00011)(000212102112111cbacbaxnnnnnnnn 021212121010010000cbcbcbannnn所以有所以有 0212121211010010nnnnnnnccbbcba当当 n时,时,021 n,所以从(,所以从(4.7)式得到)式得到0,0,1nnncba即在极限的情况下,培育的植物都即在极限的情况下,培育的植物都 是是AA型。型。若在上述问题中,不选用基若在上述问题中,不选用基 因因AA型的植物与每一植物结合,型的植物与每一植物结合,而是将具有相同基因型植物相结合,那么后代具有三种基而是将具有相同基因型
22、植物相结合,那么后代具有三种基因型的概率如因型的概率如 表所示。表所示。11/40aa01/20Aa01/41AA后后代代基基因因型型aaaaAaAaAAAA父体父体母体的基因型母体的基因型并且并且)0()(xMxnn,其中,其中 141002100411MM的特征值为的特征值为21,1,1321 通过计算,可以解出与通过计算,可以解出与 、相对应的两个线性无关的特相对应的两个线性无关的特征向量征向量e1和和e2,及与相对应的特征内及与相对应的特征内 量量e3:1 2 121,100,101321eee因此因此 02101110211,1112001011PP)0(1)(xPPDxnn 000
23、 02101110211 2100010001 111200101cban解得:解得:01000102121212121bccbbbaannnnnn当当 n 时,时,021 n,所以,所以000021,0,21bccbbaannn 因此,如果用基因因此,如果用基因 型相同的植物培育型相同的植物培育 后代,在极限情况后代,在极限情况 下,后代仅具有基下,后代仅具有基 因因AA和和aa。例例4.9 常染体隐性疾病模型常染体隐性疾病模型现在世界上已经发现的遗传病有将现在世界上已经发现的遗传病有将 近近4000种。在种。在一般情况下,遗传疾病和特殊的种族、部落及群体一般情况下,遗传疾病和特殊的种族、部
24、落及群体 有关。例如,遗传病库利氏贫血症的患者以居住在有关。例如,遗传病库利氏贫血症的患者以居住在 地中海沿岸为多,镰状网性贫血症一般流行在黑人地中海沿岸为多,镰状网性贫血症一般流行在黑人中,家族黑蒙性白痴症则流行在东欧犹太人中间。中,家族黑蒙性白痴症则流行在东欧犹太人中间。患者经常未到成年就痛苦地死去,而他们的父母则患者经常未到成年就痛苦地死去,而他们的父母则 是疾病的病源。假若我们能识别这些疾病的隐性患是疾病的病源。假若我们能识别这些疾病的隐性患 者,并且规定两个隐性患者不能结合(因为两个隐者,并且规定两个隐性患者不能结合(因为两个隐 性病患者结合,他们的后代就可能成为显性患者),性病患者
25、结合,他们的后代就可能成为显性患者),那么未来的儿童,虽然有可能是隐性患者,但绝不那么未来的儿童,虽然有可能是隐性患者,但绝不 会出现显性特征,不会受到疾病的折磨。会出现显性特征,不会受到疾病的折磨。现在,我们考虑在控现在,我们考虑在控制结合的情况下,如制结合的情况下,如何确定后代中隐性患何确定后代中隐性患者的概率。者的概率。(a)假设假设(i)常染色体遗传的正常基因记常染色体遗传的正常基因记 为为A,不不 正常基因记正常基因记 为为a,并以并以 AA,Aa,aa 分别表示正常人,隐性患者,显性患分别表示正常人,隐性患者,显性患 者的基因型者的基因型(ii)设设an,bn分别表示第分别表示第n
展开阅读全文