运筹学的优化算法

运筹学的优化算法1运筹学（OperationsResearchOR）

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

SARS的传播：微分方程、差分方程

03B

露天矿生产的车辆安排：整数规划、运输问题04A

奥运会临时超市网点设计：统计分析、数据处理、优化

04B

电力市场的输电阻塞管理：数据拟合、优化

05A

长江水质的评价和预测：预测评价、数据处理

05B

DVD在线租赁：随机规划、整数规划

06A

出版社书号问题：整数规划、数据处理、优化

数学建模竞赛中的算法(4)906B

Hiv病毒问题：线性规划、回归分析07A

人口问题：微分方程、数据处理、优化07B

公交车问题：多目标规划、动态规划、图论、0-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去掉整数约束,用单纯形法IPLPxl*

判别是否整数解xI*=xl*Yes去掉非整数域No多个LP……19分枝定界法步骤一般求解对应的松驰问题，可能会出现下面几种情况：若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。20分枝定界法步骤一般求解对应的松驰问题，可能会出现下面几种情况：若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。若松驰问题无可行解，则原整数规划问题也无可行解，计算结束。21若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。22若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。从不满足整数条件的基变量中任选一个xl进行分枝，它必须满足xl

[xl]

或xl

[xl

]+1中的一个，把这两个约束条件加进原问题中，形成两个互不相容的子问题（两分法）。23定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。24定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。剪枝：把那些子问题的最优值与界值比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查清为止。25例：

用分枝定界法求解：MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0整数用单纯形法可解得相应的松驰问题的最优解（6/5，21/10）Z=111/10为各分枝的上界。26012344321x1x2分枝：x1

1,x1

2P1P2（6/5，21/10）27两个子问题：（P1）MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0，x1

1，整数用单纯形法可解得相应的（P1）的最优解（1，9/4）Z=10(3/4)28（P2）MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0，x1

2，整数用单纯形法可解得相应的（P2）的最优解（2，1/2）Z=9(1/2)29012344321x1x2再对（P1）x1

1（1，9/4）分枝：（P3）x2

2（P4）x2

3P1P2P3P430（P1）两个子问题：（P3）MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0,x1

1,x2

2整数用单纯形法可解得相应的（P3）的最优解（1，2）Z=10为上界31（P1）两个子问题：（P4）MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,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多阶段资源分配问题

设有数量为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）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续（2）38例2生产和存储控制问题

某工厂生产某种季节性商品，需要作下一年度的生产计划，假定这种商品的生产周期需要两个月，全年共有6个生产周期，需要作出各个周期中的生产计划。39设已知各周期对该商品的需要量如下表所示：周期123456需求量551030508例2续（1）40例2续（2）

假设这个工厂根据需要可以日夜两班生产或只是日班生产，当开足日班时，每一个生产周期能生产商品15个单位，每生产一个单位商品的成本为100元。当开足夜班时，每一生产周期能生产的商品也是15个，但是由于增加了辅助性生产设备和生产辅助费用，每生产一单位商品的成本为120元。由于生产能力的限制，可以在需求淡季多生产一些商品储存起来以备需求旺季使用，但存储商品是需要存储费用的，假设每单位商品存储一周期需要16元，已知开始时存储为零，年终也不存储商品备下年使用，问应该如何作生产和存储计划，才能使总的生产和存储费用最小？41例2续（3）

设第i个周期的生产量为xi，周期末的存储量为ui，那么这个问题用式子写出来就是：求x1,x2,…,x6，满足条件：

x1=5+u1x2+u1=5+u2x3+u2=10+u3x4+u3=30+u4x5+u4=50+u5x6+u5=80xi30,0uj,i=1,2,…,6;j=1,2,…,5

使S==

