《单变量优化模型》由会员分享，可在线阅读，更多相关《单变量优化模型（33页珍藏版）》请在金锄头文库上搜索。
1、第三讲: 单变量优化模型 与求解方法,-水鹏朗,数学建模理论与实验,3.1 单变量优化建模举例,符号化问题描述,时间变量在正整数范围取值,按照问题求解需要可以看成整数变量或实数变量,P(t),目标函数,3.1单变量优化建模举例(续）,一头重200磅的猪每天增重5磅, 饲养每天花费45美分. 猪的市场价格是每磅65美分,但价格每天下降1美分,问: 何时出售收益最大?,基本假设,目标函数,优化模型,约束条件,优化变量,优化问题的求解有两种途径:(1)枚举法，计算出目标函数在自然数集合上的函数值，找出最大值点（特殊方法）；(2)t按照连续变量处理，求出最大值点后进行取整运算(通用方法）。,3.1单变
2、量优化建模举例(续）,一头重200磅的猪每天增重5磅, 饲养每天花费45美分. 猪的市场价格是每磅65美分,但价格每天下降1美分,问: 何时出售收益最大?,单变量优化问题的求解,枚举法,没有推广价值, 当自变量连续取值或有 相当多的离散取值时无法工作!,解析方法,定理:有界闭区间上的连续函数必然存在最大值和最小值点.,3.1单变量优化建模举例(续）,一头重200磅的猪每天增重5磅, 饲养每天花费45美分. 猪的市场价格是每磅65美分,但价格每天下降1美分,问: 何时出售收益最大?,单变量优化问题的求解,解析方法,定理:有界闭区间上的连续可微函数的最大值点必然在区间端点或函数的驻点达到. 驻点:
3、,问题回答:第8天出售获利最大.,解析方法的不通用性,假定猪体重的增加服从指数规律 目标函数变成了 求驻点需要解一元非线性方程，难以解析求解。事实上，求驻点本身就可转化为一个单变量无约束优化问题：,3.2 模型参数敏感性分析,一头重200磅的猪每天增重5磅, 饲养每天花费45美分. 猪的市场价格是每磅65美分,但价格每天下降1美分,问: 何时出售收益最大?,最优决策: 最优出售时间,市场价格因素: 猪肉价格每天降价因子 r,养殖猪的品质: 猪的重量每天的增加因子 g,问题:当市场价格因素或养殖猪的品质发生变化时, 最优决策是否对这些变化敏感?,3.2 模型参数的敏感性分析,一头重200磅的猪每
4、天增重5磅, 饲养每天花费45美分. 猪的市场价格是每磅65美分,但价格每天下降1美分,问: 何时出售收益最大?,市场因素的敏感性分析,3.2 模型参数的敏感性分析,一头重200磅的猪每天增重5磅, 饲养每天花费45美分. 猪的市场价格是每磅65美分,但价格每天下降1美分,问: 何时出售收益最大?,市场因素的敏感性分析,价格因素的相对变化率,由价格因素变化引起的最优售出时间的相对变化率,最优售出时间对价格变化因素的敏感性度量: +号 表示 r增加导致售出时间 t 加长，-号 表示 r 增加导致 t 减小。小的绝对值表示不敏感，大的绝对值表示敏感。,解释： 价格因子r的增加会导致最优出售时间 缩
5、短，定量地说，价格因子r 上升2%，会导致 最优出售时间缩短7%。,3.2 模型参数的敏感性分析,养殖猪品质因素的敏感性分析,解释： 品质因子g的增加会导致最优出售时间加长，收益增加，定量地说，品质因子g 上升1%，会导致最优出售时间加长越 3%。最优售出时间对养殖猪的价格因素和品质因子敏感度是差不多的，但影响的方向是相反的。,3.2 模型参数的敏感性分析,问题：对于假设r=0.01,g=5,当价格因子和品质因子在什么范围变化是，最优售出时间t=8是不变的？,最优 出售时间保持是8的价格和品质因子变化的范围,一般情况下，当优化模型受多个参数同时影响时，往往是固定其它参数，仅对一个参数变化讨论最
6、优解对参数的敏感性更为常用。往往和微积分中偏导数的概念相联系。,3.3 单变量优化问题的求解方法,优化问题的一般形式,最小值点的表达形式,全局最小值点：是指该点的函数值不大于函数在区间a,b上任何点的值。 局部极小值点：该点的函数值比函数在它某个邻域内的函数值都小。,单变量函数优化问题求解中，经典的方法主要是寻找局部极小值的各种搜索方法；寻找全局最小值点的方法有遗传算法、神经网络等带有智能搜索的方法（计算耗时大）。,Argument-自变量,3.3 单变量优化问题的求解方法,3.3.1 进退搜索法,单谷性函数：函数由下降区间，极小值点，上升区间三部分构成。一般来说，寻找这样的区间是计算耗时的预
7、处理，没有特别有效的简单方法。,方法:从某点x0出发，以h为步长，如果f(x0)f(x0+h),沿自变量增加方向函数值下降下降，则搜索成功，否则搜索失败。 要点：成功则加倍前进，失败则小步后退 设在第k步搜索起点为 ，搜索步长为 如果 ，搜索成功，更新起点和步长： 进入下一步搜索。 如果 ，搜索失败，退回原出发点，缩短步长并反向搜索,3.3 单变量优化问题的求解方法,进退搜索算法流程,3.3 单变量优化问题的求解方法,实例演示,输入起始点x=0； 起始步长h=1,优点: 算法简单 缺点: 搜索次数多, 接近极小值点时反复搜索,3.3 单变量优化问题的求解方法,3.3.2 区间收缩法-黄金分割法
8、(0.618法),单谷函数：函数由下降区间，极小值点，上升区间三部分构成。一般来说，寻找这样的区间是计算耗时的预处理，没有特别有效的简单方法。,单谷函数,定义 设函数f(x)在区间a,b上有定义，满足 1)在a,b上f(x)有极小点x*: 2)函数f(x)在x*处是左减右增： 对ax1x2b, 有 当x2 x*时，f(x1) f(x2) 当x1 x*时，f(x1) f(x2),3.3 单变量优化问题的求解方法,3.3.2 区间收缩法-黄金分割法(0.618法),搜索区间,设函数f(x)是区间a,b的单谷函数，设x*为f(x)的极小点，若存在c,da,b，使得cx*d, 则区间c,d称为f(x)
9、的极小点的一个搜索区间,区间收缩法就是构造一个搜索区间序列,使得:,3.3 单变量优化问题的求解方法,3.3.2 区间收缩法-黄金分割法(0.618法),区间收缩方法: 在区间a,b内插入两点c, d, 满足af(d)时, 极小值x*c, b (2) f(c)f(d),极小值x*a, d,问题: c, d 如何选择 搜索区间收缩的最快?,华罗庚的 “优选法” 或 黄金分割法,Why? c点位于函数的下降段,Why? d点位于函数的上升段,3.3 单变量优化问题的求解方法,3.3.2 区间收缩法-黄金分割法(0.618法),华罗庚的 “优选法”,点d是区间a, b的黄金分割点(左长右短),点c是
10、区间a, b的黄金分割点(左短右长),黄金分割的特点,黄金分割之美,肚脐-这是身体上下部位的黄金分割点，肚脐以上身体长度与肚脐以下的比值是06181。 喉结-它所分割的咽喉至头顶与咽喉至肚脐的距离比也为06181； 肘关节-它到肩关节与它到中指尖之比还是06181； 手的中指长度与手掌长度之比是06181； 手掌的宽度与手掌的长度之比是06181。,3.3 单变量优化问题的求解方法,3.3 单变量优化问题的求解方法,黄金分割法算法演示,a=0,b=5,a=1.91,b=5,a=1.91,b=3.81926,a=2.6395,b=3.81926,a=3.0903,b=3.81926,a=3.09
11、03,b=3.5410,a=3.0903,b=3.3688,a=3.1967,b=3.3688,a=3.1967,b=3.3031,a=3.2373,b=3.3031,注意: 前面两种方法与函数在区间a, b上是否连续无关,3.3 单变量优化问题的求解方法,为什么是黄金分割？,前后两次收缩总是共用某个黄金分割点，意味着每次区间收缩仅需要计算一个函数值。,角色对换,3.3 单变量优化问题的求解方法,为什么是黄金分割？,对于黄金分割，每计算一次函数值，解的范围缩小到原区间的0.618.,按别的方法效果如何呢？,计算两个函数值，收缩2/3, 每个函数值平均收缩到原区间的sqrt(2/3)=0.816
12、50.618,计算两个函数值，收缩0.5+, 每个函数值平均收缩到原区间的sqrt(0.5+)0.70710.618,3.3 单变量优化问题的求解方法,为什么是黄金分割？,规则简单，易于操作和推广； 收缩效率高，每计算一次函数值，区间收缩0.618； 对函数要求少，单谷或单峰函数。,实际应用中，计算一次函数值往往等价于做一次复杂的试验，因此，寻优算法被期望达到最优解用尽可能少的函数值计算次数。,应用举例,干旱地区打井位置确定问题：在某干旱地区需要沿从A-B点1000米的干枯河床打10米深的测试井发现正确的井口位置，设计合适的方案以便井口位置在泉眼5米范围内。,3.3 单变量优化问题的求解方法,
13、地面,A,B,泉眼,探测井,0,1000,x-位置坐标,位置确定依靠探测井底土壤湿度，湿度越大，位置越接近泉眼； 假定湿度是位置的单峰函数； 建模目的是用最少数目的探测井把位置确定到泉眼5米的范围内； 设湿度函数是y=f(x),x0,1000,No,3.3 单变量优化问题的求解方法,黄金分割法,Yes,No,Yes,K-收缩次数,仅需要打8口测试井！,全局搜索方法需要1000/5=200口测试井，费用、劳动输出巨大！,3.3 单变量优化问题的求解方法,3.3.3 抛物线插值法,开口向上的抛物线具有唯一的最小值点和最小值,对于在区间a,b上的单谷函数f(x), 取 , 求过三点 的抛物线P(x)
14、.,3.3 单变量优化问题的求解方法,3.3.3 抛物线插值法,x4是抛物线的最小值点,主要结论,3.3 单变量优化问题的求解方法,3.3 单变量优化问题的求解方法,抛物线插值区间收缩算法,3.3 单变量优化问题的求解方法,3.3.4 牛顿迭代方法,(i). 函数f(x)在区间a,b的二阶导数存在; (ii). 函数f(x)在区间a,b上是单谷函数; (iii). 函数f(x)在区间(a,b)上的二阶导数大于零.,基本要求,在区间a,b的每一个内点上,函数在这一点附近可以进行二阶Taylor展开:,二阶Taylor展开,当 时, 是开口向上的抛物线,抛物线的最小值点为:,3.3 单变量优化问题的求解方法,算例演示,迭代过程,注:(1)牛顿迭代方法中迭代过程中二阶导数必须大于零,否则迭代过程可能发散; (2)迭代初期,收敛速度很快,但随着接近极小值点,收敛速度明显下降.,课后作业,1 尝试用Matlab或者C+实现上面四种求解算法中的两种。并用编制的程序求 并尝试讨论初始点对计算结果的影响。,2 尝试用Matlab或者C+实现打井找水问题的程序实现，假定泉眼在103米处，湿度函数是 试给出用黄金分割法获得的测试井的坐标位置。,
