运筹学的优化算法.ppt

《运筹学的优化算法.ppt》由会员分享，可在线阅读，更多相关《运筹学的优化算法.ppt（199页珍藏版）》请在三一办公上搜索。

1、1,运筹学的优化算法,2,运 筹 学（Operations Research OR）由于运筹学研究的广泛性和复杂性，人们至今没有形成一个统一的定义。以下给出几种定义：运筹学是一种科学决策的方法运筹学是依据给定目标和条件从众多方案中选择最优方案的最优化技术。运筹学是一种给出坏的问题的答案的艺术，否则的话问题的结果会更坏。,3,运筹学模型 运筹学研究的模型主要是抽象模型数学模型。,4,运筹学包含的分支数学规划（线性规划、整数规划、目标规划、动态规划、网络规划等）图论与网络流决策分析,5,运筹学包含的分支排队论可靠性数学理论库存论对策论搜索论计算机模拟等,6,数学建模竞赛中的算法(1),93A 非线

2、性交调的频率设计:拟合、规划93B 足球队排名次:矩阵论、图论、层次分析法、整数规划94A 逢山开路:图论、插值、动态规划94B 锁具装箱问题:图论、组合数学95A 飞行管理问题:非线性规划、线性规划95B 天车与冶炼炉的作业调度:非线性规划、动态规划、层次分析法、PETRI方法、图论方法、排队论方法96A 最优捕鱼策略：微分方程、积分、非线性规划,7,96B 节水洗衣机：非线性规划97A 零件参数设计：微积分、非线性规划、随机模拟97B 截断切割：组合优化、几何变换、枚举、蒙特卡罗、递归、最短路98A 投资收益与风险：线性规划、非线性规划98B 灾情巡视路线：最小生成树、Hamilton圈、

3、旅行商问题99A 自动化车床管理：积分、概率分布、随机模拟、分布拟合度检验,数学建模竞赛中的算法(2),8,99B 钻井布局：几何变换、枚举、最大完全子图、混合整数规划00A DNA分类：神经网络、最小二乘拟合、统计分类00B 管道订购和运输：最短路、二次规划01A 血管的三维重建：数据挖掘、曲面重建与拟合01B 公交车调度：非线性规划02A 车灯光源优化设计：最优化02B 彩票中的数学：概率与优化,数学建模竞赛中的算法(3),9,03ASARS的传播：微分方程、差分方程 03B露天矿生产的车辆安排：整数规划、运输问题04A 奥运会临时超市网点设计：统计分析、数据处理、优化 04B 电力市场的

4、输电阻塞管理：数据拟合、优化 05A 长江水质的评价和预测：预测评价、数据处理 05BDVD在线租赁：随机规划、整数规划 06A 出版社书号问题：整数规划、数据处理、优化,数学建模竞赛中的算法(4),10,06B Hiv病毒问题：线性规划、回归分析07A 人口问题：微分方程、数据处理、优化07B 公交车问题：多目标规划、动态规划、图 论、0-1规划08A 照相机问题：非线性方程组、优化08B 大学学费问题：数据收集和处理、统计分 析、回归分析,数学建模竞赛中的算法(5),11,赛题发展的特点：1.对选手的计算机能力提出了更高的要求：赛题的解决依赖计算机，题目的数据较多，手工计算不能完成，计算机

5、模拟和以算法形式给出最终结果。2.赛题的开放性增大:解法的多样性，一道赛题可用多种解法。开放性还表现在对模型假设和对数据处理上。3.试题向大规模数据处理方向发展 4.求解算法和各类现代算法的融合,12,1.蒙特卡罗方法(Monte-Carlo方法,MC),数学建模竞赛常用算法(1),该算法又称计算机随机性模拟方法，也称统计试验方法。MC方法是一种基于“随机数”的计算方法，能够比较逼真地描述事物的特点及物理实验过程，解决一些数值方法难以解决的问题。,MC方法的雏型可以追溯到十九世纪后期的蒲丰随机投针试验，即著名的蒲丰问题。MC方法通过计算机仿真(模拟)解决问题，同时也可以通过模拟来检验自己模型的

