河北女子职业技术学院：《数学建模与数学实验》课程教学资源（PPT课件讲稿）非线性规划

教学建模与数学奥验 非线性规擷 河北女子职业技术学院数学教硏室

1 数学建模与数学实验 河北女子职业技术学院数学教研室 非线性规划

实验目的 1、直观了解非线性规划的基本内容。 2、掌握用数学软件求解优化问题。 实验内容 1、非线性规划的基本理论。 2、用数学软件求解非线性规划。 3、钢管讧购及运输优化模型 4、实验作业

2 实验目的 实验内容 2、掌握用数学软件求解优化问题。 1、直观了解非线性规划的基本内容。 1、非线性规划的基本理论。 4、实验作业。 2、用数学软件求解非线性规划。 3、钢管订购及运输优化模型

非线性规划 非线性规划的基本概念 非线性规划的基本解法

3 *非线性规划的基本解法 非线性规划的基本概念 非线性规划 返回

非现性规划的基本概念 定义如果目标函数或约束条件中至少有一个是非线性函数 时的最优化问题就叫做非线性规划问题 一般形式: minf(r) 2)(4)≥07=12…m (x)=0j=12 其中X=(x1,12…,xn)∈E,f81,h;是定义在P上的实值函 数,简记:f:F→E,g;:En→E E1→)E 其它情况:求目标函数的最大值或约束条件为小于等于零 的情况,都可通过取其相反数化为上述一般形式

4 定义 如果目标函数或约束条件中至少有一个是非线性函数 时的最优化问题就叫做非线性规划问题． 非现性规划的基本概念 一般形式: （1） 其中 ， 是定义在 E n 上的实值函 数，简记: min f (X ) ( )  ( )     = =  = 0 1,2,..., . 0 1,2,...,m; . . h X j l g X i st j i ( ) T n X = x1 , x2 ,, xn  E gi hj f , , n 1 j n 1 i n 1 f : E → E , g : E → E , h : E → E 其它情况: 求目标函数的最大值或约束条件为小于等于零 的情况，都可通过取其相反数化为上述一般形式．

