运筹学决策论精品文稿.ppt

《运筹学决策论精品文稿.ppt》由会员分享，可在线阅读，更多相关《运筹学决策论精品文稿.ppt（94页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学决策论第1页，本讲稿共94页11.1 决策分析的基本问题决策分析的基本问题第2页，本讲稿共94页决策决策(Decision Making)是一种对已知目标和方案的选择过程，是一种对已知目标和方案的选择过程，当人们已知确定需实现的目标是什么，根据一定的决策准则，当人们已知确定需实现的目标是什么，根据一定的决策准则，在供选方案中做出决策的过程。诺贝尔奖获得者西蒙认为，管在供选方案中做出决策的过程。诺贝尔奖获得者西蒙认为，管理就是决策，他认为决策是对稀有资源备选分配方案进行选择理就是决策，他认为决策是对稀有资源备选分配方案进行选择排序的过程。学者排序的过程。学者Gregory在决策分析中提及，

2、决策是对决在决策分析中提及，决策是对决策者将采取的行动方案的选择过程。策者将采取的行动方案的选择过程。决策科学包括决策心理学、决策的数量化方法、决策评价以决策科学包括决策心理学、决策的数量化方法、决策评价以及决策支持系统、决策自动化等。及决策支持系统、决策自动化等。随着计算机和信息通信技术的发展，决策分析的研究也得到随着计算机和信息通信技术的发展，决策分析的研究也得到极大的促进，随之产生了计算机辅助决策支持系统（极大的促进，随之产生了计算机辅助决策支持系统（Decision Support System），许多问题在计算机的帮助下得以解决，在一），许多问题在计算机的帮助下得以解决，在一定程度上

3、代替了人们对一些常见问题的决策分析过程。定程度上代替了人们对一些常见问题的决策分析过程。11.1 决策分析的基本问题决策分析的基本问题第3页，本讲稿共94页11.1.1 决策分析基本概念决策分析基本概念决策决策 狭义决策认为决策就是作决定，单纯强调最终结果；广义狭义决策认为决策就是作决定，单纯强调最终结果；广义决策认为将管理过程的行为都纳入决策范畴，决策贯穿于整个管决策认为将管理过程的行为都纳入决策范畴，决策贯穿于整个管理过程中。理过程中。决策目标决策目标 决策者希望达到的状态，工作努力的目的。一般而言，决策者希望达到的状态，工作努力的目的。一般而言，在管理决策中决策者追求的当然是利益最大化。

4、在管理决策中决策者追求的当然是利益最大化。决策准则决策准则 决策判断的标准，备选方案的有效性度量。决策判断的标准，备选方案的有效性度量。决策属性决策属性 决策方案的性能、质量参数、特征和约束，如技术指决策方案的性能、质量参数、特征和约束，如技术指标、重量、年龄、声誉等，用于评价它达到目标的程度和水平。标、重量、年龄、声誉等，用于评价它达到目标的程度和水平。科学决策过程科学决策过程 任何科学决策的形成都必须执行科学的决策程序，任何科学决策的形成都必须执行科学的决策程序，如图如图11-1所示。决策最忌讳的就是决策者拍脑袋决策，只有经历所示。决策最忌讳的就是决策者拍脑袋决策，只有经历过图过图11-1

5、所示的所示的“预决策预决策决策决策决策后决策后”三个阶段，才有可能三个阶段，才有可能产生科学的决策产生科学的决策 11.1 决策分析的基本问题决策分析的基本问题第4页，本讲稿共94页11.1 决策分析的基本问题决策分析的基本问题调查研究调查研究 确定决策目标确定决策目标搜集有关的信息资料搜集有关的信息资料预测技术预测技术预测未来的可能情况预测未来的可能情况拟订各种可行方案拟订各种可行方案可行性研究可行性研究方案评估方案评估决策准则决策准则方案选择方案选择方案实施方案实施预预决决策策决决策策实实施施情情况况反反馈馈意意见见决策后决策后图图11-1 科学决策过程科学决策过程第5页，本讲稿共94页1

6、1.1 决策分析的基本问题决策分析的基本问题决策系统决策系统 状态空间、策略空间、损益函数构成了决策系统。状态空间、策略空间、损益函数构成了决策系统。状态空间状态空间 不以人的意志为转移的客观因素，设一个状态为不以人的意志为转移的客观因素，设一个状态为Si，有，有m种不同状态，其集合记为：种不同状态，其集合记为：S称状态空间，称状态空间，S的元素的元素Si称为状态变量。称为状态变量。策略空间策略空间 人们根据不同的客观情况，可能做出主观的选择，人们根据不同的客观情况，可能做出主观的选择，记一种策略方案为记一种策略方案为Ui，有，有n种不同的策略，其集合为：种不同的策略，其集合为：U称为策略空间

