《数学实验 第4版》课件 3.2 非线性规划

第三章最优化方法实验3.1线性规划实验3.2非线性规划实验3.2非线性规划一、非线性规划的概念二、二次规划三、无约束非线性规划四、带约束非线性规划五、应用举例一、非线性规划的概念

如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问题.

一般说来，解非线性规划要比解线性规划问题困难得多.而且，也不象线性规划有单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围.

下面通过实例归纳出非线性规划数学模型的一般形式，介绍有关非线性规划的基本概念.实验3.2非线性规划故有限制条件元.试选择最佳投资方案.元，并预计可收益个项目可供选择投资，并且至少要对（投资决策问题）某企业有元，投资于第个项目需花资金例4其中一个项目投资.已知该企业拥有总资金解设投资决策变量为则投资总额为，投资总收益为因为公司至少要对一个项目投资，并且总的投资金额不能超过总资金A，实验3.2非线性规划另外，由于只取值0或1，所以还有最佳投资方案应是投资额最小而总收益最大的方案.s.t.所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比.因此，其数学模型为：实验3.2非线性规划

上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问题，其中目标函数或约束条件中至少有一个非线性函数，这类问题称之为非线性规划问题，简记为（NP）.其中称为决策变量，称为目标函数，和称为约束函数.称为等式约束，称为不等式约束.实验3.2非线性规划可概括为一般形式

对于一个实际问题，在把它归结成非线性规划问题时，一般要注意以下几点：(1)确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们.(2)提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极小化或极大化的目标.并且，运用各种科学和技术原理，把它表示成数学关系式.(3)给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或“坏”的价值标准，并用某种数量形式来描述它.实验3.2非线性规划(4)寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些不等式或等式来表示.

如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任意一点达到.我们先来讨论最简单的非线性规划——二次规划．实验3.2非线性规划二、二次规划

二次规划（QuadraticProgramming，记作QP）指目标函数是二次函数，约束条件为线性的.其一般形式为：s.t.为阶对称矩阵，特别地，当正定时，目标函数为凸函数，线性约束下可行域是凸集，称为凸二次规划．实验3.2非线性规划式中的意义与线性规划相同，、、、、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(...);实验3.2非线性规划例5

求解

s.t.解输入命令：H=[2-2;-24];c=[-4;-12];A=[-12;21];b=[2;3];

Aeq=[1,1];beq=[2];VLB=[0;0];VUB=[];[x,z]=quadprog(H,c,A,b,Aeq,beq,VLB,VUB)↙

实验3.2非线性规划x=0.66671.3333z=

-16.4444三、无约束非线性规划无约束非线性规划的一般形式是可以是非线性的．其中[x,fval]=fminbnd(fun,x1,x2,options)，这里fun是用M文件定义的函数或Matlab中的单变量数学函数.这实际上就是多元函数极值问题．1．求单变量有界非线性函数在区间上的极小值:Matlab的命令为它的返回值是极小值点和函数的极小值.实验3.2非线性规划例6

求函数

的最小值.

解编写M文件fun1.mfunctionf=fun1(x);f=(x-3)^2-1;在Matlab的命令行窗口输入[x,y]=fminbnd('fun1',0,5)↙

即可求得极小值点和极小值.x=3y=-1实验3.2非线性规划例7

求在中的最小值与最大值

解：命令如下f=@(x)2*exp(-x).*sin(x)';[xmin,ymin]=fminbnd(f,0,8)f1=@(x)-2*exp(-x).*sin(x)';%f的最大值点即-f的最小值点[xmax,ymax]=fminbnd(f1,0,8)↙运行结果：xmin=3.9270ymin=-0.0279xmax=0.7854ymax=-0.6448实验3.2非线性规划

所以函数在x=3.9270处取得最小值-0.0279，在x=0.7854处取得最大值0.6448.，则水槽的容积为：例8有一张边长为3m的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪可使水槽的容积最大？解设剪去的正方形的边长为建立无约束优化模型为：先编写M文件fun2.m如下:functionf=fun2(x)f=-(3-2*x).^2*x;主程序为:[x,fval]=fminbnd('fun2',0,1.5);xmax=xfmax=-fval↙实验3.2非线性规划运算结果为:xmax=0.5000fmax=2.0000即剪掉的正方形的边长为0.5米时水槽的容积最大,最大容积为2立方米.实验3.2非线性规划2．求多变量函数的极小值其中是一个向量，是一个标量函数.Matlab中求解多变量函数极小值的基本命令有两个：[x,fval]=fminunc(fun,x0,options,p1,p2,...)[x,fval]=fminsearch(fun,x0,options,p1,p2,...).实验3.2非线性规划例9

求解

解：编写M-文件fun3.m:functionf=fun3(x)f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);

x0=[-1,1];

[x,y]=fminunc('fun3',x0)↙x=0.5000-1.0000y=

3.6609e-15实验3.2非线性规划[x,y]=fminsearch('fun3',x0)↙x=0.5000-1.0000y=5.1425e-10四、带约束非线性规划

