【数学建模】第6讲_非线性规划模型.ppt

《【数学建模】第6讲_非线性规划模型.ppt》由会员分享，可在线阅读，更多相关《【数学建模】第6讲_非线性规划模型.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学建模数学建模非线性规划模型非线性规划模型 1.1.非线性规划的基本理论非线性规划的基本理论4.4.实验作业实验作业2.用数学软件求解非线性规划用数学软件求解非线性规划3 . 供应与选址以及生产安排计划供应与选址以及生产安排计划 问题问题 *非线性规划的基本解法非线性规划的基本解法非线性规划的基本概念非线性规划的基本概念非线性规划非线性规划 返回返回 定义定义 如果目标函数或约束条件中至少有一个是非线性函数,则最优化问题就叫做非线性规划问题非线性规划问题非现性规划的基本概念非现性规划的基本概念 一般形式一般形式: （1） 其中 ， 是定义在 R Rn 上的实值函数，简记: Xfmin jih

2、gf, 其它情况其它情况: 求目标函数的最大值，或约束条件小于等于零两种情况，都可通过取其相反数化为上述一般形式1nj1ni1nR :h ,R :g ,R :RRRfnTnRxxxX=,21L =.,.,2 , 1 0 m;1,2,., 0. . ljXhiXgtsji 定义定义1 1 把满足问题（1）中条件的解 称为可行解可行解（或可行（或可行点点），），所有可行点的集合称为可行集可行集（或（或可行域可行域）记为D即 问题(1)可简记为 XfDXmin定义定义2 2 对于问题(1),设 ,若存在 ,使得对一切 ,且 ,都有 ,则称X*是f(X)在D上的局部极小值点局部极小值点（局部最优解局部

3、最优解）特别地,当 时，若 ,则称X*是f(X)在D上的严格局部极小值点严格局部极小值点（严格局部最严格局部最优解优解）DX *0DX *XX*XX XfXf* XfXf*定义定义3 3 对于问题(1),设 ,若对任意的 ,都有则称X*是f(X)在D上的全局极小值点全局极小值点（全局最优解全局最优解）特别地,当 时，若 ,则称X*是f(X)在D上的严格全局极小值严格全局极小值点点（严格全局最优解严格全局最优解）DX *DX *XX XfXf* 返回返回)(nRX njiRXXhXg XD = =, 0, 0| ,Xf Xf *非线性规划的基本解法非线性规划的基本解法SUTM外点法外点法SUTM

4、内点法（障碍罚函数法）内点法（障碍罚函数法）1 罚函数法罚函数法2 近似规划法近似规划法 返回返回 罚函数法罚函数法 罚函数法罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解这类方法称为序列无约束最小化方法序列无约束最小化方法简称为SUMTSUMT法法 其一为SUMTSUMT外点法外点法，其二为SUMTSUMT内点内点法法 )2( , 0min,1212=ljjmiiXhMXgMXfMXT可设：R1 min, (3)nXT X M将问题（）转化为无约束问题： 其中T(X,M)称为罚函数罚函数，M称为罚因子罚因子，带M的项称为罚项罚项，这里的罚

5、函数只对不满足约束条件的点实行惩罚:当 时，满足各 ，故罚项为0，不受惩罚当 时,必有约束条件 ，故罚项大于0，要受惩罚DX 0, 0=XhXgiiDX 00XhXgii或SUTMSUTM外点法外点法 min0 1,2,., ; s.t. (1)0 1,2,., .ijfXgXimhXjl=对一般的非线性规划： 罚函数法的缺点缺点：每个近似最优解Xk往往不是容许解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着Mk的增大，可能导致错误1任意给定初始点 X0，取M11，给定允许误差 ，令k=1；2求无约束极值问题 的最优解，设Xk=X(Mk)

6、，即 ；3若存在 ，使 ,则取MkM( ),令k=k+1返回（2），否则，停止迭代得最优解 计算时也可将收敛性判别准则 改为 0Rmin,nXT X MRmin,(,)nkkXT X MT XM=mii1kiXg10, 1=MMk 0, 0min12=miiXgMkXX*kiXg SUTM SUTM外点法外点法(罚函数法)的迭代步骤迭代步骤min (1)s.t. 0 1,2,.,ifXgXim=考虑问题：00|0,1,2, iDXgXimD=L设集合，是可行域中所有严格内点的集合.0 1min, kkkXDIX rXr这样问题（）就转化为求一系列极值问题：得（ ）.SUTMSUTM内点法（内点

7、法（障碍函数法） 为障碍因子.为障碍项，或其中称或 ：构造障碍函数rXgrXgrXgrXfrXIXgrXfrXIrXImiimiimiimii=11111 ln1)(),( ln, 内点法的迭代步骤内点法的迭代步骤(1) 给定允许误差0，取10 , 01r； 近似规划法的基本思想近似规划法的基本思想：将问题(3)中的目标函数 和约束条件 近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题，再用单纯形法求解之，把其符合原始条件的最优解作为(3)的解的近似Xf0 (1,., ); 0 (1, )ijgXimhXjl= L近似规划法近似规划法每得到一个近似解，都从这点出发，重复

8、以上步骤 这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解 近似规划法的算法步骤如下：算法步骤如下：(3)在上述近似线性规划问题的基础上增加一组限制步长的线性约束条件因为线性近似通常只在展开点附近近似程度较高，故需要对变量的取值范围加以限制， 所增加的约束条件是： njxxkjkjj, 1 L= 求解该线性规划问题，得到最优解1kX； 返回返回 用MATLAB软件求解,其输入格式输入格式如下: 1x=quadprog(H,C,A,b); 2x=quadprog(H,C,A,b,Aeq,beq); 3x=quadprog(H,

9、C,A,b,Aeq,beq,VLB,VUB); 4x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0); 5x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB,X0,options); 6x,fval=quaprog(); 7x,fval,exitflag=quaprog(); 8x,fval,exitflag,output=quaprog();1二次规划二次规划例例1 1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x22 -x1+2x22 x10, x20 1写成标准形式写成标准形式： 2输入命令输

