数学建模与数学实验：第6讲 非线性规划

《数学建模与数学实验：第6讲 非线性规划》由会员分享，可在线阅读，更多相关《数学建模与数学实验：第6讲 非线性规划（44页珍藏版）》请在装配图网上搜索。

1、1数学建模与数学实验数学建模与数学实验后勤工程学院数学教研室非线性规划非线性规划 2实验目的实验目的实验内容实验内容2、掌握用数学软件求解优化问题。、掌握用数学软件求解优化问题。1、直观了解非线性规划的基本内容。、直观了解非线性规划的基本内容。1 1、非线性规划的基本理论。、非线性规划的基本理论。4 4、实验作业。、实验作业。2、用数学软件求解非线性规划。、用数学软件求解非线性规划。3、钢管订购及运输优化模型、钢管订购及运输优化模型3*非线性规划的基本解法非线性规划的基本解法非线性规划的基本概念非线性规划的基本概念非线性规划非线性规划 返回返回4 定义定义 如果目标函数或约束条件中至少有一个是

2、非线性函数时的最优化问题就叫做非线性规划问题非线性规划问题非现性规划的基本概念非现性规划的基本概念 一般形式一般形式:（1）其中 ，是定义在 En 上的实值函数，简记:Xfmin .,.,2,1 0 m;1,2,.,0.ljXhiXgtsjinTnExxxX,21jihgf,1nj1ni1nE :h ,E :g ,E :EEEf 其它情况其它情况:求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式5 定义定义1 1 把满足问题（1）中条件的解 称为可行解可行解（或可行（或可行点点），），所有可行点的集合称为可行集可行集（或（或可行域可行域）记为D即 问题(1)可

