运筹学的优化算法ppt课件.ppt

《运筹学的优化算法ppt课件.ppt》由会员分享，可在线阅读，更多相关《运筹学的优化算法ppt课件.ppt（199页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1运筹学的优化算法运筹学的优化算法2345693A 非线性交调的频率设计非线性交调的频率设计: 拟合、规划拟合、规划93B 足球队排名次足球队排名次: 矩阵论、图论、层次分析法、矩阵论、图论、层次分析法、整数规划整数规划94A 逢山开路逢山开路: 图论、插值、动态规划图论、插值、动态规划94B 锁具装箱问题锁具装箱问题: 图论、组合数学图论、组合数学95A 飞行管理问题飞行管理问题 : 非线性规划、线性规划非线性规划、线性规划95B 天车与冶炼炉的作业调度天车与冶炼炉的作业调度: 非线性规划、动态非线性规划、动态规划、层次分析法、规划、层次分析法、PETRI方法、图论方法、排队方法、图论方法、

2、排队论方法论方法96A 最优捕鱼策略最优捕鱼策略：微分方程、积分、非线性规划微分方程、积分、非线性规划796B 节水洗衣机节水洗衣机：非线性规划非线性规划97A 零件参数设计零件参数设计：微积分、非线性规划、随机模微积分、非线性规划、随机模拟拟97B 截断切割截断切割：组合优化、几何变换、枚举、蒙特组合优化、几何变换、枚举、蒙特卡罗、递归、最短路卡罗、递归、最短路98A 投资收益与风险投资收益与风险：线性规划、非线性规划线性规划、非线性规划98B 灾情巡视路线灾情巡视路线：最小生成树、最小生成树、Hamilton圈、圈、旅行商问题旅行商问题99A 自动化车床管理自动化车床管理：积分、概率分布、

3、随机模拟、积分、概率分布、随机模拟、分布拟合度检验分布拟合度检验899B 钻井布局钻井布局：几何变换、枚举、最大完全子图、几何变换、枚举、最大完全子图、混合整数规划混合整数规划00A DNA分类分类：神经网络、最小二乘拟合、统计神经网络、最小二乘拟合、统计分类分类00B 管道订购和运输管道订购和运输：最短路、二次规划最短路、二次规划01A 血管的三维重建血管的三维重建：数据挖掘、曲面重建与拟数据挖掘、曲面重建与拟合合01B 公交车调度公交车调度：非线性规划非线性规划02A 车灯光源优化设计车灯光源优化设计：最优化最优化02B 彩票中的数学彩票中的数学：概率与优化概率与优化903A SARS S

4、ARS的传播：的传播： 微分方程、差分方程微分方程、差分方程 03B 露天矿生产的车辆安排：露天矿生产的车辆安排： 整数规划、运输问整数规划、运输问题题04A 奥运会临时超市网点设计：奥运会临时超市网点设计：统计分析、数据统计分析、数据处理、优化处理、优化 04B 电力市场的输电阻塞管理：电力市场的输电阻塞管理：数据拟合、优化数据拟合、优化 05A 长江水质的评价和预测：长江水质的评价和预测： 预测评价、数据预测评价、数据处理处理 05B DVD DVD在线租赁：在线租赁： 随机规划、整数规划随机规划、整数规划 06A 出版社书号问题：出版社书号问题： 整数规划、数据处理、整数规划、数据处理、

5、优化优化1006B Hiv Hiv病毒问题：病毒问题： 线性规划、回归分析线性规划、回归分析07A 人口问题：人口问题： 微分方程、数据处理、优化微分方程、数据处理、优化07B 公交车问题：公交车问题： 多目标规划、动态规划、图多目标规划、动态规划、图 论、论、0-10-1规划规划08A 照相机问题：照相机问题： 非线性方程组、优化非线性方程组、优化08B 大学学费问题：大学学费问题： 数据收集和处理、统计分数据收集和处理、统计分 析、回归分析析、回归分析11 赛题发展的特点：赛题发展的特点：1. 对选手的计算机能力提出了更高的要求：赛题对选手的计算机能力提出了更高的要求：赛题的解决依赖计算机