10、入命令： H=2 -2; -2 4; c=-2 ;-6;A=1 1; -1 2;b=2;2; Aeq=;beq=; VLB=0;0;VUB=; x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB)3运算结果运算结果为： x =08 1.2， z = -7.2T111222 2 -221min( , )2 462xxzx xxx = 1212 1 121 2200 xxxxs.t. 1 首先建立M文件fun.m,用来定义目标函数F（X）:function f=fun(X);f=F(X);2一般非线性规划一般非线性规划 其中X为n维变元向量，G(X)与Ceq(X)均为非线性函

11、数组成的向量，其他变量的含义与线性规划、二次规划中相同用MATLAB求解上述问题，基本步骤分三步：3 建立主程序.求解非线性规划的函数是fmincon,命令的基本格式如下： (1) x=fmincon(fun,X0,A,b) (2) x=fmincon(fun,X0,A,b,Aeq,beq) (3) x=fmincon(fun,X0,A,b, Aeq,beq,VLB,VUB) (4) x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon)(5)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon,options) (6)

12、x,fval= fmincon() (7) x,fval,exitflag= fmincon() (8)x,fval,exitflag,output= fmincon()输出极值点M文件迭代的初值参数说明变量上下限1写成标准形式写成标准形式： s.t. 00546322121xxxx2100 xx22212121212minxxxxf=22212121212minxxxxf= 2x1+3x2 6 s.t. x1+4x2 5 x1,x2 0例例22先建立先建立M-文件文件 fun3m: function f=fun3(x); f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(

13、2)23再建立主程序youh2m： x0=1;1; A=2 3 ;1 4; b=6;5; Aeq=;beq=; VLB=0;0; VUB=; x,fval=fmincon(fun3,x0,A,b,Aeq,beq,VLB,VUB)4运算结果为：运算结果为： x = 07647 10588 fval = -202941 1先建立先建立M文件文件fun4m定义目标函数定义目标函数: function f=fun4(x); f=exp(x(1) *(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);12212122( )e (42421)xf xxxx xx= x1+x2=0

14、 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0例例3 2再建立再建立M文件文件myconm定义非线性约束：定义非线性约束： function g,ceq=mycon(x) g=15+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10; ceq=;3主程序主程序youh3m为为:x0=-1;1;A=;b=;Aeq=1 1;beq=0;vlb=;vub=;x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb, vub,mycon)4 运算结果为运算结果为： x = -12250 12250 fval = 18951 例4 1222

