数学建模 非线性规划模型用MATLAB++LINGO

非线性规划 讲义大纲 : 1.非线性规划的定义和相关概念 . 2.常用的求解非线性规划的方法 . 3.MATLAB求解 非线性规划及例题 . 4.lingo求解 非线性规划及例题 . 5.练习 . 非现性规划的基本概念 定义 如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题 一般形式 : （ 1） 其中 ， 是定义在 En 上的实值函数，简记 : Xfm in .,.,2,1 0m;1 , 2 , . . . , 0. ljXhiXgtsji nTn ExxxX , 21 ji hgf ,1nj1ni1n E :h ,E :g ,E : EEEf 其它情况 : 求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式 定义 1 把满足问题（ 1）中条件的解 称为 可行解 （或可行点 ），所有可行点的集合称为 可行集 （或 可行域 ）记为 D即 问题 (1)可简记为 nji EXXhXgXD ,0,0|)( nEX XfDX min定义 2 对于问题 (1)，设 ，若存在 ,使得对一切 ，且 ，都有 ，则称 X*是 f(X)在 D上的局部极小值点 （ 局部最优解 ） 特别地当 时， 若 则称 X*是f(X)在 D上的 严格局部极小值点（严格局部最优解） DX * 0DX *XX*XX XfXf * XfXf *定义 3 对于问题 (1),设 ,对任意的 ,都有 则称 X*是 f(X)在 D上的 全局极小值点 （ 全局最优解 ） 特别地当 时，若 ，则称 X*是 f(X)在 D上的 严格全局极小值点（ 严格全局最优解 ） DX * DX XfXf *XX XfXf *返回 非线性规划的基本解法 SUTM外点法 SUTM内点法（障碍罚函数法） 1、罚函数法 2、 近似规划法 返回 罚函数法 罚函数法 基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解这类方法称为 序列无约束最小化方法 (Sequential Unconstrained Minization Technique) 简称为 SUMT法 其一为 SUMT外点法 ，其二为 SUMT内点法 )2( ,0m i n,1212 ljjmii XhMXgMXfMXT可设： )3( ,m i n 1 MXTnEX ）转化为无约束问题：将问题（其中 T(X,M)称为 罚函数 ， M称为 罚因子 ， 带 M的项称为 罚项 ， 这里的罚函数只对不满足约束条件的点实行惩罚：当 时，满足各 ，故罚项 =0，不受惩罚当 时，必有 的约束条件，故罚项 0，要受惩罚 XD 0,0 XhXg ii DX 00 XhXg ii 或SUTM外点法 )1( ., . . . ,2,1 0m;1 , 2 , . . . , 0. m i n ljXhiXgtsXfji对一般的非线性规划： 罚函数法的 缺点 是：每个近似最优解 Xk往往不是容许解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着 Mk的增大，可能导致错误 1、 任意给定初始点 X0，取 M11，给定允许误差 ，令 k=1； 2、 求无约束极值问题 的最优解，设为 Xk=X(Mk)，即 ； 3、 若存在 ，使 ，则取 MkM( )令 k=k+1返回（ 2），否则，停止迭代得最优解 . 计算时也可将收敛性判别准则 改为 . 0 MXTnEX ,min ),(,m i n kkEXMXTMXTn mii 1 ki Xg 10, 1 MM k 0,0m i n12 mii XgMkXX * ki XgSUTM外点法 (罚函数法 )的 迭代步骤 例题 .min x2 s.t. x=1 显然本问题的最优解为 x*=1 用 SMT外点法 : T(x,M)=x2+Mmin(0,x-1)2 = 求 minT(x,M).本题可由 T(x,M)=2x+2M(x-1)=0,解得 : x=M/(1+M),M趋于无穷 . 可知 x从小于 1趋于 1,罚函数从外部趋于最优解 . 2221x x Xx M x x X 当当 )1(, . . . ,2,10.m i n i mXgtsXfi考虑问题： 所有严格内点的集合。是可行域中，设集合 00 ,2,1,0| DmiXgXD i 11111, , l n ( , ) ( )1l n mmiii immiii iI X r I X r f X r g X I X r f X rgXr g X r rgX 构 造 障 碍 函 数： 或其 中 称 或 为 障 碍 项 ， 为 障 碍 因 子 ）（得值问题：）就转化为求一系列极这样问题（kkkDXrXrXI ,m i n10SUTM内点法（ 障碍函数法 ） 内点法的迭代步骤 (1) 给定允许误差 0 ，取 10,01 r ； ( 2 ) 求 出 约 束 集 合 D 的 一 个 内 点 00 DX ，令 1k ；( 3 ) 以 01 DX k 为 初 始 点 ， 求 解 kDXrXI ,m i n0， 其 中0DX 的 最 优 解 ， 设 为 0DrXX kk ；( 4 ) 检 验 是 否 满 足 mikiXgr1ln 或 miikXgr11，满足 ， 停 止 迭 代 ，kXX *；否则取kkrr 1，令 1 kk ，返回 (3 ）例题 .min x2 s.t. x=1 显然本问题的最优解为 x*=1 用 SMT内点法 : 罚函数 I(x,rk)=x2 rkln(x-1),求其最值 . 可见 ,x从大于 1趋于 1. , 2 0111, 0 , 12kkkkrI x r xxrx r x 解 得 令 得 近似规划法的基本思想 ： 将问题 (3)中的目标函数 和约束条件 近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题，再用单纯形法求解之，把其符合原始条件的最优解作为 (3)的解的近似 Xf ),1( 0 m ) ;1 ,. .,( 0 ljXhiXg ji 近似规划法 每得到一个近似解后，都从这点出发，重复以上步骤 这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解。 近似规划法的 算法步骤如下 ( 2 ) 在点kX 处 ， 将 Xf ， XhXgji, 按 泰 勒 级 数 展 开 并取 一 阶 近 似 ， 得 到 近 似 线 性 规 划 问 题 ： kTkkXXXfXfXf m i n miXXXgXgXgkTkikii,1 0 lXXXhXhXhkTkjkjj,1j 0 ；( 1 ) 给定初始可行点 112111 , nxxxX ，步长限制 njj ,11 ，步长缩小系数 1,0 ，允许误差 ，令 k = 1 ； 5) 判 断 精 度 ：若 njkj ,1 ，则 点1kX为 近 似 最 优 解 ；否则，令 njkjkj ,1 1 ， k = k + 1 ， 返 回 步 骤 ( 2 ) ( 3 ) 在 上 述 近 似 线 性 规 划 问 题 的 基 础 上 增 加 一 组 限 制 步 长 的 线性 约 束 条 件 因 为 线 性 近 似 通 常 只 在 展 开 点 附 近 近 似 程 度 较高 ，故 需 要 对 变 量 的 取 值 范 围 加 以 限 制 ，所 增 加 的 约 束 条 件 是 ： njxxkjkjj,1 求 解 该 线 性 规 划 问 题 ， 得 到 最 优 解1kX ；( 4 ) 检验 1kX 点 对 原 约 束 是 否 可 行 。 若 1kX 对 原 约 束 可 行 ，则转步骤 ( 5 ) ；否 则 ，缩 小 步 长 限 制 ，令 njkjkj ,1 ，返回步骤 ( 3 ) ， 重 解 当 前 的 线 性 规 划 问 题 ；返回 例题 1、用近似规划法求解下列问题。 12221 1 2222 1 2121m i n 2 1. . 2 5 0700 5 , 0 1 03 , 2 . 5 , 2 , 1 , 0 . 5TTf x x xs t g x x xg x x xxx 1初 始 点 ： x解：第一次迭代：在点 x1处将 g1(x), g2(x)线性化。 1 1 11 1 11212369 . 7 52 . 554 0 . 2 5 6 5 0 2TTg x g x g x x xxxxx 1 1 12 2 21212364 . 7 52 . 559 . 2 5 6 5 0 3TTg x g x g x x xxxxx 步长限制： 111122, 2 3 2 1 51 2 . 5 1 1 . 5 3 . 5 4x x x xxx 即2 114 , 36 2 0Tx 解（ 1）（ 2）（ 3）（ 4），得 ， 检验，可得 x2不满足原始约束。 第二次迭代，减少 2111221 , 0 . 51 3 1 2 450 . 5 2 . 5 0 . 5 2 3Txxxx 解（ 1,2,3,5)，得 x2=(4,3)T,f(x2)= -11.所以 x2为最小值点 . 用 MATLAB软件求解 ,其 输入格式 如下 : 1. x=quadprog(H,C,A,b); 2. x=quadprog(H,C,A,b,Aeq,beq); 3. x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB); 4. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0); 5. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0,options); 6. x,fval=quaprog(.); 7. x,fval,exitflag=quaprog(.); 8. x,fval,exitflag,output=quaprog(.); 1、二次规划 标准型为： M i n Z = 21XTH X + cTX s . t . A X =0时，返回不超过 x的最大整数；当 x=100; x1*r21+x2*r22+x3*r23=100; x1*r31+x2*r32+x3*r33=100; x1*r41+x2*r42+x3*r43=70; x1+x2+x3=105; x1+x2+x3=5.9; 2.9*r12+2.1*r22+1.5*r32+1.8*r42=5.9; 2.9*r13+2.1*r23+1.5*r33+1.8*r43=5.9; 2.9*r11+2.1*r21+1.5*r31+1.8*r41=x2;x2=x3; gin(x1);gin(x2);gin(x3); gin(r11);gin(r21);gin(r31);gin(r41); gin(r12);gin(r22);gin(r32);gin(r42); gin(r13);gin(r23);gin(r33);gin(r43); end 运行结果如下： Feasible solution found at iteration: 26565 Model Title: 钢管下料； Variable Value X1 72.00000 R11 1.000000 X2 29.00000 R12 0.000000 X3 14.00000 R13 2.000000 R21 1.000000 R22 1.000000 R23 0.000000 R31 0.000000 R32 3.000000 R33 1.000000 R41 1.000000 R42 0.000000 R43 0.000000 Lingo源程序二 model: Title 钢管下料 - 最小化钢管根数的 LINGO模型 ; SETS: NEEDS/1.4/:LENGTH,NUM; ! 定义基本集合 NEEDS及其属性 LENGTH,NUM; CUTS/1.3/:X; ! 定义基本集合 CUTS及其属性 X; PATTERNS(NEEDS,CUTS):R; ! 定义派生集合 PATTERNS（这是一个稠密集合）及其属性 R; ENDSETS DATA: LENGTH=2.9 2.1 1.5 1.8; NUM=100 100 100 70; CAPACITY=7.4; ENDDATA min=SUM(CUTS(I): X(I) ); !目标函数 ; Lingo源程序二 FOR(NEEDS(I): SUM(CUTS(J): X(J)*R(I,J) ) NUM(I) ); !满足需求约束 ; FOR(CUTS(J): SUM(NEEDS(I): LENGTH(I)*R(I,J) ) CAPACITY -MIN(NEEDS(I):LENGTH(I) ); !合理切割模式约束 ; SUM(CUTS(I): X(I) ) 105; SUM(CUTS(I): X(I) ) X(I+1) ); !人为增加约束 ; FOR(CUTS(J): GIN(X(J) ) ; FOR(PATTERNS(I,J): GIN(R(I,J) ); end 运行结果如下： Local optimal solution found at iteration: 64408 Objective value: 113.0000 Model Title: 钢管下料 - 最小化钢管根数的 LINGO模型 Variable Value Reduced Cost CAPACITY 7.400000 0.000000 LENGTH( 1) 2.900000 0.000000 LENGTH( 2) 2.100000 0.000000 LENGTH( 3) 1.500000 0.000000 LENGTH( 4) 1.800000 0.000000 NUM( 1) 100.0000 0.000000 NUM( 2) 100.0000 0.000000 NUM( 3) 100.0000 0.000000 NUM( 4) 70.00000 0.000000 X( 1) 50.00000 1.000000 X( 2) 37.00000 1.000000 X( 3) 26.00000 1.000000 运行结果如下： R( 1, 1) 1.000000 0.000000 R( 1, 2) 0.000000 0.000000 R