上海对外贸易学院：《运筹学》课程教学资源（PPT课件讲稿）第十六章 Markov过程

凌晨: 十六章 Markov过程 Markoⅴ过程是随机过程研究的对象之 运动是世界存在的本质,我们所关注的事物 对象、目标等等,无不在变化中,其中大多数 还处在随机变化中 探讨随机运动的趋势、可能的结果,就是 Markov过程的关注所在 重点:掌握 Marko过程研究问题的思路和方 法

Ling Xueling Markov 过程是随机过程研究的对象之一 运动是世界存在的本质，我们所关注的事物、 对象、目标等等，无不在变化中，其中大多数 还处在随机变化中 探讨随机运动的趋势、可能的结果，就是 Markov 过程的关注所在 重点：掌握 Markov 过程研究问题的思路和方 法。 第十六章 Markov 过程 凌晨: 凌晨:

凌晨: 基本概念 1、 Markov过程干什么? 虽然,在其任意一个时间周期时运动系统的状态可能 都无法完全地确定,如:17:00时是否有剩余报纸? 还要研究:在连续的时间周期下,有重复试验的系统 之演变(趋势)之可能结果,如:进100份报纸,当天 能卖完?可能性? 与概率论相比,两者都研究无法确定的事物,但概率 论研究重点在特定时间下系统的状态本身,而 Markov 过程侧重于连续时间周期变化下系统状态的进化

Ling Xueling 1 、 Markov 过程干什么？ 虽然，在其任意一个时间周期时运动系统的状态可能 都无法完全地确定，如：17:00 时是否有剩余报纸？ 还要研究：在连续的时间周期下，有重复试验的系统 之演变 (趋势) 之可能结果，如：进100份报纸，当天 能卖完？可能性？ 与概率论相比，两者都研究无法确定的事物，但概率 论研究重点在特定时间下系统的状态本身，而 Markov 过程侧重于连续时间周期变化下系统状态的进化。 基本概念 凌晨: 凌晨:

凌晨: 基本概念 2、用处(仅举4个方面,后面例子只举2个) 1)机器在某个周期时处于正常运转状态,则在下 个周期是正常或不正常状态之概率是 )顾客在某个周期购买A品牌则在下一周期是买A 还是买B之概率? 3)顾客在某个周期进入A超市购物则在下一周期进 入A还是进入B之概率? )若将应收帐款按照帐龄分为若干类,则在某一周 期属于可收回帐目类,在下一周期归于呆帐类的 概率是?

Ling Xueling 2 、用处 ( 仅举 4 个方面，后面例子只举 2 个) 1) 机器在某个周期时处于正常运转状态，则在下一 个周期是正常或不正常状态之概率是？ 2) 顾客在某个周期购买 A 品牌则在下一周期是买 A 还是买 B 之概率？ 3) 顾客在某个周期进入 A 超市购物则在下一周期进 入 A 还是进入 B 之概率？ 4) 若将应收帐款按照帐龄分为若干类，则在某一周 期属于可收回帐目类，在下一周期归于呆帐类的 概率是？ 基本概念 凌晨: 凌晨:

凌晨: 基本概念 3、约定(因为本章只作介绍,需要有太多的 预备知识,所以只好事先约定) 1)不详细讨论 Markov过程本身,只从简单例子说明 2)讨论将限制于一一有静态转移概率的 Markov链, (1)系统仅有有限个状态; (2)转移概率是常数; (3)某周期的状态概率仅决定于紧前周期的状态

Ling Xueling 3 、约定（因为本章只作介绍，需要有太多的 预备知识，所以只好事先约定） 1) 不详细讨论 Markov 过程本身，只从简单例子说明 2) 讨论将限制于－－有静态转移概率的 Markov 链， 即： (1) 系统仅有有限个状态； (2) 转移概率是常数； (3) 某周期的状态概率仅决定于紧前周期的状态。 基本概念 凌晨: 凌晨:

凌晨: 第一节市场份额分析 虽然市场份额是由许多顾客之购买行为所决定的,但我们将采 用:追踪一个顾客的连续购买行为,以达到研究整个系统之目 的。所以,以下“系统 指 因为任意 个,又因为是大量试验,所以被认为可代表总体 、例子及术语介绍 1、例子 假定1:在一个小镇上仅有两家杂货店M和A;(两种状态 假定2:每位顾客每周只进行一次采购,要么M要么A,每周 不会同时去两家一一从实际出发,此假定是合理的 说明:1)多几家店一一无非多几种状态,此处只为简单方便 2)以周为周期是个习惯,其实可取平均估计值为周期 要研究的问题: 1)M和A的市场份额各为多少? 2)顾客对M和A的忠实度各为多少? 3)如果市场份额低的店要搞促销活动,如何定预算?

Ling Xueling 虽然市场份额是由许多顾客之购买行为所决定的，但我们将采 用：追踪一个顾客的连续购买行为，以达到研究整个系统之目 的。所以，以下“系统”常常指“一个顾客”－－因为任意一 个，又因为是大量试验，所以被认为可代表总体 一、例子及术语介绍 1、例子 假定1：在一个小镇上仅有两家杂货店 M 和 A；（两种状态） 假定2：每位顾客每周只进行一次采购，要么 M 要么 A，每周 不会同时去两家－－从实际出发，此假定是合理的 说明：1) 多几家店－－无非多几种状态，此处只为简单方便 2) 以周为周期是个习惯，其实可取平均估计值为周期 要研究的问题： 1) M 和 A 的市场份额各为多少？ 2) 顾客对 M 和 A 的忠实度各为多少？ 3) 如果市场份额低的店要搞促销活动，如何定预算？ 第一节 市场份额分析 凌晨: 凌晨:

凌晨: 第一节市场份额分析 2、术语 将采用跟踪某一位顾客采购行为的方法进行研究 1)试验一了解顾客的采购店,一个周期会有一个 试验,也就有一个结果 2)状态一一某周期顾客选定不同店,称为系统的不 同状态,此例中,约定: 状态1:顾客在M店购物 状态2:顾客在A店购物 3)状态概率的意义一一购物过程会延续下去,不管 能得出什么结论,都不可能事先确定试验结果, 但若能求出某周期两个状态的概率足矣,因为市 场份额已可估计得到

Ling Xueling ２、术语 将采用跟踪某一位顾客采购行为的方法进行研究 1) 试验－－了解顾客的采购店，一个周期会有一个 试验，也就有一个结果 2) 状态－－某周期顾客选定不同店，称为系统的不 同状态，此例中，约定： 状态1： 顾客在 M 店购物 状态2： 顾客在 A 店购物 3) 状态概率的意义－－购物过程会延续下去，不管 能得出什么结论，都不可能事先确定试验结果， 但若能求出某周期两个状态的概率足矣，因为市 场份额已可估计得到。 第一节 市场份额分析 凌晨: 凌晨:

凌晨: 第一节市场份额分析 状态转移概率 利用 Markovγ过程研究连续试验中不同状态的概率,最基本的 是先要求得:转移概率 调研与转移概率值 1)市场调研:10个星期内跟踪任意选定的100个人,采集购 物数据 2)数据处理:概率统计方法,注意力集中在顾客对M和A的 转移购物上 3)假设得出以下的:一一从统计数据可得出!! 下一个周期去 M店 A店 当前周期去M店 0.9 0.1 A店 0.2 0.8 称为转移概率值

Ling Xueling 二．状态转移概率 利用 Markov 过程研究连续试验中不同状态的概率，最基本的 是先要求得：转移概率 1、调研与转移概率值 1) 市场调研：10 个星期内跟踪任意选定的 100 个人，采集购 物数据 2) 数据处理：概率统计方法，注意力集中在顾客对 M 和 A 的 转移购物上 3) 假设得出以下的：－－从统计数据可得出！！ 下一个周期去 M 店 A 店 当前周期去 M 店 0.9 0.1 A 店 0.2 0.8 称为转移概率值。 第一节 市场份额分析 凌晨: 凌晨:

凌晨: 第一节市场份额分析 状态转移概率 2、关于转移概率的说明 1)行数据之和=1说明:每行实际给出一个概 率分布 2)0.90.8——分别是对M/A的忠实度 0.1/0.2--对M/A的转移特征 3)在研究的时间段内,假定转移概率不会变 即:系统无大变化(商业环境相差不大) 4)转移概率值是统计数据得来的

Ling Xueling 二、状态转移概率 2、关于转移概率的说明 1）行数据之和＝1说明：每行实际给出一个概 率分布 2) 0.9/0.8－－分别是对M / A 的忠实度 0.1/0.2－－对 M / A 的转移特征 3) 在研究的时间段内，假定转移概率不会变， 即：系统无大变化（商业环境相差不大） 4) 转移概率值是统计数据得来的。 第一节 市场份额分析 凌晨: 凌晨:

凌晨: 第一节市场份额分析 状态转移概率 3、转移概率矩阵 令:P;=某周期i状态,下一个周期转移到j状 态的概率 则称 Pu p 0.90.1 P p21 p 0.20.8 为转移概率矩阵 意义:由转移概率矩阵,即可求出系统从某状态向 下一个状态转移的概率

Ling Xueling 二、状态转移概率 3、转移概率矩阵 令： p i j = 某周期 i 状态，下一个周期转移到 j 状 态的概率 则称 为转移概率矩阵 意义：由转移概率矩阵，即可求出系统从某状态向 下一个状态转移的概率。 第一节 市场份额分析 凌晨: 凌晨:         =        = 0.2 0.8 0.9 0.1 2 1 2 2 1 1 1 2 p p p p P

凌晨: 第一节市场份额分析 树形图研究系统的演变一一直观方法 1、方法 第0周第一周第二周 0.9 第二周之概率 0.1 09)(0.9)=0.81 0.9 去M 0.9)00.1)=0.09 0.2 (0.1)(0.2)=0.02 0.8 0.8 0.1)(0.8)=0.08 去A 系统在第二周去M(状态1)的概率:0.81+0.02=0.83 系统在第二周去A(状态2)的概率:0.09+0.08=0.17

Ling Xueling 三、树形图研究系统的演变－－直观方法 1、方法 系统在第二周去 M (状态1)的概率：0.81 + 0.02 = 0.83 系统在第二周去A (状态2) 的概率：0.09 + 0.08 = 0.17 。 第一节 市场份额分析 凌晨: 凌晨: 0.9 0.8 0.9 0.1 0.2 0.8 第一周 第二周 去M 去A 第0周 第二周之概率 (0.9)(0.9)=0.81 (0.9)(0.1)=0.09 (0.1)(0.2)=0.02 (0.1)(0.8)=0.08