为最小，其中42例2续（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.510－2.54.50－7.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次掷出正面的概率为：Y222223…n…P(Y2=k)1/21/221/23…1/2n…X012…n-1…相互独立设掷出正面前掷出反面的次数为随机变量X,则有分布列：则方案2的平均收益为：66Y222223…n…P(Y2=k)1/21/221/23…1/2n…X012…n-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⑷同理在60元到200元之间求出某点的效用值。经过几次提问，决策者稳定在81对于此决策者，此时的心态，任给一个值，比如25元（横坐标），通过曲线，即可查出其效用值。三、效用曲线的类型：ⅠⅡⅢ总体上讲，效用曲线可分为：Ⅰ：保守型Ⅱ：中间型Ⅲ：冒险型82ⅠⅡⅢ保守型的人对收益增加反映比较迟钝，相反对损失反映比较敏感。冒险型的人对损失增加反映比较迟钝，相反对收益反映比较敏感。中间型介于两者之间。83四、最大效用期望值决策准则及其应用最大效用期望值决策准则，就是依据效用理论，通过效用函数（或效用曲线）计算出各个策略结点的效用期望值，以效用期望值最大的策略作为最优策略的选优准则。即以效用期望值代替风险型决策中的期望益损值进行决策。例某厂计划生产一种新产品，经预测，该新产品销路好与差的概率各占50%，该生产工艺有三种。第Ⅰ、Ⅱ种为现有工艺，第Ⅲ种为新工艺，因此第Ⅲ种工艺的生产有顺利与不顺利两种情况，且已知顺利的概率为0.8，不顺利的概率为0.2。三种工艺在销路好、差状态下的收益值见收益值表。又利用84心理测试法，对该厂厂长在生产工艺决策问题上的效用函数已测出，见厂长效用函数表。现求：⑴作出此问题的决策树。⑵以最大期望益损值为最优决策准则求此问题的最优决策

