运筹学的优化算法.ppt

运筹学的优化算法运筹学的优化算法1运运 筹筹 学学（Operations Research OR）由由于于运运筹筹学学研研究究的的广广泛泛性性和和复复杂杂性性，人人们们至至今今没没有有形形成成一一个个统统一一的的定定义义。以以下下给给出出几种定义：几种定义：v运筹学是一种科学决策的方法运筹学是一种科学决策的方法v运运筹筹学学是是依依据据给给定定目目标标和和条条件件从从众众多多方方案案中选择最优方案的最优化技术。中选择最优方案的最优化技术。v运运筹筹学学是是一一种种给给出出坏坏的的问问题题的的答答案案的的艺艺术术，否则的话问题的结果会更坏。否则的话问题的结果会更坏。2运筹学模型运筹学模型 运运筹筹学学研研究究的的模模型型主主要要是是抽抽象模型象模型数学模型。数学模型。3运筹学包含的分支运筹学包含的分支v数数学学规规划划（线线性性规规划划、整整数数规规划划、目标规划、动态规划、网络规划等）目标规划、动态规划、网络规划等）v图论与网络流图论与网络流v决策分析决策分析4运筹学包含的分支运筹学包含的分支v排队论排队论v可靠性数学理论可靠性数学理论v库存论库存论v对策论对策论v搜索论搜索论v计算机模拟等计算机模拟等5数学建模竞赛中的算法数学建模竞赛中的算法(1)93A非线性交调的频率设计非线性交调的频率设计:拟合、规划拟合、规划93B足球队排名次足球队排名次:矩阵论、图论、层次分析法、矩阵论、图论、层次分析法、整数规划整数规划94A逢山开路逢山开路:图论、插值、动态规划图论、插值、动态规划94B锁具装箱问题锁具装箱问题:图论、组合数学图论、组合数学95A飞行管理问题飞行管理问题:非线性规划、线性规划非线性规划、线性规划95B天车与冶炼炉的作业调度天车与冶炼炉的作业调度:非线性规划、动态非线性规划、动态规划、层次分析法、规划、层次分析法、PETRI方法、图论方法、排队方法、图论方法、排队论方法论方法96A最优捕鱼策略最优捕鱼策略：微分方程、积分、非线性规划微分方程、积分、非线性规划696B节水洗衣机节水洗衣机：非线性规划非线性规划97A零件参数设计零件参数设计：微积分、非线性规划、随机模微积分、非线性规划、随机模拟拟97B截断切割截断切割：组合优化、几何变换、枚举、蒙特组合优化、几何变换、枚举、蒙特卡罗、递归、最短路卡罗、递归、最短路98A投资收益与风险投资收益与风险：线性规划、非线性规划线性规划、非线性规划98B灾情巡视路线灾情巡视路线：最小生成树、最小生成树、Hamilton圈、圈、旅行商问题旅行商问题99A自动化车床管理自动化车床管理：积分、概率分布、随机模拟、积分、概率分布、随机模拟、分布拟合度检验分布拟合度检验数学建模竞赛中的算法数学建模竞赛中的算法(2)799B钻井布局钻井布局：几何变换、枚举、最大完全子图、几何变换、枚举、最大完全子图、混合整数规划混合整数规划00ADNA分类分类：神经网络、最小二乘拟合、统计神经网络、最小二乘拟合、统计分类分类00B管道订购和运输管道订购和运输：最短路、二次规划最短路、二次规划01A血管的三维重建血管的三维重建：数据挖掘、曲面重建与拟数据挖掘、曲面重建与拟合合01B公交车调度公交车调度：非线性规划非线性规划02A车灯光源优化设计车灯光源优化设计：最优化最优化02B彩票中的数学彩票中的数学：概率与优化概率与优化数学建模竞赛中的算法数学建模竞赛中的算法(3)803ASARSSARS的传播：的传播：微分方程、差分方程微分方程、差分方程 03B露露天天矿矿生生产产的的车车辆辆安安排排：整整数数规规划划、运运输输问问题题04A 奥运会临时超市网点设计：奥运会临时超市网点设计：统计分析、数据统计分析、数据处理、优化处理、优化 04B 电力市场的输电阻塞管理：电力市场的输电阻塞管理：数据拟合、优化数据拟合、优化 05A 长江水质的评价和预测：长江水质的评价和预测：预测评价、数据预测评价、数据处理处理 05BDVDDVD在线租赁：在线租赁：随机规划、整数规划随机规划、整数规划 06A 出版社书号问题：出版社书号问题：整数规划、数据处理、整数规划、数据处理、优化优化数学建模竞赛中的算法数学建模竞赛中的算法(4)906B HivHiv病毒问题：病毒问题：线性规划、回归分析线性规划、回归分析07A 人口问题：人口问题：微分方程、数据处理、优化微分方程、数据处理、优化07B 公交车问题：公交车问题：多目标规划、动态规划、图多目标规划、动态规划、图 论、论、0-10-1规划规划08A 照相机问题：照相机问题：非线性方程组、优化非线性方程组、优化08B 大学学费问题：大学学费问题：数据收集和处理、统计分数据收集和处理、统计分 析、回归分析析、回归分析数学建模竞赛中的算法数学建模竞赛中的算法(5)10赛题发展的特点：赛题发展的特点：1.对选手的计算机能力提出了更高的要求：赛题对选手的计算机能力提出了更高的要求：赛题的解决依赖计算机，题目的数据较多，手工计算的解决依赖计算机，题目的数据较多，手工计算不能完成，计算机模拟和以算法形式给出最终结不能完成，计算机模拟和以算法形式给出最终结果。果。2.赛题的开放性增大赛题的开放性增大:解法的多样性，一道赛题解法的多样性，一道赛题可用多种解法。开放性还表现在对模型假设和对可用多种解法。开放性还表现在对模型假设和对数据处理上。数据处理上。3.试题向大规模数据处理方向发展试题向大规模数据处理方向发展4.求解算法和各类现代算法的融合求解算法和各类现代算法的融合111.蒙特卡罗方法(Monte-Carlo方法,MC)数学建模竞赛常用算法数学建模竞赛常用算法(1)该算法又称计算机随机性模拟方法计算机随机性模拟方法，也称统计试验统计试验方法方法。MC方法是一种基于“随机数”的计算方法，能够比较逼真地描述事物的特点及物理实验过程，解决一些数值方法难以解决的问题。MC方法的雏型可以追溯到十九世纪后期的蒲丰随机投针试验，即著名的蒲丰问题蒲丰问题。MC方法通过计算机仿真(模拟)解决问题，同时也可以通过模拟来检验自己模型的正确性，是比赛中经常使用的方法。1297年的年的A题题 每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。02年的年的B题题 关于彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。数学建模竞赛常用算法数学建模竞赛常用算法1398 年美国赛年美国赛A 题题生物组织切片的三维插值处理生物组织切片的三维插值处理94 年年A 题逢山开路题逢山开路山体海拔高度的插值计算山体海拔高度的插值计算数学建模竞赛常用算法数学建模竞赛常用算法(2)2.数据拟合、参数估计、插值等数据处理算法 比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MATLAB 作为工具。与图形处理有关的问题很多与拟合有关系。此类问题在MATLAB中有很多函数可以调用，只有熟悉MATLAB，这些方法才能用好。1498年年B 题题 用很多不等式完全可以把问题刻画清楚用很多不等式完全可以把问题刻画清楚数学建模竞赛常用算法数学建模竞赛常用算法(3)3.规划类问题算法 此类问题主要有线性规划、整数规划、多目标规划、线性规划、整数规划、多目标规划、二次规划二次规划等。竞赛中很多问题都和数学规划有关，可以说不少的模型都可以归结为一组不等式作为约束条件、几个函数表达式作为目标函数的问题，遇到这类问题，求解就是关键了。因此列举出规划后用Lindo、Lingo 等软件来进行解决比较方便，所以还需要熟悉这两个软件。1598 年年B 题、题、00年年B 题、题、95 年锁具装箱年锁具装箱等问题体现等问题体现了了图论问题图论问题的重要性。的重要性。数学建模竞赛常用算法数学建模竞赛常用算法(4)4.图论问题 这类问题算法有很多，包括：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配，最大流，二分匹配等问题。1692 年年B 题用分枝定界法题用分枝定界法97 年年B 题是典型的动态规划问题题是典型的动态规划问题98 年年B 题体现了分治算法题体现了分治算法数学建模竞赛常用算法数学建模竞赛常用算法(5)5.计算机算法设计中的问题 计算机算法设计包括很多内容：动态规划、回溯搜动态规划、回溯搜索、分治算法、分枝定界索、分治算法、分枝定界等计算机算法.这方面问题和ACM 程序设计竞赛中的问题类似，可看一下与计算机算法有关的书。17分枝定界法分枝定界法原问题的松驰问题：原问题的松驰问题：任何整数规划（任何整数规划（IP），凡放弃某些约束），凡放弃某些约束条件（如整数要求）后，所得到的问题条件（如整数要求）后，所得到的问题（P）都称为（都称为（IP）的松驰问题。）的松驰问题。最通常的松驰问题是放弃变量的整数性最通常的松驰问题是放弃变量的整数性要求后，（要求后，（P）为线性规划问题。）为线性规划问题。18去掉整数约束去掉整数约束去掉整数约束去掉整数约束,用单纯形法用单纯形法用单纯形法用单纯形法IP LP IP LP xl*判别是否整数解判别是否整数解xI*=xl*YesYes去掉非整数域去掉非整数域NoNo多个多个LPLP19 分枝定界法步骤分枝定界法步骤一般求解对应的松驰问题，可能会出现一般求解对应的松驰问题，可能会出现下面几种情况：下面几种情况：若所得的最优解的各分量恰好是整数，若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计则这个解也是原整数规划的最优解，计算结束。算结束。20 分枝定界法步骤分枝定界法步骤一般求解对应的松驰问题，可能会出现一般求解对应的松驰问题，可能会出现下面几种情况：下面几种情况：若所得的最优解的各分量恰好是整数，若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计则这个解也是原整数规划的最优解，计算结束。算结束。若松驰问题无可行解，则原整数规划若松驰问题无可行解，则原整数规划问题也无可行解，计算结束。问题也无可行解，计算结束。21若松驰问题有最优解，但其各分量不全若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最是整数，则这个解不是原整数规划的最优解，转下一步。优解，转下一步。22若松驰问题有最优解，但其各分量不全若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最是整数，则这个解不是原整数规划的最优解，转下一步。优解，转下一步。从不满足整数条件的基变量中任选从不满足整数条件的基变量中任选 一一个个xl进行分枝，它必须满足进行分枝，它必须满足xl xl 或或 xl xl +1中的一个，把这两个约束条件加进中的一个，把这两个约束条件加进原问题中，形成两个互不相容的子问题原问题中，形成两个互不相容的子问题（两分法）（两分法）。23定界：把满足整数条件各分枝的最优定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用它来判目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。断分枝是保留还是剪枝。24定界：把满足整数条件各分枝的最优定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用它来判目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。断分枝是保留还是剪枝。剪枝：把那些子问题的最优值与界值剪枝：把那些子问题的最优值与界值比较，凡不优或不能更优的分枝全剪掉，比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查清为止。直到每个分枝都查清为止。25例：例：用分枝定界法求解：用分枝定界法求解：Max Z=4x1+3x2s.t.3x1+4x2 12 4x1+2x2 9 x1,x2 0 整数整数用单纯形法可解得相应的松驰问题的用单纯形法可解得相应的松驰问题的最优解（最优解（6/5，21/10）Z=111/10为各分为各分枝的上界。枝的上界。260 1 2 3 44 3 2 1x1x2分枝：分枝：分枝：分枝：x x1 1 1,x 1,x1 1 2 2P P1 1P P2 2（6/5，21/10）27两个子问题：两个子问题：（P1）Max Z=4x1+3x2 s.t.3x1+4x2 12 4x1+2x2 9 x1,x2 0，x1 1 ，整数，整数用单纯形法可解得相应的（用单纯形法可解得相应的（P1）的最优）的最优解（解（1，9/4）Z=10(3/4)28（P2）Max Z=4x1+3x2 s.t.3x1+4x2 12 4x1+2x2 9 x1,x2 0，x1 2 ，整数，整数用单纯形法可解得相应的（用单纯形法可解得相应的（P2）的最优）的最优解（解（2，1/2）Z=9(1/2)290 1 2 3 44 3 2 1x1x2再对（再对（再对（再对（P P1 1）x x1 1 1 1（1，9/4）分枝：分枝：分枝：分枝：（P P3 3）x x2 2 2 2 （P P4 4）x x2 2 3 3P P1 1P P2 2P P3 3P P4 430（P1）两个子问题：）两个子问题：（P3）Max Z=4x1+3x2 s.t.3x1+4x2 12 4x1+2x2 9 x1,x2 0,x1 1,x2 2整数整数用单纯形法可解得相应的（用单纯形法可解得相应的（P3）的最优）的最优解（解（1，2）Z=10 为上界为上界31（P1）两个子问题：）两个子问题：（P4）Max Z=4x1+3x2 s.t.3x1+4x2 12 4x1+2x2 9 x1,x2 0,x1 1,x2 3整数整数用单纯形法可解得相应的（用单纯形法可解得相应的（P4）的最优）的最优解（解（0，3）Z=932X1 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/10原问题的最优解原问题的最优解（1，2）Z=1033多阶段决策过程最优化多阶段决策过程最优化 多阶段决策过程是指这样一类特殊的活动多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联过程，他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。题也称为序贯决策问题。动态规划应用举例动态规划应用举例34最优化原理：最优策略的任一后部子策略都是最优的。无论以前状态决策如何，从眼下直到最后的诸决策必构成最优子策略。例1最短路线问题AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143动态规划应用举例动态规划应用举例35例例1 1 多阶段资源分配问题多阶段资源分配问题 设设有有数数量量为为x的的某某种种资资源源，将将它它投投入入两两种种生生产产方方式式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个阶段后的最大总收入。个阶段后的最大总收入。36若以若以y与与x-y分别投入生产方式分别投入生产方式A与与B，在第一，在第一阶段生产后回收的总资源为阶段生产后回收的总资源为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）37因因此此，我我们们的的问问题题就就变变成成：求求y,y1,y2,yn-1，以以使使g(y)+h(x-y)+g(y1)+h(x1-y1)+g(yn-1)+h(xn-1-yn-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）38例例2 2 生产和存储控制问题生产和存储控制问题某工厂生产某种季节性商品，需要作下一某工厂生产某种季节性商品，需要作下一年度的生产计划，假定这种商品的生产周期需年度的生产计划，假定这种商品的生产周期需要两个月，全年共有要两个月，全年共有6个生产周期，需要作出个生产周期，需要作出各个周期中的生产计划。各个周期中的生产计划。39设已知各周期对该商品的需要量如下表所示设已知各周期对该商品的需要量如下表所示：周期周期123456需求量需求量551030508例例2 2 续（续（1 1）40例例2 2 续（续（2 2）假设这个工厂根据需要可以日夜两班生产或只是日假设这个工厂根据需要可以日夜两班生产或只是日班生产，当开足日班时，每一个生产周期能生产商品班生产，当开足日班时，每一个生产周期能生产商品1515个单位，每生产一个单位商品的成本为个单位，每生产一个单位商品的成本为100100元。当开足元。当开足夜班时，每一生产周期能生产的商品也是夜班时，每一生产周期能生产的商品也是1515个，但是由个，但是由于增加了辅助性生产设备和生产辅助费用，每生产一单于增加了辅助性生产设备和生产辅助费用，每生产一单位商品的成本为位商品的成本为120120元。由于生产能力的限制，可以在元。由于生产能力的限制，可以在需求淡季多生产一些商品储存起来以备需求旺季使用，需求淡季多生产一些商品储存起来以备需求旺季使用，但存储商品是需要存储但存储商品是需要存储费用的，假设每单位商品存储一费用的，假设每单位商品存储一周期需要周期需要16元，已知开始时存储为零，年终也不存储商元，已知开始时存储为零，年终也不存储商品备下年使用，问应该如何作生产和存储计划，才能使品备下年使用，问应该如何作生产和存储计划，才能使总的生产和存储费用最小？总的生产和存储费用最小？41例例2 2 续（续（3 3）设第设第i个周期的生产量为个周期的生产量为xi，周期末的存储量为，周期末的存储量为ui，那，那么这个问题用式子写出来就是：求么这个问题用式子写出来就是：求x1,x2,x6，满足条件：，满足条件：x1=5+u1x2+u1=5+u2x3+u2=10+u3x4+u3=30+u4x5+u4=50+u5x6+u5=80 xi30,0uj,i=1,2,6;j=1,2,5使使S=为最小，其中为最小，其中42例例2 2 续（续（4 4）43逆序递推方程：（1）k=5时，状态它们到F点的距离即为最短路。AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143例1：1阶段2阶段3阶段4阶段5阶段44AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（2）k=4时，状态它们到F点需经过中途点E，需一一分析从E到F的最短路：先说从D1到F的最短路有两种选择：经过E1,E2,比较最短。45AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143这说明由D1到F的最短距离为7，其路径为相应的决策为：46这说明由D2到F的最短距离为5，其路径为相应的决策为：AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314347AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即D3到F的最短距离为5，其路径为相应的决策为：48（3）k=3时，状态这说明由C1到F的最短距离为12，相应的决策为AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314349AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即由C2到F的最短距离为10，相应的决策为50即由C3到F的最短距离为8，相应的决策为即由C4到F的最短距离为9，相应的决策为AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314351AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（4）k=2时，状态这说明由B1到F的最短距离为13，相应的决策为52即由B2到F的最短距离为15，相应的决策为AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314353AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（1）k=1时，只有一个状态点A,则即由A到F的最短距离为17，相应的决策为54所以最优路线为：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143再按计算顺序反推可得最优决策序列：5597年年A 题用模拟退火算法题用模拟退火算法00年年B 题用神经网络分类算法题用神经网络分类算法01年年B 题这种难题也可以使用神经网络题这种难题也可以使用神经网络美国美国03年年B 题题伽马刀问题也是目前研究的课题，目前算法最佳的是遗传算法算法最佳的是遗传算法。数学建模竞赛常用算法数学建模竞赛常用算法(6)6.最优化理论的三大非经典算法:模拟退火法(SA)、神经网络(NN)、遗传算法(GA)近几年的赛题越来越复杂，很多问题没有什么很好的模型可以借鉴，于是这三类算法很多时候可以派上用场。5697 年年A 题、题、99 年年B 题都可以题都可以用网格法搜索用网格法搜索数学建模竞赛常用算法数学建模竞赛常用算法(7)网格算法和穷举法一样，只是网格法是连续问题的穷举。此类算法运算量较大。7.网格算法和穷举算法 这种方法最好在运算速度较快的计算机中进行，还有要用高级语言来做，最好不要用MATLAB 做网格，否则会算很久。57很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此需要将连续问题进行将连续问题进行离散化处理后再用计算机求解离散化处理后再用计算机求解。比如差分代替微分、求和代替积分等思想都是把连续问题离散化的常用方法。数学建模竞赛常用算法数学建模竞赛常用算法(8)8.连续问题离散化的方法58数值分析研究各种求解数学问题的数值计算方法求解数学问题的数值计算方法，特别是适合于计算机实现方法与算法。数学建模竞赛常用算法数学建模竞赛常用算法(9)9.数值分析方法 它的主要内容包括函数的数值逼近、数值微分与数函数的数值逼近、数值微分与数值积分、非线性方程的数值解法、数值代数、常微分方值积分、非线性方程的数值解法、数值代数、常微分方程数值解程数值解等。数值分析是计算数学的一个重要分支，把理论与计算紧密结合,是现代科学计算的基础。MATLAB等数学软件中已经有很多数值分析的函数可以直接调用。5901年年A 题中需要你会读题中需要你会读BMP 图象图象98年美国年美国A 题需要你知道三维插值计算题需要你知道三维插值计算03年年B 题要求更高，不但需要编程计算还要进行题要求更高，不但需要编程计算还要进行处理处理数学建模竞赛常用算法数学建模竞赛常用算法(10)10.图象处理算法 赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB进行处理。数模论文中也有很多图片需要展示，解决这类问题要熟悉MATLAB图形图像工具箱。60例1某公司拥有一块可能有油的土地，根据可能出油的多少，该块土地属于四种类型：可产油50万桶、20万桶、5万桶、无油。公司目前有3个方案可供选择：自行钻进；无条件将该块土地出租给其他使用者；有条件的租给其他生产者。若自行钻井，打出一口有油井的费用是10万元，打出一口无油井决策分析决策分析61的费用是7.5万元，每一桶油的利润是1.5万。若无条件出租，不管出油多少，公司收取固定租金4.5万元；若有条件出租，公司不收取租金，但当产量为20万桶至50万桶时，每桶公司收取0.5元。由上计算得到该公司可能的利润收入见表14-1.按过去的经验，该块土地属于上面4种类型的可能性分别为10%，15%，25%和50%。问题是该公司应选择哪种方案，可获得最大利润？62表14-1石油公司可能利润收入表（单位：万元）类 型项目50万桶20万桶5万桶无油自行钻井无条件出租有条件出租654.525204.5102.54.507.54.50解：各个方案的期望收益为根据期望收益最大原则，应选择，即自行钻井。63效用理论效用理论一、效用概念的引入一、效用概念的引入前面介绍风险型决策方法时，提到可根据期望益损值（最大或前面介绍风险型决策方法时，提到可根据期望益损值（最大或最小）作为选择最优方案的原则，但这样做并不一定合理。请最小）作为选择最优方案的原则，但这样做并不一定合理。请看下面的例子：看下面的例子：例例6设有两个决策问题：设有两个决策问题：问题问题1：方案：方案A1：稳获：稳获100元；元；方案方案B1:用掷硬币的方法，掷出正面获得用掷硬币的方法，掷出正面获得250元，掷元，掷出反面获得出反面获得0元。元。64问题问题2：方案：方案A2：稳获：稳获1000元；元；方案方案B2:用掷硬币的方法，直到掷出正面为止，记所用掷硬币的方法，直到掷出正面为止，记所掷次数为掷次数为N，则当正面出现时，可获，则当正面出现时，可获2N元元.当你遇到这两类问题时，如何决策？大部分会选择当你遇到这两类问题时，如何决策？大部分会选择A1和和A2。但不妨计算一下其期望值：但不妨计算一下其期望值：Y10250P(Y1=k)1/21/2方案方案B1的收益为随机变量的收益为随机变量Y1。则其期望收益为：则其期望收益为：65设方案设方案B2的收益为随机变量的收益为随机变量Y2。Ai=“第第i次掷出正面次掷出正面”，则第，则第n次掷出正面的概率为：次掷出正面的概率为：Y222223nP(Y2=k)1/21/221/231/2nX012n-1相互独立相互独立设掷出正面前掷出反面的次数为随机变量设掷出正面前掷出反面的次数为随机变量X,则有分布列：则有分布列：则方案则方案2的平均收益为：的平均收益为：66Y222223nP(Y2=k)1/21/221/231/2nX012n-1于是，根据期望收益最大原则，应选择于是，根据期望收益最大原则，应选择B1和和B2，但这一结果，但这一结果很难令实际决策者接受。此乃研究效用函数的初衷。很难令实际决策者接受。此乃研究效用函数的初衷。例例7（赌一把）一个正常的人，遇到（赌一把）一个正常的人，遇到“赌一把赌一把”的机会。情的机会。情况况如下面的树，问此人如何决策？如下面的树，问此人如何决策？67正常人B赌不赌45元掷出正面P=0.5-10元P=0.50100元掷出反面45元对绝大部分人来说，对绝大部分人来说，只要兜里有只要兜里有10元钱，元钱，又不急用的话，就选又不急用的话，就选择择“赌赌”。因此时。因此时“赌赌”的平均收益为：的平均收益为：类似的问题，让一个被判刑十年且手头仅有类似的问题，让一个被判刑十年且手头仅有10元钱的罪犯元钱的罪犯做下面的决策：做下面的决策：68罪犯B赌释放释放45元掷出正面P=0.5-10元P=0.5-10元100元掷出反面45元此时罪犯可能要选此时罪犯可能要选择交出择交出10元钱，获元钱，获得释放。得释放。以上例子说明：以上例子说明：相同的期望益损值（以货币值为度量）的不同随机事件之相同的期望益损值（以货币值为度量）的不同随机事件之间其风险可能存在着很大的差异。即说明间其风险可能存在着很大的差异。即说明货币量的期望益损货币量的期望益损值不能完全反映随机事件的风险程度。值不能完全反映随机事件的风险程度。同一同一随机事件对不同的决策者的吸引力可能完全不同，因随机事件对不同的决策者的吸引力可能完全不同，因此可采用不同的决策。这与决策者个人的气质、冒险精神、此可采用不同的决策。这与决策者个人的气质、冒险精神、69经济状况、经验等等主观因素有很大的关系。经济状况、经验等等主观因素有很大的关系。即使同一个人在不同情况下对同一即使同一个人在不同情况下对同一随机事件也会采用随机事件也会采用不同的态度。不同的态度。当我们以期望益损值（以货币值为度量）作决策准则时，实当我们以期望益损值（以货币值为度量）作决策准则时，实际已经假定际已经假定期望益损值相等的各个随机事件是等价的，具有期望益损值相等的各个随机事件是等价的，具有相同的风险程度，且对不同的人具有相同的吸引力相同的风险程度，且对不同的人具有相同的吸引力。但对有。但对有些问题这个假定是不合适的。因此不能采用货币度量的期望些问题这个假定是不合适的。因此不能采用货币度量的期望益损值作决策准则，而用所谓益损值作决策准则，而用所谓“效用值效用值”作决策准则。作决策准则。70二、效用曲线的确定及分类二、效用曲线的确定及分类老王B二次抽奖一次500元P=0.50元P=0.5500元1000元500元为了讲清为了讲清“效用效用”与与“效效用值用值”的概念，看下的概念，看下例例例例老王参加某电视台综艺老王参加某电视台综艺节目而得奖。他有两种方式可选择：节目而得奖。他有两种方式可选择：一次获得一次获得500元奖金。元奖金。分别以概率分别以概率0.5与与0.5的机会抽奖可获得的机会抽奖可获得1000元与元与0元。元。试问老王该选择何种方式领奖？试问老王该选择何种方式领奖？71事件事件的期望益损值都是的期望益损值都是500元，但有人认为元，但有人认为应选择应选择他认为他认为的的“价值价值”比比大，有的相反。都是大，有的相反。都是“主观价主观价值值”。此时他认为事件此时他认为事件的效用比事件的效用比事件来的大。来的大。如何来度量随机事件的效用（或说如何来度量随机事件的效用（或说“价值价值”）？我们用）？我们用“效用效用值值”u来度量效用值的大小。来度量效用值的大小。“效用值效用值”是一个是一个“主观价值主观价值”，且，且是一是一个相对大小的值。通常假定决策者最偏好、最倾向、最喜欢的个相对大小的值。通常假定决策者最偏好、最倾向、最喜欢的事情（方案）的效用为事情（方案）的效用为1，而最不偏好、最不倾向、最不喜欢，而最不偏好、最不倾向、最不喜欢的事情（方案）的效用为的事情（方案）的效用为0。一般来说，若用一般来说，若用r来表示期望收益值（这里收益值作广义理来表示期望收益值（这里收益值作广义理解，不一定是货币量，也可以是某事件的结果），则解，不一定是货币量，也可以是某事件的结果），则r的效用的效用72那么，当那么，当时如时如何计算呢？何计算呢？值用值用来表示。因此有来表示。因此有一般用心理测试的方法来确定一般用心理测试的方法来确定，具体做法是：反复向，具体做法是：反复向决策决策者提出下面的问题：者提出下面的问题：“如果事件如果事件是以概率是以概率P得到收益为得到收益为，以概率（以概率（1-P）得到收益为）得到收益为，事件，事件是以是以100%概率得概率得到收到收益为益为你认为你认为取多大值时，事件取多大值时，事件与事件与事件是是相当的（即认为效用值相等）？如果决策者经过思考后，认为相当的（即认为效用值相等）？如果决策者经过思考后，认为时时两事件效用是相当的，即有两事件效用是相当的，即有73当当，已知时，则已知时，则的效用值可的效用值可求出。如当求出。如当则则则则可求出可求出的效用值，再在已知效用值的三点的效用值，再在已知效用值的三点中的任意两点，再作出同样的问题来问决策者，则可在两点中中的任意两点，再作出同样的问题来问决策者，则可在两点中求出一点的效用值。如此继续，可得到在求出一点的效用值。如此继续，可得到在及及中间的中间的一系列一系列的效用值的效用值。再以。再以作横坐标，作横坐标，作作纵坐标可纵坐标可得该决策者的效用曲线。举例如下。得该决策者的效用曲线。举例如下。例例设某决策者在股票交易所购买股票，现有两种选择：设某决策者在股票交易所购买股票，现有两种选择：选择股票选择股票01号，预计每手（号，预计每手（100股）可能分别以概率股）可能分别以概率0.5获利获利200元，概率元，概率0.5损失损失100元。元。74选择股票选择股票02号，预计每手（号，预计每手（100股）可能以概率股）可能以概率1.0获获利利25元。元。试问该决策者应选择何种方式购买股票？试问该决策者应选择何种方式购买股票？用心理测试法对该决策者提问：用心理测试法对该决策者提问：对上述事件对上述事件 ，问决策者愿意选择何种方式？，问决策者愿意选择何种方式？决策者B01号股票02号股票0.5P=0.5-100元P=0.525元200元若决策者选择若决策者选择，则，则降降低低到到20元，若还选元，若还选择择则再降低则再降低，若降至，若降至0元（即不赔不赚）时，元（即不赔不赚）时，决策者犹豫不定，说明决策者犹豫不定，说明选择股票选择股票01号，预计每手（号，预计每手（100股）可能分别以概率股）可能分别以概率0.5获利获利200元，概率元，概率0.5损失损失100元。元。75此时随机事件此时随机事件的效的效用值用值与与相等。相等。求出求出时的时的效益效益值：值：得到效用曲线的三点。得到效用曲线的三点。0元P=1.0决策者01号股票02号股票0.5P=0.5-100元P=0.5200元B1B20.576决策者01号股票02号股票0.75P=0.50元P=0.540元200元选择股票选择股票02号，预计每手号，预计每手（100股）可能以概股）可能以概率率1.0获利获利40元。元。试问该决策者应选择何种试问该决策者应选择何种方式购买股票？方式购买股票？再求再求 与与 之间某一点之间某一点 的效用值。提出的效用值。提出如下的问题：如下的问题：选择股票选择股票01号，预计每手（号，预计每手（100股）可能分别以概率股）可能分别以概率0.5获利获利200元，概率元，概率0.5损失损失0元。元。B1B2P=1.00.7577决策者01号股票02号股票0.75P=0.50元P=0.5200元B1B2P=1.00.7540元60元若决策者选择若决策者选择，则，则提提高高02号股票到号股票到60元。决策元。决策者犹豫不定，说明此时随者犹豫不定，说明此时随机事件机事件的效用值与的效用值与相等。相等。求出求出时的效时的效用值：用值：得到效用曲线的四个点。得到效用曲线的四个点。78提出如下的问题，可得提出如下的问题，可得-100元到元到0元之间的某点元之间的某点效用值。效用值。选择股票选择股票01号，预计号，预计每手可能分别以概率每手可能分别以概率0.5获利获利0元，元，以概率以概率0.5获利获利-100元。元。决策者B101号股票02号股票P=0.5-100元P=0.5-30元0元B2P=1.0选择股票选择股票02号，号，预计每手可能以概预计每手可能以概率率1.0获利获利-30元。元。79试问该决策者应选择何种方式购买股票？试问该决策者应选择何种方式购买股票？决策者01号股票02号股票0.25P=0.5-100元P=0.50元B1B2P=1.00.25-30元-60元80120元决策者01号股票02号股票0.875P=0.560元P=0.5200元B1B2P=1.00.875 同理在同理在6060元到元到200200元之元之间求出某点的