带有约束条件的极值问题称为约束极值问题，也叫约束规划问题.求解约束极值问题要比求解无约束极值问题困难得多.为了简化其优化工作，可采用以下方法：带约束非线性规划的一般形式为:其中是定义在上的实值函数．实验3.2非线性规划将约束问题化为无约束问题；将非线性规划问题化为线性规划问题，以及能将复杂问题变换为较简单问题的其它方法.标准型为：用Matlab解非线性规划的一般步骤是：（1）首先建立M文件fun.m，定义目标函数F(ｘ):functionf=fun(ｘ);f=F(ｘ);（2）若约束条件中有非线性约束:C(x)<=0或Ceq(x)=0，则建立M文件nonlcon.m定义函数C(x)与Ceq(x):Function[C,Ceq]=nonlcon(x)C=...Ceq=...实验3.2非线性规划（3）建立主程序．非线性规划求解的函数是fmincon，命令的基本格式如下：①x=fmincon(‘fun’,X0,A,b)②x=fmincon(‘fun’,X0,A,b,Aeq,beq)③x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB)④x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’)⑤x=fmincon(‘fun’,X0,A,b,Aeq,beq,VLB,VUB,’nonlcon’,options)⑥[x,fval]=fmincon(...)其中x为返回的自变量的值，fval为返回的函数的值，X0为迭代的初值，VLB,VUB变量上下限，options参数说明．实验3.2非线性规划例10

求s.t.解

（1）先建立M文件fun4.m,定义目标函数:functionf=fun4(x);f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);（2）再建立M文件mycon.m定义非线性约束：function[g,ceq]=mycon(x)g=[1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10];ceq=0;实验3.2非线性规划（3）求解非线性规划:x0=[-1;1];A=[];b=[];Aeq=[11];beq=[0];vlb=[];vub=[];[x,fval]=fmincon('fun4',x0,A,b,Aeq,beq,vlb,vub,'mycon')↙（4）运算结果为：

x=-3.16233.1623fval=1.1566实验3.2非线性规划例11

抛物面被平面截成一椭圆，求原点到这椭圆的最短距离．解（1）先建立M文件fun5.m,定义目标函数:functionf=fun5(x)f=sqrt(x(1)^2+x(2)^2+x(3)^2);（2）再建立M文件mycon1.m定义非线性约束：function[g,ceq]=mycon1(x)g=0;ceq=x(1)^2+x(2)^2-x(3);实验3.2非线性规划（4）运算结果为：x=0.36600.36600.2679fval=0.5829实验3.2非线性规划（3）求解非线性规划:x0=[0;0;0];A=[];b=[];Aeq=[111];beq=[1];vlb=[];vub=[];[x,fval]=fmincon('fun5',x0,A,b,Aeq,beq,vlb,vub,'mycon1')

↙例12资金使用问题：设有400万元资金,要求4年内使用完,若在一年内使用资金x万元,则可得效益年利率为10%.试制定出资金的使用计划,以使4年效益之和为最大.万元(效益不能再使用),当年不用的资金可存入银行,解设变量表示第i年所使用的资金数,则有

实验3.2非线性规划（1）先建立M文件fun6.m,定义目标函数:functionf=fun6(x)f=-(sqrt(x(1))+sqrt(x(2))+sqrt(x(3))+sqrt(x(4)));（2）由于没有非线性约束条件，可直接求解非线性规划:

x0=[1;1;1;1];vlb=[0;0;0;0];vub=[];A=[1,0,0,0;1.1,1,0,0;1.21,1.1,1,0;1.331,1.21,1.1,1];b=[400,440,484,532.4];Aeq=[];beq=[];[x,fval]=fmincon('fun6',x0,A,b,Aeq,beq,vlb,vub)↙实验3.2非线性规划（3）结果为:实验3.2非线性规划x=86.1883104.2878126.1883152.6879fval=-43.0860五、应用举例:供应与选址总的吨千米数最小．

某公司有6个建筑工地，每个工地的位置（用平面坐标a，b表示，单位：km）及水泥日用量d（单位：t）由表给出．目前有两个临时料场位于，日储量各有20t．（1）假设从料场到工地之间均有直线道路相连，试制订每天的供应计划，即从A、B两料场分别向各工地运送多少吨水泥，使工地1234561.258.750.55.7537.251.250.754.7556.57.753547611（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量仍各为20t，问应建在何处，节省的吨千米数有多大．实验3.2非线性规划30，因此目标函数为：解向工地从料场的运送量为记工地的位置为，水泥日用量，，料场位置为，日储量为约束条件实验3.2非线性规划，这是一个线性规划问题，（1）当用临时料场时，决策变量为计算程序如下：a=[1.258.750.55.7537.25];b=[1.250.754.7556.57.75];d=[3547611]';e=[2020]';g=[51];h=[27];c=zeros(1,12);fori=1:6c(i)=sqrt((g(1)-a(i))^2+(g(2)-b(i))^2);c(i+6)=sqrt((h(1)-a(i))^2+(h(2)-b(i))^2);endA=[ones(1,6),zeros(1,6);zeros(1,6),ones(1,6)];Aeq=[eye(6),eye(6)];v1=zeros(1,12);[x,fval]=linprog(c,A,e,Aeq,d,v1,[])↙实验3.2非线性规划x=

3

5

0

7

0

1

0

0

4

0

6

10fval=136.2275即由料场A、B向6个工地运料方案如表所示：123456料场A350701料场B0040610

总的吨千米数为136.2275．实验3.2非线性规划计算结果为：（2）当为新建料场选址时，决策变量为和，这是一个非线性规划问题．计算程序如下：首先建立目标函数的Ｍ文件：functionf=liaoch(x)a=[1.258.750.55.7537.25];b=[1.250.754.7556.57.75];f1=0;fori=1:6