数建模与教堂奥验 非线性规
数学建模与数学实验 非线性规划
实验目的 1.直观了解非线性规划的基本内容 2.掌握用数学软件求解优化问题 实验内容 1.非线性规划的基本理论, 2,用数学软件求解非线性规划 3.钢管讧购及运输优化模型 4.实验作业
实验目的 实验内容 2． 掌握用数学软件求解优化问题． 1． 直观了解非线性规划的基本内容． 1．非线性规划的基本理论． 4．实验作业． 2． 用数学软件求解非线性规划． 3． 钢管订购及运输优化模型．
非线性规划 非线性规划的基本概念 六非线性规划的基本解法 返回
*非线性规划的基本解法 非线性规划的基本概念 非线性规划 返回
非现性规划的基本概念 定义如果目标函数或约束条件中至少有一个是非线性函数, 则最优化问题就叫做非线性规划问题. 般形式: min f(r) g(x)≥0t 12 S t 12(x)=0=12 其中X=(x,x2,xy∈R",f81,h;是定义在R上的实值函 数,简记:f:R2→R,g1:R→R,h;:R1→R 其它情况:求目标函数的最大值,或约束条件小于等于零 两种情况,都可通过取其相反数化为上述一般形式
定义 如果目标函数或约束条件中至少有一个是非线性函数, 则最优化问题就叫做非线性规划问题． 非现性规划的基本概念 一般形式: （1） 其中 ， 是定义在 R n 上的实值函 数，简记: min f (X ) gi hj f , , 其它情况: 求目标函数的最大值，或约束条件小于等于零 两种情况，都可通过取其相反数化为上述一般形式． n 1 j n 1 i n 1 f : R → R , g : R → R , h : R → R ( ) T n X = x1 , x2 ,L, xn R ( ) ( ) = = = 0 1,2,..., . 0 1,2,..., m; . . h X j l g X i st j i
定义1把满足问题(1)中条件的解ⅹ(R")称为可行解(或可行 点),所有可行点的集合称为可行集(或可行域).记为D.即 D={x1g;(x)≥0,h,(x)=0,X∈R了问题()可简记为m/(x 定义2对于问题(1),设ⅹ*∈D,若存在δ>0,使得对一切 X∈D,且|x=x1|<6,都有A)(x),则称X是在D上的 局部极小值息(同部最优解).特别地,当x≠X*时,若 (x)k(x),则称X是(X)在D上的严格局部极小值点(严格局部最 优解) 定义3对于间题(1),设x∈D,若对任意的x∈D,都有(x)(), 则称γ是fX)在D上的全局极小值点(全局最优解).特别地,当 x≠x时,若(x)</(x),则称x是(X在D上的严格全局极小值 点(严格全局最优解) 返回
定义1 把满足问题（1）中条件的解 称为可行解（或可行 点），所有可行点的集合称为可行集（或可行域）．记为D．即 问题(1)可简记为 f (X )． XD 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 * X X f(X ) f (X ) * 返回 ( ) n X R D = {X| gi (X ) 0, hj (X )= 0, X R n} ( ) (X ), f X f *
非线性规划的基本解法 SUTM外点法 1.罚函数法 SUTM内点法(障碍罚函数法) 2,近似规划法 返回
非线性规划的基本解法 SUTM外点法 SUTM内点法（障碍罚函数法） 1． 罚函数法 2． 近似规划法 返回
罚函数法 罚函数法基本思想是通过构造罚函数把 约束问题转化为一系列无约束最优化问题, 进而用无约東最优化方法去求解.这类方法 称为序列无约束最小化方法.简称为SUMT 法 其一为SUMT外点法,其二为SUMT内点 法
罚函数法 罚函数法基本思想是通过构造罚函数把 约束问题转化为一系列无约束最优化问题， 进而用无约束最优化方法去求解．这类方法 称为序列无约束最小化方法．简称为SUMT 法． 其一为SUMT外点法，其二为SUMT内点 法．
SUTM外点法 对一般的非线性规划:minf(X) 8(X)≥0i=1,2 s t (1) X)=0 可设:(x,M)=/(x)+M∑min(g:(x)+M∑b(x)(2) i=1 将问题①)转化为无约束问题:minr(X,M) (3) 其中T(X,M称为罚函数,M称为罚因子,带M的项称为罚项, 这里的罚函数只对不满足约束条件的点实行惩罚:ⅹ∈D时,满足 各g;(X)≥02(x)=0,故罚项为0,不受惩罚.当X∈D时,必 有约束条件s(X)<0或h(X)≠0,故罚项大于0,要受惩罚
( , ) ( ) min (0, ( )) ( ) (2) 1 2 1 2 = = = + + l j j m i 可设：T X M f X M gi X M h X ( ) R 1 min , (3) n X T X M 将问题（）转化为无约束问题： 其中T(X,M)称为罚函数，M称为罚因子，带M的项称为罚项， 这里的罚函数只对不满足约束条件的点实行惩罚:当 时，满足 各 ，故罚项为0，不受惩罚．当 时,必 有约束条件 ，故罚项大于0，要受惩罚． X D gi (X) 0,hi (X) = 0 X D gi (X ) 0或hi (X ) 0 SUTM外点法 ( ) ( ) ( ) min 0 1,2,..., ; s.t. (1) 0 1,2,..., . i j f X g X i m h X j l = = = 对一般的非线性规划：
SUTM外点法(罚函数法)的迭代步骤 1.任意给定初始点Y,取M1>1,给定允许误差>0,令k=1; 2.求无约束极值问题minT(X,M)的最优解,设X=x(M),即 n minT(X, M=T(Xk ); X∈R 3.若存在和≤1≤m,使一g(x)>2则取MMM1=aAMa=0), 令k=k+1返回(2),否则,停止迭代.得最优解x*≈xk 计算时也可将收敛性判别准则-s(k)改为M∑m0g(xP0 罚函数法的缺点:每个近似最优解κ往往不是容许解,而 只能近似满足约束,在实际问题中这种结果可能不能使用;在 解一系列无约束问题中,计算量太大,特别是随着M的增大 可能导致错误
罚函数法的缺点：每个近似最优解X k往往不是容许解，而 只能近似满足约束，在实际问题中这种结果可能不能使用；在 解一系列无约束问题中，计算量太大，特别是随着Mk的增大， 可能导致错误． 1．任意给定初始点 X 0，取M1>1，给定允许误差 ，令k=1； 2．求无约束极值问题 的最优解，设X k=X(Mk)，即 ； 3．若存在 ，使 ,则取Mk>M( ), 令k=k+1返回（2），否则，停止迭代．得最优解 ． 计算时也可将收敛性判别准则 改为 ． 0 ( ) R min , n X T X M ( ) R min , ( , ) n k k X T X M T X M = 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内点法(障碍函数法) minf(X) 考虑问题: (X)≥0i=1 设集合D=(X1g(x)>0.1=12…,m}≠D是 可行域中所有严格内点的集合 构造障碍函数 1(x,r):1(x,r)=f(x)+lns()或1(x,n)=f(x)+∑ g,(x) 其中称ng:(x)或r∑、为障碍项,r为障碍因子 这样问题(1)就转化为求一系列极值问题: min(X,r)得X(r) X∈D
( ) ( ) min (1) s.t. 0 1, 2,..., i f X g X i m = 考虑问题： { ( ) } 0 0 | 0, 1, 2, , D X g X i m D i 设集合 = = ， 是 可行域中所有严格内点的集合. ( ) 0 1 min , k k k X D I X r X r 这样问题（）就转化为求一系列极值问题： 得 （ ）. SUTM内点法（障碍函数法） ( ) ( ) ( ) ( ) ( ) ( ) ( ) 其中称 或 为障碍项， 为障碍因子. ： 或 构造障碍函数 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 ( , ) ( )