6、，题目的数据较多，手工计算的解决依赖计算机，题目的数据较多，手工计算不能完成，计算机模拟和以算法形式给出最终结不能完成，计算机模拟和以算法形式给出最终结果。果。 2. 赛题的开放性增大赛题的开放性增大: 解法的多样性，一道赛题解法的多样性，一道赛题可用多种解法。开放性还表现在对模型假设和对可用多种解法。开放性还表现在对模型假设和对数据处理上。数据处理上。 3. 试题向大规模数据处理方向发展试题向大规模数据处理方向发展 4. 求解算法和各类现代算法的融合求解算法和各类现代算法的融合 121.蒙特卡罗方法(Monte-Carlo方法, MC) 该算法又称计算机随机性模拟方法计算机随机性模拟方法，也

7、称统计试验统计试验方法方法。MC方法是一种基于“随机数”的计算方法，能够比较逼真地描述事物的特点及物理实验过程，解决一些数值方法难以解决的问题。 MC方法的雏型可以追溯到十九世纪后期的蒲丰随机投针试验，即著名的蒲丰问题蒲丰问题。 MC方法通过计算机仿真(模拟)解决问题，同时也可以通过模拟来检验自己模型的正确性，是比赛中经常使用的方法。1397年的年的A题题 每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照

8、正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。02年的年的B题题 关于彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。14 98 年美国赛年美国赛A 题题 生物组织切片的三维插值处理生物组织切片的三维插值处理 94 年年A 题逢山开路题逢山开路 山体海拔高度的插值计算山体海拔高度的插值计算2. 数据拟合、参数估计、插值等数据处理算法 比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MATLAB 作为工具。与图形处理有关的

9、问题很多与拟合有关系。 此类问题在MATLAB中有很多函数可以调用，只有熟悉MATLAB，这些方法才能用好。1598年年B 题题 用很多不等式完全可以把问题刻画清楚用很多不等式完全可以把问题刻画清楚3. 规划类问题算法 此类问题主要有线性规划、整数规划、多目标规划、线性规划、整数规划、多目标规划、二次规划二次规划等。竞赛中很多问题都和数学规划有关，可以说不少的模型都可以归结为一组不等式作为约束条件、几个函数表达式作为目标函数的问题，遇到这类问题，求解就是关键了。 因此列举出规划后用Lindo、Lingo 等软件来进行解决比较方便，所以还需要熟悉这两个软件。1698 年年B 题、题、00年年B

10、题、题、95 年锁具装箱年锁具装箱等问题体等问题体现了现了图论问题图论问题的重要性。的重要性。4. 图论问题 这类问题算法有很多，包括：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配，最大流，二分匹配等问题。1792 年年B 题用分枝定界法题用分枝定界法97 年年B 题是典型的动态规划问题题是典型的动态规划问题98 年年B 题体现了分治算法题体现了分治算法5. 计算机算法设计中的问题 计算机算法设计包括很多内容：动态规划、回溯搜动态规划、回溯搜索、分治算法、分枝定界索、分治算法、分枝定界等计算机算法. 这方面问题和ACM 程序设计竞赛中的问题类似，可看一下与

11、计算机算法有关的书。1819IP LP IP LP xl* * 判别是否整数解判别是否整数解xI* * = xl* *YesYes去掉非整数域去掉非整数域NoNo多个多个LPLP2021 若所得的最优解的各分量恰好是整数，若所得的最优解的各分量恰好是整数，若所得的最优解的各分量恰好是整数，若所得的最优解的各分量恰好是整数，若所得的最优解的各分量恰好是整数，若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计则这个解也是原整数规划的最优解，计则这个解也是原整数规划的最优解，计则这个解也是原整数规划的最优解，计则这个解也是原整数规划的最优解，计则这个解也是原整数规划的最优解，计算结

12、束。算结束。算结束。算结束。算结束。算结束。2223 若松驰问题有最优解，但其各分量不全若松驰问题有最优解，但其各分量不全若松驰问题有最优解，但其各分量不全若松驰问题有最优解，但其各分量不全若松驰问题有最优解，但其各分量不全若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最是整数，则这个解不是原整数规划的最是整数，则这个解不是原整数规划的最是整数，则这个解不是原整数规划的最是整数，则这个解不是原整数规划的最是整数，则这个解不是原整数规划的最优解，转下一步。优解，转下一步。优解，转下一步。优解，转下一步。优解，转下一步。优解，转下一步。2425 定界：把满足整数条件各分枝的最优

