《运筹学决策论》PPT课件.ppt

第11章 决策论 Theory of Decision,11.1 决策分析的基本问题11.2 确定型和非确定型决策11.3 风险型决策 11.4 效用理论11.5马尔可夫决策,运 筹 学 Operations Research,11.1 决策分析的基本问题,决策(Decision Making)是一种对已知目标和方案的选择过程，当人们已知确定需实现的目标是什么，根据一定的决策准则，在供选方案中做出决策的过程。诺贝尔奖获得者西蒙认为，管理就是决策，他认为决策是对稀有资源备选分配方案进行选择排序的过程。学者Gregory在决策分析中提及，决策是对决策者将采取的行动方案的选择过程。决策科学包括决策心理学、决策的数量化方法、决策评价以及决策支持系统、决策自动化等。随着计算机和信息通信技术的发展，决策分析的研究也得到极大的促进，随之产生了计算机辅助决策支持系统（Decision Support System），许多问题在计算机的帮助下得以解决，在一定程度上代替了人们对一些常见问题的决策分析过程。,11.1 决策分析的基本问题,11.1.1 决策分析基本概念,决策 狭义决策认为决策就是作决定，单纯强调最终结果；广义决策认为将管理过程的行为都纳入决策范畴，决策贯穿于整个管理过程中。决策目标 决策者希望达到的状态，工作努力的目的。一般而言，在管理决策中决策者追求的当然是利益最大化。决策准则 决策判断的标准，备选方案的有效性度量。决策属性 决策方案的性能、质量参数、特征和约束，如技术指标、重量、年龄、声誉等，用于评价它达到目标的程度和水平。科学决策过程 任何科学决策的形成都必须执行科学的决策程序，如图11-1所示。决策最忌讳的就是决策者拍脑袋决策，只有经历过图11-1所示的“预决策决策决策后”三个阶段，才有可能产生科学的决策,11.1 决策分析的基本问题,11.1 决策分析的基本问题,调查研究,确定决策目标,搜集有关的信息资料,预测技术,预测未来的可能情况,拟订各种可行方案,可行性研究,方案评估,决策准则,方案选择,方案实施,预决策,决策,实施情况反馈意见,决策后,图11-1 科学决策过程,11.1 决策分析的基本问题,决策系统 状态空间、策略空间、损益函数构成了决策系统。状态空间 不以人的意志为转移的客观因素，设一个状态为Si，有m种不同状态，其集合记为：,S称状态空间，S的元素Si称为状态变量。策略空间 人们根据不同的客观情况，可能做出主观的选择，记一种策略方案为Ui，有n种不同的策略，其集合为：,U称为策略空间；U的元素Uj称为决策变量。损益函数 当状态处在Si情况下，人们做出Uj决策，从而产生的损益值Vij，显然Vij是Si，Uj的函数，即：,11.1 决策分析的基本问题,当状态变量是离散型变量时，损益值构成的矩阵叫损益矩阵,上述三个主要素组成了决策系统，决策系统可以表示为三个主要素的函数：,DD（S,U,V）,人们将根据不同的判断标准原则，求得实现系统目标的最优（或满意）决策方案。,11.1 决策分析的基本问题,11.1.2 决策分析基本原则,1.最优化（满意）原则2.系统原则3.可行性原则4.信息对称、准全原则,11.1.3 决策分析基本分类,表111,表112 程序化、非程序化、半程序化决策,11.1 决策分析的基本问题,下一节：确定型和非确定型决策,11.1 决策分析的基本问题,11.2 确定型和非确定型决策,11.2 确定型和非确定型决策,11.2.1 确定型决策,确定型决策是指决策的未来状态是已知的，只需从备选的决策方案中，挑选出最优方案。,【例11.1】某企业根据市场需要，需添置一台数控机床，可采用的方式有三种：甲方案：引进外国进口设备，固定成本1000万元，产品每件可变成本为12元；乙方案：用较高级的国产设备，固定成本800万元，产品每件可变成本为15元；丙方案：用一般国产设备，固定成本600万元，产品每件可变成本为20元；试确定在不同生产规模情况下的购置机床的最优方案。,【解】此题为确定型决策利用经济学知识，选取最优决策最优决策也就是在不同生产规模条件下，选择总成本较低的方案各方案的总成本线如图11.2,图11.2,TC甲F甲Cv甲Q100012QTC乙F乙Cv乙Q80015QTC丙F丙Cv丙Q60020Q,图中出现了A、B、C三个交点，其中A点经济意义：在A点采用甲方案与丙方案成本相同TC甲TC丙，F甲Cv甲QAF丙Cv丙QA,Q50,11.2 确定型和非确定型决策,同理：B点TC乙TC丙，F乙Cv乙QBF丙Cv丙QB,C点：TCL甲TC乙，F甲Cv甲QCF乙Cv乙QC,B点经济意义为：当生产40万件时，采用乙方案和采用丙方案成本相同均为1400万元,图11.2,11.2 确定型和非确定型决策,得到生产规模最优方案为：当生产规模产量小于40万件时，采用丙方案；当生产规模产量大于40万件，小于200/3万件时，采用乙方案；当生产规模产量大于200/3万件时，采用甲方案,其经济意义为：当生产规模为万件时，采用甲、乙方案成本相同从图中可知：当生产规模QB时，采用丙方案；当QB 生产规模 QC时，采用乙方案；当QC 生产规模时，采用甲方案,图11.2,11.2 确定型和非确定型决策,11.2.2 非确定型决策,（1）状态空间 是指不以人的意志为转移的客观因素，设一个状态为Si，有m种不同状态，其集合记为：,S 称状态空间；S的元素Si称为状态变量,由于在非确定决策中，各种决策环境是不确定的，所以对于同一个决策问题，用不同的方法求值，将会得到不同的结论，在现实生活中，同一个决策问题，决策者的偏好不同，也会使得处理相同问题的原则方法不同,（2）策略空间 是指人们根据不同的客观情况，可能做出主观的选择，记一种策略方案为Ui，有n种不同的策略，其集合,11.2 确定型和非确定型决策,U 称为策略空间；U的元素Uj称为决策变量,（3）损益函数 是指当状态处在Si情况下，人们做出Uj决策，从而产生的损益值Vij，显然Vij是Si、Uj的函数，即,当状态变量是离散型变量时，损益值构成的矩阵叫损益矩阵,11.2 确定型和非确定型决策,或简记为,上述三个主要素组成了决策系统，决策系统可以表示为三个主要素的函数：,DD（S,U,V）,常用的非确定型准则有5种：1.悲观准则2.乐观准则3.折衷法、实用主义准则4.等可能性准则5.最小机会损失（后悔）准则,11.2 确定型和非确定型决策,【例11.2】某公司为经营业务的需要，决定要在现有生产条件不变的情况下，生产一种新产品，现可供开发生产的产品有I、II、III、IV四种不同产品，对应的方案为A1,A2,A3,A4由于缺乏相关资料背景，对产品的市场需求只能估计为大中小三种状态，而且对于每种状态出现的概率无法预测，每种方案在各种自然状态下的效益值表，如表11.3所示,表11.3 效益值表(单位：万元),11.2 确定型和非确定型决策,（1）小中取大法（悲观主义准则maxmin）,则对应的A4方案为决策方案，即生产产品IV,策略值为,11.2 确定型和非确定型决策,(2)大中取大法（乐观主义准则maxmax）,则对应的A1方案为决策方案，即生产产品I,策略值为,11.2 确定型和非确定型决策,（3）最小机会损失准则（Minimax regret criterion）,编制机会损失表:,找出每个方案的最大机会损失Zi:,选择最小的机会损失值:,对应的方案l即为所决策方案,则应选对应的A2方案为决策方案，即生产产品,11.2 确定型和非确定型决策,策略值为,（4）等可能性决策准则(Equal likelihood criterion),则应选择对应的A1方案为决策方案，即生产产品I,11.2 确定型和非确定型决策,(5)折衷法，现实主义准则(Hurwicz criterion),max min法是当0时状态，max max是1时状态,原则：决策者给出乐观系数 则说明决策者越接近悲观；则说明决策者越接近乐观,则应选择对应的决策方案A4，即生产产品IV。,11.2 确定型和非确定型决策,下一节：风险型决策,11.2 确定型和非确定型决策,作业：教材P268 T1、2,11.3 风险型决策,11.3 风险型决策,风险型决策是指每种自然状态出现的概率大体可以估计，并可算出在不同状态下的效益值.,期望值准则(Expected value criterion),求效益期望值EMV。效益期望值条件效益值概率，即,选择最大效益期望值所对应的方案为决策方案,1.最大效益期望值准则,11.3 风险型决策,【例11.3】某电讯公司决定开发新产品，需要对产品品种做出决策，有三种产品A1，A2，A3可供生产开发。未来市场对产品需求情况有三种，即较大、中等、较小，经估计各种方案在各种自然状态下的效益值，见表115各种自然状态发生的概率分别为0.3，0.4和0.3那么工厂应生产哪种产品，才能使其收益最大。,表115 效益表(单位：万元),11.3 风险型决策,【解】效益的期望值表如下,因此选择相应方案，即开发A1产品。,求每个方案的期望后悔值，最小期望后悔值对应的方案即为所选方案。求解过程留给同学们作练习。,除了前面7种决策准则外，还有完全信息期望值准则(EVPI:Expected value of perfect information)样本信息期望值准则Expected value of sample information(EVSI)完全信息后悔值期望值准则Expected regret value of perfect information,2 最小期望后悔值准则(Expected regret value),11.3 风险型决策,11.3 风险型决策,决策树法（Decision Tree）,决策树是由决策点、事件点及结果构成的树形图，一般应用于序列决策中。,:表示决策点，也称为树根，由它引发的分枝称之为方案分枝，方案节点被称为树枝n条分枝表示有n种供选方案,:表示策略点，其上方数字表示该方案的最优收益期望值，由其引出的m条线称为概率枝表示有m种自然状态，其发生的概率已标明在分枝上,：表示每个方案在相应自然状态的效益值,：表示经过比较选择此方案被删除掉了，称之为剪枝,方法：根据题意作出决策树图；,从右向左计算各方案期望值，并进行标注；,对期望值进行比较，选出最大效益期望值，写在上方，表明其所对应方案为决策方案，同时在其它方案上打上 删除,H,H1,Hi,Hm,E(H1),E(Hi),E(Hm),V11,V1j,V1n,Vi1,Vij,Vin,Vm1,Vmj,Vmn,pj,pn,p1,pj,pn,p1,pj,pn,图143 决策树图,maxE(Hi),11.3 风险型决策,【例11.4】某厂决定生产某产品，要对机器进行改造投入不同数额的资金进行改造有三种方法，分别为购新机器、大修和维护，根据经验,销路好发生的概率为0.6相关投入额及不同销路情况下的效益值如表11.6所示，请选择最佳方案,表11.6 效益值表(单位：万元),11.3 风险型决策,解 根据题意，作出决策树，见图114 计算各方案的效益期望值：,最大值为,选对应方案A3，即维护机器，并将A1，A2剪枝,11.3 风险型决策,A,0.8,A1,A2,A3,-5,-0.8,0.8,25,好0.6,-20,20,-12,15,-8,不好0.4,图144 决策树图,好0.6,不好0.4,好0.6,不好0.4,购新,大修,维护,11.3 风险型决策,多级决策问题,【例11.5】某公司由于市场需求增加，使得公司决定要扩大公司规模，供选方案有三种：第一种方案，新建一个大工厂，需投资250万元；第二种方案，新建一个小工厂，需投资150万元；第三种方案，新建一个小工厂，2年后若产品销路好再考虑扩建，扩建需追加120万元，后3年收益与新建大工厂间如表11.7所示，根据预测该产品前三年畅销和滞销的概率分别为0.6，0.4若前2年畅销，则后3年畅销后滞销概率为0.8，0.2；若前2年滞销，则后3年一定滞销请对方案做出选择,11.3 风险型决策,表11.7 效益值(单位：万元),解（1）画决策树,11.3 风险型决策,畅销0.8,150,滞销0.2,-50,5,330,6,-150,滞销1,-50,2,28,畅销0.6,滞销0.4,畅销0.8,80,滞销0.2,20,7,204,8,60,滞销1,20,3,108.4,畅销0.6,滞销0.4,畅销0.8,150,滞销0.2,-50,210,12,204,11,210,扩建,不扩建,9,畅销0.8,滞销0.2,80,20,4,10,20,滞销1,畅销0.6,滞销0.4,60,后3年,前2年,1,112,大工厂,小工厂,先小后大,112,图1111 决策树图,解（1）画决策树,120,150,150,250,比较方案,E(4)最大，则取最大值112，对应的方案是先小后大作为选定方案，即先建小厂，后扩建大工厂的方案为最终方案,11.3 风险型决策,11.3.3 贝叶斯决策Bayesian Decision,开始人们对原来的状态参数提出某一概率分布。后来通过调查又获得许多信息，只要原来信息不是错误的，则应该用后来的补充信息修正原来的认识。用补充的情报改进原来的概率分布。,将依据过去的信息或经验由决策者估计的概率称之为主观概率,未收到新信息时根据已有信息和经验，估计出的概率分布称为先验概率；用随机试验确定出的概率称为客观概率收到新信息,修正后的概率分布称为后验概率事件B已经发生的条件下，事件A发生的概率，称为事件A在给定B下的条件概率,贝叶斯公式：,若A1、A2、构成一个完备事件，P（Ai)0,则对任何概率不为零的事件B，有,11.3 风险型决策,更一般地,此公式为后验概率,11.3 风险型决策,例如，根据以往的经验，产品需求量的概率为,产品进入市场2个月的试销后，需求量的样本信息(比例)为,贝叶斯公式：,若A1、A2、构成一个完备事件，P（Ai)0,则对任何概率不为零的事件B，有,11.3 风险型决策,【例】盒子里有100枚均匀的硬币，有60枚是正常的，40枚两面都是徽。从盒子中任取一枚让你猜是哪一类硬币。猜中得5元，猜不中不得钱。你猜是哪一类？,获利的期望值V(A1)=53/5+02/5=3V(A2)=03/5+52/5=2,正确的决策是：应该选择猜正常,11.3 风险型决策,如果现在抛掷3次，3次都出现徽，你又如何猜？该硬币是正常的概率为多少，是双徽的概率为多少。,设H为3次出现反面这一随机事件，B1为硬币是正常，B2为硬币是双徽，则,3次都出现双徽的概率为：,11.3 风险型决策,用后验概率代替原来的概率，决策矩阵为：,获利的期望值V(A1)=53/19+02/5=15/19V(A2)=03/5+516/19=80/19,正确的决策是：应该选择猜双徽,11.3 风险型决策,根据过去经验可知当自然状态为Nj条件下调查结果为Zk的条件概率,再利用贝叶斯公式和全概率公式，求当结果为ZK的条件下自然状态为Nj的条件概率,11.3 风险型决策,在后验分析中用,代替先验分析中的P（Nj），利用期望值准则计算出Ek,再根据全概率公式，可知结果为Zk的概率为,因此，后验分析的效益期望值为,11.3 风险型决策,当状态只有两个时，后验概率及期望收益可用快捷公式计算。记先验概率向量为P，条件概率矩阵为A，后验概率矩阵为B，收益矩阵为V，有,则先验收益期望值向量为EMV1PTV后验收益期望值矩阵为EkBV,11.3 风险型决策,【例11.6】某厂对一台机器的换代问题做决策，有三种方案：A1为买另一台新机器；A2为对老机器进行改建；A3是维护加强输入不同质量的原料，三种方案的收益见表11.8约有30%的原料是质量好的，还可以花600元对原料的质量进行测试，这种测试可靠性见表11.9求最优方案,11.3 风险型决策,表11.9 测试可靠性,表11.8 收益表(单位：万元),11.3 风险型决策,【解】（1）若不做测试，各方案的先验收益,应选方案3，维护老机器。,(2)计算后验概率,已知,联合概率为：,11.3 风险型决策,边际概率为,代入（11.2）从而可得后验概率,11.3 风险型决策,则有,即当测试结果为原料的质量好，则购买新机器；若测试结果为原材料的质量差，则维护老机器。,决策为：应花600元进行测试，测试后若质量好，购入新机器生产；若质量差，维护老机器生产,【例】石油开发决策问题,11.3 风险型决策,11.3 风险型决策,P(Finding 勘探结果|State自然状态),勘探好的概率：P(F)=P(O)*P(F|O)+P(D)*P(F|D)=0.60.8+0.40=0.48,勘探好的概率：P(U)=P(O)*P(U|O)+P(D)*P(U|D)=0.60.2+0.41=0.52,勘探好时有油的概率P(O|F)=P(O)*P(F|O)/P(O)*P(F|O)+P(D)*P(F|D)=0.60.8/0.48=1,勘探好时干涸的概率P(D|F)=P(D)*P(F|D)/P(O)*P(F|O)+P(D)*P(F|D)=0.40/0.48=0,勘探不好时有油的概率P(O|U)=P(O)*P(U|O)/P(O)*P(U|O)+P(D)*P(U|D)=0.60.2/0.52=0.2037,勘探不好时干涸的概率P(D|U)=P(D)*P(U|D)/P(O)*P(U|O)+P(D)*P(U|D)=0.41/0.52=0.7692,0.48,0.52,1,0.230769,0,0.769231,决策树参看文件：DATAchpt11ch11.xls,下一节：效用理论,作业：教材P269 T37,11.3 风险型决策,11.4 效用理论Utility Theory,11.4.1 效用,贝努利(D.Berneulli)首次提出效用概念，他用图11.7表示出人们对钱财的真实价值的考虑与其钱财拥有量之间有对数关系效用是一种相对的指标值，它的大小表示决策者对于风险的态度，对某事物的倾向、偏差等主观因素的强弱程度用于量度决策者对于风险的态度.,效用U,货币M,图117 贝努利效用曲线,11.4 效用理论Utility Theory,【例】（1）方案A1；稳获100元。方案B1：用抛掷硬币的方法，猜对得250元，猜错不得钱。,（2）方案A2；稳获100元。方案B2：用抛掷硬币的方法，直到出现正面为止，第n 次出现正面得到2n元。,大多数选择A1、A2.通过计算有,E(B1)E(A1)，E(B2)E(A2),一般来说效用值在0,1之间取值.凡是决策者最看好、最倾向、最愿意的事物（事件）的效用值可取1；反之，效用值取0当各方案期望值相同时，一般用最大效用值决策准则，选择效用值最大的方案,11.4 效用理论Utility Theory,通过效用指标将某些难于量化、有质的区别的事件给予量化，得到各方案的综合效用值，选择效用值最大的方案作为决策准则。,11.4.2 效用曲线,确定效用曲线的基本方法有两种：一种是直接提问法，需要决策者回答提问，主观衡量应用较少；第二种是对比提问法，此法使用较多,设现有A0，A1两种方案供选A0表示决策者不需要花费任何风险可获益x0；而A1有两种自然状态，可以概率P获得收益x1，以概率（1P）获得收益x2；且x1x0 x2,令yi表示效益xi的效用值则x0，x1，x2的效用值分别表示为y0，y1，y2 若在某条件下，决策者认为A0,A1两方案等价，则有：,11.4 效用理论Utility Theory,4个数p，x0，x1，x2中给定3个，提问第4个变量由决策者确定，求出效用值。,一般采用改进VM(Von NeumannMorgenstern)方法，固定P0.5，x1，x2改变x0三次，得出相应的y的值，确定三点，作出效用曲线,11.4 效用理论Utility Theory,【例11.7】x1=100，x2=400,取y(x1)=0,y(x2)=1,-100,400,第一次提问：x0为何值时，上式成立？答：“0”,y(0)=0.50+0.510.5,1,(0,0.5),第二次提问：x0为何值时，上式成立？答：“200”,y(200)=0.5y(0)+0.51=0.50.5+0.510.75,第三次提问：x0为何值时，上式成立？答：“100”,y(100)=0.5y(0)+0.5y(200)=0.50.5+0.50.750.625,(200,0.75),(100,0.625),100,200,300,0,11.4 效用理论Utility Theory,不同决策者对待风险态度不同，因而会得到不同形状的效用曲线一般可分为保守型、中间型、风险型，如下图,y,1,I,II,x,(Xmax,1),(Xmin,0),Xmax,Xmin,0,11.4.3 效用曲线类型,图中I为保守型，其特点为：当收益值较小时，效用值增加较快；随收益值增大时，效用值增加速度变慢，表明决策者不求大利，谨慎小心，保守,图中II为中间型，其特点为：收益值和效用值成正比，表明决策者完全按机遇办事，心平气和,图中III为风险型，其特点为与I保守型恰好相反，当收益值较小时，效用值增加较慢；随收益值增大时，效用值增加速度变快，表明决策者对增加收益反应敏感，愿冒较大风险，谋求大利，不怕冒险,III,11.4 效用理论Utility Theory,常用的效用函数：,11.4 效用理论Utility Theory,11.4.4 效用值的应用,【例11.8】若某决策问题的决策树如下图所示，其决策者的效用期望值同时附在效益期望值后，请做出决策,E(2)=0.53000.5(200)=50 E(3)0.52000.5(100)=50,根据最大效益期望值准则，无法判断优劣,y2=0.510.500.5，y3=0.50.9+0.50.3=0.6,解：(1）计算效益期望值分别为,11.4 效用理论Utility Theory,A2方案效用值A1方案效用值，因此取A2方案为决策方案绘制效用曲线图见下图，可知，该决策者偏向于保守型，不求大利，谨慎小心,11.4 效用理论Utility Theory,-200,300,1,0,100,200,-100,y,x,11.5 马尔可夫决策 Markov Decision,11.5马尔可夫决策 Markov Decision,11.5.1 马尔可夫链,用X(t)表示随机系统在时刻t 的状态，状态序列,为一随机过程，如果系统当前的转移概率只与当前的运行状态有关，而与以前的状态无关，即：对随机过程,若对任意的0t1t2tntn+1及tiT，X（tn+1）关于X（t1）,X（tn）的条件概率恰好等于X（tn+1）关于X（tn）的条件概率，用数学符号表示为：,则称 具有马尔可夫性随机过程称为马尔可夫过程。,所有可能的全体取值称为过程的状态空间。,若马氏过程的状态空间为非负整数集E0，1，2，称为马氏链。例如，今天下雨这一状态用“0”表示，不下雨用“1”表示，则状态空间为 E0，1。天气变化过程符合马Markov性。,11.5.2 转移概率,记Pij为从状态X(n)=i转移到下一个状态X（n+1）=j 的概率，一步转移概率矩阵为,11.5马尔可夫决策 Markov Decision,【例11.9】有3家电器公司分别生产三种不同牌子的空调。各自开展广告攻势促销本公司产品。各公司所占的市场比例是随时间变化的。XXn，n0构成一个以E1,2,3为 状态空间的Markov链。假设在任一时刻，公司1能留住它的1/2的老顾客，其余的则对半购买另两个公司的产品；公司2的一半顾客能留下，其余转向公司1；公司3有3/4能留下，其余流向公司2。Markov链的转移概率矩阵和转移图：,1/2,1/4,1/4,1/2,1/2,1/4,3/4,11.5马尔可夫决策 Markov Decision,求n期后公司i的市场占有率，n时的市场占有率。,记Pj(n)=P(Xn=j)为Markov链X时刻n处于状态j的概率，P为初始分布。,【定理】XXn，n0为一个Markov链，则有,对任意m，n0，有,对任意i，jE，有,此方程称为Champan-Kolmogorov方程，简称CK方程,11.5.3 转移状态,11.5马尔可夫决策 Markov Decision,【例11.10】假设3个公司开始的市场占有率为(0.3，0.35，0.35),求5个月后的市场占有率(状态)。,【解】P0(0.3，0.35，0.35),11.5马尔可夫决策 Markov Decision,遍历性：如果一个齐次的马尔可夫链X(n),n=1,2,的n步转移概率为Pij(n)，对于一切状态i,j，存在着不依赖于初始状态i的常数Pj，使得,成立，则称此马尔可夫链具有遍历性也就是说，一个具有遍历性的马尔可夫链，当转移的次数n极大时，此系统转移到状态j的概率为一个常数Pj，而与初始状态无关,求,【引理】设m 阶矩阵P具有m个线性无关的特征向量 B(b1,b2,bm)对应的特征值为1，2，m，则B可逆且有PBB1，Pn=BnB1.其中diag(1，2，m),11.5马尔可夫决策 Markov Decision,上例中，求Pn及,求转移概率矩阵P的特征值及特征向量。由|IP|=0得,特征值及特征向量矩阵为,11.5马尔可夫决策 Markov Decision,则有,11.5马尔可夫决策 Markov Decision,长期后市场占有率各占1/3,由,得,解方程得到稳定状态的概率G,11.5马尔可夫决策 Markov Decision,【例11.10】设某公司有两种状态：1和2，1为盈利，2为亏损当其处于1时，下一年仍为1的概率是1/2，因此下一年转为2的概率也是1/2当公司处于状态2时，下一年经过努力回到状态1的概率为2/5，仍处于亏损状态的概率为3/5若公司现处于状态1，问经过n年后该公司处于状态1和2的概率各是多少？,解：显然，系统有两个状态，设S为状态空间，则：S=i,j=1,2此处，p11=1/2,p12=1/2,p21=2/5,p22=3/5因此,设G(g1，g2)，由GGP,11.5马尔可夫决策 Markov Decision,设G(g1，g2)，由GGP,11.5马尔可夫决策 Markov Decision,11.5.4 收益预测模型,设系统在第n个时期处于状态X(n)=i，转移到过程终结时的总期望收益为,rij 表示从状态X(n)=i 转移到下一个状态X（n+1）=j 相应的收益，则有：,n表示从第n个时期到过程终结的决策规则的序列,其中n为第n个时期的决策规则，,11.5马尔可夫决策 Markov Decision,q(i)表示由状态i 作一次转移的期望报酬，即状态的即时期望报酬则,令,或,11.5马尔可夫决策 Markov Decision,若记数从末端开始，上式的逆序写法为：,则,11.7马尔可夫决策 Markov Decision,11.7马尔可夫决策 Markov Decision,【例】商品的转移概率矩阵和利润表如下,转移概率表,利润表(万元),q1=0.550+0.51030，q2=0.420+0.6(20)4,6期利润预测,11.5.5 最优策略模型,Markov决策由五重组来描述：1.状态 i 2.策略集，状态i 的策略规则为 3.转移概率矩阵P 4.报酬，状态i 的策略规则为 转移到状态j 的报酬为 期望即时报酬为 5.目标函数V(n),11.5马尔可夫决策 Markov Decision,Markov决策（MD）描述,在某一时刻（阶段）随机变量X处于状态i，决策者选择某个策略使目标最优。,MD常用的目标有3种：1.有限阶段目标；2.折扣目标；3.平均目标,有限阶段目标最大。通过Z变换：,11.5马尔可夫决策 Markov Decision,记,i=1,2,m(11.18),解方程组求出变量 fi 与 v,采用迭代计算：（1）选择一个初始策，每一个状态i（i=1，2，m）选择一个决策规则 使其决策，令n=0；,(2)对已知策略，令，求解方程组(11.18)，得相应的策略获利v（n）和相对值 f（n），（i=1,2,m；n=0,1,2）；,11.5马尔可夫决策 Markov Decision,（3）应用上一策略已求得的，寻求一个新的策略规则 n+1，对每一个状态i，使,由此得新的策略,（4）若所得策略 与前次迭代所得策略 完全相等，则停止迭代，已得到了最优策略；否则回到步骤2，令n=n+1,11.5马尔可夫决策 Markov Decision,【例11.12】某水泥厂有一台窑炉处于两种运行状态，即运转和故障，窑炉工人每年定期检查设备一次若窑炉正常则选择维护或不维护；若窑炉故障则选择大修或常规维修，其转移概率与相应的报酬如下表，试求该厂应采取的最佳策略使在无限期的未来每年所获平均收入最大,表11.12 转移概率和报酬,11.5马尔可夫决策 Markov Decision,【解】此问题共有两种状态，每个状态有两种决策，因此共有四种可行决策。,为运转时不维护；,为运转时维护；,为故障时大修；,为故障时进行常规维修,(1)选取初始策略,即当运转时不维护,而故障时大修，则有,11.7马尔可夫决策 Markov Decision,11.5马尔可夫决策 Markov Decision,(2)开始定值运算，并估计初始策略,令f2=0，解上述方程组，得v（0）=13.85，,(3)进入策略改进程序，求改进策略对状态1，寻求策略,使,选取决策,，当窑炉运转，采取维护策略，,对状态2，寻求新策略,使,选取决策，当窑炉故障时，采取大修策略,求得改进策略为：,策略 与 策略不同，所以还没有得到最优策略，须继续迭代,11.5马尔可夫决策 Markov Decision,(4)再进行定值运算求,解方程得：v（1）=37.96，,(5)寻求改进策略，,对状态1，有：,仍取策略,11.5马尔可夫决策 Markov Decision,对状态2，有：,仍取策略,因此得到：,这与前一次迭代结果完全一样，因而求得了最优策略即为：运转时的决策是进行维护，故障时进行大修，工厂未来每年期望报酬为37.96万元,11.5马尔可夫决策 Markov Decision,11.5马尔可夫决策 Markov Decision,作业：教材P269 T8、9、10,The End of Chapter 11,2,3,1,现在扩建,明年扩建,5.7,(0.655),4.9,(0.655),0.2,0.5,0.3,0.2,0.5,0.3,10,8,-1,8,6,1,(1),(0.9),(0),(0.9),(0.8),(0.25),习题11.4,习题11.5,1,2,3,摸球,不摸球,0,白：0.45,红：0.55,4,5,蓝：0.70,绿：0.30,10,11,50,0,12,13,50,0,蓝：0.10,绿：0.90,6,8,7,9,第2次摸球,第2次摸球,不摸球,不摸球,10,10,10,0,0,25,5,25,0,1.25,1.25,