序贯决策.ppt

1序贯序贯决策分析决策分析 1.多阶段决策多阶段决策2.序贯决策序贯决策3.马尔可夫决策马尔可夫决策2在经济管理活动中，由于某些问题的特殊性，需在经济管理活动中，由于某些问题的特殊性，需要将活动过程分为若干个相互联系的阶段，在它要将活动过程分为若干个相互联系的阶段，在它的每一个阶段都需要做出决策，从而使整个过程的每一个阶段都需要做出决策，从而使整个过程达到最好的活动效果。达到最好的活动效果。当各个阶段决策确定后，就组成了一个决策系列，当各个阶段决策确定后，就组成了一个决策系列，决定了整个过程的一条活动路线。决定了整个过程的一条活动路线。把一个问题看作是一个前后关联的具有链状结构把一个问题看作是一个前后关联的具有链状结构的多阶段过程就成为多阶段决策过程。的多阶段过程就成为多阶段决策过程。1.多阶段决策多阶段决策 1.1 多阶段决策问题多阶段决策问题 3多阶段决策的特点：多阶段决策的特点：决策者需要做出时间上有先后之别的多次决策；决策者需要做出时间上有先后之别的多次决策；前一次决策的选择将直接影响到后一次决策，后前一次决策的选择将直接影响到后一次决策，后一次决策的状态取决于前一次决策的结果；一次决策的状态取决于前一次决策的结果；决策者关系的是多次决策的总结果，而不是各次决策者关系的是多次决策的总结果，而不是各次决策的即时后果（全程最优）。决策的即时后果（全程最优）。1.1 多阶段决策问题多阶段决策问题 1.多阶段决策多阶段决策 4解决多阶段问题的主要方法：解决多阶段问题的主要方法：决策树方法；决策树方法；动态规划方法动态规划方法1.2 多阶段决策方法多阶段决策方法 多阶段决策分析的步骤：多阶段决策分析的步骤：根据具体问题适当划分阶段；根据具体问题适当划分阶段；确定各阶段的状态变量，寻找多阶段之间的联系；确定各阶段的状态变量，寻找多阶段之间的联系；由后到前用逆序法进行决策分析由后到前用逆序法进行决策分析1.多阶段决策多阶段决策 有关活动方案的决策方法决策树法 构成（三点两枝）：决策点：代表最后的方案选择 状态点：代表方案将会遇到的不同状态 结果点：代表每一种状态所得到的结果 方案枝：由决策点引出的线段，连接决策点和状态点，每一线段代表一个方案。概率枝：由状态点引出的线段，连接状态点和结果点。每一线段代表一种状态。1234 某厂为适应市场的需要，准备扩大生产能力，有两某厂为适应市场的需要，准备扩大生产能力，有两种方案可供选择：第一方案是建大厂；第二方案是先建种方案可供选择：第一方案是建大厂；第二方案是先建小厂，后考虑扩建。如建大厂，需投资小厂，后考虑扩建。如建大厂，需投资700700万元，在市场万元，在市场销路好时，每年收益销路好时，每年收益210210万元，销路差时，每年亏损万元，销路差时，每年亏损4040万万元。在第二方案中，先建小厂，如销路好，元。在第二方案中，先建小厂，如销路好，3 3年后进行扩年后进行扩建。建小厂的投资为建。建小厂的投资为300300万元，在市场销路好时，每年收万元，在市场销路好时，每年收益益9090万元，销路差时，每年收益万元，销路差时，每年收益6060万元，如果万元，如果3 3年后扩建，年后扩建，扩建投资为扩建投资为400400万元，收益情况同第一方案一致。未来市万元，收益情况同第一方案一致。未来市场销路好的概率为场销路好的概率为0.70.7，销路差的概率为，销路差的概率为0.30.3；如果前；如果前3 3年年销路好，则后销路好，则后7 7年销路好的概率为年销路好的概率为0.90.9，销路差的概率为，销路差的概率为0.10.1。无论选用何种方案，使用期均为。无论选用何种方案，使用期均为1010年，试做决策分年，试做决策分析。析。例题分析例题分析 这这是是一一个个多多阶阶段段的的决决策策问问题题，考考虑虑采采用用期期望望收收益益最最大大为为标标准准选择选择最最优优方案。方案。第一步，画出决策树图第一步，画出决策树图。145789623606060609090-40-40210210-40-40210210-40-40建大厂建大厂 建小厂建小厂 销路好销路好0.70.7 销路差销路差0.30.3 销路好销路好0.70.7 销路差销路差0.30.3 销路好销路好0.90.9 销路差销路差0.10.1 扩建扩建 不扩建不扩建 销路好销路好0.90.9 销路差销路差0.10.1 销路好销路好0.90.9 销路差销路差0.10.1 3 3年内年内 7 7年内年内 1227.51227.51247.51247.512951295-280-280895895420420895895609609 第二步，第二步，从右向左从右向左计计算各点的期望收益算各点的期望收益值值。点点4 4：2102100.90.97-407-400.10.17=12957=1295（万元）（万元）点点5 5：-40-407=-2807=-280（万元）（万元）点点2 2：129512950.7+2100.7+2100.70.73-2803-2800.3-400.3-400.30.33=1227.53=1227.5（万元）（万元）点点8 8：2102100.90.97-407-400.10.17-400=8957-400=895（万元）（万元）点点9 9：90900.90.97+607+600.10.17=6097=609（万元）（万元）点点6 6是个决策点，比是个决策点，比较较点点8 8和点和点9 9的期望收益，的期望收益，选择扩选择扩建。建。点点6 6：895895（万元）（万元）点点7 7：60607=4207=420（万元）（万元）点点3 3：8958950.7+2100.7+2100.70.73+4203+4200.3+600.3+600.30.33=1247.53=1247.5（万元）（万元）第三步，第三步，进进行决策。行决策。比比较较点点2 2和和点点3 3的的期期望望收收益益，点点3 3期期望望收收益益值值较较大大，可可见见，最最优优方方案案是是先先建建小小厂厂，如如果果销销路路好，好，3 3年以后再年以后再进进行行扩扩建。建。11某某公公司司考考虑虑是是否否花花费费4000元元钱钱从从某某科科研研机机构构购购买买某某项项技技术术，然然后后产产销销新新产产品品，如如果果买买技技术术，可可以以进进行行大大批批（a1）、中中批批（a2）或或小小批批生生产产（a3），可可能能出出现现的的市市场场情情况况也也分分为为畅畅销销、一一般般和和滞滞销销三三种种情情况况。其收益矩阵如表其收益矩阵如表1所示。所示。1.3 应用举例应用举例 1.多阶段决策多阶段决策 12为为了了更更准准确确地地了了解解市市场场，在在正正式式投投产产前前可可先先生生产产少少量量产产品品试试销销。由由于于要要增增添添少少量量生生产产设设备备等等原原因因，试试销销费费需需要要600元元。由由于于试试销销前前未未做做广广告告，顾顾客客对对产产品品不不太太了了解解，加加之之试试销销销销量量较较小小，试试销销结结果果很很不不准准确确。假假设设试试销销结结果果分分为为产产品品受受欢欢迎迎(H1）、一一般般(H2)和和不不受受欢欢迎迎(H3)三种，其准确度如表三种，其准确度如表21.多阶段决策多阶段决策 1.3 应用举例应用举例 13如不买此项技术，把这笔费用用在其他方面，在同如不买此项技术，把这笔费用用在其他方面，在同样的时期可获利样的时期可获利80008000元。那么，该公司应该如何元。那么，该公司应该如何决策？决策？（1 1）是否买技术？）是否买技术？（2 2）如果买技术，是否采取试销办法？）如果买技术，是否采取试销办法？（3 3）如果不试销，应大批生产，中批生产还是小批）如果不试销，应大批生产，中批生产还是小批生产？如果试销，又应该如何根据试销结果决定生产？如果试销，又应该如何根据试销结果决定其行动？其行动？1.3 应用举例应用举例 141.多阶段决策多阶段决策 1.3 应用举例应用举例 151.多阶段决策多阶段决策 1.3 应用举例应用举例 试销结果下的后验概率试销结果下的后验概率 16 某工厂现有10万元资金可供生产某种产品使用，生产过程有两个方案可供选择。方案1：每万元资金，每年可产生0.5万元的利润，年产量为2000吨。方案2：每万元资金，每年可产生0.2万元的利润，年产量为3000吨。每年可用一部分资金采取一种方案生产，另外一部分资金采取另一种方案进行生产，但一年内不变。假设前一年的利润可作为下一年的资金在两个方案间再行分配，但一个方案前一年的资金不得在下一年向另一方案转移。那么，为使四年内的总产量最高，该厂在这四年中应该如何分配资金？连续连续情形的情形的决策分析决策分析应用举例应用举例17有些决策问题，在进行决策后又产生一些新情况，有些决策问题，在进行决策后又产生一些新情况，需要进行新的决策，接着又有一些新的情况，有需需要进行新的决策，接着又有一些新的情况，有需要进行新的决策。这样决策、新情况、决策要进行新的决策。这样决策、新情况、决策，就，就构成一个系列，成为系贯决策。构成一个系列，成为系贯决策。多阶段决策的阶段数是确定的，序贯决策的阶段多阶段决策的阶段数是确定的，序贯决策的阶段数是不确定的，它依赖于执行决策过程中所出现的数是不确定的，它依赖于执行决策过程中所出现的状况。状况。决策方法：决策树决策方法：决策树2.序列决策序列决策 例例 设有某石油勘探队，在一片估计能出油的荒田钻探，可以先做地震试验，然后决定钻井与否。或者不做地震试验，只凭经验决定钻井与否。做地震试验的费用每次30000元，钻井费用为10000元。若钻井后出油，这井队可收入40000元；若不出油就没有任何收入。各种情况下出油的概率已估计出，并标在图上。问钻井队的决策者如何做出决策使收入的期望值为最大。图图 原决策树原决策树 203.1 马尔可夫决策问题马尔可夫决策问题 决策问题采取的行动已经确定，但将这个行动付诸实践的过程又分为几个时期。在不同的时期，系统可以处在不同的状态，而这些状态发生的概率又可受前面时期实际所处状态的影响。其中一种最简单、最基本的情形，是每一时期状态参数的概率分布只与这一时期的前一时期实际所处的状态有关，而与更早的状态无关，这就是所谓的马尔可夫链。利用马氏过程分析系统当前状态并预测未来状态的决策方法，称为马尔可夫决策。3.马尔可夫决策马尔可夫决策 21预测在本质上就是利用预测对象的历史数据去推预测在本质上就是利用预测对象的历史数据去推知预测对象的未来。知预测对象的未来。在经济管理现象中存在一种在经济管理现象中存在一种“无后效性无后效性”，即，即“系统在每一时刻的状态仅仅取决于前一时刻的状态，系统在每一时刻的状态仅仅取决于前一时刻的状态，而与其过去的历史无关。而与其过去的历史无关。”例如：池塘里有三张荷叶，编号为例如：池塘里有三张荷叶，编号为1，2，3，假设，假设有一只青蛙随机地在荷叶上跳来跳去，在初始时刻，有一只青蛙随机地在荷叶上跳来跳去，在初始时刻，它在它在2号荷叶上。在时刻，它有可能跳到号荷叶上。在时刻，它有可能跳到1号或者号或者3号荷叶上，也有可能原地不动。号荷叶上，也有可能原地不动。3.马尔可夫决策马尔可夫决策 3.1 马尔可夫决策问题马尔可夫决策问题 22把青蛙某个时刻所在的荷叶成为青蛙所处的状态，把青蛙某个时刻所在的荷叶成为青蛙所处的状态，这样，青蛙在未来处于什么状态，只与它现在所处的这样，青蛙在未来处于什么状态，只与它现在所处的状态无关，与它以前所处的状态无关。这种性质就是状态无关，与它以前所处的状态无关。这种性质就是所谓的所谓的“无后效性无后效性”，即马尔可夫（，即马尔可夫（Markov）性。）性。对于某些情况，知道预测对象的当前状态，希望由对于某些情况，知道预测对象的当前状态，希望由此推知预测对象的今后状态，如果这样的对象在状态此推知预测对象的今后状态，如果这样的对象在状态转移过程中满足马尔可夫性，则可以利用随机过程转移过程中满足马尔可夫性，则可以利用随机过程（stochastic process）的有关理论进行预测。这种预测）的有关理论进行预测。这种预测技术不需要太多的历史数据和资料，只需要预测对象技术不需要太多的历史数据和资料，只需要预测对象最近和当前的资料。最近和当前的资料。3.马尔可夫决策马尔可夫决策 3.1 马尔可夫决策问题马尔可夫决策问题 3.马尔可夫决策马尔可夫决策 23所谓马尔可夫链，就是一种随机时间系列，它在将来所谓马尔可夫链，就是一种随机时间系列，它在将来取什么值只与它现在的取值有关，而与它过去取什么值取什么值只与它现在的取值有关，而与它过去取什么值的历史情况无关，即无后效性。的历史情况无关，即无后效性。具备这个性质的离散性随机过程，称为马尔可夫链。具备这个性质的离散性随机过程，称为马尔可夫链。下面介绍几个有关的基本概念下面介绍几个有关的基本概念 3.马尔可夫决策马尔可夫决策 3.2 马尔可夫链与转移概率矩阵马尔可夫链与转移概率矩阵 3.马尔可夫决策马尔可夫决策 24定义定义1:设设随机时间系列随机时间系列 满足条件满足条件 每个随机变量每个随机变量Xn只取非负整数值。只取非负整数值。对任意的非负整数对任意的非负整数 3马尔可夫决策马尔可夫决策 3.2 马尔可夫链与转移概率矩阵马尔可夫链与转移概率矩阵 3.马尔可夫决策马尔可夫决策 25 随机过程 如果对任意 都存在则称 具有马尔可夫性。26有些经济现象本身就满足马尔可夫性。有些经济现象本身就满足马尔可夫性。比如，考察产品的销售情况时，产品销售比如，考察产品的销售情况时，产品销售从畅销转从畅销转而滞销而滞销或者从滞销转而畅销等显然只与其当前状态或者从滞销转而畅销等显然只与其当前状态有关；某产品的有关；某产品的市场占有率市场占有率发生变化，即进行状态发生变化，即进行状态转移时，也只与当前状态有关；转移时，也只与当前状态有关；机器设备从机器设备从待修到正常工作待修到正常工作或从正常工作到待修状或从正常工作到待修状态还是只与机器设备的当前状态有关等。当然也有态还是只与机器设备的当前状态有关等。当然也有很多经济现象不满足这种马尔可夫性。很多经济现象不满足这种马尔可夫性。在这种情况下，如能近似满足马尔可夫性，则也能在这种情况下，如能近似满足马尔可夫性，则也能采用这种预测方法。反之，就不能采用马尔可夫预采用这种预测方法。反之，就不能采用马尔可夫预测方法。测方法。3.马尔可夫决策马尔可夫决策 3.2 马尔可夫链与转移概率矩阵马尔可夫链与转移概率矩阵 定义定义：如果随机过程：如果随机过程 满足下述性质，满足下述性质，则称则称 是一个有限状态的马尔可夫链是一个有限状态的马尔可夫链（MarkovMarkov）。（1）具有有限种状态；（2）具有马尔可夫性；（3）转移概率具有平稳性。28定义定义2:状态转移概率状态转移概率3.2 马尔可夫链与转移概率矩阵马尔可夫链与转移概率矩阵 马尔可夫链的概率特性取决于条件概率马尔可夫链的概率特性取决于条件概率在概率论中，条件概率在概率论中，条件概率 表达了由状态表达了由状态B向状态向状态A转移的概率，简称为状态转移概率。转移的概率，简称为状态转移概率。的含义是，某系统在时刻的含义是，某系统在时刻m处于状态处于状态 Ei的条件下，时的条件下，时刻刻m+k处于状态处于状态Ej的概率。的概率。3.马尔可夫决策马尔可夫决策 29定义定义2 状态转移概率状态转移概率3.2 马尔可夫链与转移概率矩阵马尔可夫链与转移概率矩阵 3.马尔可夫决策马尔可夫决策 阴天阴天晴天晴天下雨下雨 晴天晴天 阴天阴天 下雨下雨晴天晴天 0.50 0.25 0.25阴天阴天 0.375 0.25 0.375下雨下雨 0.25 0.125 0.62531例题例题3.2 马尔可夫链与转移概率矩阵马尔可夫链与转移概率矩阵 某某地区地区有有A、B、C三家食品厂生产同一食品，有三家食品厂生产同一食品，有10000个用户（或购货点），假设在研究期间无新用户加入个用户（或购货点），假设在研究期间无新用户加入也无老用户退出，只有用户的转移。已知也无老用户退出，只有用户的转移。已知2007年年5月份月份有有5000户是户是A厂的顾客，厂的顾客，4000户是户是B厂的顾客，厂的顾客，1000户户是是C厂的顾客。厂的顾客。6月份，月份，A厂有厂有4000户原来的顾客，上户原来的顾客，上月的顾客有月的顾客有500户转到户转到B厂，厂，50户转到户转到C厂；厂；B厂有厂有3000户原来的顾客，上月的顾客有户原来的顾客，上月的顾客有200户转到户转到A厂，厂，800户户转到转到C厂；厂；C厂有厂有800户原来的顾客，上月的顾客有户原来的顾客，上月的顾客有100户转到户转到A厂，厂，100户转到户转到B厂。试计算其状态转移概率。厂。试计算其状态转移概率。3.马尔可夫决策马尔可夫决策 323.2 马尔可夫链与转移概率矩阵马尔可夫链与转移概率矩阵 3.马尔可夫决策马尔可夫决策 333.2 马尔可夫链与转移概率矩阵马尔可夫链与转移概率矩阵 3.马尔可夫决策马尔可夫决策 34状态转移概率矩阵状态转移概率矩阵3.2 马尔可夫链与转移概率矩阵马尔可夫链与转移概率矩阵 将考察对象从一个状态转移到另一个状态的转移概将考察对象从一个状态转移到另一个状态的转移概率按行组成一个矩阵，称此矩阵为状态转移概率矩率按行组成一个矩阵，称此矩阵为状态转移概率矩阵。其中称阵。其中称 为一步转移概率矩阵。为一步转移概率矩阵。3.马尔可夫决策马尔可夫决策 35一步转移概率矩阵具有性质：一步转移概率矩阵具有性质：3.2 马尔可夫链与转移概率矩阵马尔可夫链与转移概率矩阵 3.马尔可夫决策马尔可夫决策 36k步转移概率矩阵：步转移概率矩阵：3.2 马尔可夫链与转移概率矩阵马尔可夫链与转移概率矩阵 k步转移概率矩阵步转移概率矩阵的性质的性质：3.马尔可夫决策马尔可夫决策 37状态转移概率矩阵状态转移概率矩阵 3.马尔可夫决策马尔可夫决策 38例题：某经济系统有三种状态例题：某经济系统有三种状态 (比如畅销、比如畅销、一般、滞销一般、滞销)。系统状态转移情况见下表。试求系统。系统状态转移情况见下表。试求系统2步转移概率矩阵。步转移概率矩阵。3.2 马尔可夫链与转移概率矩阵马尔可夫链与转移概率矩阵 3.马尔可夫决策马尔可夫决策 393.2 马尔可夫链与转移概率矩阵马尔可夫链与转移概率矩阵 3.马尔可夫决策马尔可夫决策 3.3 3.3 稳态概率稳态概率称 为稳态概率。且因此我们可以从n n步转移矩阵的 极限取得稳态概率分布3.马尔可夫决策马尔可夫决策 此方程组为稳态方程 P的这一特性在实的这一特性在实用中有重要的价值。通常在市场预测中，所讨论的用户转移概率矩阵就属于标准概率矩阵，它可以通过几步转移达到稳定（平衡）状态。在这种情况下，各厂家的用户占有率不再发生变化，此时的称为最终用户的占有率P向量。向量。3.马尔可夫决策马尔可夫决策 马尔科夫决策方法马尔科夫决策方法 马马尔尔科科夫夫决决策策方方法法就就是是根根据据某某些些变变量量的的现现在在状状态态及及其其变变化化趋趋向向，来来预预测测它它在在未未来来某某一一特特定定期期间间可可能能出出现现的的状状态态，从从而而提提供供某某种种决策的依据。决策的依据。马马尔尔科科夫夫决决策策基基本本方方法法是是用用转转移移概概率率矩矩阵进行预测和决策。阵进行预测和决策。（1 1）转移概率矩阵中的元素是根据近期市场）转移概率矩阵中的元素是根据近期市场 或顾客的保留与得失流向资料确定的。或顾客的保留与得失流向资料确定的。（2 2）下一期的概率只与上一期的预测结果有）下一期的概率只与上一期的预测结果有 关，不取决于更早期的概率。关，不取决于更早期的概率。（3 3）利用转移概率矩阵进行决策，其最后结）利用转移概率矩阵进行决策，其最后结 果取决于转移矩阵的组成，不取决于原果取决于转移矩阵的组成，不取决于原 始条件，即最初占有率。始条件，即最初占有率。马尔科夫决策方法进行决策的特点：马尔科夫决策方法进行决策的特点：转移概率矩阵决策的应用步骤转移概率矩阵决策的应用步骤 1 1、建立转移概率矩阵。、建立转移概率矩阵。2 2、利用转移概率矩阵进行模拟预测。、利用转移概率矩阵进行模拟预测。3 3、求出转移概率矩阵的平衡状态，即稳、求出转移概率矩阵的平衡状态，即稳 定状态。定状态。4 4、应用转移概率矩阵进行决策。、应用转移概率矩阵进行决策。3.3 3.3 马尔可夫马尔可夫应用实例应用实例 例例 某生产商标为的产品的厂商为了与另外两个生产同类产品和的厂家竞争，有三种可供选择的措施：（1）发放有奖债券；（2）开展广告宣传；（3）优质售后服务。三种方案分别实施以后，经统计调查可知，该类商品的市场占有率的转移矩阵分别是 已知三种商标的商品的月总销售量为1000万件，每件可获利1元。另外，三种措施的成本费分别为150万，40万，30万。从长远利益考虑，生产商标为的产品的厂商应该采取何种措施？习题：习题：我国出口某种设备，在国际市场上的销售状况有两种：畅销和滞销。畅销每年可以获利100万元，滞销时每年仅获利30万元。以一年为一个时期，如果不采用广告推广产品或采取广告措施，状态的转移矩阵分别为如表1、表2所示。假定上一年处于畅销状态，每年的广告费为15万元。为了保证今后3年的利润最大化，是否应该采用广告措施？畅销滞销畅销0.80.2滞销0.40.6畅销滞销畅销0.90.1滞销0.70.3表表1 1 不不采取广告措施采取广告措施 表表2 2 采取采取广告措施广告措施