6、正确性，是比赛中经常使用的方法。,13,97年的A题 每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。02年的B题 关于彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。,数学建模竞赛常用算法,14,98 年美国赛A

7、 题 生物组织切片的三维插值处理94 年A 题逢山开路 山体海拔高度的插值计算,数学建模竞赛常用算法(2),2.数据拟合、参数估计、插值等数据处理算法,比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MATLAB 作为工具。与图形处理有关的问题很多与拟合有关系。,此类问题在MATLAB中有很多函数可以调用，只有熟悉MATLAB，这些方法才能用好。,15,98年B 题 用很多不等式完全可以把问题刻画清楚,数学建模竞赛常用算法(3),3.规划类问题算法,此类问题主要有线性规划、整数规划、多目标规划、二次规划等。竞赛中很多问题都和数学规划有关，可以说不少的模型都可以归结为

8、一组不等式作为约束条件、几个函数表达式作为目标函数的问题，遇到这类问题，求解就是关键了。,因此列举出规划后用Lindo、Lingo 等软件来进行解决比较方便，所以还需要熟悉这两个软件。,16,98 年B 题、00年B 题、95 年锁具装箱等问题体现了图论问题的重要性。,数学建模竞赛常用算法(4),4.图论问题,这类问题算法有很多，包括：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配等问题。,17,92 年B 题用分枝定界法97 年B 题是典型的动态规划问题98 年B 题体现了分治算法,数学建模竞赛常用算法(5),5.计算机算法设计中的问题,计算机算法设计包括

9、很多内容：动态规划、回溯搜索、分治算法、分枝定界等计算机算法.,这方面问题和ACM 程序设计竞赛中的问题类似，可看一下与计算机算法有关的书。,18,分枝定界法原问题的松驰问题：任何整数规划（IP），凡放弃某些约束条件（如整数要求）后，所得到的问题（P）都称为（IP）的松驰问题。,最通常的松驰问题是放弃变量的整数性要求后，（P）为线性规划问题。,19,去掉整数约束,用单纯形法,20,分枝定界法步骤一般求解对应的松驰问题，可能会出现下面几种情况：若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。,21,分枝定界法步骤一般求解对应的松驰问题，可能会出现下面几种情况：若所得的

10、最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。若松驰问题无可行解，则原整数规划问题也无可行解，计算结束。,22,若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。,23,若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。从不满足整数条件的基变量中任选 一个xl进行分枝，它必须满足xl xl 或 xl xl+1中的一个，把这两个约束条件加进原问题中，形成两个互不相容的子问题（两分法）。,24,定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。,25,定界：把满足整数条件

11、各分枝的最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。剪枝：把那些子问题的最优值与界值比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查清为止。,26,例：用分枝定界法求解：Max Z=4x1+3x2s.t.3x1+4x2 12 4x1+2x2 9 x1,x2 0 整数用单纯形法可解得相应的松驰问题的最优解（6/5，21/10）Z=111/10为各分枝的上界。,27,0 1 2 3 4,4 3 2 1,x1,x2,分枝：x1 1,x1 2,P1,P2,（6/5，21/10）,28,两个子问题：（P1）Max Z=4x1+3x2 s.t.3x1+4x2 12 4x1+2x2 9

12、x1,x2 0，x1 1，整数用单纯形法可解得相应的（P1）的最优解（1，9/4）Z=10(3/4),29,（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),30,0 1 2 3 4,4 3 2 1,x1,x2,再对（P1）x1 1（1，9/4）分枝：（P3）x2 2（P4）x2 3,P1,P2,P3,P4,31,（P1）两个子问题：（P3）Max Z=4x1+3x2 s.t.3x1+4x2 12 4x1+2x2 9 x1,x2 0,x1 1,x2 2整数用单

13、纯形法可解得相应的（P3）的最优解（1，2）Z=10 为上界,32,（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=9,33,X1 2,X2 2,X1 1,X2 3,P1:(1,9/4)Z=10(3/4),P4:(0,3)Z=9,P2:(2,1/2)Z=9(1/2),P3:(1,2)Z=10,P:(6/5,21/10)Z=111/10,原问题的最优解（1，2）Z=10,34,多阶段决策过程最优化 多阶段决策过程是指这样一类特殊的活动过程，他们可以按