定义1把满足问题(1)中条件的解X(∈E")称为可行解(或可行 点),所有可行点的集合称为可行集(或可行域).记为D.即 D={x18(x)20(x)=0,X∈Ey)间题(1)可简记为m( 定义2对于问题(1),设X∈D若存在δ>0,使得对一切 X∈D且|x-x|<,都有/x)(x)则称X是()在D上的 局部极小值点(局部最优解).特别地当x≠x时,若x)kx) 则称X*是f(X)在D上的严格局部极小值点(严格局部最优解) 定义3对于问题(,设x∈D,对任意的x∈D,都有rx)(x) 则称X是f(X在D上的全局极小值点(全局最优解).特别地当 x≠Xx时,若Ax)(x),则称X是r在D上的严格全局极小值点 (严格全局最优解)

5 定义1 把满足问题（1）中条件的解 称为可行解（或可行 点），所有可行点的集合称为可行集（或可行域）．记为D．即 D = X | gi (X )  0, hj (X ) = 0, X  E n  问题(1)可简记为 ． ( ) n X  E f (X ) XD min 定义2 对于问题(1)，设 ，若存在 ,使得对一切 ，且 ，都有 ，则称X *是f(X)在D上的 局部极小值点（局部最优解）．特别地当 时，若 ， 则称X *是f(X)在D上的严格局部极小值点（严格局部最优解）． X  D *   0 X D −   * X X * X  X f(X )  f (X ) * f(X )  f (X ) * 定义3 对于问题(1),设 ,对任意的 ,都有 则称X *是f(X)在D上的全局极小值点（全局最优解）．特别地当 时，若 ，则称X *是f(X)在D上的严格全局极小值点 （严格全局最优解）． X  D * X D f(X )  f (X ) * * X  X f(X )  f (X ) * 返回

非线性规划的基本解法 SUTM外点法 1、罚函数法 SUTM内点法(障碍罚函数法) 2、近似规划法

6 非线性规划的基本解法 SUTM外点法 SUTM内点法（障碍罚函数法） 1、罚函数法 2、近似规划法 返回

罚函数法 罚函数法基本思想是通过构造罚函数把 约束问题转化为一系列无约束最优化问题, 进而用无约束最优化方法去求解.这类方法 称为序列无约束最小化方法.简称为SUMT 法 其一为SUM外点法,其二为SUMT内点 法

7 罚函数法 罚函数法基本思想是通过构造罚函数把 约束问题转化为一系列无约束最优化问题， 进而用无约束最优化方法去求解．这类方法 称为序列无约束最小化方法．简称为SUMT 法． 其一为SUMT外点法，其二为SUMT内点 法．

SUTM外点法 对一般的非线性规划:minf(X) X)≥0 31b1(x)=0=12 可设:7(x,M0)=(x)+M∑m(g(x)+M∑b(x)(2) 将问题①转化为无约束问题:min7(X,M X∈E 其中T(X,M)称为罚函数,M称为罚因子,带M的项称为罚项,这 里的罚函数只对不满足约束条件的点实行惩罚:X∈D时,满 足g/(x)≥0h(x)=0,故罚项0,不受惩罚.XgD时, g(X)0,要受惩罚 8

8 ( , ) ( ) min (0, ( ))  ( ) (2) 1 2 1 2   = = = + + l j j m i 可设：T X M f X M gi X M h X 1 min T(X,M ) (3) n XE 将问题（）转化为无约束问题： 其中T(X,M)称为罚函数，M称为罚因子，带M的项称为罚项，这 里的罚函数只对不满足约束条件的点实行惩罚：当 时，满 足各 ，故罚项=0，不受惩罚．当 时， 必有 的约束条件，故罚项>0，要受惩罚． X D gi (X)  0,hi (X) = 0 X  D gi (X )  0或hi (X )  0 SUTM外点法 ( ) ( ) ( ) (1) 0 1,2,..., . 0 1,2,..., m; . . min    = =  = h X j l g X i st f X j i 对一般的非线性规划：

SUTM外点法(罚函数法)的迭代步骤 1、任意给定初始点X,取M1>1,给定允许误差E>0,令k=1 2、求无约束极值问题mn7(x,MO)的最优解,设为X=X(M),即 minT(X, M)=T(XR, Mk X∈En 3、若存在≤1≤m),使-8(x)>,则取M2M(=aMa=10 令kk+1返回(2),否则,停止迭代.得最优解x*≈xk 计算时也可将收敛性判别准则-8()>改为Mm)0 罚函数法的缺点是:每个近似最优解X往往不是容许解, 而只能近似满足约束,在实际问题中这种结果可能不能使用; 在解一系列无约束问题中,计算量太大,特别是随着M的增大, 可能导致错误

9 罚函数法的缺点是：每个近似最优解X k往往不是容许解， 而只能近似满足约束，在实际问题中这种结果可能不能使用； 在解一系列无约束问题中，计算量太大，特别是随着Mk的增大， 可能导致错误． 1、任意给定初始点X 0，取M1>1，给定允许误差 ，令k=1； 2、求无约束极值问题 的最优解，设为X k=X(Mk)，即 ； 3、若存在 ，使 ，则取Mk>M( ) 令k=k+1返回（2），否则，停止迭代．得最优解 . 计算时也可将收敛性判别准则 改为 .   0 T(X M ) n X E min ,  min ( , ) ( , ) k k X E T X M T X M n =  i(1  i  m) − ( )   k gi X Mk+1 = M, =10 min(0, ( )) 0 1 2   = m i M gi X k X  X * − ( )   k gi X SUTM外点法(罚函数法)的迭代步骤

SUTM内点法(障碍函数法) 考虑问题 min st )≥0i=12.…,m 设集合D={Xg,(x)>0,i=12…,m}≠,D是可行域中 所有严格内点的集合。 构造障碍函数 (X,(x,)=f(X)+r∑ng(x)或(X)=f(X)+r∑ i=1 g 其中称∑hg(x)或∑。为障碍项,r为障碍因子 这样问题(1)就转化为求一系列极值问题: minl(Xx,)得X( X∈D

10 ( ) ( ) (1) . . 0 1,2,..., min i    st g X  = m f X i 考虑问题：  ( )  所有严格内点的集合。 设集合D 0 = X | gi X  0,i =1,2,,m  ，D 0 是可行域中 ( ) ( ) ( ) ( ) ( ) ( ) ( ) 其中称 或 为障碍项， 为障碍因子 ： 或 构造障碍函数 r g X r g X r g X I X r I X r f X r g X I X r f X r m i i m i i m i i m i i     = = = = = + = + 1 1 1 1 1 ln 1 , , ln ( , ) ( ) ( ) 得 （ ） 这样问题（）就转化为求一系列极 值问题： k k k X D I X r X r min , 1 0  SUTM内点法（障碍函数法）