13、定界：把满足整数条件各分枝的最优定界：把满足整数条件各分枝的最优定界：把满足整数条件各分枝的最优定界：把满足整数条件各分枝的最优定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用它来判目标函数值作为上（下）界，用它来判目标函数值作为上（下）界，用它来判目标函数值作为上（下）界，用它来判目标函数值作为上（下）界，用它来判目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。断分枝是保留还是剪枝。断分枝是保留还是剪枝。断分枝是保留还是剪枝。断分枝是保留还是剪枝。断分枝是保留还是剪枝。26270 1 2 3 44 3 2 1x1x22829300 1 2 3 44 3 2 1x1x231

14、3233X1 2X2 2X1 1X2 3P1:(1,9/4)Z=10(3/4)P4: (0,3) Z=9P2:(2,1/2) Z=9(1/2)P3: (1,2) Z=10P:(6/5,21/10) Z=111/1034动态规划应用举例动态规划应用举例35最优化原理：最优策略的任一后部子策略都是最优的。无论以前状态决策如何，从眼下直到最后的诸决策必构成最优子策略。例1最短路线问题AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143动态规划应用举例动态规划应用举例36例例1 1 多阶段资源分配问题多阶段资源分配问题 设有数量为设有数量为x的某种资源，将它

15、投入两种的某种资源，将它投入两种生产方式生产方式A和和B中：以数量中：以数量y投入生产方式投入生产方式A，剩下的量投入生产方式剩下的量投入生产方式B，则可得到收入，则可得到收入g(y)+h(x-y)，其中，其中g(y)和和h(y)是已知函数，并是已知函数，并且且g(0)=h(0)=0；同时假设以；同时假设以y与与x-y分别投入两分别投入两种生产方式种生产方式A，B后可以回收再生产，回收率分后可以回收再生产，回收率分别为别为a与与b。试求进行。试求进行n个阶段后的最大总收入。个阶段后的最大总收入。37若以若以y与与x-y分别投入生产方式分别投入生产方式A与与B，在第一，在第一阶段生产后回收的总资

16、源为阶段生产后回收的总资源为x1=ay+b(x-y)，再将，再将x1投入生产方式投入生产方式A和和B，则可得到收入，则可得到收入g(y1)+h(x1-y1)，继续回收资源继续回收资源x2=ay1+b(x1-y1)， 若上面的过程进行若上面的过程进行n个阶段，我们希望选择个阶段，我们希望选择n个变量个变量y,y1,y2,yn-1，使这，使这n个阶段的总收入最大。个阶段的总收入最大。 例例1 1 续（续（1 1）38 因此，我们的问题就变成：求因此，我们的问题就变成：求y,y1,y2,yn-1，以使以使g(y)+h(x-y)+ g(y1)+h(x1-y1)+ +g(yn-1)+h(xn-1-yn-

17、1) 达到最大，且满足条件达到最大，且满足条件 x1=ay+b(x-y) x2=ay1+b(x1-y1) xn-1=ayn-2+b(xn-2-yn-2) yi与与xi均非负均非负,i=1,2, ,n-1 例例1 1 续（续（2 2）39例例2 2 生产和存储控制问题生产和存储控制问题某工厂生产某种季节性商品，需要作下一某工厂生产某种季节性商品，需要作下一年度的生产计划，假定这种商品的生产周期需年度的生产计划，假定这种商品的生产周期需要两个月，全年共有要两个月，全年共有6个生产周期，需要作出个生产周期，需要作出各个周期中的生产计划。各个周期中的生产计划。40设已知各周期对该商品的需要量如下表所示