14、时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。,动态规划应用举例,35,最优化原理：最优策略的任一后部子策略都是最优的。,无论以前状态决策如何，从眼下直到最后的诸决策必构成最优子策略。,例1 最短路线问题,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,动态规划应用举例,36,例1 多阶段资源分配问题,设有数量为x的某种资源，将它投入两种生产方式A和B中：以数量y投入生产方式A，剩下的量投入生产

15、方式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，在第一阶段生产后回收的总资源为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）,38,因此，我们的问题就变成：求y,y1,y2

16、,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 续（2）,39,例2 生产和存储控制问题,某工厂生产某种季节性商品，需要作下一年度的生产计划，假定这种商品的生产周期需要两个月，全年共有6个生产周期，需要作出各个周期中的生产计划。,40,设已知各周期对该商品的需要量如下表所示：,例2 续（1）,41,例2 续（2）,假设这个工厂根据需要可以日夜两班生产或只是日班生产，当开

17、足日班时，每一个生产周期能生产商品15个单位，每生产一个单位商品的成本为100元。当开足夜班时，每一生产周期能生产的商品也是15个，但是由于增加了辅助性生产设备和生产辅助费用，每生产一单位商品的成本为120元。由于生产能力的限制，可以在需求淡季多生产一些商品储存起来以备需求旺季使用，但存储商品是需要存储费用的，假设每单位商品存储一周期需要16元，已知开始时存储为零，年终也不存储商品备下年使用，问应该如何作生产和存储计划，才能使总的生产和存储费用最小？,42,例2 续（3）,设第i个周期的生产量为xi，周期末的存储量为ui，那么这个问题用式子写出来就是：求x1,x2,x6，满足条件：x1=5+u

18、1 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=为最小，其中,43,例2 续（4）,44,逆序递推方程：,（1）k=5 时，状态,它们到F 点的距离即为,最短路。,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,例1：,1阶段,2阶段,3阶段,4阶段,5阶段,45,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,

19、2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,（2）k=4 时，状态,它们到F 点需经过中途,点E，需一一分析从E 到 F的最短路：先说从D1到F 的最短路,有两种选择：经过 E1,E2,比较最短。,46,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,这说明由 D1 到F 的最短距离为7，其路径为,相应的决策为：,47,这说明由 D2 到F 的最短距离为5，其路径为,相应的决策为：,A,B1,B2,C1,C2,C3,C4,D1,D

20、2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,48,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,即 D3 到F 的最短距离为5，其路径为,相应的决策为：,49,（3）k=3 时，状态,这说明由 C1 到F 的最短距离为12，相应的决策为,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1

21、,4,3,50,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,即由 C2 到F 的最短距离为10，相应的决策为,51,即由 C3 到F 的最短距离为8，相应的决策为,即由 C4 到F 的最短距离为9，相应的决策为,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,52,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,

22、3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,（4）k=2时，状态,这说明由 B1 到F 的最短距离为13，相应的决策为,53,即由 B2到F 的最短距离为15，相应的决策为,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,54,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,（1）k=1 时，只有一个状态点A,则,

23、即由 A到F 的最短距离为17，相应的决策为,55,所以最优路线为：,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,再按计算顺序反推可得最优决策序列：,56,97年A 题用模拟退火算法00年B 题用神经网络分类算法01年B 题这种难题也可以使用神经网络美国03年B 题伽马刀问题也是目前研究的课题，目前算法最佳的是遗传算法。,数学建模竞赛常用算法(6),6.最优化理论的三大非经典算法:模拟退火法(SA)、神经网络(NN)、遗传算法(GA),近几年的赛题越来越复杂，很多问题没

