1、第三讲: 单变量优化模型 与求解方法,-水鹏朗 雷达信号处理国防科技重点实验室,数学建模基础,3.1 单变量优化建模举例,符号化问题描述,时间变量在正整数范围取值,按照问题求解需要可以看成整数变量或实数变量,目标函数,3.1单变量优化建模举例(续）,一头重200磅的猪每天增重5磅, 饲养每天花费45美分. 猪的市场价格是每磅65美分,但价格每天下降1美分,问: 何时出售收益最大?,基本假设,目标函数,优化模型,约束条件,优化变量,优化问题的求解有两种途径:(1)枚举法，计算出目标函数在自然数集合上的函数值，找出最大值点（特殊方法）；(2)t按照连续变量处理，求出最大值点后进行取整运算(通用方法
2、）。,3.1单变量优化建模举例(续）,一头重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 模型参数的敏感性分析,一头
4、重200磅的猪每天增重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上的任何点的值。 局部极小值点：该点的函数值比函数在它的某个邻域内的函数值小。,单变量函数优化问题求解中，经典的方法主要是寻找局部极小值 的各种搜索方法；寻找全局最小值点的方法有遗传算法，神经网络等方法（计算耗时大）。,3.3 单变量优化问题的求解方法,3.3.1 进退搜索法,单谷性函数：函数由下降区间，极小值点，上升区间三部分构成。一般来说，寻找这样的区间是计算耗时的预处理，没有特别有效的简单方法。,方法:从某点x0出发，以h
7、为步长，如果f(x0)f(x0+h),沿自变量增加方向函数值下降下降，则搜索成功，否则搜索失败。 要点：成功则加倍前进，失败则小步后退设在第k步搜索起点为 ，搜索步长为 如果 ，搜索成功，更新起点和步长：进入下一步搜索。如果 ，搜索失败，退回原出发点，缩短步长并反向搜索,3.3 单变量优化问题的求解方法,进退搜索算法流程,3.3 单变量优化问题的求解方法,实例演示,输入起始点x=0； 起始步长h=1,优点: 算法简单 缺点: 搜索次数多, 接近极小值点时反复搜索,3.3 单变量优化问题的求解方法,3.3.2 区间收缩法-黄金分割法(0.618法),单谷性函数：函数由下降区间，极小值点，上升区间
8、三部分构成。一般来说，寻找这样的区间是计算耗时的预处理，没有特别有效的简单方法。,下单峰函数,定义 设函数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)的极小点的一个搜索区间,区间收缩法就是构造一个搜索区间序列,使得:,3
9、.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 如何选择 搜索区间收缩的最快?,华罗庚的 “优选法” 或 黄金分割法,3.3 单变量优化问题的求解方法,3.3.2 区间收缩法-黄金分割法(0.618法),华罗庚的 “优选法”,点d是区间a, b的黄金分割点(左长右短),点c是区间a, b的黄金分割点(左短右长),黄金分割的特点,黄金分割与美学,肚脐-这是身体上下部位的黄金分割点，肚脐以上身体长度与肚脐以下的比
10、值是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.0903,b=3.5410,a=3.0903,b=3.3688,a=3.1967,b=3.3688,a=3.1967,b=3.3031,a
11、=3.2373,b=3.3031,注意: 前面两种方法与函数在区间a, b上是否连续无关,3.3 单变量优化问题的求解方法,3.3.3 抛物线插值法,开口向下的抛物线具有唯一的最小 值点和最小值,对于在区间a,b上的单谷函数f(x), 取 , 求过三点的抛物线P(x).,3.3 单变量优化问题的求解方法,3.3.3 抛物线插值法,x4是抛物线的最小值点,主要结论,(1) 如果 ,则极小值,(2) 如果 ,则极小值,f(x2),f(x4),(3) 如果 ,则极小值,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)迭代初期,收敛速度很快,但随着接近极小值点,收敛速度明显下降.,