18、设已知各周期对该商品的需要量如下表所示：周期周期123456需求量需求量551030508例例2 2 续（续（1 1）41例例2 2 续（续（2 2） 假设这个工厂根据需要可以日夜两班生产或只是日假设这个工厂根据需要可以日夜两班生产或只是日班生产，当开足日班时，每一个生产周期能生产商品班生产，当开足日班时，每一个生产周期能生产商品1515个单位，每生产一个单位商品的成本为个单位，每生产一个单位商品的成本为100100元。当开足元。当开足夜班时，每一生产周期能生产的商品也是夜班时，每一生产周期能生产的商品也是1515个，但是由个，但是由于增加了辅助性生产设备和生产辅助费用，每生产一单于增加了辅助

19、性生产设备和生产辅助费用，每生产一单位商品的成本为位商品的成本为120120元。由于生产能力的限制，可以在元。由于生产能力的限制，可以在需求淡季多生产一些商品储存起来以备需求旺季使用，需求淡季多生产一些商品储存起来以备需求旺季使用，但存储商品是需要存储但存储商品是需要存储费用的，假设每单位商品存储一费用的，假设每单位商品存储一周期需要周期需要16元，已知开始时存储为零，年终也不存储商元，已知开始时存储为零，年终也不存储商品备下年使用，问应该如何作生产和存储计划，才能使品备下年使用，问应该如何作生产和存储计划，才能使总的生产和存储费用最小？总的生产和存储费用最小？42例例2 2 续（续（3 3）

20、设第设第i个周期的生产量为个周期的生产量为xi，周期末的存储量为，周期末的存储量为ui，那，那么这个问题用式子写出来就是：求么这个问题用式子写出来就是：求x1,x2,x6，满足条件：，满足条件： x1=5+u1 x2+u1=5+u2 x3+u2=10+u3 x4+u3=30+u4 x5+u4=50+u5 x6+u5=8 0 xi 30,0 uj,i=1,2,6;j=1,2, ,5 使使S= = 为最小，其中为最小，其中 6511()1 6ijijfxu)1852345(16)(5432161xxxxxxfii433015,300120150 ,100)(iiiiixxxxxf例例2 2 续（续

21、（4 4）44逆序递推方程：0)(1 , 2 , 3 , 4 , 5)(),(min)(6611xfkxfuxdxfkkkkkukkk（1）k=5时，状态,215EEX它们到F点的距离即为最短路。, 4)(15Ef; 3)(25Ef,)(1*5FEu.)(2*5FEuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143例1：1阶段2阶段3阶段4阶段5阶段45AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（2）k=4时，状态,3214DDDX它们到F点需经过中途点E，需一一分析从E到F的最短路：先说从D

22、1到F的最短路有两种选择：经过E1,E2,比较最短。.)(2*5FEu,)(1*5FEu46AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143)(),(),(),(min)(252141511414EfEDdEfEDdDf. 735 , 43min这说明由D1到F的最短距离为7，其路径为.11FED相应的决策为：.)(11*4EDu.)(2*5FEu,)(1*5FEu47)(),(),(),(min)(252241512424EfEDdEfEDdDf. 532 , 46min这说明由D2到F的最短距离为5，其路径为.22FED相应的决策为：.)(2

23、2*4EDuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu48AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143)(),(),(),(min)(252341513434EfEDdEfEDdDf. 533, 41min即D3到F的最短距离为5，其路径为.22FED相应的决策为：.)(13*4EDu.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu49（3）k=3时，状态,43214CCCCX )(),(),(),(min

24、)(242131411313DfDCdDfDCdCf.1258, 75min这说明由C1到F的最短距离为12，相应的决策为.)(11*3DCuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu5)(24Df7)(14Df50AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143)(),(),(),(min)(242231412323DfDCdDfDCdCf.1055 , 74min即由C2到F的最短距离为10，相

25、应的决策为.)(22*3DCu)(),(),(),(min)(343332423333DfDCdDfDCdCf. 854 , 53min.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu7)(14Df5)(24Df5)(34Df51即由C3到F的最短距离为8，相应的决策为.)(23*3DCu)(),(),(),(min)(343432424343DfDCdDfDCdCf. 954 , 58min即由C4到F的最短距离为9，相应的决策为.)(34*3DCuAB1B2C1C2C3C4D1D2D3E1E2F45236877584534

26、8435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu5)(24Df5)(34Df52AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（4）k=2时，状态,212BBX)(),(),(),(),(),(min)(33312232121311212CfCBdCfCBdCfCBdBf.1386 ,103 ,122min这说明由B1到F的最短距离为13，相应的决策为.)(21*2CBu.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*

27、4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu.)(23*3DCu.)(34*3DCu12)(13Cf10)(23Cf8)(33Cf53)(),(),(),(),(),(min)(43422333222322222CfCBdCfCBdCfCBdBf.1597 , 87 ,108min即由B2到F的最短距离为15，相应的决策为.)(32*2CBuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu

28、.)(23*3DCu.)(34*3DCu.)(21*2CBu9)(43Cf10)(23Cf8)(33Cf54AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（1）k=1时，只有一个状态点A,则)(),(),(),(min)(222112111BfBAdBfBAdAf.17155 ,134min即由A到F的最短距离为17，相应的决策为.)(1*1BAu.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu.)(23*3DCu.)(34*3DCu.)(32*2CBu.)