24、有什么很好的模型可以借鉴，于是这三类算法很多时候可以派上用场。,57,97 年A 题、99 年B 题都可以用网格法搜索,数学建模竞赛常用算法(7),网格算法和穷举法一样，只是网格法是连续问题的穷举。此类算法运算量较大。,7.网格算法和穷举算法,这种方法最好在运算速度较快的计算机中进行，还有要用高级语言来做，最好不要用MATLAB 做网格，否则会算很久。,58,很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此需要将连续问题进行离散化处理后再用计算机求解。比如差分代替微分、求和代替积分等思想都是把连续问题离散化的常用方法。,数学建模竞赛常用算法(8),8.连续问题离散化的方

25、法,59,数值分析研究各种求解数学问题的数值计算方法，特别是适合于计算机实现方法与算法。,数学建模竞赛常用算法(9),9.数值分析方法,它的主要内容包括函数的数值逼近、数值微分与数值积分、非线性方程的数值解法、数值代数、常微分方程数值解等。数值分析是计算数学的一个重要分支，把理论与计算紧密结合,是现代科学计算的基础。,MATLAB等数学软件中已经有很多数值分析的函数可以直接调用。,60,01年A 题中需要你会读BMP 图象98年美国A 题需要你知道三维插值计算03年B 题要求更高，不但需要编程计算还要进行处理,数学建模竞赛常用算法(10),10.图象处理算法,赛题中有一类问题与图形有关，即使问

26、题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB进行处理。,数模论文中也有很多图片需要展示，解决这类问题要熟悉MATLAB图形图像工具箱。,61,例1某公司拥有一块可能有油的土地，根据可能出油的多少，该块土地属于四种类型：可产油50万桶、20万桶、5万桶、无油。公司目前有3个方案可供选择：自行钻进；无条件将该块土地出租给其他使用者；有条件的租给其他生产者。若自行钻井，打出一口有油井的费用是10万元，打出一口无油井,决策分析,62,的费用是7.5万元，每一桶油的利润是1.5万。若无条件出租，不管出油多少，公司收取固定租金4.5万元；

27、若有条件出租，公司不收取租金，但当产量为20万桶至50万桶时，每桶公司收取0.5元。由上计算得到该公司可能的利润收入见表14-1.按过去的经验，该块土地属于上面4种类型的可能性分别为10%，15%，25%和50%。问题是该公司应选择哪种方案，可获得最大利润？,63,表14-1 石油公司可能利润收入表（单位：万元）,解：各个方案的期望收益为,根据期望收益最大原则，应选择，即自行钻井。,64,效用理论,一、效用概念的引入,前面介绍风险型决策方法时，提到可根据期望益损值（最大或最小）作为选择最优方案的原则，但这样做并不一定合理。请看下面的例子：,例6 设有两个决策问题：问题1：方案A1：稳获100元

28、；方案B1:用掷硬币的方法，掷出正面获得250元，掷出反面获得0元。,65,问题2：方案A2：稳获1000元；方案B2:用掷硬币的方法，直到掷出正面为止，记所掷次数为N，则当正面出现时，可获2N元.,当你遇到这两类问题时，如何决策？大部分会选择 A1 和 A2。但不妨计算一下其期望值：,方案B1的收益为随机变量Y1。则其期望收益为：,66,设方案B2的收益为随机变量Y2。Ai=“第i次掷出正面”，则第n次掷出正面的概率为：,相互独立,设掷出正面前掷出反面的次数为随机变量X,则有分布列：,则方案2的平均收益为：,67,于是，根据期望收益最大原则，应选择B1和B2，但这一结果很难令实际决策者接受。

29、此乃研究效用函数的初衷。,例7（赌一把）一个正常的人，遇到“赌一把”的机会。情况如下面的树，问此人如何决策？,68,正常人,B,赌,不赌,45元,掷出正面,P=0.5,-10元,P=0.5,0,100元,掷出反面,45元,对绝大部分人来说，只要兜里有10元钱，又不急用的话，就选择“赌”。因此时“赌”的平均收益为：,类似的问题，让一个被判刑十年且手头仅有10元钱的罪犯做下面的决策：,69,罪犯,B,赌,释放,45元,掷出正面,P=0.5,-10元,P=0.5,-10元,100元,掷出反面,45元,此时罪犯可能要选择交出10元钱，获得释放。,以上例子说明：,相同的期望益损值（以货币值为度量）的不同