3、简记为 njiEXXhXgXD,0,0|)(nEX XfDXmin定义定义2 2 对于问题(1)，设 ，若存在 ,使得对一切 ，且 ，都有 ，则称X*是f(X)在D上的局部极小值点局部极小值点（局部最优解局部最优解）特别地当 时，若 ，则称X*是f(X)在D上的严格局部极小值点严格局部极小值点（严格局部最优解严格局部最优解）DX*0DX*XX*XX XfXf*XfXf*定义定义3 3 对于问题(1),设 ,对任意的 ,都有 则称X*是f(X)在D上的全局极小值点全局极小值点（全局最优解全局最优解）特别地当 时，若 ，则称X*是f(X)在D上的严格全局极小值点严格全局极小值点（严格全局最优解严格

4、全局最优解）DX*DX XfXf*XX XfXf*返回返回6非线性规划的基本解法非线性规划的基本解法SUTM外点法外点法SUTM内点法（障碍罚函数法）内点法（障碍罚函数法）1、罚函数法、罚函数法2、近似规划法近似规划法 返回返回7 罚函数法罚函数法 罚函数法罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解这类方法称为序列无约束最小化方法序列无约束最小化方法简称为SUMTSUMT法法 其一为SUMTSUMT外点法外点法，其二为SUMTSUMT内点内点法法8 )2(,0min,1212ljjmiiXhMXgMXfMXT可设：)3(,min 1MX

5、TnEX）转化为无约束问题：将问题（其中T(X,M)称为罚函数罚函数，M称为罚因子罚因子，带M的项称为罚项罚项，这里的罚函数只对不满足约束条件的点实行惩罚：当 时，满足各 ，故罚项=0，不受惩罚当 时，必有 的约束条件，故罚项0，要受惩罚DX 0,0XhXgiiDX 00XhXgii或SUTMSUTM外点法外点法 )1(.,.,2,1 0 m;1,2,.,0.min ljXhiXgtsXfji对一般的非线性规划：9 罚函数法的缺点缺点是：每个近似最优解Xk往往不是容许解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着Mk的增大，可能导致错误

6、1、任意给定初始点X0，取M11，给定允许误差 ，令k=1；2、求无约束极值问题 的最优解，设为Xk=X(Mk)，即 ；3、若存在 ，使 ，则取MkM()令k=k+1返回（2），否则，停止迭代得最优解 .计算时也可将收敛性判别准则 改为 .0MXTnEX,min),(,minkkEXMXTMXTnmii1kiXg10,1MMk 0,0min12miiXgMkXX*kiXg SUTM SUTM外点法外点法(罚函数法)的迭代步骤迭代步骤10)1(,.,2,10.min i mXgtsXfi考虑问题：所有严格内点的集合。是可行域中，设集合00,2,1,0|DmiXgXDi 为障碍因子为障碍项，或其中

7、称或：构造障碍函数rXgrXgrXgrXfrXIXgrXfrXIrXImiimiimiimii11111 ln1)(),(ln,）（得值问题：）就转化为求一系列极这样问题（kkkDXrXrXI ,min10SUTMSUTM内点法（内点法（障碍函数法）11 内点法的迭代步骤内点法的迭代步骤(1)给定允许误差0，取10,01r；(2)求出约束集合 D 的一个内点00DX，令1k；(3)以01DXk为 初 始 点，求 解kDXrXI,min0，其 中0DX 的最优解，设为 0DrXXkk；(4)检验是否满足mikiXgr1ln或miikXgr11，满足，停止迭代，kXX*；否则取kkrr 1，令1

8、kk，返回(3）12 近似规划法的基本思想近似规划法的基本思想：将问题(3)中的目标函数 和约束条件 近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题，再用单纯形法求解之，把其符合原始条件的最优解作为(3)的解的近似Xf),1(0 m);1,.,(0ljXhiXgji近似规划法近似规划法每得到一个近似解后，都从这点出发，重复以上步骤 这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验表明，这样的序列往往收敛于非线性规划问题的解。13 近似规划法的算法步骤如下算法步骤如下(2)在点kX处，将Xf，XhXgji,按泰勒级数展开并取一阶近似，得到近似线

9、性规划问题：kTkkXXXfXfXfmin miXXXgXgXgkTkikii,1 0 lXXXhXhXhkTkjkjj,1j 0；(1)给定初始可行点112111,nxxxX，步长限制njj,11，步长缩小系数1,0，允许误差，令 k=1；145)判断精度：若njkj,1 ，则点1kX为近似最优解；否则，令 njkjkj,1 1，k=k+1，返回步骤(2)(3)在上述近似线性规划问题的基础上增加一组限制步长的线性约束条件因为线性近似通常只在展开点附近近似程度较高，故需要对变量的取值范围加以限制，所增加的约束条件是：njxxkjkjj,1 求解该线性规划问题，得到最优解1kX；(4)检验1kX

10、点对原约束是否可行。若1kX对原约束可行，则转步骤(5)；否则，缩小步长限制，令 njkjkj,1 ，返回步骤(3)，重解当前的线性规划问题；返回返回15用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(.)

11、;7.x,fval,exitflag=quaprog(.);8.x,fval,exitflag,output=quaprog(.);1、二次规划、二次规划标准型为：Min Z=21XTHX+cTX s.t.AX=b beqXAeq VLBXVUB 16例例1 1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t.x1+x22 -x1+2x22 x10,x20 MATLAB（youh1）1、写成标准形式写成标准形式：2、输入命令输入命令：H=1-1;-1 2;c=-2;-6;A=1 1;-1 2;b=2;2;Aeq=;beq=;VLB=0;0;VUB=;x,z=q

12、uadprog(H,c,A,b,Aeq,beq,VLB,VUB)3、运算结果运算结果为：x=0.6667 1.3333 z=-8.2222212121622 11-1 ),(minxxxxxxzT212100222 11 1 xxxxs.t.17 1.首先建立M文件fun.m,定义目标函数F（X）:function f=fun(X);f=F(X);2、一般非线性规划、一般非线性规划标准型为：min F(X)s.t AX=b beqXAeq G(X)0 Ceq(X)=0 VLBXVUB 其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同

13、.用Matlab求解上述问题，基本步骤分三步：2.若约束条件中有非线性约束:G(X)0或Ceq(X)=0,则建立M文件nonlcon.m定义函数G(X)与Ceq(X):function G,Ceq=nonlcon(X)G=.Ceq=.183.建立主程序.非线性规划求解的函数是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)

14、(5)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon,options)(6)x,fval=fmincon(.)(7)x,fval,exitflag=fmincon(.)(8)x,fval,exitflag,output=fmincon(.)输出极值点M文件迭代的初值参数说明变量上下限19注意：注意：1 fmincon函数提供了大型优化算法和中型优化算法。默认时，若在fun函数中提供了梯度（options参数的GradObj设置为on），并且只有上下界存在或只有等式约束，fmincon函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。2 f

15、mincon函数的中型算法使用的是序列二次规划法。在每一步迭代中求解二次规划子问题，并用BFGS法更新拉格朗日Hessian矩阵。3 fmincon函数可能会给出局部最优解，这与初值X0的选取有关。201、写成标准形式写成标准形式：s.t.00546322121xxxx2100 xx22212121212minxxxxf22212121212minxxxxf 2x1+3x2 6 s.t x1+4x2 5 x1,x2 0例例2212、先建立先建立M-文件文件 fun3.m:function f=fun3(x);f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)2MATLA