7、；称为策略空间；U的元素的元素Uj称为决策变量。称为决策变量。损益函数损益函数 当状态处在当状态处在Si情况下，人们做出情况下，人们做出Uj决策，从而产生的决策，从而产生的损益值损益值Vij，显然，显然Vij是是Si，Uj的函数，即：的函数，即：第6页，本讲稿共94页11.1 决策分析的基本问题决策分析的基本问题当状态变量是离散型变量时，损益值构成的矩阵叫损益矩阵当状态变量是离散型变量时，损益值构成的矩阵叫损益矩阵 上述三个主要素组成了决策系统，决策系统可以表示为三个主上述三个主要素组成了决策系统，决策系统可以表示为三个主要素的函数：要素的函数：DD（S,U,V）人们将根据不同的判断标准原则，

8、求得实现系统目标的最优人们将根据不同的判断标准原则，求得实现系统目标的最优（或满意）决策方案。（或满意）决策方案。第7页，本讲稿共94页11.1 决策分析的基本问题决策分析的基本问题11.1.2 决策分析基本原则决策分析基本原则1.最优化（满意）原则最优化（满意）原则2.系统原则系统原则3.可行性原则可行性原则4.信息对称、准全原则信息对称、准全原则第8页，本讲稿共94页11.1.3 决策分析基本分类决策分析基本分类表表111按影响范围按影响范围战略决策、战役决策、战术决策战略决策、战役决策、战术决策按状态空间按状态空间确定型决策、非确定型决策、风险型决策确定型决策、非确定型决策、风险型决策按

9、决策时间按决策时间程序化决策、半程序化决策、非程序化决策程序化决策、半程序化决策、非程序化决策按描述方法按描述方法定性化决策、定量化决策定性化决策、定量化决策按目标数量按目标数量单目标决策、多目标决策单目标决策、多目标决策按连续性按连续性单级决策、序贯决策单级决策、序贯决策按决策者数量按决策者数量个人决策、群决策个人决策、群决策按问题大小按问题大小宏观决策、微观决策宏观决策、微观决策表表112 程序化、非程序化、半程序化决策程序化、非程序化、半程序化决策决策类型决策类型传统方法传统方法现代方法现代方法程序化程序化现有的规章制度现有的规章制度运筹学、管理信息系统（运筹学、管理信息系统（MIS）半

10、程序化半程序化经验、直觉经验、直觉灰色系统、模糊数学等方法灰色系统、模糊数学等方法非程序化非程序化经验、应急创新能力经验、应急创新能力人工智能、风险应变能力培训人工智能、风险应变能力培训11.1 决策分析的基本问题决策分析的基本问题第9页，本讲稿共94页下一节：确定型和非确定型决策下一节：确定型和非确定型决策11.1 决策分析的基本问题决策分析的基本问题第10页，本讲稿共94页11.2 确定型和非确定型决策确定型和非确定型决策第11页，本讲稿共94页11.2 确定型和非确定型决策确定型和非确定型决策11.2.1 确定型决策确定型决策确定型决策确定型决策是指决策的未来状态是已知的，只需从备选的决

11、策方是指决策的未来状态是已知的，只需从备选的决策方案中，挑选出最优方案。案中，挑选出最优方案。【例【例11.1】某企业根据市场需要，需添置一台数控机床，可采】某企业根据市场需要，需添置一台数控机床，可采用的方式有三种：用的方式有三种：甲方案：引进外国进口设备，固定成本甲方案：引进外国进口设备，固定成本1000万元，产品每件万元，产品每件可变成本为可变成本为12元；元；乙方案：用较高级的国产设备，固定成本乙方案：用较高级的国产设备，固定成本800万元，产品每件万元，产品每件可变成本为可变成本为15元；元；丙方案：用一般国产设备，固定成本丙方案：用一般国产设备，固定成本600万元，产品每件可变万元