30、随机事件之间其风险可能存在着很大的差异。即说明货币量的期望益损值不能完全反映随机事件的风险程度。同一随机事件对不同的决策者的吸引力可能完全不同，因此可采用不同的决策。这与决策者个人的气质、冒险精神、,70,经济状况、经验等等主观因素有很大的关系。即使同一个人在不同情况下对同一随机事件也会采用不同的态度。,当我们以期望益损值（以货币值为度量）作决策准则时，实际已经假定期望益损值相等的各个随机事件是等价的，具有相同的风险程度，且对不同的人具有相同的吸引力。但对有些问题这个假定是不合适的。因此不能采用货币度量的期望益损值作决策准则，而用所谓“效用值”作决策准则。,71,二、效用曲线的确定及分类,老王

31、,B,二次抽奖,一次,500元,P=0.5,0元,P=0.5,500元,1000元,500元,为了讲清“效用”与“效用值”的概念，看下例,例 老王参加某电视台综艺,节目而得奖。他有两种方式可选择：,一次获得500元奖金。,分别以概率 0.5 与 0.5的机会抽奖可获得1000元与0元。,试问老王该选择何种方式领奖？,72,事件 的期望益损值都是500元，但有人认为应选择,他认为 的“价值”比 大，有的相反。都是“主观价值”。,此时他认为事件 的效用比事件 来的大。,如何来度量随机事件的效用（或说“价值”）？我们用“效用值”u来度量效用值的大小。“效用值”是一个“主观价值”，且是一个相对大小的值

32、。通常假定决策者最偏好、最倾向、最喜欢的事情（方案）的效用为1，而最不偏好、最不倾向、最不喜欢的事情（方案）的效用为0。,一般来说，若用r来表示期望收益值（这里收益值作广义理解，不一定是货币量，也可以是某事件的结果），则r的效用,73,那么，当 时如何计算呢？,值用 来表示。因此有,一般用心理测试的方法来确定，具体做法是：反复向决策者提出下面的问题：“如果事件 是以概率P得到收益为，以概率（1-P）得到收益为，事件 是以100%概率得到收益为 你认为 取多大值时，事件 与事件 是相当的（即认为效用值相等）？如果决策者经过思考后，认为 时 两事件效用是相当的，即有,74,当，已知时，则 的效用值

33、可求出。如当 则 则可求出,的效用值，再在已知效用值的三点,中的任意两点，再作出同样的问题来问决策者，则可在两点中求出一点的效用值。如此继续，可得到在 及 中间的一系列 的效用值。再以 作横坐标，作纵坐标可得该决策者的效用曲线。举例如下。,例 设某决策者在股票交易所购买股票，现有两种选择：,选择股票01号，预计每手（100股）可能分别以概率0.5获利200元，概率0.5 损失100元。,75,选择股票02号，预计每手（100股）可能以概率1.0获利25元。,试问该决策者应选择何种方式购买股票？,用心理测试法对该决策者提问：对上述事件，问决策者愿意选择何种方式？,决策者,B,01号股票,02号股

34、票,0.5,P=0.5,-100元,P=0.5,25元,200元,若决策者选择，则降低 到20元，若还选择则再降低，若降至0元（即不赔不赚）时，,决策者犹豫不定，说明,选择股票01号，预计每手（100股）可能分别以概率0.5获利200元，概率0.5 损失100元。,76,此时随机事件 的效用值与 相等。,求出 时的效益值：,得到效用曲线的三点。,77,决策者,01号股票,02号股票,0.75,P=0.5,0元,P=0.5,40元,200元,选择股票02号，预计每手,（100股）可能以概率1.0获利40元。,试问该决策者应选择何种方式购买股票？,再求 与 之间某一点 的效用值。提出如下的问题：,

