最优化方法-read.ppt

3 最优化方法 3.1 线性规划 大M单纯形解法 3.3 非线性规划 我们主要介绍无约束最优化问题： 给定下单峰区间 [a, b] 及控制误差?＞0, 黄金分割法(0.618法)的迭代步骤： 下面我们再给出一个求初始区间的进退算法, 在所求出的区间上 f (x)是下单峰函数. 给定初始点x0和初始步长?＞0, 进退算法的迭代步骤： 最速下降法 最速下降法的优缺点 序列无约束最小化方法 * * 许多生产计划与管理问题都可以归纳为最优化问题, 最优化模型是数学建模中应用最广泛的模型之一,其内容包括线性规划、整数线性规划、非线性规划、动态规划、变分法、最优控制等. 近几年来的全国大学生数学建模竞赛中，几乎每次都有一道题要用到此方法. 此类问题的一般形式为： min f (x), s.t. x∈?. 目标函数 约束条件 可行解域 线性规划是最优化方法中理论完整、方法成熟、应用广泛的一个重要分支 . 线性规划问题的数学模型是将实际问题转化为一组线性不等式或等式约束下求线性目标函数的最小(大)值问题, 它都可以化为如下标准(矩阵)形式： A = (aij )m×n c = (c1 , c2 , … , cn ) x≥0指x中的每一个分量xj ≥0 不难将一般的线性规划问题化成如下标准形式： 大M单纯形解法是引入m个人工变量xn+1 , …, xn+m将原问题变为 大M单纯形解法中的M为足够大的正数, 起“惩罚”作用, 以便排除人工变量. 线性规划问题主要解法是单纯形解法，一般用Lingo软件求解. 值得注意的是：在建立线性规划模型后求解时，尽量删除那些取值为零的变量. min{ f (x)| x ∈En }, 这里x =(x1 , x2 , …, xn)T. 我们先介绍求解一元函数 y = f (x)极小值的数值迭代算法：一维有哪些信誉好的足球投注网站算法中的黄金分割法(0.618法). 分割法原理：设函数 f (x) 在闭区间 [a, b] 上是下单峰函数, 即在 (a, b) 内 f (x) 由唯一的极小点x*, 在x* 的左边 f (x) 严格单调下降, 在x* 的右边f (x)严格单调上升. 那么对于(a, b)内任意两点x1＜x2, 如果 f (x1)＜ f (x2 ), 则x*∈[a, x2]；否则x*∈[x1, b]. 如右图 ①取 x2 = a + 0.618 (b - a), f2 = f (x2), 转向②. ②取 x1 = a + 0.382 (b - a), f1 = f (x1), 转向③. ③若 | b – a |＜? , 则取x* = (a + b )/2, 停. 否则转向④. ④若f1＜ f2 , 则取b = x2 , x2 = x1, f2 = f1 , 转向②; 若f1= f2 , 则取a = x1, b = x2, 转向①; 若f1＞f2 , 则取a = x1, x1= x2, f1 = f2 , 转向⑤. ⑤取 x2 = a + 0.618 (b - a), f2= f (x2), 转向③. ①取 x1 = x0 +? , 计算 f (x0 ), f (x1). 若f (x0) ≥ f (x1), 则转向②；否则转向④. ②取? = 2? , x2 = x1 +? , 计算 f (x2 ). 若f (x2)≥ f (x1), 则得到区间 [x0 , x2] 为初始区间, 停；否则转向③. ③取 x0 = x1 , x1 = x2 , f (x0 ) = f (x1 ), f (x1) = f (x2 ), 转向②. ④取? =2? , x2 = x0 - ? , 计算 f (x2 ). 若f (x2 )≥ f (x0 ), 则得到区间 [x2 , x1] 为初始区间, 停；否则转向⑤. ⑤取 x1 = x0 , x0 = x2, f (x1 ) = f (x0 ), f (x0 ) = f (x2 ), 转向④. 对于无约束最优化问题：min{ f (x)},这里的x = (x1 , x2 , …, xn)T.下面给出一个基于最速下降方向的算法,它是由柯西(Cauchy)在1847年提出的,是求无约束极值的最早的数值算法. 给定控制误差? ＞0和初始点xk (k = 0), 最速下降法的迭代步骤： ① 计算g(xk ). 梯度 ② 若|| g (xk )||≤? , 则取x*= xk, 停；否则,令pk = - g(