3 最优化方法 许多生产计划与管理问题都可以归纳为最优化问题, 最优化模型是数学建模中应用最广泛的模型之一,其内容包括线性规划、整数线性规划、非线性规划、动态规划、变分法、最优控制等. 近几年来的全国大学生数学建模竞赛中，几乎每次都有一道题要用到此方法. 此类问题的一般形式为： min f (x),

Presentation on theme: "3 最优化方法 许多生产计划与管理问题都可以归纳为最优化问题, 最优化模型是数学建模中应用最广泛的模型之一,其内容包括线性规划、整数线性规划、非线性规划、动态规划、变分法、最优控制等. 近几年来的全国大学生数学建模竞赛中，几乎每次都有一道题要用到此方法. 此类问题的一般形式为： min f (x),"— Presentation transcript:

1 3 最优化方法 许多生产计划与管理问题都可以归纳为最优化问题, 最优化模型是数学建模中应用最广泛的模型之一,其内容包括线性规划、整数线性规划、非线性规划、动态规划、变分法、最优控制等. 近几年来的全国大学生数学建模竞赛中，几乎每次都有一道题要用到此方法. 此类问题的一般形式为： min f (x), s.t. x∈. 目标函数 约束条件 可行解域

2 3.1 线性规划 A = (aij )m×n 线性规划是最优化方法中理论完整、方法成熟、应用广泛的一个重要分支 .
线性规划问题的数学模型是将实际问题转化为一组线性不等式或等式约束下求线性目标函数的最小(大)值问题, 它都可以化为如下标准(矩阵)形式： A = (aij )m×n c = (c1 , c2 , … , cn ) x≥0指x中的每一个分量xj ≥0

3 大M单纯形解法 不难将一般的线性规划问题化成如下标准形式： 大M单纯形解法是引入m个人工变量xn+1 , …, xn+m将原问题变为

4 线性规划问题主要解法是单纯形解法，一般用Lingo软件求解. 值得注意的是：在建立线性规划模型后求解时，尽量删除那些取值为零的变量.
大M单纯形解法中的M为足够大的正数, 起“惩罚”作用, 以便排除人工变量. 线性规划问题主要解法是单纯形解法，一般用Lingo软件求解. 值得注意的是：在建立线性规划模型后求解时，尽量删除那些取值为零的变量.

5 3.3 非线性规划 我们主要介绍无约束最优化问题：
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]. 如右图

6 给定下单峰区间 [a, b] 及控制误差＞0, 黄金分割法(0.618法)的迭代步骤：
①取 x2 = a (b - a), f2 = f (x2), 转向②. ②取 x1 = a (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 (b - a), f2= f (x2), 转向③.

7 下面我们再给出一个求初始区间的进退算法, 在所求出的区间上 f (x)是下单峰函数. 给定初始点x0和初始步长＞0, 进退算法的迭代步骤：
①取 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 ), 转向④.

8 f (xk + k pk ) = min {f (xk+pk) | ≥0}.
最速下降法 对于无约束最优化问题：min{ f (x)},这里的x = (x1 , x2 , …, xn)T.下面给出一个基于最速下降方向的算法,它是由柯西(Cauchy)在1847年提出的,是求无约束极值的最早的数值算法. 梯度 给定控制误差 ＞0和初始点xk (k = 0), 最速下降法的迭代步骤： ① 计算g(xk ). ② 若|| g (xk )||≤ , 则取x*= xk, 停；否则,令pk = - g(xk), 用一维搜索法求k , 使得 f (xk + k pk ) = min {f (xk+pk) | ≥0}. ③ 令xk+1 = xk+k pk , k = k + 1, 转向①.

9 最速下降法的优缺点 最速下降法的优点是具有整体收敛性, 计算量小, 初始点要求不高；缺点是整体收敛速度慢(所谓最速下降方向仅反映f (x)在xk 的局部性质). 最速下降法适用于寻优过程的前期迭代,当接近极值点时,宜选用其它收敛快的算法如牛顿法(P74)、阻尼牛顿法(P75)、拟牛顿法(P75). 以下介绍拟牛顿法.

10 拟牛顿法 给定控制误差  ＞0和初始点xk 及初始矩阵Hk (k = 0, H0通常取单位阵), DFP(或BFGS)算法的迭代步骤：
① 计算g (xk ), 令p k = -Hk g(xk ), 由一维搜索求步长k , 使得 f (xk + k pk ) = min{ f (xk + pk ) | ≥0}. ② 令xk+1 = xk + k pk . 若|| g(xk+1 )||≤, 则取x*= xk+1, 停；否则令 sk = xk+1- xk , yk = g(xk+1) - g(xk), ③ 由DFP(或BFGS)公式(见P75)计算得Hk+1. 令k = k + 1, 转向①.

11 有约束最优化 有约束最优化问题的数学模型一般形式是 x∈E n; i∈{1, 2, … , k}; j∈{ k +1, 2, … , m};
这里仅给出两种解法. ⑴ 线性逼近法(P76) 线性逼近法的基本思想是将目标函数和约束函数近似为线性函数, 将有约束最优化问题转化为线性规划问题, 然后用单纯形法求解.

12 ⑵ 罚函数法 它将有约束最优化问题转化为求解无约束最优化问题： 其中M为足够大的正数, 起“惩罚”作用, 称之为罚因子, F(x, M )称为罚函数. 定理 对于某个确定的正数M, 若罚函数F(x, M )的最优解x* 满足有约束最优化问题的约束条件, 则x* 是该问题的最优解.

13 序列无约束最小化方法 罚函数法在理论上是可行的, 在实际计算中的缺点是罚因子M的取值难于把握, 太小起不到惩罚作用；太大则由于误差的影响会导致错误. 这些缺点, 可根据上述定理加以改进, 先取较小的正数M, 求出F(x, M )的最优解x* . 当x*不满足有约束最优化问题的约束条件时, 放大M (例如乘以10)重复进行, 直到x* 满足有约束最优化问题的约束条件时为止. 这种改进的方法称为序列无约束最小化方法(Sequential Unconstrained Minimization Technique), 简称SUMT法.