⑶以最大效用期望值为最优决策准则求此问题的最优决策收益值r/万元2001005020-10-20-50-100效用值u(r)1.00.790.660.570.460.420.290厂长效用值函数85ⅠⅡⅢ顺利（0.8）不顺利（0.2）销路概率收益销路概率收益销路概率收益销路概率收益好差0.50.520-10好差0.50.5100-20好差0.50.5200-50好差0.50.550-100收益值表单位：万元解：⑴作出此问题的决策树。86决策者工艺Ⅰ工艺ⅡⅠⅡⅢ新工艺Ⅲ销路差0.5销路好0.5销路差0.5销路好0.5ⅣⅤ顺利0.8销路好0.5销路差0.5销路好0.5销路差0.554055不顺利0.275收益值20-10100-20200-50-10050-2587⑵计算各结点的期望益损值：结点Ⅰ：万元结点Ⅱ：万元结点Ⅲ：万元结点Ⅳ：万元结点Ⅴ：万元从期望益损值可看出，第Ⅲ种工艺方案为最优方案。此时最优期望收益值为55万元。88决策者工艺Ⅰ工艺Ⅱ0.515ⅠⅡⅢ新工艺Ⅲ销路差0.5销路好0.5销路差0.5销路好0.5ⅣⅤ顺利0.8销路好0.5销路差0.5销路好0.5销路差0.55400.605550.582不顺利0.2750.645收益值效用值200.57-100.461000.79-200.422001.0-500.29-1000.0500.660.33-2589⑶计算各结点的效用期望值：结点Ⅰ：万元结点Ⅱ：万元结点Ⅲ：万元结点Ⅳ：万元结点Ⅴ：万元从效用期望值可看出，第Ⅱ种工艺方案为最优方案。此时最大效用期望值为0.605。90用效用期望值作标准还有一个优点是：对于不同量纲的目标，可以折算成效用值，然后相加，求各个方案的总效用值来进行比较。例某公司欲购置一批汽车，须考查两项指标：功率和价格。该公司决策者认为最合适的功率为70kw，若低于55kw，则不宜使用；而最满意的价格为4.0万元。若超过5.6万元，则不能接受。目前市场上能满足该公司基本要求的汽车型号有：Ⅰ，Ⅱ，Ⅲ。它们的功率和价格分别为91指标牌号功率/kw价格/万元ⅠⅡⅢ6065704.14.55.2问该公司决策者应作何种决策？解：这是一个涉及功率和价格的多目标决策问题，且两个目标相互矛盾，量纲也不同，无法用绝对数字进行比较。对此可用如下的方法：应用效用理论，把每个方案的各个指标折合成效用值，然后加权相加，计算出每个方案的总的效用值，然后进行比较。92首先，应用效用理论，给出该公司决策者的功率效用曲线与价格效用曲线，然后再求出下属各点的效用值，其结果为：又通过询问，了解到决策者对功率与价格这两个目标的权重分别为0.6,0.4。因此可作出决策树：93决策者0.63ⅠⅡⅢ价格0.4功率0.60.780.68功率0.6功率0.6价格0.4价格0.40.750.200.906070650.451.00.804.14.55.2计算各结点的效用期望值：94决策者0.63ⅠⅡⅢ价格0.4功率0.60.780.68功率0.6功率0.6价格0.4价格0.4因此，按效用期望值作标准，应选择第Ⅱ种牌号的车型为最优决策。0.750.200.906070650.451.00.804.14.55.295层次分析法层次分析法（AnalyticalHierarchyProcess,简称AHP)是美国匹兹堡大学教授A.L.Saaty于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注意到：有104105所以106在一般情况下，可以证明判断矩阵的最大特征值为单根，且当判断矩阵具有满意的一致性时，稍大于矩阵阶数，其余特征根接近于零。这时AHP得出的结论才基本合理。但由于客观事物的复杂性和人们认识上的多样性，要求所有的判断都有完全的一致性是不可能的，但我们要求一定程度上的判断一致，因此对构造的判断矩阵需要进行一致性检验。107二、AHP的步骤用AHP分析问题大体要经过以下五个步骤：⑴建立层次结构模型；⑵构造判断矩阵；⑶层次单排序；⑷层次总排序；⑸一致性检验。其中后三个步骤在整个过程中需要逐层地进行。108⑴建立层次结构模型人们在日常生活中经常会碰到许多决策问题：买一件衬衫，你要在棉的、丝的、涤纶的、…及花边的、白的、方格的、…之中作出抉择；请朋友吃饭，要筹划是办家宴还是去饭店，是吃中餐还是西餐或自助餐；假期旅游，是去风光绮丽的杭州，还是去迷人的北戴河，或者是去山水甲天下的桂林。如果你以为这些日常生活小事不必作为决策问题认真对待的话，那么，当你面临报考学校、选择专业，或者抉择工作岗位的时候，就要慎重考虑、反复考虑，尽可能地做出满意的抉择了。109从事各种职业的人也经常面临决策：一个厂长要决定购买哪种设备，上马什么产品；科技人员要选择研究课题；医生要为疑难病例选择治疗方案；经理要从若干应试者中选择秘书；各地区、各部门的官员要对人口、交通、经济、环境等领域的发展规划作出决策。层次分析法的基本思路与人对一个复杂的决策问题的思维、判断过程大体上类似。不妨用前面提到过的假期旅游为例，假如有、、三个旅游胜地供你选择，你会根据诸如景色、费用、居住、饮食、旅途条件等一些准则去反复比较哪三个候选地点。首先，你会确定这些准则在你心目中各占多大比重，如110果你经济宽绰、醉心旅游，自然特别看重景色，而平素简朴或手头拮据的人则会优先考虑费用，中老年则会对居住、饮食等条件给予较大关注。其次，你会就每一准则将三个地点进行对比，譬如景色最好，次之；费用最低，次之；居住条件较好等。最后，你要将这两个层次的比较判断进行综合，在，，中确定哪个作为最佳地点。上面的思维过程可以加工整理成以下几个步骤：1．将决策问题分解为3个层次，最上层为目标层，即选择旅游地，最下层为方案层，有，，3个供你选择地点，中间层为准则层，有景色、费用、居住、饮食、旅途5个准则，各层间的联系用相连的直线表示。见下图111目标层选择旅游地景色费用居住饮食旅途准则层方案层图5.1选择旅游地的层次结构112⑵构造判断矩阵①通过相互比较确定各准则对于目标的权重，即构造判断矩阵。设准则层5个准则景色，费用，居住，饮食旅途。相对于目标层：选择旅游地，两两比较打分。相对重要程度定义解释135792，4，6，8同等重要略微重要相当重要明显重要绝对重要介于两重要程度之间目标i与j同样重要目标i比j略微重要目标i比j重要目标i比j明显重要目标i比j绝对重要113采用1～9的比例表度的依据是：①心理学的实验表明，大多数人对不同事物在相同属性上的差别的分辨能力在5～9，采用1～9的标度反映了大多数人的判断能力；②大量的社会调查表明，1～9的比例标度早已被人们所熟悉和采用；③科学考察和实践表明，1～9的比例标度已完全能区分引起人们感觉差别的事物的各种属性。114选择旅游地景色费用居住饮食旅途115相对于景色相对于费用相对于居住相对于饮食116相对于旅途⑶层次单排序所谓层次单排序是指，对于上一层某因素而言，本层次各因素的重要性的排序。具体计算是：对于判断矩阵B，计算满足117的特征根与特征向量，式中为的最大特征根，为对应于的正规化的特征向量，的分量即是相应元素单排序的权值。自上而下，先求判断矩阵A的最大特征值与特征向量。118例如：相对于景色经计算对应于的正规化的特征向量为对应于的正规化的特征向量为119同理算出的最大特征值分别为：所对应的特征向量分别为120将5个特征向量按列依次排成一矩阵：为了检验矩阵的一致性，需要计算它的一致性指标CI，定义一般的，只要就可认为判断矩阵具有满意的一致性。121⑷层次总排序各个方案优先程度的排序向量为首选旅游地为，其次为，再者122一般地，若层次结构有k个层次（目标层算第一层），则方案的优先程度的排序向量为123二、层次分析法的计算方法层次分析法有两大问题：①判断矩阵一致性的调整；②判断矩阵的最大特征根与特征向量的计算。对于②，精确解应是线性代数中的计算方法。但从使用的角度看，一般采用近似方法计算。主要有三种计算方法。1、幂法幂法使我们有可能利用计算机得到任意精确解的最大特征根及其对应的特征向量。步骤为⑴任取与判断矩阵B同价的正规化的初始向量；⑵计算124⑶令计算⑷对于预先给定的精确度，当对所有i=1,2,…n成立时，则为所求特征向量。可由下式求得式中：n为矩阵的阶数；为向量的第i个分量。1252、和积法为简化计算，可采用近似方法—和积法计算，它可以用计算器在保证足够精确度的条件下运用AHP。其具体计算步骤为：⑴将判断矩阵每一列正规化⑵将按行相加126⑶将规范化得向量127⑷计算判断矩阵最大特征根例用和积法求下列的判断矩阵的最大特征值和相应的特征向量。128列向量规一化按行求和规一化129这个方法实际上是将A的列向量规一化后取平均值，作为A的特征向量。因为当A为一致阵时，它的每一列向量都是特征向量，所以当A的不一致性不严重时，取A的列向量（归一化后）平均值作为近似特征向量是合理的。1303.方根法⑴将判断矩阵每一列正规化⑵将按行相乘⑶将规范化131得向量⑷计算判断矩阵最大特征根132例9某单位拟从3名干部中选拔一名领导，选拔的标准有政策水平、工作作风、业务知识、口才、写作能力和健康状况。下面用AHP方法对3人综合评估、量化排序。⑴建立层次结构模型133目标层选一领导干部健康状况业务知识口才写作能力工作作风准则层方案层政策水平134健康情况业务知识写作能力口才政策水平工作作风健康情况业务知识写作能力口才政策水平工作作风A的最大特征值相应的特征向量为：135假设3人关于6个标准的判断矩阵为：健康情况业务知识写作能力口才136政策水平工作作风由此可求得各属性的最大特征值和相应的特征向量。特征值健康情况业务知识写作能力口才政策水平工作作风