12、，产品每件可变成本为成本为20元；元；试确定在不同生产规模情况下的购置机床的最优方案。试确定在不同生产规模情况下的购置机床的最优方案。第12页，本讲稿共94页【解】【解】此题为确定型决策利用经济学知识，选取最优决策此题为确定型决策利用经济学知识，选取最优决策最优决策也就是在不同生产规模条件下，选择总成本较低的方最优决策也就是在不同生产规模条件下，选择总成本较低的方案各方案的总成本线如图案各方案的总成本线如图11.2 图图11.2TC甲甲F甲甲Cv甲甲Q100012QTC乙乙F乙乙Cv乙乙Q80015QTC丙丙F丙丙Cv丙丙Q60020Q 图中出现了图中出现了A、B、C三个交点，三个交点，其中其

13、中A点经济意义：在点经济意义：在A点采用甲点采用甲方案与丙方案成本相同方案与丙方案成本相同TC甲甲TC丙丙，F甲甲Cv甲甲QAF丙丙Cv丙丙QA Q5011.2 确定型和非确定型决策确定型和非确定型决策第13页，本讲稿共94页同理：同理：B点点TC乙乙TC丙丙，F乙乙Cv乙乙QBF丙丙Cv丙丙QB C点：点：TCL甲甲TC乙乙，F甲甲Cv甲甲QCF乙乙Cv乙乙QC B点经济意义为：当生产点经济意义为：当生产40万件时，采用乙方案和采用丙方案成万件时，采用乙方案和采用丙方案成本相同均为本相同均为1400万元万元 图图11.211.2 确定型和非确定型决策确定型和非确定型决策第14页，本讲稿共94

14、页得到生产规模最优方案为：当得到生产规模最优方案为：当生产规模产量小于生产规模产量小于40万件时，万件时，采用丙方案；当生产规模产量采用丙方案；当生产规模产量大于大于40万件，小于万件，小于200/3万件万件时，采用乙方案；当生产规模时，采用乙方案；当生产规模产量大于产量大于200/3万件时，采用万件时，采用甲方案甲方案 其经济意义为：当生产规模为万件时，采用甲、乙方案成本相其经济意义为：当生产规模为万件时，采用甲、乙方案成本相同从图中可知：当生产规模同从图中可知：当生产规模QB时，采用丙方案；当时，采用丙方案；当QB 生生产规模产规模 QC时，采用乙方案；当时，采用乙方案；当QC 0,则对任

15、何概率不则对任何概率不为零的事件为零的事件B，有，有11.3 风险型决策风险型决策 第40页，本讲稿共94页更一般地更一般地此公式为后验概率此公式为后验概率11.3 风险型决策风险型决策 第41页，本讲稿共94页产品需求量产品需求量x0100200300400先验概率先验概率p(xi)0.050.150.30.250.25例如，根据以往的经验，产品需求量的概率为例如，根据以往的经验，产品需求量的概率为产品进入市场产品进入市场2个月的试销后，需求量的样本信息个月的试销后，需求量的样本信息(比例比例)为为产品需求量产品需求量0100200300400需求量比例需求量比例0.050.150.350.

16、250.20贝叶斯公式：贝叶斯公式：若若A1、A2、构成一个完备事件，构成一个完备事件，P（Ai)0,则对任何概率不则对任何概率不为零的事件为零的事件B，有，有11.3 风险型决策风险型决策 第42页，本讲稿共94页【例】盒子里有【例】盒子里有100枚均匀的硬币，有枚均匀的硬币，有60枚是正常的，枚是正常的，40枚两面枚两面都是徽。从盒子中任取一枚让你猜是哪一类硬币。猜中得都是徽。从盒子中任取一枚让你猜是哪一类硬币。猜中得5元，元，猜不中不得钱。你猜是哪一类？猜不中不得钱。你猜是哪一类？B1(正常正常)B1(双徽双徽)3/52/5A1(猜正常猜正常)50A2(猜双徽猜双徽)05获利的期望值获利