35、选择股票01号，预计每手（100股）可能分别以概率0.5获利200元，概率0.5 损失0元。,B1,B2,P=1.0,0.75,78,60元,若决策者选择，则提高02号股票到60元。决策者犹豫不定，说明此时随机事件 的效用值与 相等。,求出 时的效用值：,得到效用曲线的四个点。,79,提出如下的问题，可得-100元到0元之间的某点效用值。,选择股票01号，预计,每手可能分别以概率0.5获利0元，以概率0.5获利-100元。,选择股票02号，,预计每手可能以概率1.0获利-30元。,80,试问该决策者应选择何种方式购买股票？,-60元,81,120元,同理在60元到200元之间求出某点的效用值。

36、,经过几次提问，决策者稳定在,82,对于此决策者，此时的心态，任给一个值，比如25元（横坐标），通过曲线，即可查出其效用值。,三、效用曲线的类型：,总体上讲，效用曲线可分为：保守型：中间型：冒险型,83,保守型的人对收益增加反映比较迟钝，相反对损失反映比较敏感。,冒险型的人对损失增加反映比较迟钝，相反对收益反映比较敏感。,中间型介于两者之间。,84,四、最大效用期望值决策准则及其应用,最大效用期望值决策准则，就是依据效用理论，通过效用函数（或效用曲线）计算出各个策略结点的效用期望值，以效用期望值最大的策略作为最优策略的选优准则。即以效用期望值代替风险型决策中的期望益损值进行决策。,例 某厂计划

37、生产一种新产品，经预测，该新产品销路好与差的概率各占50%，该生产工艺有三种。第、种为现有工艺，第种为新工艺，因此第种工艺的生产有顺利与不顺利两种情况，且已知顺利的概率为0.8，不顺利的概率为0.2。三种工艺在销路好、差状态下的收益值见收益值表。又利用,85,心理测试法，对该厂厂长在生产工艺决策问题上的效用函数已测出，见厂长效用函数表。现求：作出此问题的决策树。以最大期望益损值为最优决策准则求此问题的最优决策 以最大效用期望值为最优决策准则求此问题的最优决策,厂长效用值函数,86,收益值表,单位：万元,解：作出此问题的决策树。,87,决策者,工艺,工艺,新工艺,销路差0.5,销路好0.5,销路

38、差0.5,销路好0.5,顺利0.8,销路好0.5,销路差0.5,销路好0.5,销路差0.5,5,40,55,不顺利0.2,75,收益值,20,-10,100,-20,200,-50,-100,50,-25,88,计算各结点的期望益损值：,结点：,万元,结点：,万元,结点：,万元,结点：,万元,结点：,万元,从期望益损值可看出，第种工艺方案为最优方案。此时最优期望收益值为55万元。,89,决策者,工艺,工艺,0.515,新工艺,销路差0.5,销路好0.5,销路差0.5,销路好0.5,顺利0.8,销路好0.5,销路差0.5,销路好0.5,销路差0.5,5,40,0.605,55,0.582,不顺利

39、0.2,75,0.645,收益值,效用值,20,0.57,-10,0.46,100,0.79,-20,0.42,200,1.0,-50,0.29,-100,0.0,50,0.66,0.33,-25,90,计算各结点的效用期望值：,结点：,万元,结点：,万元,结点：,万元,结点：,万元,结点：,万元,从效用期望值可看出，第种工艺方案为最优方案。此时最大效用期望值为0.605。,91,用效用期望值作标准还有一个优点是：对于不同量纲的目标，可以折算成效用值，然后相加，求各个方案的总效用值来进行比较。,例 某公司欲购置一批汽车，须考查两项指标：功率和价格。该公司决策者认为最合适的功率为70kw，若低于

40、55kw，则不宜使用；而最满意的价格为4.0万元。若超过5.6 万元，则不能接受。目前市场上能满足该公司基本要求的汽车型号有：，。它们的功率和价格分别为,92,问该公司决策者应作何种决策？,解：这是一个涉及功率和价格的多目标决策问题，且两个目标相互矛盾，量纲也不同，无法用绝对数字进行比较。对此可用如下的方法：应用效用理论，把每个方案的各个指标折合成效用值，然后加权相加，计算出每个方案的总的效用值，然后进行比较。,93,首先，应用效用理论，给出该公司决策者的功率效用曲线 与价格效用曲线，然后再求出下属各点的效用值，其结果为：,又通过询问，了解到决策者对功率与价格这两个目标的权重分别为0.6,0.

