运筹学全套配套课件朱道立 ch08.ppt

《运筹学全套配套课件朱道立 ch08.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、教学要求：第八章马尔可夫链和马尔可夫决策过程掌握掌握马尔可夫分析的基本原理和方法会运用马尔可夫决策过程解决一些基本问题了解马尔可夫决策过程的建模和求解方法目录马尔可夫链n步转移概率马尔可夫链中状态的分类稳态概率马尔可夫决策规划目录马尔可夫链n步转移概率马尔可夫链中状态的分类稳态概率马尔可夫决策规划定义离散时间随机过程：假设我们观测一个系统在离散时间点上某个特性的情况，令为此系统特性在时刻t的值。离散时间的随机过程就是关于随机变量之间关系的描述。马尔可夫链：称一个离散时间随机过程为马尔可夫链，如果对于所有的和状态，成立称概率规则在时间上是平稳的链为平稳马尔可夫链。转移概率：在

2、马尔可夫链中，对于所有的状态i和j，以及所有的时刻t，有，称为马尔可夫链的转移概率。对于平稳马尔可夫链，转移概率可以用一个转移概率矩阵P表示。例题赌徒问题考虑一赌徒，在时刻0拥有赌金2元，在时刻进行赌局。在每赌博中，赢一元的概率是，输一元的概率是。赌徒的目标是赌金增加到4元，所以当赌金增加到4元或输光时赌博结束。请描述此离散时间随机过程，并判断其是否为一个平稳马尔可夫链？若是，请写出其概率转移矩阵。解答我们定义为赌徒在第t场赌局结束后的赌金，则可以把看作是离散时间的随机过程。注意到是已知条件，但是和其后的值是随机的。因为赌徒在第t+1场赌局结束时的赌金概率分布只依赖于赌徒在第t场

3、赌局结束时的赌金，所以此为一个马尔可夫链。因为赌博输赢的概率并不因时间而改变，所以此又为一个平稳马尔可夫链。其转移概率矩阵如下：目录马尔可夫链n步转移概率马尔可夫链中状态的分类稳态概率马尔可夫决策规划n步转移概率假设已知马尔可夫链的转移概率矩阵P。问：如果一个马尔可夫链在时刻m处于状态i，那么在n个阶段后，此马尔可夫链处于状态j的概率是多少？因为研究的是平稳马尔可夫链，所以这个概率与m无关，可以记作：其中，称作从状态i到状态j的n步转移概率。显然，；；又由转移概率矩阵，得：就是矩阵的第i行第j列元素。推而广之，可知对于n>1，例题饮料的市场份额问题假设目前饮料市场上只有两种饮料。

4、假定顾客上一次购买时选择饮料1，则下次选购饮料1的概率为90%；顾客上一次购买时选择饮料2，则下次选购饮料2的概率为80%。如果顾客当前选购的是饮料2，则在此后的第二次购买时选择饮料1的概率是多少？如果顾客当前选购的是饮料1，则在此后的第三次购买时选择饮料1的概率是多少？解答1我们可以把顾客的饮料选购过程看作一个马尔可夫链，其中任何给定时刻的状态为顾客在最近一次购买时选择的饮料种类。由此，顾客的饮料选购过程可表示为两个状态的马尔可夫链，其中状态1=顾客最近一次选购的是饮料1，状态2=顾客最近一次选购的是饮料2。定义为顾客在将来第次购买时选择的饮料种类（当前一次选购的饮料种类为），

5、则可被表示为具有如下转移概率矩阵的马尔可夫链，解答2回答问题a）我们知道的第2行第1列元素。所以，，这就意味着当前购买饮料2的顾客在此后第二次购买时选择饮料1的概率是0.34。回答问题b）我们知道的第1行第1列元素。所以，初始状态未知的情况在许多情况下，我们不知道马尔可夫链在时刻0时的状态。令为系统在时刻0时处于状态的概率，则我们可以确定系统在n时刻处于状态j的概率时刻n处于状态j的概率==jis12目录马尔可夫链n步转移概率马尔可夫链中状态的分类稳态概率马尔可夫决策规划定义1路径：给定两个状态i和j。从i到j的一条路径，是指以为i起点，以j为终点的一系列状态转移，且每次转移都具

6、有正的发生概率。可达性：如果存在一条从i到j的路，则称状态j是从i状态可达的。相通性：如果状态j是从i状态可达的，且i是从j可达的，则称状态i和j是相通的。闭集：如果对于马尔可夫链中的一个状态集合S，满足任何一个S外的状态都不可能从S内的某个状态可达的，则称S为闭集。吸收状态：如果，则称状态i为吸收状态。定义2滑过状态：如果存在一个状态j，j是从i可达的，而i不是从j可达的，则称状态i为滑过状态。常返状态：如果一个状态不是滑过的，则称它为常返状态。周期性：称状态i为周期的，并有周期k>1，如果所有从i出发又返回到i的路径的长度（段数）都是k的倍数，且k是满足这样条件的最小数。非周

7、期性：如果一个常返状态不是周期的，则称为非周期的。遍历性：如果在马尔可夫链中的所有状态都是常返的，非周期性的，且互相相通的，则称这个马尔可夫链为遍历的。例题对分别具有下面转移矩阵的三个马尔可夫链，判断其是否为遍历转移矩阵P1和P3对应的马尔可夫链是遍历的，但P2对应的马尔可夫链不是遍历的，这是因为它有两个状态闭集（闭集1={1，2}，闭集2={3，4}），而不同闭集中的状态不是互相相通的。目录马尔可夫链n步转移概率马尔可夫链中状态的分类稳态概率马尔可夫决策规划稳态概率定理1：令P