17、的期望值V(A1)=53/5+02/5=3V(A2)=03/5+52/5=2正确的决策是：应该选择猜正常正确的决策是：应该选择猜正常11.3 风险型决策风险型决策 第43页，本讲稿共94页如果现在抛掷如果现在抛掷3次，次，3次都出现徽，你又如何猜？该硬币是正常次都出现徽，你又如何猜？该硬币是正常的概率为多少，是双徽的概率为多少。的概率为多少，是双徽的概率为多少。设设H为为3次出现反面这一随机事件，次出现反面这一随机事件，B1为硬币是正常，为硬币是正常，B2为硬币为硬币是双徽，则是双徽，则3次都出现双徽的概率为：次都出现双徽的概率为：11.3 风险型决策风险型决策 第44页，本讲稿共94页B1(

18、正常正常)B1(双徽双徽)3/1916/19A1(猜正常猜正常)50A2(猜双徽猜双徽)05用后验概率代替原来的概率，决策矩阵为：用后验概率代替原来的概率，决策矩阵为：获利的期望值获利的期望值V(A1)=53/19+02/5=15/19V(A2)=03/5+516/19=80/19正确的决策是：应该选择猜双徽正确的决策是：应该选择猜双徽11.3 风险型决策风险型决策 第45页，本讲稿共94页根据过去经验可知当自然状态为根据过去经验可知当自然状态为Nj条件下调查结果为条件下调查结果为Zk的条件概率的条件概率再利用贝叶斯公式和全概率公式，求当结果为再利用贝叶斯公式和全概率公式，求当结果为ZK的条件

19、下自然状的条件下自然状态为态为Nj的条件概率的条件概率 11.3 风险型决策风险型决策 第46页，本讲稿共94页在后验分析中用在后验分析中用代替先验分析中的代替先验分析中的P（Nj），利用期望值准则计算出），利用期望值准则计算出Ek再根据全概率公式，可知结果为再根据全概率公式，可知结果为Zk的概率为的概率为因此，后验分析的效益期望值为因此，后验分析的效益期望值为 11.3 风险型决策风险型决策 第47页，本讲稿共94页当状态只有两个时，后验概率及期望收益可用快捷公式计算。当状态只有两个时，后验概率及期望收益可用快捷公式计算。记先验概率向量为记先验概率向量为P，条件概率矩阵为，条件概率矩阵为A，

20、后验概率矩阵为，后验概率矩阵为B，收益矩阵为，收益矩阵为V，有，有 则先验收益期望值向量为则先验收益期望值向量为EMV1PTV后验收益期望值矩阵为后验收益期望值矩阵为EkBV11.3 风险型决策风险型决策 第48页，本讲稿共94页【例【例11.6】某厂对一台机器的换代问题做决策，有三种方案：某厂对一台机器的换代问题做决策，有三种方案：A1为买另一台新机器；为买另一台新机器；A2为为对老机器进行改建；对老机器进行改建；A3是维护加强输入不同质量的原料，三种方案的收益见表是维护加强输入不同质量的原料，三种方案的收益见表11.8约有约有30%的原料是质量好的，还可以花的原料是质量好的，还可以花600

21、元对原料的质量进行测试，这种测元对原料的质量进行测试，这种测试可靠性见表试可靠性见表11.9求最优方案求最优方案11.3 风险型决策风险型决策 原料的实际质量原料的实际质量N1好好N2差差测试结果测试结果Z1好好0.80.3Z2差差0.20.7原料质量原料质量Ni购新机器购新机器A1改建老机器改建老机器A2维护老机器维护老机器A3N1好（好（0.3）31.00.8N2差（差（0.7）-1.50.50.6表表11.9 测试可靠性测试可靠性 表表11.8 收益表收益表(单位：万元单位：万元)第49页，本讲稿共94页11.3 风险型决策风险型决策【解】【解】（1）若不做测试，各方案的先验收益 应选方

22、案应选方案3，维护老机器。，维护老机器。(2)计算后验概率计算后验概率已知已知联合概率为：联合概率为：第50页，本讲稿共94页11.3 风险型决策风险型决策 边际概率为边际概率为 代入（代入（11.2）从而可得后验概率）从而可得后验概率第51页，本讲稿共94页11.3 风险型决策风险型决策 则有则有即当测试结果为原料的质量好，则购买新机器；若测试结果为即当测试结果为原料的质量好，则购买新机器；若测试结果为原材料的质量差，则维护老机器。原材料的质量差，则维护老机器。决策为：应花决策为：应花600元进行测试，测试后若质量好，购入新机器生元进行测试，测试后若质量好，购入新机器生产；若质量差，维护老机