41、4。因此可作出决策树：,94,决策者,0.63,价格0.4,功率0.6,0.78,0.68,功率0.6,功率0.6,价格0.4,价格0.4,计算各结点的效用期望值：,95,决策者,0.63,价格0.4,功率0.6,0.78,0.68,功率0.6,功率0.6,价格0.4,价格0.4,因此，按效用期望值作标准，应选择第种牌号的车型为最优决策。,96,层次分析法,层次分析法（Analytical Hierarchy Process,简称AHP)是美国匹兹堡大学教授于20世纪70年代提出的一种系统分析方法。,AHP是一种将定性分析与定量分析相结合的系统分析方法。在进行系统分析时，经常会碰到这样的一类问

42、题：有些问题难以甚至根本不可能建立数学模型进行定量分析；也可能由于时间紧，对有些问题还来不及进行过细的定量分析，只需作出初步的选择和大致的判定就行了。例如选择一个新厂的厂址，购买一台重要的设备，确定到哪里去旅游等等。这时，我们若应用AHP进行分析，就可以简便地解决问题。,97,将AHP引入决策，是决策科学化的一大进步。它最适宜于解决难以完全用定量方法进行分析的决策问题。因此，它是复杂的社会经济系统实现科学决策的有力工具。,一、AHP的基本原理,为了说明AHP的基本原理，首先让我们分析下面的简单事实。假定我们已知n个西瓜的总重量为1，每个西瓜的重量为 问每个西瓜相对于其他西瓜的相对重量是多重？,

43、可通过两两比较（相除），得到比较矩阵（以后称之为判断矩阵）：,98,显然矩阵A满足,（1）,称满足（1）式的矩阵为互反矩阵。且满足,（2）,99,即n是A的一个特征根，,是A的对应于特征根n,的一个特征向量。,设,有,100,现在提出相反的问题：如果事先不知道每个西瓜的重量，也没有衡器去称量，如何判定每个西瓜的相对重量呢？即如何判定哪个最重，哪个次之，哪个最轻呢？,我们可以通过两两比较的方法，得出判断矩阵A,然后求出A的最大特征值，进而通过,求出A的特征向量,101,然后通过,将 规范化：,则 即为n个西瓜的相对重量。,102,使用AHP，判断矩阵的一致性是十分重要的。所谓判断矩阵的一致性，即

44、判断矩阵是否满足如下关系：,若上式完全成立时，称判断矩阵具有完全一致性。可以证明，n阶完全一致性矩阵具有以下的性质：1。A的秩为1，A的唯一非零特征根为n。2。A的任一列（行）向量都是对应于特征根n的特征向量。,证明：设,103,是n阶完全一致性矩阵，则,104,注意到：,有,105,106,所以,107,在一般情况下，可以证明判断矩阵的最大特征值为单根，且,当判断矩阵具有满意的一致性时，稍大于矩阵阶数，其余特征根接近于零。这时AHP得出的结论才基本合理。但由于客观事物的复杂性和人们认识上的多样性，要求所有的判断都有完全的一致性是不可能的，但我们要求一定程度上的判断一致，因此对构造的判断矩阵需

45、要进行一致性检验。,108,二、AHP的步骤,用AHP分析问题大体要经过以下五个步骤：建立层次结构模型；构造判断矩阵；层次单排序；层次总排序；一致性检验。其中后三个步骤在整个过程中需要逐层地进行。,109,建立层次结构模型,人们在日常生活中经常会碰到许多决策问题：买一件衬衫，你要在棉的、丝的、涤纶的、及花边的、白的、方格的、之中作出抉择；请朋友吃饭，要筹划是办家宴还是去饭店，是吃中餐还是西餐或自助餐；假期旅游，是去风光绮丽的杭州，还是去迷人的北戴河，或者是去山水甲天下的桂林。如果你以为这些日常生活小事不必作为决策问题认真对待的话，那么，当你面临报考学校、选择专业，或者抉择工作岗位的时候，就要慎