15、1122221212 min2s.t. 250 70 05, 010fXxxgXxxgXxxxx= =1先建立先建立M文件文件funm定义目标函数定义目标函数: function f=fun(x); f=-2*x(1)-x(2);2再建立再建立M文件文件mycon2m定义非线性约束：定义非线性约束：function g,ceq=mycon2(x) g=x(1)2+x(2)2-25;x(1)2-x(2)2-7; ceq=;3 主程序主程序fxxm为为: x0=3;25; VLB=0 0;VUB=5 10; x,fval,exitflag,output =fmincon(fun,x0, VLB,V

16、UB,mycon2)4 运算结果为运算结果为: x = 40000 30000fval =-110000exitflag = 1output = iterations: 4 funcCount: 17 stepsize: 1 algorithm: 1x44 char firstorderopt: cgiterations: 返回返回应用实例：应用实例： 供应与选址供应与选址 某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：km）及水泥日用量d(t)由下表给出目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20t假设从料场到工地之间均有直线道路相连 （1

17、）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少水泥，可使总的吨千米数最小 （2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20t，问应建在何处，节省的吨千米数有多大？（一）建立模型（一）建立模型 记工地的位置为(ai，bi)，水泥日用量为di，i=1,6;料场位置为(xj，yj)，日储量为ej，j=1,2；料场j向工地i的运送量为Xij当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：Xij，xj，yj（二）使用临时料场的情形（二）使用临时料场的情形 使用两个临时料场A(5,1)，B(2,7)求从料场j向工地i的运送量Xij . 在各工地用

18、量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题 线性规划模型为：=2161),(minjiijXjiaaf2 , 1 , 6 , 2 , 1 , s.t.6121=jeXidXjiijijijL设 X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6X12= X 7, X22= X 8, X32= X 9, X42= X 10, X52= X 11, X62= X 12 编写程序gying1m计算结果为：计算结果为：x = 30000 50000 00000 70000 00000 10000 00

19、000 00000 40000 00000 60000 100000fval = 1362275（三）改建两个新料场的情形（三）改建两个新料场的情形 改建两个新料场，要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小这是非线性规划问题非线性规划模型为：设 X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6 X12= X 7, X22= X 8, X32= X 9, X42= X 10, X52= X 11, X62= X 12 x1=X13, y1=X14, x2=X15, y2=X16 （1）先编写M文

20、件liaochm定义目标函数MATLAB（liaoch）(2) 取初值为线性规划的计算结果及临时料场的坐标: x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;编写主程序gying2mMATLAB（gying2）(3) 计算结果为：x= 30000 50000 00707 70000 0 09293 0 0 39293 0 60000 100707 63875 43943 57511 71867fval = 1054626exitflag = 1(4) 若修改主程序gying2m, 取初值为上面的计算结果:x0= 30000 50000 00707 70000 0 092

21、93 0 0 39293 0 60000 100707 63875 43943 57511 71867 则得结果为:x=30000 50000 03094 70000 00108 06798 0 0 36906 0 59892 103202 55369 49194 58291 72852fval =1034760exitflag = 1总的吨千米数比上面结果略优 (5) 若再取刚得出的结果为初值, 却计算不出最优解(6) 若取初值为: x0=3 5 4 7 1 0 0 0 0 0 5 11 56348 48687 72479 77499, 则计算结果为:x=30000 50000 40000

22、70000 10000 0 0 0 0 0 50000 110000 56959 49285 72500 77500fval =898835exitflag = 1总的吨千米数898835比上面结果更好 通过此例可看出fmincon函数在选取初值上的重要性 返回返回 某厂向用户提供发动机，合同规定，第一、二、某厂向用户提供发动机，合同规定，第一、二、三季度末分别交货三季度末分别交货40台、台、60台、台、80台每季度的生台每季度的生产费用为产费用为 （单位（单位:元）元）, 其中其中x是该季度生是该季度生产的台数若交货后有剩余，可用于下季度交货，产的台数若交货后有剩余，可用于下季度交货，但需支付存储费，每台每季度但需支付存储费，每台每季度c元已知工厂每季度元已知工厂每季度最大生产能力为最大生产能力为100台，第一季度开始时无存货，设台，第一季度开始时无存货，设a=50、b=0.2、c=4，问，问:工厂应如何安排生产计划，工厂应如何安排生产计划，才能既满足合同又使总费用最低讨论才能既满足合同又使总费用最低讨论a、b、c变化变化对计划的影响，并作出合理的解释对计划的影响，并作出合理的解释 2bxaxxf=生产计划安排问题生产计划安排问题练习练习 返回返回