运筹学—决策论完整版

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

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

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

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

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

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

7、的策略，其集合为： njuuuuU jn , 1, 21 U称为策略空间；称为策略空间；U的元素的元素Uj称为决策变量。称为决策变量。 损益函数损益函数 当状态处在当状态处在Si情况下，人们做出情况下，人们做出Uj决策，从而产生决策，从而产生 的损益值的损益值Vij，显然，显然Vij是是Si，Uj的函数，即：的函数，即： njmiuSvV jiij , 2 , 1;, 2 , 1),( 11.1 决策分析的基本问题决策分析的基本问题 当状态变量是离散型变量时，损益值构成的矩阵叫损益矩阵当状态变量是离散型变量时，损益值构成的矩阵叫损益矩阵 11121 21222 12 (,)(,)(,) (,)

8、(,)(,) () (,)(,)(,) n n ijm n mmmn v S Uv S Uv S U v S Uv S Uv S U VV v SUv SUv SU 上述三个主要素组成了决策系统，决策系统可以表示为三个主上述三个主要素组成了决策系统，决策系统可以表示为三个主 要素的函数：要素的函数： DD（S, U, V） 人们将根据不同的判断标准原则，求得实现系统目标的最优人们将根据不同的判断标准原则，求得实现系统目标的最优 （或满意）决策方案。（或满意）决策方案。 11.1 决策分析的基本问题决策分析的基本问题 11.1.2 决策分析基本原则决策分析基本原则 1. 最优化（满意）原则最优化

9、（满意）原则 2. 系统原则系统原则 3.可行性原则可行性原则 4.信息对称、准全原则信息对称、准全原则 11.1.3 决策分析基本分类决策分析基本分类 表表111 按影响范围按影响范围战略决策、战役决策、战术决策战略决策、战役决策、战术决策 按状态空间按状态空间确定型决策、非确定型决策、风险型决策确定型决策、非确定型决策、风险型决策 按决策时间按决策时间程序化决策、半程序化决策、非程序化决策程序化决策、半程序化决策、非程序化决策 按描述方法按描述方法定性化决策、定量化决策定性化决策、定量化决策 按目标数量按目标数量单目标决策、多目标决策单目标决策、多目标决策 按连续性按连续性单级决策、序贯决

10、策单级决策、序贯决策 按决策者数量按决策者数量个人决策、群决策个人决策、群决策 按问题大小按问题大小宏观决策、微观决策宏观决策、微观决策 表表112 程序化、非程序化、半程序化决策程序化、非程序化、半程序化决策 决策类型决策类型传统方法传统方法现代方法现代方法 程序化程序化现有的规章制度现有的规章制度运筹学、管理信息系统（运筹学、管理信息系统（MIS） 半程序化半程序化经验、直觉经验、直觉灰色系统、模糊数学等方法灰色系统、模糊数学等方法 非程序化非程序化经验、应急创新能力经验、应急创新能力人工智能、风险应变能力培训人工智能、风险应变能力培训 11.1 决策分析的基本问题决策分析的基本问题 下一

11、节：确定型和非确定型决策下一节：确定型和非确定型决策 11.1 决策分析的基本问题决策分析的基本问题 11.2 确定型和非确定型决策确定型和非确定型决策 11.2 确定型和非确定型决策确定型和非确定型决策 11.2.1 确定型决策确定型决策 确定型决策确定型决策是指决策的未来状态是已知的，只需从备选的决策方是指决策的未来状态是已知的，只需从备选的决策方 案中，挑选出最优方案。案中，挑选出最优方案。 【例【例11.1】某企业根据市场需要，需添置一台数控机床，可采】某企业根据市场需要，需添置一台数控机床，可采 用的方式有三种：用的方式有三种： 甲方案：引进外国进口设备，固定成本甲方案：引进外国进口

12、设备，固定成本1000万元，产品每件万元，产品每件 可变成本为可变成本为12元；元； 乙方案：用较高级的国产设备，固定成本乙方案：用较高级的国产设备，固定成本800万元，产品每件万元，产品每件 可变成本为可变成本为15元；元； 丙方案：用一般国产设备，固定成本丙方案：用一般国产设备，固定成本600万元，产品每件可变万元，产品每件可变 成本为成本为20元；元； 试确定在不同生产规模情况下的购置机床的最优方案。试确定在不同生产规模情况下的购置机床的最优方案。 【解】【解】 此题为确定型决策利用经济学知识，选取最优决此题为确定型决策利用经济学知识，选取最优决 策最优决策也就是在不同生产规模条件下，选

13、择总成本较低策最优决策也就是在不同生产规模条件下，选择总成本较低 的方案各方案的总成本线如图的方案各方案的总成本线如图11.2 图图11.2 TC甲 甲 F甲 甲 Cv甲 甲Q 100012Q TC乙 乙 F乙 乙 Cv乙 乙Q 80015Q TC丙 丙 F丙 丙 Cv丙 丙Q 60020Q 图中出现了图中出现了A、B、C三个交点，三个交点， 其中其中A点经济意义：在点经济意义：在A点采用甲点采用甲 方案与丙方案成本相同方案与丙方案成本相同TC甲 甲 TC 丙丙， ，F甲 甲 Cv甲 甲QA F丙 丙 Cv丙 丙QA )(50 1220 6001000 万件 甲丙 丙甲 CvCv FF QA

14、Q50 11.2 确定型和非确定型决策确定型和非确定型决策 同理：同理：B点点TC乙 乙 TC丙 丙， ，F乙 乙 Cv乙 乙QB F丙 丙 Cv丙 丙QB )(40 1520 600800 万件 乙丙 丙乙 CvCv FF QB C点：点：TCL甲 甲 TC乙 乙， ，F甲 甲 Cv甲 甲QC F乙 乙 Cv乙 乙QC B点经济意义为：当生产点经济意义为：当生产40万件时，采用乙方案和采用丙方案成万件时，采用乙方案和采用丙方案成 本相同均为本相同均为1400万元万元 （万件） 甲乙 乙甲 3 200 1215 8001000 CvCv FF QC 图图11.2 11.2 确定型和非确定型决策

15、确定型和非确定型决策 得到生产规模最优方案为：当得到生产规模最优方案为：当 生产规模产量小于生产规模产量小于40万件时，万件时， 采用丙方案；当生产规模产量采用丙方案；当生产规模产量 大于大于40万件，小于万件，小于200/3万件万件 时，采用乙方案；当生产规模时，采用乙方案；当生产规模 产量大于产量大于200/3万件时，采用万件时，采用 甲方案甲方案 其经济意义为：当生产规模为万件时，采用甲、乙方案成本相其经济意义为：当生产规模为万件时，采用甲、乙方案成本相 同从图中可知：当生产规模同从图中可知：当生产规模QB时，采用丙方案；当时，采用丙方案；当QB 生生 产规模产规模 QC时，采用乙方案；

16、当时，采用乙方案；当QC 0,则对任何概率不则对任何概率不 为零的事件为零的事件B，有，有 , 2 , 1 )|()( )|()( )|( m ABPAP ABPAP BAP i ii mm m 11.3 风险型决策风险型决策 n i iik jjk kj NPNZP NPNZP ZNP 1 )()( )()( )( njlk, 2 , 1;, 2 , 1 更一般地更一般地 此公式为后验概率此公式为后验概率 11.3 风险型决策风险型决策 产品需求量产品需求量x0100200300400 先验概率先验概率p(xi)0.050.150.30.250.25 例如，根据以往的经验，产品需求量的概率为

17、例如，根据以往的经验，产品需求量的概率为 产品进入市场产品进入市场2个月的试销后，需求量的样本信息个月的试销后，需求量的样本信息(比例比例)为为 产品需求量产品需求量0100200300400 需求量比例需求量比例0.050.150.350.250.20 贝叶斯公式：贝叶斯公式： 若若A1、A2、构成一个完备事件，构成一个完备事件，P（Ai)0,则对任何概率不则对任何概率不 为零的事件为零的事件B，有，有 , 2 , 1 )|()( )|()( )|( m ABPAP ABPAP BAP i ii mm m 11.3 风险型决策风险型决策 【例】盒子里有【例】盒子里有100枚均匀的硬币，有枚均

18、匀的硬币，有60枚是正常的，枚是正常的，40枚两面枚两面 都是徽。从盒子中任取一枚让你猜是哪一类硬币。猜中得都是徽。从盒子中任取一枚让你猜是哪一类硬币。猜中得5元，元， 猜不中不得钱。你猜是哪一类？猜不中不得钱。你猜是哪一类？ B1(正常正常)B1(双徽双徽) 3/52/5 A1(猜正常猜正常)50 A2(猜双徽猜双徽)05 获利的期望值获利的期望值 V(A1)=53/5+02/5=3 V(A2)=03/5+52/5=2 正确的决策是：应该选择猜正常正确的决策是：应该选择猜正常 11.3 风险型决策风险型决策 如果现在抛掷如果现在抛掷3次，次，3次都出现徽，你又如何猜？该硬币是正常次都出现徽，

19、你又如何猜？该硬币是正常 的概率为多少，是双徽的概率为多少。的概率为多少，是双徽的概率为多少。 设设H为为3次出现反面这一随机事件，次出现反面这一随机事件，B1为硬币是正常，为硬币是正常，B2为硬币为硬币 是双徽，则是双徽，则 1)|(, 8 1 2 1 )|( 2 3 1 BHpBHp 3次都出现双徽的概率为：次都出现双徽的概率为： 40 19 5 2 1 5 3 8 1 )()|()()|()( 2211 BpBHpBpBHpHp 19 3 40 19 5 3 8 1 )( )()|( )|( 11 1 Hp BpBHp HBp 19 16 40 19 5 2 1 )( )()|( )|(

20、 22 2 Hp BpBHp HBp 11.3 风险型决策风险型决策 B1(正常正常)B1(双徽双徽) 3/1916/19 A1(猜正常猜正常)50 A2(猜双徽猜双徽)05 用后验概率代替原来的概率，决策矩阵为：用后验概率代替原来的概率，决策矩阵为： 获利的期望值获利的期望值 V(A1)=53/19+02/5=15/19 V(A2)=03/5+516/19=80/19 正确的决策是：应该选择猜双徽正确的决策是：应该选择猜双徽 11.3 风险型决策风险型决策 根据过去经验可知当自然状态为根据过去经验可知当自然状态为Nj条件下调查结果为条件下调查结果为Zk的条件概的条件概 率率 njlkNZP

21、jk , 2 , 1;, 2 , 1)( 再利用贝叶斯公式和全概率公式，求当结果为再利用贝叶斯公式和全概率公式，求当结果为ZK的条件下自然的条件下自然 状态为状态为Nj的条件概率的条件概率 n i iik jjk kj NPNZP NPNZP ZNP 1 )()( )()( )( njlk, 2 , 1;, 2 , 1 11.3 风险型决策风险型决策 在后验分析中用在后验分析中用)( kj ZNP 代替先验分析中的代替先验分析中的P（Nj），利用期望值准则计算出），利用期望值准则计算出Ek 再根据全概率公式，可知结果为再根据全概率公式，可知结果为Zk的概率为的概率为 m i iikk NPNZ

22、PZP 1 )()()( 因此，后验分析的效益期望值为因此，后验分析的效益期望值为 l k kk ZPEEMV 1 2 )( lkmiZNPNSfE n j kjjiik , 1;, 1)(),( 1 ， miEE ij j k , 1,max 11.3 风险型决策风险型决策 当状态只有两个时，后验概率及期望收益可用快捷公式计算。当状态只有两个时，后验概率及期望收益可用快捷公式计算。 记先验概率向量为记先验概率向量为P，条件概率矩阵为，条件概率矩阵为A，后验概率矩阵为，后验概率矩阵为B， 收益矩阵为收益矩阵为V，有，有 222121 212 222121 111 212111 212 2121

23、11 111 2221 1211 2 1 , apap ap apap ap apap ap apap ap B aa aa A p p P， 则先验收益期望值向量为则先验收益期望值向量为 EMV1PTV 后验收益期望值矩阵为后验收益期望值矩阵为 EkBV 11.3 风险型决策风险型决策 【例【例11.6】 某厂对一台机器的换代问题做决策，有三种方案：某厂对一台机器的换代问题做决策，有三种方案：A1为买另为买另 一台新机器；一台新机器；A2为对老机器进行改建；为对老机器进行改建；A3是维护加强输入不同质量的是维护加强输入不同质量的 原料，三种方案的收益见表原料，三种方案的收益见表11.8约有约

24、有30%的原料是质量好的，还可以的原料是质量好的，还可以 花花600元对原料的质量进行测试，这种测试可靠性见表元对原料的质量进行测试，这种测试可靠性见表11.9求最优方求最优方 案案 11.3 风险型决策风险型决策 原料的实际质量原料的实际质量 N1好好N2差差 测试结果测试结果 Z1好好0.80.3 Z2差差0.20.7 原料质量原料质量Ni购新机器购新机器A1改建老机器改建老机器A2维护老机器维护老机器A3 N1好（好（0.3）31.00.8 N2差（差（0.7）-1.50.50.6 表表11.9 测试可靠性测试可靠性 表表11.8 收益表收益表(单位：万元单位：万元) () ki P Z

25、 N 11.3 风险型决策风险型决策 【解】【解】 （1）若不做测试，各方案的先验收益 -0.150.7(-1.5)0.33 1 EMV 65. 07 . 05 . 03 . 00 . 1 2 EMV 66. 07 . 06 . 03 . 08 . 0 3 EMV 3 0.66 l EMVEMV 万元 应选方案应选方案3，维护老机器。，维护老机器。 24. 03 . 08 . 0)()()( 11111 NPNZPZNP 06. 03 . 02 . 0)()()( 11221 NPNZPZNP (2)计算后验概率计算后验概率 () kj P ZN 已知已知 联合概率为：联合概率为： 11.3

26、风险型决策风险型决策 21122 ()() ()0.3 0.70.21P N ZP Z NP N 22222 ()() ()0.70.70.49P N ZP ZNP N 边际概率为边际概率为 45. 021. 024. 0)()()( 12111 ZNPZNPZP 55. 049. 006. 0)()()( 22212 ZNPZNPZP 代入（代入（11.2）从而可得后验概率）从而可得后验概率 533. 045. 0/24. 0)()()( 11111 ZPZNPZNP 109. 055. 0/06. 0)()()( 22121 ZPZNPZNP 467. 045. 0/21. 0)()()(

27、 11212 ZPZNPZNP 891. 055. 0/49. 0)()()( 22222 ZPZNPZNP 11.3 风险型决策风险型决策 则有则有0.5330.46731.00.8 0.1090.8911.50 0.8985 .50.6 0.7665 0.6 0.7066 1.00950.5545218 k E 6218. 0 8985. 0 k E 即当测试结果为原料的质量好，则购买新机器；若测试结果为即当测试结果为原料的质量好，则购买新机器；若测试结果为 原材料的质量差，则维护老机器。原材料的质量差，则维护老机器。 747. 0 6218. 0 8985. 0 55. 045. 0 2

28、 k EPEMV 687. 006. 0747. 0 22 CEMVEMV 决策为：应花决策为：应花600元进行测试，测试后若质量好，购入新机器生元进行测试，测试后若质量好，购入新机器生 产；若质量差，维护老机器生产产；若质量差，维护老机器生产 【例】石油开发决策问题【例】石油开发决策问题 收益收益 勘探勘探250 钻探钻探150 卖出收益卖出收益90 有油时收益有油时收益800 干涸时收益干涸时收益0 自然自然 状态状态先验概率先验概率好好不好不好 有油有油 干涸干涸 勘探结果勘探结果自然状态自然状态 11.3 风险型决策风险型决策 11.3 风险型决策风险型决策 自然状态自然状态先验概率先

29、验概率好好(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)= 1 P(Finding 勘探结果 勘探结果| State自然状态自然状态) 后验概率后验概率 P(自然状态自然状态|勘探结果勘探结果) 勘探结果勘探结果边际概率边际概率有油有油(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|

30、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|

31、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表示出人表示出人 们对钱财的真实价值的考虑与其钱财拥有量之间有对数关

32、们对钱财的真实价值的考虑与其钱财拥有量之间有对数关 系系 效用是一种相对的指标值，它的大小表示决策者对于风险的效用是一种相对的指标值，它的大小表示决策者对于风险的 态度，对某事物的倾向、偏差等主观因素的强弱程度用于量态度，对某事物的倾向、偏差等主观因素的强弱程度用于量 度决策者对于风险的态度度决策者对于风险的态度. 效用效用U 货币货币M 图图117 贝努利效用曲线贝努利效用曲线 11.4 效用理论效用理论 Utility Theory 【例】【例】 （1）方案）方案A1； ；稳获 稳获100元。方案元。方案B1：用抛掷硬币的方法，猜对得：用抛掷硬币的方法，猜对得 250元，猜错不得钱。元，猜

33、错不得钱。 （2）方案）方案A2； ；稳获 稳获100元。方案元。方案B2：用抛掷硬币的方法，直到出：用抛掷硬币的方法，直到出 现正面为止，第现正面为止，第n 次出现正面得到次出现正面得到2n元。元。 大多数选择大多数选择A1、A2.通过计算有通过计算有 E(B1)E(A1)， E(B2)E(A2) 一般来说效用值在一般来说效用值在0,1之间取值之间取值.凡是决策者最看好、最倾凡是决策者最看好、最倾 向、最愿意的事物（事件）的效用值可取向、最愿意的事物（事件）的效用值可取1；反之，效用；反之，效用 值取值取0当各方案期望值相同时，一般用最大效用值决策当各方案期望值相同时，一般用最大效用值决策

34、准则，选择效用值最大的方案准则，选择效用值最大的方案 11.4 效用理论效用理论 Utility Theory 通过效用指标将某些难于量化、有质的区别的事件给予量化，通过效用指标将某些难于量化、有质的区别的事件给予量化， 得到各方案的综合效用值，选择效用值最大的方案作为决策准得到各方案的综合效用值，选择效用值最大的方案作为决策准 则。则。 11.4.2 效用曲线效用曲线 确定效用曲线的基本方法有两种：一种是直接确定效用曲线的基本方法有两种：一种是直接提问法提问法，需要决，需要决 策者回答提问，主观衡量应用较少；第二种是策者回答提问，主观衡量应用较少；第二种是对比提问法对比提问法， 此法使用较多

35、此法使用较多 设现有设现有A0，A1两种方案供选两种方案供选A0表示决策者不需要花费任何风表示决策者不需要花费任何风 险可获益险可获益x0；而；而A1有两种自然状态，可以概率有两种自然状态，可以概率P获得收益获得收益x1，以，以 概率（概率（1P）获得收益）获得收益x2；且；且x1x0 x2 令令yi表示效益表示效益xi的效用值则的效用值则x0，x1，x2的效用值分别表示为的效用值分别表示为y0，y1， y2 若在某条件下，决策者认为若在某条件下，决策者认为A0 , A1两方案等价，则有：两方案等价，则有： 021 )1 (yyPPy 11.4 效用理论效用理论 Utility Theory

36、4个数个数p，x0，x1，x2中给定中给定3个，提问第个，提问第4个变量由决策者确定，个变量由决策者确定， 求出效用值。求出效用值。 一般采用改进一般采用改进VM(Von NeumannMorgenstern)方法，固定方法，固定P 0.5，x1，x2改变改变x0三次，得出相应的三次，得出相应的y的值，确定三点，作出效用的值，确定三点，作出效用 曲线曲线 )()(5 . 0)(5 . 0 021 xyxyxy 11.4 效用理论效用理论 Utility Theory )()(5 . 0)(5 . 0 021 xyxyxy 【例【例11.7】x1=100，x2=400,取取y(x1)=0, y(

37、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 1

38、1.4 效用理论效用理论 Utility Theory 不同决策者对待风险态度不同，因而会得到不同形状的效用曲不同决策者对待风险态度不同，因而会得到不同形状的效用曲 线一般可分为保守型线一般可分为保守型、中间型、中间型、风险型、风险型，如下图，如下图 y 1 I II x (Xmax,1) (Xmin,0) Xmax Xmin0 11.4.3 效用曲线类型效用曲线类型 图中图中I为保守型，其特点为：当收益为保守型，其特点为：当收益 值较小时，效用值增加较快；随收值较小时，效用值增加较快；随收 益值增大时，效用值增加速度变慢，益值增大时，效用值增加速度变慢， 表明决策者不求大利，谨慎小心，表明决

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

40、论 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

41、 解：解：(1）计算效益期望值分别为）计算效益期望值分别为 11.4 效用理论效用理论 Utility Theory A2方案效用值方案效用值A1方案效用值，因此取方案效用值，因此取A2方案为决策方案方案为决策方案 绘制效用曲线图见下图，可知，该决策者偏向于保守型，不求大绘制效用曲线图见下图，可知，该决策者偏向于保守型，不求大 利，谨慎小心利，谨慎小心 11.4 效用理论效用理论 Utility Theory -200300 1 0100200-100 y x 11.5 马尔可夫决策马尔可夫决策 Markov Decision 11.5马尔可夫决策马尔可夫决策 Markov Decision

42、11.5.1 马尔可夫链马尔可夫链 用用X(t)表示随机系统在时刻表示随机系统在时刻t 的状态，状态序列的状态，状态序列 TttX);( 为一随机过程，如果系统当前的转移概率只与当前的运行状为一随机过程，如果系统当前的转移概率只与当前的运行状 态有关，而与以前的状态无关，即：对随机过程态有关，而与以前的状态无关，即：对随机过程 TttX);( 若对任意的若对任意的0t1t2tntn+1及及tiT，X（tn+1）关于）关于X（t1）, X（tn）的条件概率恰好等于）的条件概率恰好等于X（tn+1）关于）关于X（tn）的条件概率，）的条件概率， 用数学符号表示为：用数学符号表示为： ,)()( ;

43、,)()( )(1 )(1 n innn n n innn UitXjtXP tUitXjtXP 策以前各时期的状态和决 则称则称 具有马尔可夫性随机过程称为马尔可夫过程。具有马尔可夫性随机过程称为马尔可夫过程。 TttX);( 所有可能的全体取值称为过程的状态空间。所有可能的全体取值称为过程的状态空间。 TttX);( 若马氏过程的状态空间为非负整数集若马氏过程的状态空间为非负整数集E0，1，2，称为马，称为马 氏链。例如，今天下雨这一状态用氏链。例如，今天下雨这一状态用“ 0”表示，不下雨用表示，不下雨用“ 1”表表 示，则状态空间为示，则状态空间为 E0，1。天气变化过程符合马。天气变化

44、过程符合马Markov性。性。 11.5.2 转移概率转移概率 记记Pij为从状态为从状态X(n)=i转移到下一个状态转移到下一个状态X（n+1）=j 的概率，一的概率，一 步转移概率矩阵为步转移概率矩阵为 mmmm m m PPP PPP PPP P 21 22221 11211 11.5马尔可夫决策马尔可夫决策 Markov Decision 【例【例11.9】有】有3家电器公司分别生产三种不同牌子的空调。各自家电器公司分别生产三种不同牌子的空调。各自 开展广告攻势促销本公司产品。各公司所占的市场比例是随时开展广告攻势促销本公司产品。各公司所占的市场比例是随时 间变化的。间变化的。 XXn

45、，n0构成一个以构成一个以E1,2,3为为 状态空间的状态空间的Markov 链。假设在任一时刻，公司链。假设在任一时刻，公司1能留住它的能留住它的1/2的老顾客，其余的则的老顾客，其余的则 对半购买另两个公司的产品；公司对半购买另两个公司的产品；公司2的一半顾客能留下，其余转的一半顾客能留下，其余转 向公司向公司1；公司；公司3有有3/4能留下，其余流向公司能留下，其余流向公司2。Markov链的转链的转 移概率矩阵和转移图：移概率矩阵和转移图： 4 3 4 1 0 0 2 1 2 1 4 1 4 1 2 1 P 1/2 1/4 1/4 1/2 1/2 1/4 3/4 11.5马尔可夫决策马

46、尔可夫决策 Markov Decision 求求n期后公司期后公司i的市场占有率，的市场占有率，n时的市场占有率。时的市场占有率。 记记Pj(n)=P(Xn=j)为为Markov链链X时刻时刻n处于状态处于状态j的概率，的概率，P为初为初 始分布。始分布。 【定理】【定理】 XXn，n0为一个为一个Markov链，则有链，则有 1121 11220, 12 (1) (,|) (2) (1)( ) (3) ( )(0),(0)(,) nn nni ii iii n m P Xi XiXiXippp P nP n P G nGP Gg gg 为初始状态，是行向量 对任意对任意m，n0，有，有)()

47、()(nPmPnmP 对任意对任意i，jE，有，有 Ek kjikij npmpnmp)()()( 此方程称为此方程称为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) )5( )0()5(PGG )3375. 0 ,3375. 0 ,325. 0( 75.

48、025. 00 05 . 05 . 0 25. 025. 05 . 0 )35. 0 ,35. 0 , 3 . 0()0() 1 ( PGG )33408. 0 ,33262. 0 ,3333. 0( 75. 025. 00 05 . 05 . 0 25. 025. 05 . 0 )35. 0 ,35. 0 , 3 . 0()0()5( 5 5 PGG 11.5马尔可夫决策马尔可夫决策 Markov Decision 遍历性：如果一个齐次的马尔可夫链遍历性：如果一个齐次的马尔可夫链X(n), n=1,2,的的n步转移步转移 概率为概率为Pij(n)，对于一切状态，对于一切状态i,j，存在着不依

49、赖于初始状态，存在着不依赖于初始状态i的常的常 数数Pj，使得，使得 jij n pnp )(lim 成立，则称此马尔可夫链具有遍历性也就是说，一个具有遍成立，则称此马尔可夫链具有遍历性也就是说，一个具有遍 历性的马尔可夫链，当转移的次数历性的马尔可夫链，当转移的次数n极大时，此系统转移到状极大时，此系统转移到状 态态j的概率为一个常数的概率为一个常数Pj，而与初始状态无关，而与初始状态无关 n n P lim求求 【引理】设【引理】设m 阶矩阵阶矩阵P具有具有m个线性无关的特征向量个线性无关的特征向量 B(b1,b2, ,bm) 对应的特征值为对应的特征值为1， 2，m，则，则B可逆且有可逆

50、且有PBB 1， ， Pn= BnB 1.其中 其中diag(1， 2，m) 11.5马尔可夫决策马尔可夫决策 Markov Decision 上例中，求上例中，求Pn及及 n n P lim 求转移概率矩阵求转移概率矩阵P的特征值及特征向量。由的特征值及特征向量。由|IP|=0得得 0)25. 0)(5 . 0)(1( 75. 025. 00 05 . 05 . 0 25. 025. 05 . 0 特征值及特征向量矩阵为特征值及特征向量矩阵为 3 1 3 1 3 2 101 3 1 3 1 3 1 , 111 211 101 4 1 2 1 1 1 BB ， 11.5马尔可夫决策马尔可夫决策

51、 Markov Decision 11 4 1 2 1 1 BBBBP n n nn nnnnn nnnnn nnn ) 4 1 ( 3 1 ) 2 1 ( 3 1 ) 4 1 ( 3 1 3 1 ) 4 1 ( 3 2 ) 2 1 ( 3 1 ) 4 1 ( 3 2 ) 2 1 ( 3 1 ) 4 1 ( 3 2 3 1 ) 4 1 ( 3 4 ) 2 1 ( 3 1 ) 4 1 ( 3 1 3 1 ) 4 1 ( 3 1 3 1 ) 4 1 ( 3 2 3 1 则有则有 11.5马尔可夫决策马尔可夫决策 Markov Decision 3 1 3 1 3 1 3 1 3 1 3 1 3 1

52、 3 1 3 1 lim n n P 3 1 , 3 1 , 3 1 lim)35. 0 ,35. 0 , 3 . 0(lim)0()(lim n n n nn PPGnGG 长期后市场占有率各占长期后市场占有率各占1/3PnGnG)() 1( GPGPnGnG nn ，)(lim) 1(lim 由由 得得 解方程得到稳定状态的概率解方程得到稳定状态的概率G 11.5马尔可夫决策马尔可夫决策 Markov Decision 【例【例11.10】 设某公司有两种状态：设某公司有两种状态：1和和2，1为盈利，为盈利，2为亏为亏 损当其处于损当其处于1时，下一年仍为时，下一年仍为1的概率是的概率是1

53、/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因此因此 5 3 5 2 2 1 2 1 222

54、1 1211 pp pp P 设设G(g1，g2)，由，由GGP 11.5马尔可夫决策马尔可夫决策 Markov Decision 设设G(g1，g2)，由，由GGP 5 3 5 2 2 1 2 1 2221 1211 pp pp P 5 3 5 2 2 1 2 1 ),(),( 2121 gggg 1, 5 3 2 1 , 5 2 2 1 21212211 gggggggg 9 5 , 9 4 21 gg 11.5马尔可夫决策马尔可夫决策 Markov Decision 11.5.4 收益预测模型收益预测模型 ),( nn if 设系统在第设系统在第n个时期处于状态个时期处于状态X(n)=i

55、，转移到过程终结时的总期，转移到过程终结时的总期 望收益为望收益为 , 2 , 1;, 2 , 1),(),( 1 11 nmijfrPif n j nnijijnn rij 表示从状态表示从状态X(n)=i 转移到下一个状态转移到下一个状态X（n+1）=j 相应的收益，相应的收益， 则有：则有： n表示从第表示从第n个时期到过程终结的决策规则个时期到过程终结的决策规则的序列的序列 , 1 nn ),( 1 nnn 其中其中n为第为第n个时期的决策规则，个时期的决策规则， 11.5马尔可夫决策马尔可夫决策 Markov Decision q(i)表示由状态表示由状态i 作一次转移的期望报酬，即

56、状态的即时期望报作一次转移的期望报酬，即状态的即时期望报 酬则酬则 ), 2 , 1()( 1 m j ijij mirPiq ),()(),( 1 11 m j nnijnn jfPiqif 令令 或或 ) 1()( 1 m j jijii nfPqnf 11.5马尔可夫决策马尔可夫决策 Markov Decision 若记数从末端开始，上式的逆序写法为：若记数从末端开始，上式的逆序写法为： )( )( )( )( 2 1 nf nf nf nF m m q q q Q 2 1 mmmm m m PPP PPP PPP P 21 22221 11211 则则 , 2 , 1) 1()(nnF

57、PQnF QF) 1 ( , 2 , 1;, 2 , 1) 1()( 1 nminfPqnf m j jijii 11.7马尔可夫决策马尔可夫决策 Markov Decision 11.7马尔可夫决策马尔可夫决策 Markov Decision 【例】商品的转移概率矩阵和利润表如下【例】商品的转移概率矩阵和利润表如下 畅销畅销滞销滞销 畅销畅销0.50.5 滞销滞销0.40.6 畅销畅销滞销滞销 畅销畅销5010 滞销滞销2020 转移概率表转移概率表利润表利润表(万元万元) q1=0.550+0.51030， q2=0.420+0.6(20)4 ), 2 , 1()( 1 m j ijij

58、mirPiq , 2 , 1) 1()(nnFPQnF 300.50.53043 (2) 40.40.645.6 300.50.54354.3 (3) 40.40.65.616.56 F F n123456 f1(n)304454.365.4376.54387.6543 f2(n)45.616.5627.65638.765649.8765 6期利润预测期利润预测 11.5.5 最优策略模型最优策略模型 Markov决策由五重组来描述：决策由五重组来描述： 1. 状态状态 i 2. 策略集策略集 ，状态，状态i 的策略规则为的策略规则为 3. 转移概率矩阵转移概率矩阵P 4. 报酬，状态报酬，状

59、态i 的策略规则为的策略规则为 转移到状态转移到状态j 的报酬为的报酬为 期望即时报酬为期望即时报酬为 5. 目标函数目标函数V(n) , 1 nn )(i )(i )(i ij r )(i i q 11.5马尔可夫决策马尔可夫决策 Markov Decision Markov决策（决策（MD）描述）描述 在某一时刻（阶段）随机变量在某一时刻（阶段）随机变量X处于状态处于状态i ，决策者选择某个，决策者选择某个 策略使目标最优。策略使目标最优。 MD常用的目标有常用的目标有3种：种： 1.有限阶段目标；有限阶段目标；2. 折扣目标；折扣目标；3.平均目标平均目标 有限阶段目标最大。通过有限阶段

60、目标最大。通过Z变换：变换： mi fnPqnfPqnf m j jiji m j jijii , 2 , 1 ) 1() 1()( 11 11.5马尔可夫决策马尔可夫决策 Markov Decision M j jiji qsv 1 (1)(0)FTQSF ( ) ii f nnvf 记记 1 1 m iij j ij vnfpnvqf 1 m iijji j vfp fq i=1,2, ,m (11.18) 解方程组求出变量解方程组求出变量 fi 与与 v 采用迭代计算：采用迭代计算： （1）选择一个初始策）选择一个初始策 ，每一个状态，每一个状态i（i=1，2，m）选择）选择 一个决策规