运筹学的优化算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,运筹学的优化算法,1,运 筹 学,（Operations Research OR）,由于运筹学研究的广泛性和复杂性，人们至今没有形成一个统一的定义。以下给出几种定义：,运筹学是一种科学决策的方法,运筹学是依据给定目标和条件从众多方案中选择最优方案的最优化技术。,运筹学是一种给出坏的问题的答案的艺术，否则的话问题的结果会更坏。,2,运筹学模型,运筹学研究的模型主要是抽象模型数学模型。,3,运筹学包含的分支,数学规划（线性规划、整数规划、 目标规划、动态规划、网络规划等）,图论与网络流,决策分析,4,运筹学包含的分支,排队论,可靠性数学理论,库存论,对策论,搜索论,计算机模拟等,5,数学建模竞赛中的算法(1),93A,非线性交调的频率设计,:,拟合、规划,93B,足球队排名次,:,矩阵论、图论、层次分析法、整数规划,94A,逢山开路,:,图论、插值、动态规划,94B,锁具装箱问题,:,图论、组合数学,95A,飞行管理问题,:,非线性规划、线性规划,95B,天车与冶炼炉的作业调度,:,非线性规划、动态规划、层次分析法、,PETRI,方法、图论方法、排队论方法,96A,最优捕鱼策略,：,微分方程、积分、非线性规划,6,96B,节水洗衣机,：,非线性规划,97A,零件参数设计,：,微积分、非线性规划、随机模拟,97B,截断切割,：,组合优化、几何变换、枚举、蒙特卡罗、递归、最短路,98A,投资收益与风险,：,线性规划、非线性规划,98B,灾情巡视路线,：,最小生成树、,Hamilton,圈、旅行商问题,99A,自动化车床管理,：,积分、概率分布、随机模拟、分布拟合度检验,数学建模竞赛中的算法(2),7,99B,钻井布局,：,几何变换、枚举、最大完全子图、混合整数规划,00A DNA,分类,：,神经网络、最小二乘拟合、统计分类,00B,管道订购和运输,：,最短路、二次规划,01A,血管的三维重建,：,数据挖掘、曲面重建与拟合,01B,公交车调度,：,非线性规划,02A,车灯光源优化设计,：,最优化,02B,彩票中的数学,：,概率与优化,数学建模竞赛中的算法(3),8,03A,SARS,的传播：,微分方程、差分方程,03B,露天矿生产的车辆安排：,整数规划、运输问题,04A,奥运会临时超市网点设计：,统计分析、数据处理、优化,04B,电力市场的输电阻塞管理：,数据拟合、优化,05A,长江水质的评价和预测：,预测评价、数据处理,05B,DVD,在线租赁：,随机规划、整数规划,06A,出版社书号问题：,整数规划、数据处理、优化,数学建模竞赛中的算法(4),9,06B,Hiv,病毒问题：,线性规划、回归分析,07A,人口问题：,微分方程、数据处理、优化,07B,公交车问题：,多目标规划、动态规划、图,论、,0-1,规划,08A,照相机问题：,非线性方程组、优化,08B,大学学费问题：,数据收集和处理、统计分,析、回归分析,数学建模竞赛中的算法(5),10,赛题发展的特点：,1. 对选手的计算机能力提出了更高的要求：赛题的解决依赖计算机，题目的数据较多，手工计算不能完成，计算机模拟和以算法形式给出最终结果。,2. 赛题的开放性增大:解法的多样性，一道赛题可用多种解法。开放性还表现在对模型假设和对数据处理上。,3. 试题向大规模数据处理方向发展,4. 求解算法和各类现代算法的融合,11,1.,蒙特卡罗方法(Monte-Carlo方法, MC),数学建模竞赛常用算法(1),该算法又称,计算机随机性模拟方法,，也称,统计试验,方法,。MC方法是一种基于“随机数”的计算方法，能够,比较逼真地描述事物的特点及物理实验过程，解决一些,数值方法难以解决的问题。,MC方法的雏型可以追溯到十九世纪后期的蒲丰随机,投针试验，即著名的,蒲丰问题,。 MC方法通过计算机仿,真(模拟)解决问题，同时也可以通过模拟来检验自己,模型的正确性，是比赛中经常使用的方法。,12,97,年的,A,题,每个零件都有自己的标定值，也都有自,己的容差等级，而求解最优的组合方案将要面对着的是一,个极其复杂的公式和,108,种容差选取方案，根本不可能去求,解析解，那如何去找到最优的方案呢？随机性模拟搜索最,优方案就是其中的一种方法，在每个零件可行的区间中按,照正态分布随机的选取一个标定值和选取一个容差值作为,一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从,中选取一个最佳的。,02,年的,B,题,关于彩票第二问，要求设计一种更好的方,案，首先方案的优劣取决于很多复杂的因素，同样不可能,刻画出一个模型进行求解，只能靠随机仿真模拟。,数学建模竞赛常用算法,13,98,年美国赛,A,题,生物组织切片的三维插值处理,94,年,A,题逢山开路,山体海拔高度的插值计算,数学建模竞赛常用算法(2),2. 数据拟合、参数估计、插值等数据处理算法,比赛中通常会遇到大量的数据需要处理，而处理数,据的关键就在于这些算法，通常使用MATLAB 作为工,具。与图形处理有关的问题很多与拟合有关系。,此类问题在MATLAB中有很多函数可以调用，只有熟,悉MATLAB，这些方法才能用好。,14,98,年,B,题,用很多不等式完全可以把问题刻画清楚,数学建模竞赛常用算法(3),3. 规划类问题算法,此类问题主要有,线性规划、整数规划、多目标规划、,二次规划,等。竞赛中很多问题都和数学规划有关，可以,说不少的模型都可以归结为一组不等式作为约束条件、,几个函数表达式作为目标函数的问题，遇到这类问题，,求解就是关键了。,因此列举出规划后用Lindo、Lingo 等软件来进行解决,比较方便，所以还需要熟悉这两个软件。,15,98,年,B,题、,00,年,B,题、,95,年锁具装箱,等问题体现了,图论问题,的重要性。,数学建模竞赛常用算法(4),4.,图论问题,这类问题算法有很多，包括：,Dijkstra、Floyd、,Prim、Bellman-Ford，最大流，二分匹配,等问题。,16,92,年,B,题用分枝定界法,97,年,B,题是典型的动态规划问题,98,年,B,题体现了分治算法,数学建模竞赛常用算法(5),5. 计算机算法设计中的问题,计算机算法设计包括很多内容：,动态规划、回溯搜,索、分治算法、分枝定界,等计算机算法.,这方面问题和ACM 程序设计竞赛中的问题类似，,可看一下与计算机算法有关的书。,17,分枝定界法,原问题的松驰问题：,任何整数规划（IP），凡放弃某些约束条件（如整数要求）后，所得到的问题（P） 都称为（IP）的松驰问题。,最通常的松驰问题是放弃变量的整数性要求后，（P）为线性规划问题。,18,去掉整数约束,用单纯形法,IP LP,x,l,*,判别是否整数解,x,I,*,=,x,l,*,Yes,去掉非整数域,No,多个LP,19,分枝定界法步骤,一般求解对应的松驰问题，可能会出现下面几种情况：,若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。,20,分枝定界法步骤,一般求解对应的松驰问题，可能会出现下面几种情况：,若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。,若松驰问题无可行解，则原整数规划问题也无可行解，计算结束。,21,若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。,22,若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。,从不满足整数条件的基变量中任选 一个,x,l,进行分枝，它必须满足,x,l,x,l,或,x,l,x,l,+1,中的一个，把这两个约束条件加进原问题中，形成两个互不相容的子问题（两分法）,。,23,定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。,24,定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。,剪枝：把那些子问题的最优值与界值比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查清为止。,25,例：,用分枝定界法求解：,Max Z=4x,1,+3x,2,s.t.,3x,1,+4x,2,12,4x,1,+2x,2,9,x,1,x,2,0 整数,用单纯形法可解得相应的松驰问题的最优解（6/5，21/10）Z=111/10为各分枝的上界。,26,0 1 2 3 4,4 3 2 1,x,1,x,2,分枝：x,1,1,x,1,2,P,1,P,2,（6/5，21/10）,27,两个子问题：,（P,1,）Max Z=4x,1,+3x,2,s.t.,3x,1,+4x,2,12,4x,1,+2x,2,9,x,1,x,2,0 ， x,1,1 ，整数,用单纯形法可解得相应的（P,1,）的最优解（1，9/4） Z=10(3/4),28,（P,2,）Max Z=4x,1,+3x,2,s.t.,3x,1,+4x,2,12,4x,1,+2x,2,9,x,1,x,2,0 ， x,1,2 ，整数,用单纯形法可解得相应的（P,2,）的最优解（2，1/2） Z=9(1/2),29,0 1 2 3 4,4 3 2 1,x,1,x,2,再对（P,1,） x,1,1,（1，9/4）,分枝：,（P,3,） x,2,2 （P,4,） x,2,3,P,1,P,2,P,3,P,4,30,（P,1,）两个子问题：,（P,3,）Max Z=4x,1,+3x,2,s.t.,3x,1,+4x,2,12,4x,1,+2x,2,9,x,1,x,2,0 ,x,1,1, x,2,2整数,用单纯形法可解得相应的（P,3,）的最优解（1，2） Z=10 为上界,31,（P,1,）两个子问题：,（P,4,）Max Z=4x,1,+3x,2,s.t.,3x,1,+4x,2,12,4x,1,+2x,2,9,x,1,x,2,0 ,x,1,1, x,2,3整数,用单纯形法可解得相应的（P,4,）的最优解（0，3） Z=9,32,X,1,2,X,2,2,X,1,1,X,2,3,P,1,:(1,9/4),Z=10(3/4),P,4,: (0,3) Z=9,P,2,:(2,1/2) Z=9(1/2),P,3,:,(1,2) Z=10,P:(6/5,21/10) Z=111/10,原问题的最优解,（1，2） Z=10,33,多阶段决策过程最优化,多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。,动态规划应用举例,34,最优化原理,：最优策略的任一后部子策略都是最优的。,无论以前状态决策如何，从眼下直到最后的诸决策必构成最优子策略。,例1 最短路线问题,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,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,动态规划应用举例,35,例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，在第一,阶段生产后回收的总资源为x,1,=ay+b(x-y)，再将x,1,投入生产方式A和B，则可得到收入g(y,1,)+h(x,1,-y,1,)，,继续回收资源x,2,=ay,1,+b(x,1,-y,1,)，,若上面的过程进行n个阶段，我们希望选择n,个变量y,y,1,y,2,y,n-1,，使这n个阶段的总收入最大。,例1 续（1）,37,因此，我们的问题就变成：求y,y,1,y,2,y,n-1,，以使g(y)+h(x-y)+ g(y,1,)+h(x,1,-y,1,)+ +g(y,n-1,)+h(x,n-1,-y,n-1,) 达到最大，且满足条件,x,1,=ay+b(x-y),x,2,=ay,1,+b(x,1,-y,1,), ,x,n-1,=ay,n-2,+b(x,n-2,-y,n-2,),y,i,与x,i,均非负,i=1,2, ,n-1,例1 续（2）,38,例2 生产和存储控制问题,某工厂生产某种季节性商品，需要作下一,年度的生产计划，假定这种商品的生产周期需,要两个月，全年共有6个生产周期，需要作出,各个周期中的生产计划。,39,设已知各周期对该商品的需要量如下表所示,：,周期,1,2,3,4,5,6,需求量,5,5,10,30,50,8,例2 续（1）,40,例2 续（2）,假设这个工厂根据需要可以日夜两班生产或只是日班生产，当开足日班时，每一个生产周期能生产商品15个单位，每生产一个单位商品的成本为100元。当开足夜班时，每一生产周期能生产的商品也是15个，但是由于增加了辅助性生产设备和生产辅助费用，每生产一单位商品的成本为120元。由于生产能力的限制，可以在需求淡季多生产一些商品储存起来以备需求旺季使用，但存储商品是需要存储,费用的，假设每单位商品存储一周期需要16元，已知开始时存储为零，年终也不存储商品备下年使用，问应该如何作生产和存储计划，才能使总的生产和存储费用最小？,41,例2 续（3）,设第i个周期的生产量为x,i,，周期末的存储量为u,i,，那,么这个问题用式子写出来就是：求x,1,x,2,x,6,，满足条件：,x,1,=5+u,1,x,2,+u,1,=5+u,2,x,3,+u,2,=10+u,3,x,4,+u,3,=30+u,4,x,5,+u,4,=50+u,5,x,6,+u,5,=8,0 x,i,30,0 u,j,i=1,2,6;j=1,2, ,5,使S= =,为最小，其中,42,例2 续（4）,43,逆序递推方程：,（1）k=5 时，状态,它们到F 点的距离即为,最短路。,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,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阶段,44,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,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,（2）k=4 时，状态,它们到F 点需经过中途,点E，需一一分析从E 到 F的最短路：先说从D,1,到F 的最短路,有两种选择：经过 E,1, E,2, 比较最短。,45,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,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,这说明由 D,1,到F 的最短距离为7，其路径为,相应的决策为：,46,这说明由 D,2,到F 的最短距离为5，其路径为,相应的决策为：,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,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,47,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,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,即 D,3,到F 的最短距离为5，其路径为,相应的决策为：,48,（3）k=3 时，状态,这说明由 C,1,到F 的最短距离为12，相应的决策为,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,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,49,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,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,即由 C,2,到F 的最短距离为10，相应的决策为,50,即由 C,3,到F 的最短距离为8，相应的决策为,即由 C,4,到F 的最短距离为9，相应的决策为,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,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,51,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,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,（4）k=2时，状态,这说明由 B,1,到F 的最短距离为13，相应的决策为,52,即由 B,2,到F 的最短距离为15，相应的决策为,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,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,53,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,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, 则,即由 A到F 的最短距离为17，相应的决策为,54,所以最优路线为：,A,B,1,B,2,C,1,C,2,C,3,C,4,D,1,D,2,D,3,E,1,E,2,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,再按计算顺序反推可得最优决策序列：,55,97,年,A,题用模拟退火算法,00,年,B,题用神经网络分类算法,01,年,B,题这种难题也可以使用神经网络,美国,03,年,B,题,伽马刀问题也是目前研究的课题，目前,算法最佳的是遗传算法,。,数学建模竞赛常用算法(6),6. 最优化理论的三大非经典算法:,模拟退火法(SA)、神经网络(NN)、遗传算法(GA),近几年的赛题越来越复杂，很多问题没有什么很好的,模型可以借鉴，于是这三类算法很多时候可以派上用场。,56,97,年,A,题、,99,年,B,题都可以,用网格法搜索,数学建模竞赛常用算法(7),网格算法和穷举法一样，只是网格法是连续问题的穷,举。此类算法运算量较大。,7. 网格算法和穷举算法,这种方法最好在运算速度较快的计算机中进行，还有,要用高级语言来做，最好不要用MATLAB 做网格，否则,会算很久。,57,很多问题都是实际来的，数据可以是连续的，而计,算机只能处理离散的数据，因此需要,将连续问题进行,离散化处理后再用计算机求解,。比如差分代替微分、,求和代替积分等思想都是把连续问题离散化的常用方,法。,数学建模竞赛常用算法(8),8. 连续问题离散化的方法,58,数值分析研究各种,求解数学问题的数值计算方法,，,特别是适合于计算机实现方法与算法。,数学建模竞赛常用算法(9),9. 数值分析方法,它的主要内容包括,函数的数值逼近、数值微分与数,值积分、非线性方程的数值解法、数值代数、常微分方,程数值解,等。数值分析是计算数学的一个重要分支，把,理论与计算紧密结合,是现代科学计算的基础 。,MATLAB等数学软件中已经有很多数值分析的函,数可以直接调用。,59,01,年,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万桶,无油,自行钻井,无条件出租,有条件出租,65,4.5,25,20,4.5,10,2.5,4.5,0,7.5,4.5,0,解：各个方案的期望收益为,根据期望收益最大原则，应选择,，,即自行钻井。,63,效用理论,一、效用概念的引入,前面介绍风险型决策方法时，提到可根据期望益损值（最大或,最小）作为选择最优方案的原则，但这样做并不一定合理。请,看下面的例子：,例6 设有两个决策问题：,问题1：方案A,1,：稳获100元；,方案B,1,: 用掷硬币的方法，掷出正面获得250元，掷,出反面获得0元。,64,问题2：方案A,2,：稳获1000元；,方案B,2,: 用掷硬币的方法，直到掷出正面为止，记所,掷次数为,N,，则当正面出现时，可获2,N,元.,当你遇到这两类问题时，如何决策？大部分会选择 A,1,和 A,2,。,但不妨计算一下其期望值：,Y,1,0,250,P(Y,1,=k),1/2,1/2,方案B,1,的收益为随机变量Y,1,。,则其期望收益为：,65,设方案B,2,的收益为随机变量Y,2,。A,i,=“第i次掷出正面” ，则第,n,次掷出正面的概率为：,Y,2,2,2,2,2,3,n,P(Y,2,=k),1/2,1/2,2,1/2,3,1/2,n,X,0,1,2,n-1,相互独立,设掷出正面前掷出反面的次数为随机变量X,则有分布列：,则方案2的平均收益为：,66,Y,2,2,2,2,2,3,n,P(Y,2,=k),1/2,1/2,2,1/2,3,1/2,n,X,0,1,2,n-1,于是，根据期望收益最大原则，应选择B,1,和B,2,，但这一结果,很难令实际决策者接受。此乃研究效用函数的初衷。,例7（赌一把）一个正常的人，遇到“赌一把”的机会。情况,如下面的树，问此人如何决策？,67,正常人,B,赌,不赌,45元,掷出正面,P=0.5,-10元,P=0.5,0,100元,掷出反面,45元,对绝大部分人来说，,只要兜里有10元钱，,又不急用的话，就选,择“赌”。因此时“赌”,的平均收益为：,类似的问题，让一个被判刑十年且手头仅有10元钱的罪犯做下面的决策：,68,罪犯,B,赌,释放,45元,掷出正面,P=0.5,-10元,P=0.5,-10元,100元,掷出反面,45元,此时罪犯可能要选,择交出10元钱，获,得释放。,以上例子说明：, 相同的期望益损值（以货币值为度量）的不同随机事件之,间其风险可能存在着很大的差异。即说明,货币量的期望益损,值不能完全反映随机事件的风险程度。, 同一,随机事件对不同的决策者的吸引力可能完全不同，因,此可采用不同的决策。这与决策者个人的气质、冒险精神、,69,经济状况、经验等等主观因素有很大的关系。, 即使同一个人在不同情况下对同一,随机事件也会采用,不同的态度。,当我们以期望益损值（以货币值为度量）作决策准则时，实,际已经假定,期望益损值相等的各个随机事件是等价的，具有,相同的风险程度，且对不同的人具有相同的吸引力,。但对有,些问题这个假定是不合适的。因此不能采用货币度量的期望,益损值作决策准则，而用所谓“效用值”作决策准则。,70,二、效用曲线的确定及分类,老王,B,二次抽奖,一次,500元,P=0.5,0元,P=0.5,500元,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元。,试问该决策者应选择何种方式购买股票？,用心理测试法对该决策者提问：, 对上述事件 ，问决策者愿意选择何种方式？,决策者,B,01号股票,02号股票,0.5,P=0.5,-100元,P=0.5,25元,200元,若决策者选择 ，则降,低 到20元，若还选择,则再降低 ，若降至0,元（即不赔不赚）时，,决策者犹豫不定，说明,选择股票01号，预计每手（100股）可能分别以概率,0.5获利200元，概率0.5 损失100元。,75,此时随机事件 的效用值,与 相等。,求出 时的效益,值：,得到效用曲线的三点。,0元,P=1.0,决策者,01号股票,02号股票,0.5,P=0.5,-100元,P=0.5,200元,B,1,B,2,0.5,76,决策者,01号股票,02号股票,0.75,P=0.5,0元,P=0.5,40元,200元,选择股票02号，预计每手,（100股）可能以概,率1.0获利40元。,试问该决策者应选择何种,方式购买股票？, 再求 与 之间某一点 的效用值。提出,如下的问题：,选择股票01号，预计每手（100股）可能分别以概率,0.5获利200元，概率0.5 损失0元。,B,1,B,2,P=1.0,0.75,77,决策者,01号股票,02号股票,0.75,P=0.5,0元,P=0.5,200元,B,1,B,2,P=1.0,0.75,40元,60元,若决策者选择 ，则提,高02号股票到60元。决策,者犹豫不定，说明此时随,机事件 的效用值与,相等。,求出 时的效用值：,得到效用曲线的四个点。,78,提出如下的问题，可得,-100元到0元之间的某点,效用值。,选择股票01号，预计,每手可能分别以概率0.5获利0元，,以概率0.5获利-100元。,决策者,B,1,01号股票,02号股票,P=0.5,-100元,P=0.5,-30元,0元,B,2,P=1.0,选择股票02号，,预计每手可能以概,率1.0获利-30元。,79,试问该决策者应选择何种方式购买股票？,决策者,01号股票,02号股票,0.25,P=0.5,-100元,P=0.5,0元,B,1,B,2,P=1.0,0.25,-30元,-60元,80,120元,决策者,01号股票,02号股票,0.875,P=0.5,60元,P=0.5,200元,B,1,B,2,P=1.0,0.875, 同理在60元到200元之,间求出某点的,效用值。,经过几次提问，决策者,稳定在,81,对于此决策者，此时的心,态，任给一个值，比如25,元（横坐标），通过曲,线，即可查出其效用值。,三、效用曲线的类型：,总体上讲，效用曲线可分为：,：保守型,：中间,型,：冒险,型,82,保守,型,的人对收益增加反映比较迟,钝，,相,反对损失,反,映比较敏感。,冒险,型,的人对,损失,增加反映比较迟,钝，相反对,收益反,映比较敏感。,中间型介于两者之间。,83,四、最大效用期望值决策准则及其应用,最大效用期望值决策准则，就是依据效用理论，通过效用函,数（或效用曲线）计算出各个策略结点的效用期望值，以效,用期望值最大的策略作为最优策略的选优准则。即以效用期,望值代替风险型决策中的期望益损值进行决策。,例 某厂计划生产一种新产品，经预测，该新产品销路好与差,的概率各占50%，该生产工艺有三种。第,、种为现有工,艺，,第,种为新工艺，因此第,种工艺的生产有顺利与不顺,利两种情况，且已知顺利的概率为0.8，不顺利的概率为0.2。,三种工艺在销路好、差状态下的收益值见收益值表。又利用,84,心理测试法，对该厂厂长在生产工艺决策问题上的效用函,数已测出，见厂长效用函数表。,现求：, 作出此问题的决策树。, 以,最大期望益损值为最优决策准则求此问题的最优决策,以最大效用期望值为最优决策准则求此问题的最优决策,收益值r/万元,200 100 50 20 -10 -20 -50 -100,效用值u(r),1.0 0.79 0.66 0.57 0.46 0.42 0.29 0,厂长效用值函数,85,顺利（0.8）,不顺利（0.2）,销路,概率,收益,销路,概率,收益,销路,概率,收益,销路,概率,收益,好,差,0.5,0.5,20,-10,好,差,0.5,0.5,100,-20,好,差,0.5,0.5,200,-50,好,差,0.5,0.5,50,-100,收益值表,单位：万元,解： 作出此问题的决策树。,86,决策者,工艺,工艺,新工艺,销路差0.5,销路好0.5,销路差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,87, 计算各结点的,期望益损值：,结点,：,万元,结点,：,万元,结点,：,万元,结点,：,万元,结点,：,万元,从期望益损值可看出，第种工艺方案为最优方案。此时最,优期望收益值为55万元。,88,决策者,工艺,工艺,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,不顺利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,89, 计算各结点的效用,期望值：,结点,：,万元,结点,：,万元,结点,：,万元,结点,：,万元,结点,：,万元,从效用期望值可看出，第,种工艺方案为最优方案。此时最,大效用期望值为0.605。,90,用效用期望值作标准还有一个优点是：对于不同量纲的目,标，可以折算成效用值，然后相加，求各个方案的总效用,值来进行比较。,例 某公司欲购置一批汽车，须考查两项指标：功率和价格。,该公司决策者认为最合适的功率为70kw，若低于55kw，则不,宜使用；而最满意的价格为4.0万元。若超过5.6 万元，则不能,接受。目前市场上能满足该公司基本要求的汽车型号有：,，。它们的,功率和价格分别为,91,指标,牌号,功率/kw,价格/万元,60,65,70,4.1,4.5,5.2,问该公司决策者应作何种决策？,解：这是一个涉及功率和价格的多目标决策问题，且两个目标,相互矛盾，量纲也不同，无法用绝对数字进行比较。对此可用,如下的方法：应用效用理论，把每个方案的各个指标折合成效,用值，然后加权相加，计算出每个方案的总的效用值，然后进,行比较。,92,首先，应用效用理论，给出该公司决策者的功率效用曲线,与价格效用曲线 ，然后再求出下属各点的效用,值，其结果为：,又通过询问，了解到决策者对功率与价格这两个目标的权重,分别为0.6, 0.4。因此可作出决策树：,93,决策者,0.63,价格0.4,功率0.6,0.78,0.68,功率0.6,功率0.6,价格0.4,价格0.4,0.75,0.20,0.90,60,70,65,0.45,1.0,0.80,4.1,4.5,5.2,计算各结点的效用期望值：,94,决策者,0.63,价格0.4,功率0.6,0.78,0.68,功率0.6,功率0.6,价格0.4,价格0.4,因此，按效用期望值作标准，应选择第,种牌号的车型为,最优决策。,0.75,0.20,0.90,60,70,65,0.45,1.0,0.80,4.1,4.5,5.2,95,层次分析法,层次分析法（Analytical Hierarchy Process ,简称AHP)是美,国匹兹堡大学教授于20世纪70年代提出的一种系统,分析方法。,AHP是一种将定性分析与定量分析相结合的系统分析方,法。在进行系统分析时，经常会碰到这样的一类问题：有,些问题难以甚至根本不可能建立数学模型进行定量分析；,也可能由于时间紧，对有些问题还来不及进行过细的定量,分析，只需作出初步的选择和大致的判定就行了。例如选,择一个新厂的厂址，购买一台重要的设备，确定到哪里去,旅游等等。这时，我们若应用AHP进行分析，就可以简便,地解决问题。,96,将AHP引入决策，是决策科学化的一大进步。它最适宜于解决难以完全用定量方法进行分析的决策问题。因此，它是复杂的社会经济系统实现科学决策的有力工具。,一、AHP的基本原理,为了说明AHP的基本原理，首先让我们分析下面的简单事实。,假定我们已知n个西瓜的总重量为1，每个西瓜的重量为,问每个西瓜相对于其他西瓜的相对重量是多重？,可通过两两比较（相除），得到比较矩阵（以后称之为判断,矩阵）：,97,显然矩阵A满足,（1）,称满足（1）式的矩阵为互反矩阵。且满足,（2）,98,即n是A的一个特征根，,是A的对应于特征根n,的一个特征向量。,设,有,99,现在提出相反的问题：如果事先不知道每个西瓜的重量，也,没有衡器去称量，如何判定每个西瓜的相对重量呢？即如何,判定哪个最重，哪个次之，哪个最轻呢？,我们可以通过两两比较的方法，得出判断矩阵A,然后求出A的,最大特征值 ，进而通过,求出A的特征向量,100,然后通过,将 规范化：,则 即为n个西瓜的相对重量。,101,使用AHP，判断矩阵的一致性是十分重要的。所谓判断矩,阵的一致性，即判断矩阵是否满足如下关系：,若上式完全成立时，称判断矩阵具有,完全一致性,。,可以证明，n阶完全一致性矩阵具有以下的性质：,1。A的秩为1，A的唯一非零特征根为n。,2。A的任一列（行）向量都是对应于特征根n的特征向量。,证明：设,102,是n阶完全一致性矩阵，则,103,注意到：,有,104,105,所以,106,在一般情况下，可以证明判断矩阵的最大特征值为单根，且,当判断矩阵具有满意的一致性时， 稍大于矩阵阶数 ，,其余特征根接近于零。这时AHP得出的结论才基本合理。但,由于客观事物的复杂性和人们认识上的多样性，要求所有的,判断都有完全的一致性是不可能的，但我们要求一定程度上,的判断一致，因此对构造的判断矩阵需要进行一致性检验。,107,二、AHP的步骤,用AHP分析问题大体要经过以下五个步骤：, 建立层次结构模型；, 构造判断矩阵；, 层次单排序；,层次总排序；,一致性检验。,其中后三个步骤在整个过程中需要逐层地进行。,108, 建立层次结构模型,人们在日常生活中经常会碰到许多决策问题：买一件衬衫，,你要在棉的、丝的、涤纶的、及花边的、白的、方格,的、之中作出抉择；请朋友吃饭，要筹划是办家宴还是去,饭店，是吃中餐还是西餐或自助餐；假期旅游，是去风光绮,丽的杭州，还是去迷人的北戴河，或者是去山水甲天下的桂,林。如果你以为这些日常生活小事不必作为决策问题认真对,待的话，那么，当你面临报考学校、选择专业，或者抉择工,作岗位的时候，就要慎重考虑、反复考虑，尽可能地做出满,意的抉择了。,109,从事各种职业的人也经常面临决策：一个厂长要决定购买哪,种设备，上马什么产品；科技人员要选择研究课题；医生要,为疑难病例选择治疗方案；经理要从若干应试者中选择秘,书；各地区、各部门的官员要对人口、交通、经济、环境等,领域的发展规划作出决策。,层次分析法的基本思路与人对一个复杂的决策问题的思维、判,断过程大体上类似。不妨用前面提到过的假期旅游为例，假如,有 、 、 三个旅游胜地供你选择，你会根据诸如景色、费,用、居住、饮食、旅途条件等一些准则去反复比较哪三个候选,地点。首先，你会确定这些准则在你心目中各占多大比重，如,110,果你经济宽绰、醉心旅游，自然特别看重景色，而平素简朴,或手头拮据的人则会优先考虑费用，中老年则会对居住、饮,食等条件给予较大关注。其次，你会就每一准则将三个地点,进行对比，譬如 景色最好， 次之； 费用最低， 次之；,居住条件较好等。最后，你要将这两个层次的比较判断进行,综合，在 ， ， 中确定哪个作为最佳地点。,上面的思维过程可以加工整理成以下几个步骤：,1将决策问题分解为3个层次，最上层为目标层，即选择旅游,地，最下层为方案层，有 ， ， 3个供你选择地点，中间层,为准则层，有景色、费用、居住、饮食、旅途5个准则，各层,间的联系用相连的直线表示。见下图,111,目标层,选择旅游地,景色,费用,居住,饮食,旅途,准则层,方案层,图5.1 选择旅游地的层次结构,112, 构造判断矩阵,通过相互比较确定各准则对于目标的权重，即构造判断矩,阵。,设准则层5个准则 景色， 费用， 居住， 饮食,旅途。相对于目标层：选择旅游地， 两两比较打分。,相对重要程度,定义,解释,1,3,5,7,9,2，4，6，8,同等重要,略微重要,相当重要,明显重要,绝对重要,介于两重要程度之间,目标i与j同样重要,目标i比j,略微重要,目标i比j重要,目标i比j明显重要,目标i比j绝对重要,113,采用19的比例表度的依据是：,心理学的实验表明，大多,数人对不同事物在相同属性上的差别的分辨能力在,59，采,用19的标度反映了大多数人的判断能力；,大量的社会调,查表明，,19的比例标度早已被人们所熟悉和采用；,科学,考察和实践表明，,19的比例标度已完全能区分引起人们感,觉差别的事物的各种属性。,114,选择旅游地,景色,费用,居住,饮食,旅途,115,相对于景色,相对于费用,相对于居住,相对于饮食,116,相对于旅途, 层次单排序,所谓层次单排序是指，对于上一层某因素而言，本层次各因素,的重要性的排序。具体计算是：,对于判断矩阵B，计算满足,117,的特征根与特征向量，式中 为 的最大特征根，,为对应于 的正规化的特征向量， 的分量 即是相应元,素单排序的权值。,自上而下，先求判断矩阵A的最大特征值与特征向量。,118,例如：,相对于景色,经计算,对应于 的正规化的特征向量为,对应于 的正规化的特征向量为,119,同理算出 的最大特征值分别为：,所对应的特征向量分别为,120,将5个特征向量按列依次排成一矩阵：,为了检验矩阵的一致性，需要计算它的一致性指标CI，定义,一般的，只要 就可认为判断矩阵具有满意的一致性。,121, 层次总排序,各个方案优先程度的排序向量为,首选旅游地为 ，其次为 ，再者,122,一般地，若层次结构有k个层次（目标层算第一层），则,方案的优先程度的排序向量为,123,二、层次分析法的计算方法,层次分析法有两大问题：,判断矩阵一致性的调整；,判断,矩阵的最大特征根与特征向量的计算。对于,，精确解应是,线性代数中的计算方法。但从使用的角度看，一般采用近似,方法计算。主要有三种计算方法。,1、幂法,幂法使我们有可能利用计算机得到任意精确解的最大特征根,及其对应的特征向量。步骤为, 任取与,判断矩阵B同价的正规化的初始向量 ；,计算,124,令 计算, 对于预先给定的精确度 ，当,对所有i=1,2, n成立时，则 为所求特征向量。 可,由下式求得,式中：n为矩阵的阶数；,为向量,的第i个分量。,125,2、和积法,为简化计算，可采用近似方法和积法计算，它可以用计,算器在保证足够精确度的条件下运用AHP。其具体计算步骤,为：, 将,判断矩阵每一列正规化, 将,按行相加,126, 将 规范化,得向量,127, 计算,判断矩阵最大特征根,例 用和积法求下列的判断矩阵的最大特征值和相应的特征向,量。,128,列向量,规一化,按行,求和,规一化,129,这个方法实际上是将A的列向量规一化后取平均值，作为A,的特征向量。因为当A为一致阵时，它的每一列向量都是特,征向量，所以当A的不一致性不严重时，取A的列向量（归,一化后）平均值作为近似特征向量是合理的。,130,3.方根法, 将,判断矩阵每一列正规化, 将,按行相乘, 将 规范化,131,得向量, 计算,判断矩阵最大特征根,132,例9 某单位拟从3名干部中选拔一名领导，选拔的标准有政,策水平、工作作风、业务知识、口才、写作能力和健康状,况。下面用AHP方法对3人综合评估、量化排序。,建立层次结构模型,133,目标层,选一领导干部,健康状况,业务知识,口才,写作能力,工作作风,准则层,方案层,政策水平,134,健康情况,业务知识,写作能力,口才,政策水平,工作作风,健康情况,业务知识,写作能力,口才,政策水平,工作作风,A的最大特征值,相应的特征向量为：,135,假设3人关于6个标准的判断矩阵为：,健康情况,业务知识,写作能力,口才,136,政策水平,工作作风,由此可求得各属性的最大特征值和相应的特征向量。,特征值,健康情况 业务知识 写作能力 口才 政策水平 工作作风,3.02 3.02 3.56 3.05 3.00 3.21,各属性的最大特征值,137,从而有,138,即在3人中应选择A担任领导职务。,139,现代优化算法,140,现代优化算法的重要性,141,现代优化算法,禁忌搜索算法,模拟退火算法,遗传算法,人工神经网络,蚁群算法,粒子群算法,混合算法,特点：,基于客观世界中的一些自然现象；,建立在计算机迭代计算的基础上；,具有普适性，可解决实际应用问题。,142,如何解决问题？,经典数学理论的解法：,Viete 定理：,由,公理、定理形成的演绎逻辑