3.023.023.563.053.003.21各属性的最大特征值137从而有138即在3人中应选择A担任领导职务。139现代优化算法140现代优化算法的重要性141现代优化算法禁忌搜索算法模拟退火算法遗传算法人工神经网络蚁群算法粒子群算法混合算法特点：基于客观世界中的一些自然现象；建立在计算机迭代计算的基础上；具有普适性，可解决实际应用问题。142如何解决问题？经典数学理论的解法：Viete

定理：由公理、定理形成的演绎逻辑体系优点：准确、快速、有明确数学意义不足：只能解决有限问题、解法是特定的无法解决高次问题及更复杂问题。考虑一个一元方程：143数值解法：

通过引入一些假设来获得问题的近似解

取初始值为1，代入得：

11.580531.577021.57705

优点：可求解问题的范围比较广泛

不足：解法的特殊性，要求迭代收敛如何解决问题？（1）144传统算法的局限解法是特定的

----不同的问题需要使用不同的解法所能解决的问题是有限的

----和数学工具直接相关，若没有解决问题的数学方法，则难以解决

145现代优化算法

现代优化算法又称智能优化算法或现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据,而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。146现代优化算法的特点它们的共同特点：都是从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。147全局优化Rastrigin’sFunction全局最小点(0,0)148现代优化算法特点：1)不依赖于初始条件；2)不与求解空间有紧密关系,对解域无可微或连续的要求;容易实现，求解稳健。3)能获得全局最优;适合于求解空间不知的情况。4)SA,GA可应用于大规模、多峰多态函数、含离散变量等全局优化问题;求解速度和质量远超过常规方法。149常用的现代优化算法

遗传算法

GeneticAlgorithm，简称GA模拟退火算法