46、重考虑、反复考虑，尽可能地做出满意的抉择了。,110,从事各种职业的人也经常面临决策：一个厂长要决定购买哪种设备，上马什么产品；科技人员要选择研究课题；医生要为疑难病例选择治疗方案；经理要从若干应试者中选择秘书；各地区、各部门的官员要对人口、交通、经济、环境等领域的发展规划作出决策。,层次分析法的基本思路与人对一个复杂的决策问题的思维、判断过程大体上类似。不妨用前面提到过的假期旅游为例，假如有、三个旅游胜地供你选择，你会根据诸如景色、费用、居住、饮食、旅途条件等一些准则去反复比较哪三个候选地点。首先，你会确定这些准则在你心目中各占多大比重，如,111,果你经济宽绰、醉心旅游，自然特别看重景色，

47、而平素简朴或手头拮据的人则会优先考虑费用，中老年则会对居住、饮食等条件给予较大关注。其次，你会就每一准则将三个地点进行对比，譬如 景色最好，次之；费用最低，次之；居住条件较好等。最后，你要将这两个层次的比较判断进行综合，在，中确定哪个作为最佳地点。,上面的思维过程可以加工整理成以下几个步骤：1将决策问题分解为3个层次，最上层为目标层，即选择旅游地，最下层为方案层，有，3个供你选择地点，中间层为准则层，有景色、费用、居住、饮食、旅途5个准则，各层间的联系用相连的直线表示。见下图,112,目标层,选择旅游地,景色,费用,居住,饮食,旅途,准则层,方案层,图5.1 选择旅游地的层次结构,113,构造

48、判断矩阵,通过相互比较确定各准则对于目标的权重，即构造判断矩阵。,设准则层5个准则 景色，费用，居住，饮食 旅途。相对于目标层：选择旅游地，两两比较打分。,114,采用19的比例表度的依据是：心理学的实验表明，大多数人对不同事物在相同属性上的差别的分辨能力在59，采用19的标度反映了大多数人的判断能力；大量的社会调查表明，19的比例标度早已被人们所熟悉和采用；科学考察和实践表明，19的比例标度已完全能区分引起人们感觉差别的事物的各种属性。,115,选择旅游地,景色,费用,居住,饮食,旅途,116,相对于景色,相对于费用,相对于居住,相对于饮食,117,相对于旅途,层次单排序,所谓层次单排序是指

49、，对于上一层某因素而言，本层次各因素的重要性的排序。具体计算是：,对于判断矩阵B，计算满足,118,的特征根与特征向量，式中 为 的最大特征根，为对应于 的正规化的特征向量，的分量 即是相应元素单排序的权值。,自上而下，先求判断矩阵A的最大特征值与特征向量。,119,例如：,相对于景色,经计算,对应于 的正规化的特征向量为,对应于 的正规化的特征向量为,120,同理算出 的最大特征值分别为：,所对应的特征向量分别为,121,将5个特征向量按列依次排成一矩阵：,为了检验矩阵的一致性，需要计算它的一致性指标CI，定义,一般的，只要 就可认为判断矩阵具有满意的一致性。,122,层次总排序,各个方案优

50、先程度的排序向量为,首选旅游地为，其次为，再者,123,一般地，若层次结构有k个层次（目标层算第一层），则方案的优先程度的排序向量为,124,二、层次分析法的计算方法,层次分析法有两大问题：判断矩阵一致性的调整；判断矩阵的最大特征根与特征向量的计算。对于，精确解应是线性代数中的计算方法。但从使用的角度看，一般采用近似方法计算。主要有三种计算方法。,1、幂法幂法使我们有可能利用计算机得到任意精确解的最大特征根及其对应的特征向量。步骤为 任取与判断矩阵B同价的正规化的初始向量；计算,125,令 计算,对于预先给定的精确度，当,对所有i=1,2,n成立时，则 为所求特征向量。可由下式求得,式中：n为