16、B(youh2)3、再建立主程序youh2.m：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=0.7647 1.0588 fval=-2.0294221先建立先建立M文件文件 fun4.m,定义目标函数定义目标函数: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);)12424()(22122211xxxxxexfx x1+x2=0 s.t.1.

17、5+x1x2-x1-x2 0 -x1x2 10 0例例32再建立再建立M文件文件mycon.m定义非线性约束：定义非线性约束：function g,ceq=mycon(x)g=x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;233主程序主程序youh3.m为为:x0=-1;1;A=;b=;Aeq=1 1;beq=0;vlb=;vub=;x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb,vub,mycon)MATLAB(youh3)3.运算结果为运算结果为：x=-1.2250 1.2250 fval=1.895124 例

18、4 100 ,50 07 025 .2min 21222122221121xxxxXgxxXgtsxxXf1先建立先建立M-文件文件fun.m定义目标函数定义目标函数:function f=fun(x);f=-2*x(1)-x(2);2再建立再建立M文件文件mycon2.m定义非线性约束：定义非线性约束：function g,ceq=mycon2(x)g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;253.主程序主程序fxx.m为为:x0=3;2.5;VLB=0 0;VUB=5 10;x,fval,exitflag,output =fmincon(fun,x0,VLB,VUB,m

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

20、。（1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？工地位置（a，b）及水泥日用量 d 1 2 3 4 5 6 a 1.25 8.75 0.5 5.75 3 7.25 b 1.25 0.75 4.75 5 6.5 7.25 d 3 5 4 7 6 11 （一）、建立模型（一）、建立模型 记工地的位置为记工地的位置为(ai，bi)，水泥日用量为，水泥日用量为di，i=1,6;料场位置为料场位置为(xj，yj)，日储量为，日储量为ej，j

21、=1,2；从料场；从料场j向工地向工地i的运送量为的运送量为Xij。目标函数为：216122)()(minjiijijijbyaxXf 约束条件为：2,1 ,6,2,1 ,6121jeXidXjiijijij 当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：Xij，xj，yj。（二）使用临时料场的情形（二）使用临时料场的情形 使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题.线性规划模型为：2161),(minjiijXjiaaf2,1 ,6,2,1 ,s.

22、t.6121jeXidXjiijijij其中 22)()(),(ijijbyaxjiaa，i=1,2,6,j=1,2,为常数。设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 编写程序gying1.mMATLAB（gying1）30计算结果为：计算结果为：x=3.0000 5.0000 0.0000 7.0000 0.0000 1.0000 0.0000 0.0000 4.0000 0.0000 6.0000 10.0000fval=136.2275

23、即由料场A、B向6 个工地运料方案为：1 2 3 4 5 6 料场A 3 5 0 7 0 1 料场B 0 0 4 0 6 10 总的吨千米数为136.2275。31（三）改建两个新料场的情形（三）改建两个新料场的情形 改建两个新料场，要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小。这是非线性规划问题。非线性规划模型为：216122)()(minjiijijijbyaxXf2,1 ,6,2,1 ,.6121jeXidXtsjiijijij32设 X11=X1,X21=X 2,X31=X 3,X41=X 4,X51=X 5,X61=X 6 X12=X 7,X22=X

24、 8,X32=X 9,X42=X 10,X52=X 11,X62=X 12 x1=X13,y1=X14,x2=X15,y2=X16 （1）先编写M文件liaoch.m定义目标函数。MATLAB（liaoch）(2)取初值为线性规划的计算结果及临时料场的坐标:x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;编写主程序gying2.m.MATLAB（gying2）33(3)计算结果为：x=3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867fv

25、al=105.4626exitflag=1即两个新料场的坐标分别为(6.3875,4.3943),(5.7511,7.1867),由料场 A、B 向 6 个 工地运料方案为：1 2 3 4 5 6 料场 A 3 5 0.0707 7 0 0.9293 料场 B 0 0 3.9293 0 6 10.0707 总的吨千米数为105.4626。比用临时料场节省约 31 吨千米.34(4)若修改主程序gying2.m,取初值为上面的计算结果:x0=3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943

26、 5.7511 7.1867得结果为:x=3.0000 5.0000 0.3094 7.0000 0.0108 0.6798 0 0 3.6906 0 5.9892 10.3202 5.5369 4.9194 5.8291 7.2852fval=103.4760exitflag=1总的吨千米数比上面结果略优.(5)若再取刚得出的结果为初值,却计算不出最优解.MATLAB（gying2）MATLAB（gying2）35(6)若取初值为:x0=3 5 4 7 1 0 0 0 0 0 5 11 5.6348 4.8687 7.2479 7.7499,则计算结果为:x=3.0000 5.0000 4.

27、0000 7.0000 1.0000 0 0 0 0 0 5.0000 11.0000 5.6959 4.9285 7.2500 7.7500fval=89.8835exitflag=1总的吨千米数89.8835比上面结果更好.通过此例可看出fmincon函数在选取初值上的重要性.MATLAB（gying2）返回返回36钢管订购及运输优化模型钢管订购及运输优化模型2000年年“网易杯网易杯”全国大学生数学建模竞赛全国大学生数学建模竞赛B题题37符号说明：符号说明：的距离到：表示结点11.jjjjAAA个结点的钢管数量个工厂运到第：表示从第jixij所需要的钢管数量：表示结点jjAn个结点的最大

28、生产能力：表示第jsj之间的平衡点到：表示结点1jjjAAtjA1jAjt)0(1t个结点的运费和成本个工厂运到第：单位产品从第jiaij是已知的量，是待求的变量，而其中1.,jjijijjijAsnatx3820)(1()1()2)(1(2)1(1.0 )(21()21(1.01.1.1.1.1.1.jjjjjjjjjjjjjjjjjjjjjjtAtAtttAtAtttAtC1、铺设总费用：、铺设总费用：1411.jjjCC2、成本及运输总费用：、成本及运输总费用：71152ijijijaxW总费用总费用=铺设总费用铺设总费用+成本及运输总费用成本及运输总费用=C+W模型的分析与建立模型的分

29、析与建立39 015,2,7,1 00 500,152,3,j .1.15215271152711411.jjjijjijjiijijijjiijijjjjAtjixxsxnxtsaxCf或建立模型建立模型40模型求解模型求解利用利用MATLAB软件包求解得：软件包求解得：钢 厂S1S2S3S4S5S6S7订购量 800 800 10000 101515500总费用127863241 订购量订购量 A2A3A4A5A6A7A8A9A10A11A12A13A14A15S18000201133200266000000000S28001791114295003000000000S31000 1391

30、11860006640000000S4000000000000000S51015 03582420000004150000S61556 00000000035186333621165S7000000000000000订购和运输方案表订购和运输方案表 返回返回42 某厂向用户提供发动机，合同规定，第一、二、某厂向用户提供发动机，合同规定，第一、二、三季度末分别交货三季度末分别交货40台、台、60台、台、80台每季度的生台每季度的生产费用为产费用为 （元），其中（元），其中x是该季生产的台是该季生产的台数若交货后有剩余，可用于下季度交货，但需支数若交货后有剩余，可用于下季度交货，但需支付存储费，每

31、台每季度付存储费，每台每季度c元已知工厂每季度最大生元已知工厂每季度最大生产能力为产能力为100台，第一季度开始时无存货，设台，第一季度开始时无存货，设a=50、b=0.2、c=4，问工厂应如何安排生产计划，才能既，问工厂应如何安排生产计划，才能既满足合同又使总费用最低讨论满足合同又使总费用最低讨论a、b、c变化对计划变化对计划的影响，并作出合理的解释的影响，并作出合理的解释练习练习 1 1 2bxaxxf43 一一基基金金管管理理人人的的工工作作是是，每每天天将将现现有有的的美美元元、英英镑镑、马马克克、日日元元四四种种货货币币按按当当天天汇汇率率相相互互兑兑换换，使使在在满满足足需需要要的

32、的条条件件下下，按按美美元元计计算算的的价价值值最最高高设设某某天天的的汇汇率率、现现有有货货币币和和当当天天需需求求如如下下：美美元元英英镑镑马马克克日日元元现现有有量量)10(8需需求求量量)10(8美美元元1.589281.743138.386英英镑镑1.69712.9579234.713马马克克.57372.33808179.34681日日元元.007233.00426.01261010 问问该该天天基基金金管管理理人人应应如如何何操操作作(“按按美美元元计计算算的的价价值值”指指兑兑 入入、兑兑 出出 汇汇 率率 的的 平平 均均 值值，如如 1 英英 镑镑 相相 当当 于于258928.01697.1=1.696993 美美元元)练习练习 2 2 返回返回44谢谢 谢！谢！