SimulatedAnnealing，简称SA禁忌搜索算法神经网络算法群智能算法，包括蚁群算法、粒子群算法微分进化算法（DifferentialEvolution）……150搜索示例：三个孩子的年龄(1)两个多年未见的朋友相遇，聊了很多事情。…A：既然你是数学教授，那你帮我算这个题，今天是个特殊日子：我三个儿子都在今天庆祝生日！那么你能算出他们都有多大吗？B：好，但你得跟我讲讲他们的情况。A：好的，我给你一些提示，他们三个年龄之积是36.B：很好，但我还需要更多提示。151三个孩子的年龄(2)A：我的大儿子的眼睛是蓝色的。B考虑了一下说，但是，我还有一点信息来解决你的这个难题。B：哦，够了，B给出了正确的答案，即三个小孩的年龄。A：他们三个年龄之和等于那幢房子的窗户个数。A指着对面的一幢房子说。152三个孩子的年龄(3)根据对话信息，用搜索的方法来解此问题。信息1:三个小孩年龄之积为36只有以下8种可能，搜索范围减少至8种情况:第一个小孩年龄36181299664第二个小孩年龄12342633第三个小孩年龄11112123153三个孩子的年龄(4)信息2:三个小孩年龄之和等于窗户数第一个小孩年龄36181299664第二个小孩年龄12342633第三个小孩年龄11112123窗户数:3821161413131110如果窗户数为38、21、16、14、11、10即可得出答案B还需信息，即窗户数为13.则可能为(9、2、2)或(6、6、1)信息2:大儿子眼睛是蓝色的得答案：(9、2、2)154典型问题——旅行商问题（Travelingsalesmanproblem,TSP）给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。123412181032搜索示例：TSP问题155典型问题——旅行商问题（Travelingsalesmanproblem,TSP）计算复杂度：指数灾难

城市数2425262728293031计算时间1sec24sec10min4.3hour4.9day136.5day10.8year325yearTSP的搜索的困难156模拟退火法157模拟退火算法及模型

算法的提出

模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。算法的目的解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。物理退火过程158物理退火过程

什么是退火：退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。物理退火过程159模拟退火算法及模型

物理退火过程

加温过程——增强粒子的热运动，消除系统原先可能存在的非均匀态；等温过程——对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。物理退火过程160161模拟退火算法及模型

数学表述

在温度T，分子停留在状态r满足Boltzmann概率分布物理退火过程162模拟退火算法及模型

数学表述在同一个温度T，选定两个能量E1<E2，有在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。物理退火过程<1>0163模拟退火算法及模型

数学表述

若|D|为状态空间D中状态的个数，D0是具有最低能量的状态集合：当温度很高时，每个状态概率基本相同，接近平均值1/|D|；状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/|D|；当温度趋于0时，分子停留在最低能量状态的概率趋于1。物理退火过程能量最低状态非能量最低状态164模拟退火算法及模型

Metropolis准则（1953）——以概率接受新状态固体在恒定温度下达到热平衡的过程可以用MonteCarlo方法（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。物理退火过程165模拟退火算法及模型

Metropolis准则（1953）——以概率接受新状态若在温度T，当前状态i→新状态j

若Ej<Ei，则接受j为当前状态；否则，若概率p=exp[-(Ej-Ei)/kBT]

大于[0,1)区间的随机数，则仍接受状态j

为当前状态；若不成立则保留状态i

为当前状态。物理退火过程166模拟退火算法及模型

Metropolis准则（1953）——以概率接受新状态

p=exp[-(Ej-Ei)/kBT]

在高温下，可接受与当前状态能量差较大的新状态；在低温下，只接受与当前状态能量差较小的新状态。物理退火过程167模拟退火算法及模型

相似性比较

组合优化与物理退火的相似性组合优化问题金属物体解粒子状态最优解能量最低的状态设定初温熔解过程Metropolis抽样过程等温过程控制参数的下降冷却目标函数能量168算法描述169案例讲解已知敌方100个目标的经度、纬度我方有一个基地，经度和纬度为（70,40）。假设我方飞机的速度为1000公里/小时。我方派一架飞机从基地出发，侦察完敌方所有目标，再返回原来的基地。在敌方每一目标点的侦察时间不计，求该架飞机所花费的时间（假设我方飞机巡航时间可以充分长）。170模拟退火算法及模型

基本步骤

给定初温t=t0，随机产生初始状态s=s0，令k=0；

RepeatRepeat

产生新状态sj=Genete(s)；

ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；

Until算法终止准则满足；输出算法搜索结果。模拟退火算法的基本思想和步骤171模拟退火算法及模型

影响优化结果的主要因素

给定初温t=t0，随机产生初始状态s=s0，令k=0；

RepeatRepeat

产生新状态sj=Genete(s)；

ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；

Until算法终止准则满足；输出算法搜索结果。模拟退火算法的基本思想和步骤三函数两准则初始温度172173174175模拟退火算法关键参数和操作的设计原则

(1)在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；

(2)随温度的下降，接受使目标函数上升的解的概率要逐渐减小；

(3)当温度趋于零时，只能接受目标函数下降的解。方法

具体形式对算法影响不大一般采用min[1,exp(-∆C/t)]状态接受函数176模拟退火算法关键参数和操作的设计收敛性分析