23、器生产产；若质量差，维护老机器生产 第52页，本讲稿共94页【例】石油开发决策问题【例】石油开发决策问题收益收益勘探勘探250钻探钻探150卖出收益卖出收益90有油时收益有油时收益800干涸时收益干涸时收益011.3 风险型决策风险型决策 第53页，本讲稿共94页11.3 风险型决策风险型决策 自然状态自然状态先验概率先验概率好好(FSS)不好不好(USS)有油有油(Oil)P(O)=0.6P(F|O)=0.8P(U|O)=0.2干涸干涸(Dry)P(D)=0.4P(F|D)=0P(U|D)=1P(Finding 勘探结果勘探结果|State自然状态自然状态)后验概率后验概率P(自然状态自然状

24、态|勘探结果勘探结果)勘探结果勘探结果边际概率边际概率有油有油(Oil)干涸干涸(Dry)好好(F)不好不好(U)勘探好的概率：勘探好的概率：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(

25、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.76920.480.5210.23076900.769231决策树参看文件：决策树参看文件：DATAchpt11ch11.xls第54页，本讲稿共94页下一节：效用理论下一节：效用理论作业：教材作业：教材P269 T3711.3 风险型决策风险型

26、决策 第55页，本讲稿共94页11.4 效用理论效用理论Utility Theory第56页，本讲稿共94页11.4.1 效用效用贝努利贝努利(D.Berneulli)首次提出效用概念，他用图首次提出效用概念，他用图11.7表示出表示出人们对钱财的真实价值的考虑与其钱财拥有量之间有对数关人们对钱财的真实价值的考虑与其钱财拥有量之间有对数关系系效用是一种相对的指标值，它的大小表示决策者对于风险的效用是一种相对的指标值，它的大小表示决策者对于风险的态度，对某事物的倾向、偏差等主观因素的强弱程度用于量态度，对某事物的倾向、偏差等主观因素的强弱程度用于量度决策者对于风险的态度度决策者对于风险的态度.效

27、用效用U货币货币M图图117 贝努利效用曲线贝努利效用曲线11.4 效用理论效用理论Utility Theory第57页，本讲稿共94页【例】【例】（1）方案）方案A1；稳获稳获100元。方案元。方案B1：用抛掷硬币的方法，猜对得：用抛掷硬币的方法，猜对得250元，猜错不得钱。元，猜错不得钱。（2）方案）方案A2；稳获稳获100元。方案元。方案B2：用抛掷硬币的方法，直到出现：用抛掷硬币的方法，直到出现正面为止，第正面为止，第n 次出现正面得到次出现正面得到2n元。元。大多数选择大多数选择A1、A2.通过计算有通过计算有E(B1)E(A1)，E(B2)E(A2)一般来说效用值在一般来说效用值在

28、0,1之间取值之间取值.凡是决策者最看好、最凡是决策者最看好、最倾向、最愿意的事物（事件）的效用值可取倾向、最愿意的事物（事件）的效用值可取1；反之，效；反之，效用值取用值取0当各方案期望值相同时，一般用最大效用值决当各方案期望值相同时，一般用最大效用值决策准则，选择效用值最大的方案策准则，选择效用值最大的方案 11.4 效用理论效用理论Utility Theory第58页，本讲稿共94页通过效用指标将某些难于量化、有质的区别的事件给予量化，通过效用指标将某些难于量化、有质的区别的事件给予量化，得到各方案的综合效用值，选择效用值最大的方案作为决策准得到各方案的综合效用值，选择效用值最大的方案作

29、为决策准则。则。11.4.2 效用曲线效用曲线确定效用曲线的基本方法有两种：一种是直接确定效用曲线的基本方法有两种：一种是直接提问法提问法，需要决，需要决策者回答提问，主观衡量应用较少；第二种是策者回答提问，主观衡量应用较少；第二种是对比提问法对比提问法，此法使用较多此法使用较多 设现有设现有A0，A1两种方案供选两种方案供选A0表示决策者不需要花费任何风表示决策者不需要花费任何风险可获益险可获益x0；而；而A1有两种自然状态，可以概率有两种自然状态，可以概率P获得收益获得收益x1，以，以概率（概率（1P）获得收益）获得收益x2；且；且x1x0 x2 令令yi表示效益表示效益xi的效用值则的效

30、用值则x0，x1，x2的效用值分别表示为的效用值分别表示为y0，y1，y2 若在某条件下，决策者认为若在某条件下，决策者认为A0,A1两方案等价，则有：两方案等价，则有：11.4 效用理论效用理论Utility Theory第59页，本讲稿共94页4个数个数p，x0，x1，x2中给定中给定3个，提问第个，提问第4个变量由决策者确定，个变量由决策者确定，求出效用值。求出效用值。一般采用改进一般采用改进VM(Von NeumannMorgenstern)方法，固定方法，固定P0.5，x1，x2改变改变x0三次，得出相应的三次，得出相应的y的值，确定三点，作出效用的值，确定三点，作出效用曲线曲线 1

31、1.4 效用理论效用理论Utility Theory第60页，本讲稿共94页【例【例11.7】x1=100，x2=400,取取y(x1)=0,y(x2)=1-100400第一次提问：第一次提问：x0为何值时，上式成立？答：为何值时，上式成立？答：“0”y(0)=0.50+0.510.51(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.

32、50.5+0.50.750.625(200,0.75)(100,0.625)100200 300011.4 效用理论效用理论Utility Theory第61页，本讲稿共94页不同决策者对待风险态度不同，因而会得到不同形状的效用曲不同决策者对待风险态度不同，因而会得到不同形状的效用曲线一般可分为保守型线一般可分为保守型、中间型、中间型、风险型、风险型，如下图，如下图 y1IIIx(Xmax,1)(Xmin,0)XmaxXmin011.4.3 效用曲线类型效用曲线类型图中图中I为保守型，其特点为：当收益为保守型，其特点为：当收益值较小时，效用值增加较快；随收值较小时，效用值增加较快；随收益值增大

33、时，效用值增加速度变慢，益值增大时，效用值增加速度变慢，表明决策者不求大利，谨慎小心，表明决策者不求大利，谨慎小心，保守保守图中图中II为中间型，其特点为：收为中间型，其特点为：收益值和效用值成正比，表明决策益值和效用值成正比，表明决策者完全按机遇办事，心平气和者完全按机遇办事，心平气和图中图中III为风险型，其特点为与为风险型，其特点为与I保守型恰好相反，当收益值较小保守型恰好相反，当收益值较小时，效用值增加较慢；随收益值时，效用值增加较慢；随收益值增大时，效用值增加速度变快，增大时，效用值增加速度变快，表明决策者对增加收益反应敏感，表明决策者对增加收益反应敏感，愿冒较大风险，谋求大利，不怕

34、愿冒较大风险，谋求大利，不怕冒险冒险 III11.4 效用理论效用理论Utility Theory第62页，本讲稿共94页常用的效用函数：常用的效用函数：11.4 效用理论效用理论Utility Theory第63页，本讲稿共94页11.4.4 效用值的应用效用值的应用【例【例11.8】若某决策问若某决策问题的决策树如下图所示，题的决策树如下图所示，其决策者的效用期望值其决策者的效用期望值同时附在效益期望值后，同时附在效益期望值后，请做出决策请做出决策 E(2)=0.53000.5(200)=50 E(3)0.52000.5(100)=50 根据最大效益期望值准则，无法判断优劣根据最大效益期望

35、值准则，无法判断优劣 y2=0.510.500.5，y3=0.50.9+0.50.3=0.6 解：解：(1）计算效益期望值分别为）计算效益期望值分别为11.4 效用理论效用理论Utility Theory第64页，本讲稿共94页A2方案效用值方案效用值A1方案效用值，因此取方案效用值，因此取A2方案为决策方案方案为决策方案绘制效用曲线图见下图，可知，该决策者偏向于保守型，不求大绘制效用曲线图见下图，可知，该决策者偏向于保守型，不求大利，谨慎小心利，谨慎小心 11.4 效用理论效用理论Utility Theory-20030010100200-100yx第65页，本讲稿共94页11.5 马尔可夫

36、决策马尔可夫决策 Markov Decision第66页，本讲稿共94页11.5马尔可夫决策马尔可夫决策 Markov Decision11.5.1 马尔可夫链马尔可夫链 用用X(t)表示随机系统在时刻表示随机系统在时刻t 的状态，状态序列的状态，状态序列为一随机过程，如果系统当前的转移概率只与当前的运行状为一随机过程，如果系统当前的转移概率只与当前的运行状态有关，而与以前的状态无关，即：对随机过程态有关，而与以前的状态无关，即：对随机过程 若对任意的若对任意的0t1t2tntn+1及及tiT，X（tn+1）关于）关于X（t1）,X（tn）的条件概率恰好等于）的条件概率恰好等于X（tn+1）关

37、于）关于X（tn）的条件）的条件概率，用数学符号表示为：概率，用数学符号表示为：第67页，本讲稿共94页则称则称 具有马尔可夫性随机过程称为马尔可夫过程。具有马尔可夫性随机过程称为马尔可夫过程。所有可能的全体取值称为过程的状态空间。所有可能的全体取值称为过程的状态空间。若马氏过程的状态空间为非负整数集若马氏过程的状态空间为非负整数集E0，1，2，称为马，称为马氏链。例如，今天下雨这一状态用氏链。例如，今天下雨这一状态用“0”表示，不下雨用表示，不下雨用“1”表表示，则状态空间为示，则状态空间为 E0，1。天气变化过程符合马。天气变化过程符合马Markov性。性。11.5.2 转移概率转移概率

38、记记Pij为从状态为从状态X(n)=i转移到下一个状态转移到下一个状态X（n+1）=j 的概率，一的概率，一步转移概率矩阵为步转移概率矩阵为11.5马尔可夫决策马尔可夫决策 Markov Decision第68页，本讲稿共94页【例【例11.9】有】有3家电器公司分别生产三种不同牌子的空调。各自家电器公司分别生产三种不同牌子的空调。各自开展广告攻势促销本公司产品。各公司所占的市场比例是随时开展广告攻势促销本公司产品。各公司所占的市场比例是随时间变化的。间变化的。XXn，n0构成一个以构成一个以E1,2,3为为 状态空间的状态空间的Markov链。假设在任一时刻，公司链。假设在任一时刻，公司1能

39、留住它的能留住它的1/2的老顾客，其余的则的老顾客，其余的则对半购买另两个公司的产品；公司对半购买另两个公司的产品；公司2的一半顾客能留下，其余转的一半顾客能留下，其余转向公司向公司1；公司；公司3有有3/4能留下，其余流向公司能留下，其余流向公司2。Markov链的转链的转移概率矩阵和转移图：移概率矩阵和转移图：1/21/41/41/21/21/43/411.5马尔可夫决策马尔可夫决策 Markov Decision第69页，本讲稿共94页求求n期后公司期后公司i的市场占有率，的市场占有率，n时的市场占有率。时的市场占有率。记记Pj(n)=P(Xn=j)为为Markov链链X时刻时刻n处于状

40、态处于状态j的概率，的概率，P为初为初始分布。始分布。【定理】【定理】XXn，n0为一个为一个Markov链，则有链，则有对任意对任意m，n0，有，有对任意对任意i，jE，有，有此方程称为此方程称为Champan-Kolmogorov方程，简称方程，简称CK方程方程11.5.3 转移状态转移状态 11.5马尔可夫决策马尔可夫决策 Markov Decision第70页，本讲稿共94页【例【例11.10】假设】假设3个公司开始的市场占有率为个公司开始的市场占有率为(0.3，0.35，0.35),求求5个月后的市场占有率个月后的市场占有率(状态状态)。【解】【解】P0(0.3，0.35，0.35)

41、11.5马尔可夫决策马尔可夫决策 Markov Decision第71页，本讲稿共94页遍历性：如果一个齐次的马尔可夫链遍历性：如果一个齐次的马尔可夫链X(n),n=1,2,的的n步转移步转移概率为概率为Pij(n)，对于一切状态，对于一切状态i,j，存在着不依赖于初始状态，存在着不依赖于初始状态i的常的常数数Pj，使得，使得 成立，则称此马尔可夫链具有遍历性也就是说，一个具有遍成立，则称此马尔可夫链具有遍历性也就是说，一个具有遍历性的马尔可夫链，当转移的次数历性的马尔可夫链，当转移的次数n极大时，此系统转移到状极大时，此系统转移到状态态j的概率为一个常数的概率为一个常数Pj，而与初始状态无关

42、，而与初始状态无关 求求【引理】设【引理】设m 阶矩阵阶矩阵P具有具有m个线性无关的特征向量个线性无关的特征向量 B(b1,b2,bm)对应的特征值为对应的特征值为1，2，m，则，则B可逆且有可逆且有PBB1，Pn=BnB1.其中其中diag(1，2，m)11.5马尔可夫决策马尔可夫决策 Markov Decision第72页，本讲稿共94页上例中，求上例中，求Pn及及求转移概率矩阵求转移概率矩阵P的特征值及特征向量。由的特征值及特征向量。由|IP|=0得得特征值及特征向量矩阵为特征值及特征向量矩阵为11.5马尔可夫决策马尔可夫决策 Markov Decision第73页，本讲稿共94页则有则

43、有11.5马尔可夫决策马尔可夫决策 Markov Decision第74页，本讲稿共94页长期后市场占有率各占长期后市场占有率各占1/3由由得得解方程得到稳定状态的概率解方程得到稳定状态的概率G11.5马尔可夫决策马尔可夫决策 Markov Decision第75页，本讲稿共94页【例【例11.10】设某公司有两种状态：设某公司有两种状态：1和和2，1为盈利，为盈利，2为亏损为亏损当其处于当其处于1时，下一年仍为时，下一年仍为1的概率是的概率是1/2，因此下一年转为，因此下一年转为2的概的概率也是率也是1/2当公司处于状态当公司处于状态2时，下一年经过努力回到状态时，下一年经过努力回到状态1的

44、的概率为概率为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)，由，由GGP11.5马尔可夫决策马尔可夫决策 Markov Decision第76页，本讲稿共94页设设G(g1，g2)，由，由GGP11.5马尔可夫决策马尔可夫决策 Markov De

45、cision第77页，本讲稿共94页11.5.4 收益预测模型收益预测模型 设系统在第设系统在第n个时期处于状态个时期处于状态X(n)=i，转移到过程终结时的总期，转移到过程终结时的总期望收益为望收益为 rij 表示从状态表示从状态X(n)=i 转移到下一个状态转移到下一个状态X（n+1）=j 相应的收益，相应的收益，则有：则有：n表示从第表示从第n个时期到过程终结的决策规则个时期到过程终结的决策规则的序列的序列 其中其中n为第为第n个时期的决策规则，个时期的决策规则，11.5马尔可夫决策马尔可夫决策 Markov Decision第78页，本讲稿共94页q(i)表示由状态表示由状态i 作一次

46、转移的期望报酬，即状态的即时期望报作一次转移的期望报酬，即状态的即时期望报酬则酬则 令令或或11.5马尔可夫决策马尔可夫决策 Markov Decision第79页，本讲稿共94页若记数从末端开始，上式的逆序写法为：若记数从末端开始，上式的逆序写法为：则则 11.7马尔可夫决策马尔可夫决策 Markov Decision第80页，本讲稿共94页11.7马尔可夫决策马尔可夫决策 Markov Decision【例】商品的转移概率矩阵和利润表如下【例】商品的转移概率矩阵和利润表如下畅销畅销滞销滞销畅销畅销0.50.5滞销滞销0.40.6畅销畅销滞销滞销畅销畅销5010滞销滞销2020转移概率表转移

47、概率表利润表利润表(万元万元)q1=0.550+0.51030，q2=0.420+0.6(20)4第81页，本讲稿共94页n123456f1(n)304454.365.4376.54387.6543f2(n)45.616.5627.65638.765649.87656期利润预测期利润预测11.5.5 最优策略模型最优策略模型 Markov决策由五重组来描述：决策由五重组来描述：1.状态状态 i 2.策略集策略集 ，状态，状态i 的策略规则为的策略规则为 3.转移概率矩阵转移概率矩阵P 4.报酬，状态报酬，状态i 的策略规则为的策略规则为 转移到状态转移到状态j 的报酬为的报酬为 期望即时报酬为

48、期望即时报酬为 5.目标函数目标函数V(n)11.5马尔可夫决策马尔可夫决策 Markov Decision 第82页，本讲稿共94页Markov决策（决策（MD）描述）描述 在某一时刻（阶段）随机变量在某一时刻（阶段）随机变量X处于状态处于状态i ，决策者选择某个，决策者选择某个策略使目标最优。策略使目标最优。MD常用的目标有常用的目标有3种：种：1.有限阶段目标；有限阶段目标；2.折扣目标；折扣目标；3.平均目标平均目标有限阶段目标最大。通过有限阶段目标最大。通过Z变换：变换：11.5马尔可夫决策马尔可夫决策 Markov Decision记记第83页，本讲稿共94页i=1,2,m (11

49、.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第84页，本讲稿共94页（3）应用上一策略已求得的）应用上一策略已求得的 ，寻求一个新的策略规则，寻求一个新

50、的策略规则 n+1，对每一个状态，对每一个状态i，使，使 由此得新的策略由此得新的策略（4）若所得策略）若所得策略 与前次迭代所得策略与前次迭代所得策略 完全相等，则完全相等，则停止迭代，已得到了最优策略；否则回到步骤停止迭代，已得到了最优策略；否则回到步骤2，令，令n=n+1 11.5马尔可夫决策马尔可夫决策 Markov Decision第85页，本讲稿共94页【例【例11.12】某水泥厂有一台窑炉处于两种运行状态，即运转和】某水泥厂有一台窑炉处于两种运行状态，即运转和故障，窑炉工人每年定期检查设备一次若窑炉正常则选择维故障，窑炉工人每年定期检查设备一次若窑炉正常则选择维护或不维护；若窑炉