29、(21*2CBu13)(12Bf15)(22Bf55,)(21*2CBu,)(22*3DCu,)(22*4EDu.)(2*5FEu所以最优路线为：FEDCBA2221AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu.)(23*3DCu.)(34*3DCu.)(32*2CBu.)(21*2CBu再按计算顺序反推可得最优决策序列：,)(1*1BAu.)(1*1BAu5697年年A 题用模拟退火算法题用模拟退火算法00

30、年年B 题用神经网络分类算法题用神经网络分类算法01年年B 题这种难题也可以使用神经网络题这种难题也可以使用神经网络美国美国03年年B 题题伽马刀问题也是目前研究的课题，目前算法最佳的是遗传算法算法最佳的是遗传算法。6. 最优化理论的三大非经典算法: 模拟退火法(SA)、神经网络(NN)、遗传算法(GA) 近几年的赛题越来越复杂，很多问题没有什么很好的模型可以借鉴，于是这三类算法很多时候可以派上用场。5797 年年A 题、题、99 年年B 题都可以题都可以用网格法搜索用网格法搜索 网格算法和穷举法一样，只是网格法是连续问题的穷举。此类算法运算量较大。7. 网格算法和穷举算法 这种方法最好在运算

31、速度较快的计算机中进行，还有要用高级语言来做，最好不要用MATLAB 做网格，否则会算很久。58很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此需要将连续问题进行将连续问题进行离散化处理后再用计算机求解离散化处理后再用计算机求解。比如差分代替微分、求和代替积分等思想都是把连续问题离散化的常用方法。8. 连续问题离散化的方法59数值分析研究各种求解数学问题的数值计算方法求解数学问题的数值计算方法，特别是适合于计算机实现方法与算法。9. 数值分析方法 它的主要内容包括函数的数值逼近、数值微分与数函数的数值逼近、数值微分与数值积分、非线性方程的数值解法、数值代数、常微分方值积

32、分、非线性方程的数值解法、数值代数、常微分方程数值解程数值解等。数值分析是计算数学的一个重要分支，把理论与计算紧密结合,是现代科学计算的基础 。 MATLAB等数学软件中已经有很多数值分析的函数可以直接调用。6001年年A 题中需要你会读题中需要你会读BMP 图象图象98年美国年美国A 题需要你知道三维插值计算题需要你知道三维插值计算03年年B 题要求更高，不但需要编程计算还要进行题要求更高，不但需要编程计算还要进行处理处理10. 图象处理算法 赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB进行

33、处理。 数模论文中也有很多图片需要展示，解决这类问题要熟悉MATLAB图形图像工具箱。61例1某公司拥有一块可能有油的土地，根据可能出油的多少，该块土地属于四种类型：可产油50万桶、20万桶、5万桶、无油。公司目前有3个方案可供选择：自行钻进；无条件将该块土地出租给其他使用者；有条件的租给其他生产者。若自行钻井，打出一口有油井的费用是10万元，打出一口无油井决策分析决策分析62的费用是7.5万元，每一桶油的利润是1.5万。若无条件出租，不管出油多少，公司收取固定租金4.5万元；若有条件出租，公司不收取租金，但当产量为20万桶至50万桶时，每桶公司收取0.5元。由上计算得到该公司可能的利润收入见

34、表14-1.按过去的经验，该块土地属于上面4种类型的可能性分别为10%，15%，25%和50%。问题是该公司应选择哪种方案，可获得最大利润？63表14-1石油公司可能利润收入表（单位：万元）1 . 01p 类 型项目50万桶20万桶5万桶无油自行钻井无条件出租有条件出租654.525204.5102.54.507.54.501S2S3S4S15. 02p25. 03p5 . 04p2A3A1A解：各个方案的期望收益为125. 5)75. 0(5 . 0)5 . 2(25. 02015. 06510. 0)(1AE5 . 45 . 45 . 05 . 425. 05 . 415. 05 . 41

35、0. 0)(2AE405 . 0025. 01015. 02510. 0)(3AE根据期望收益最大原则，应选择，即自行钻井。1A64效用理论效用理论一、效用概念的引入一、效用概念的引入前面介绍风险型决策方法时，提到可根据期望益损值（最大或前面介绍风险型决策方法时，提到可根据期望益损值（最大或最小）作为选择最优方案的原则，但这样做并不一定合理。请最小）作为选择最优方案的原则，但这样做并不一定合理。请看下面的例子：看下面的例子：例例6 设有两个决策问题：设有两个决策问题：问题问题1：方案：方案A1：稳获：稳获100元；元； 方案方案B1: 用掷硬币的方法，掷出正面获得用掷硬币的方法，掷出正面获得2

36、50元，掷元，掷出反面获得出反面获得0元。元。65问题问题2：方案：方案A2：稳获：稳获1000元；元； 方案方案B2: 用掷硬币的方法，直到掷出正面为止，记所用掷硬币的方法，直到掷出正面为止，记所掷次数为掷次数为N，则当正面出现时，可获，则当正面出现时，可获2N元元.当你遇到这两类问题时，如何决策？大部分会选择当你遇到这两类问题时，如何决策？大部分会选择 A1 和和 A2。但不妨计算一下其期望值：但不妨计算一下其期望值：Y10250P(Y1=k)1/21/2方案方案B1的收益为随机变量的收益为随机变量Y1。则其期望收益为：则其期望收益为：E YE X1111()0250125100()226

37、6设方案设方案B2的收益为随机变量的收益为随机变量Y2。Ai=“第第i次掷出正面次掷出正面” ，则第，则第n次掷出正面的概率为：次掷出正面的概率为：Y222223nP(Y2=k)1/21/221/231/2nX012n-1nnnnnnAPAPAPAAAP2121)21()()()()(11111相互独立相互独立nAAA,21设掷出正面前掷出反面的次数为随机变量设掷出正面前掷出反面的次数为随机变量X,则有分布列：则有分布列：则方案则方案2的平均收益为：的平均收益为：67Y222223nP(Y2=k)1/21/221/231/2nX012n-1nnE YE A2322231111()2222100

38、0()2222 于是，根据期望收益最大原则，应选择于是，根据期望收益最大原则，应选择B1和和B2，但这一结果，但这一结果很难令实际决策者接受。此乃研究效用函数的初衷。很难令实际决策者接受。此乃研究效用函数的初衷。例例7（赌一把）一个正常的人，遇到（赌一把）一个正常的人，遇到“赌一把赌一把”的机会。情的机会。情况况如下面的树，问此人如何决策？如下面的树，问此人如何决策？68正常人B赌不赌45元掷出正面P=0.5-10元P=0.50100元掷出反面45元对绝大部分人来说，对绝大部分人来说，只要兜里有只要兜里有10元钱，元钱，又不急用的话，就选又不急用的话，就选择择“赌赌”。因此时。因此时“赌赌”的

39、平均收益为：的平均收益为：EE11()100( 10)450()22 赌赌不不赌赌类似的问题，让一个被判刑十年且手头仅有类似的问题，让一个被判刑十年且手头仅有10元钱的罪元钱的罪犯做下面的决策：犯做下面的决策：69罪犯B赌释放释放45元掷出正面P=0.5-10元P=0.5-10元100元掷出反面45元此时罪犯可能要选此时罪犯可能要选择交出择交出10元钱，获元钱，获得释放。得释放。以上例子说明：以上例子说明： 相同的期望益损值（以货币值为度量）的不同随机事件之相同的期望益损值（以货币值为度量）的不同随机事件之间其风险可能存在着很大的差异。即说明间其风险可能存在着很大的差异。即说明货币量的期望益损

40、货币量的期望益损值不能完全反映随机事件的风险程度。值不能完全反映随机事件的风险程度。 同一同一随机事件对不同的决策者的吸引力可能完全不同，因随机事件对不同的决策者的吸引力可能完全不同，因此可采用不同的决策。这与决策者个人的气质、冒险精神、此可采用不同的决策。这与决策者个人的气质、冒险精神、70经济状况、经验等等主观因素有很大的关系。经济状况、经验等等主观因素有很大的关系。 即使同一个人在不同情况下对同一即使同一个人在不同情况下对同一随机事件也会采用随机事件也会采用不同的态度。不同的态度。当我们以期望益损值（以货币值为度量）作决策准则时，实当我们以期望益损值（以货币值为度量）作决策准则时，实际已

41、经假定际已经假定期望益损值相等的各个随机事件是等价的，具有期望益损值相等的各个随机事件是等价的，具有相同的风险程度，且对不同的人具有相同的吸引力相同的风险程度，且对不同的人具有相同的吸引力。但对有。但对有些问题这个假定是不合适的。因此不能采用货币度量的期望些问题这个假定是不合适的。因此不能采用货币度量的期望益损值作决策准则，而用所谓益损值作决策准则，而用所谓“效用值效用值”作决策准则。作决策准则。71二、效用曲线的确定及分类二、效用曲线的确定及分类老王B二次抽奖一次500元P=0.50元P=0.5500元1000元500元为了讲清为了讲清“效用效用”与与“效效用值用值”的概念，看下的概念，看下

42、例例例例 老王参加某电视台综艺老王参加某电视台综艺节目而得奖。他有两种方式可选择：节目而得奖。他有两种方式可选择：:1A一次获得一次获得500元奖金。元奖金。:2A分别以概率分别以概率 0.5 与与 0.5的机会抽奖可获得的机会抽奖可获得1000元与元与0元。元。试问老王该选择何种方式领奖？试问老王该选择何种方式领奖？72事件事件 的期望益损值都是的期望益损值都是500元，但有人认为应选择元，但有人认为应选择,1A2A,1A他认为他认为 的的“价值价值”比比 大，有的相反。都是大，有的相反。都是“主观价值主观价值”。1A2A此时他认为事件此时他认为事件 的效用比事件的效用比事件 来的大。来的大

43、。1A2A如何来度量随机事件的效用（或说如何来度量随机事件的效用（或说“价值价值”）？我们用）？我们用“效用效用值值”u来度量效用值的大小。来度量效用值的大小。“效用值效用值”是一个是一个“主观价值主观价值”，且，且是一是一个相对大小的值。通常假定决策者最偏好、最倾向、最喜欢的个相对大小的值。通常假定决策者最偏好、最倾向、最喜欢的事情（方案）的效用为事情（方案）的效用为1，而最不偏好、最不倾向、最不喜欢，而最不偏好、最不倾向、最不喜欢的事情（方案）的效用为的事情（方案）的效用为0。一般来说，若用一般来说，若用r来表示期望收益值（这里收益值作广义理来表示期望收益值（这里收益值作广义理解，不一定是

44、货币量，也可以是某事件的结果），则解，不一定是货币量，也可以是某事件的结果），则r的效用的效用73u ru rmaxmin()1,()0那么，当那么，当 时如何计算呢？时如何计算呢？rrrminmax值用值用 来表示。因此有来表示。因此有)(ru)(ru一般用心理测试的方法来确定一般用心理测试的方法来确定 ，具体做法是：反复向决策，具体做法是：反复向决策者提出下面的问题：者提出下面的问题：“如果事件如果事件 是以概率是以概率P得到收益为得到收益为 ，以概率（以概率（1-P）得到收益为）得到收益为 ，事件，事件 是以是以100%概率得到收概率得到收益为益为 你认为你认为 取多大值时，事件取多大值

45、时，事件 与事件与事件 是是相当的（即认为效用值相等）？如果决策者经过思考后，认为相当的（即认为效用值相等）？如果决策者经过思考后，认为 时时 两事件效用是相当的，即有两事件效用是相当的，即有A1r1r2A2r rrr21(),rA1A2rr0 rrr201()u rpu rp u r012( )( )(1) ( )74当当 ， ， 已知时，则已知时，则 的效用值可求出。如当的效用值可求出。如当 则则 则可求出则可求出p)(2ru)(1ru0r,min2max1rrrr, 0)(, 1)(21ruru0rrrr201()的效用值，再在已知效用值的三点的效用值，再在已知效用值的三点,2r,0r1

46、r中的任意两点，再作出同样的问题来问决策者，则可在两点中中的任意两点，再作出同样的问题来问决策者，则可在两点中求出一点的效用值。如此继续，可得到在求出一点的效用值。如此继续，可得到在 及及 中间的中间的一系列一系列 的效用值的效用值 。再以。再以 作横坐标，作横坐标， 作纵坐标可作纵坐标可得该决策者的效用曲线。举例如下。得该决策者的效用曲线。举例如下。minrmaxrir)(iruir)(iru例例 设某决策者在股票交易所购买股票，现有两种选择：设某决策者在股票交易所购买股票，现有两种选择：:1A选择股票选择股票01号，预计每手（号，预计每手（100股）可能分别以概率股）可能分别以概率0.5获

47、利获利200元，概率元，概率0.5 损失损失100元。元。75:2A选择股票选择股票02号，预计每手（号，预计每手（100股）可能以概率股）可能以概率1.0获获利利25元。元。试问该决策者应选择何种方式购买股票？试问该决策者应选择何种方式购买股票？用心理测试法对该决策者提问：用心理测试法对该决策者提问： 对上述事件对上述事件 ，问决策者愿意选择何种方式？，问决策者愿意选择何种方式？,1A2A决策者B01号股票02号股票0.5P=0.5-100元P=0.525元200元若决策者选择若决策者选择 ，则降，则降低低 到到20元，若还选择元，若还选择则再降低则再降低 ，若降至，若降至0元（即不赔不赚）

48、时，元（即不赔不赚）时，2A2A2A2A决策者犹豫不定，说明决策者犹豫不定，说明1)200(u0)100(u05 . 015 . 0(?)u:1A选择股票选择股票01号，预计每手（号，预计每手（100股）可能分别以概率股）可能分别以概率0.5获利获利200元，概率元，概率0.5 损失损失100元。元。76此时随机事件此时随机事件 的效用值的效用值与与 相等。相等。1A2A求出求出 时的效益时的效益值：值：0r)100()1 ()200()0(uppuu. 5 . 005 . 015 . 025. 05 . 075. 000. 1100100200 x)(xU得到效用曲线的三点。得到效用曲线的三

49、点。5 . 0)0(u0元P=1.0决策者01号股票02号股票0.5P=0.5-100元P=0.5200元1)200(u0)100(uB1B20.577决策者01号股票02号股票0.75P=0.50元P=0.540元200元:2A选择股票选择股票02号，预计每手号，预计每手（100股）可能以概股）可能以概率率1.0获利获利40元。元。试问该决策者应选择何种试问该决策者应选择何种方式购买股票？方式购买股票？ 再求再求 与与 之间某一点之间某一点 的效用值。提出的效用值。提出如下的问题：如下的问题：200r0r0r:1A选择股票选择股票01号，预计每手（号，预计每手（100股）可能分别以概率股）可

50、能分别以概率0.5获利获利200元，概率元，概率0.5 损失损失0元。元。1)200(u5 . 0)0(u5 . 05 . 015 . 0(?)uB1B2P=1.00.7578决策者01号股票02号股票0.75P=0.50元P=0.5200元1)200(u5 . 0)0(uB1B2P=1.00.7540元60元若决策者选择若决策者选择 ，则提，则提高高02号股票到号股票到60元。决策元。决策者犹豫不定，说明此时随者犹豫不定，说明此时随机事件机事件 的效用值与的效用值与 相等。相等。1A1A2A求出求出 时的效用值：时的效用值：60r)0()1 ()200()60(uppuu.75. 05 .