非线性规划(2006.11).ppt

1、数学实验之九,投资决策问题,一般模型与算法概述,Matlab软件求解简介,实验内容,主要内容,范例：选址问题,实验目的,1、掌握使用MATLAB优化工具箱求解非线性规划的方法；2、练习建立实际问题的非线性规划模型；,某钢铁厂准备用5000万元用于A、B两个项目技改进行投资。预估投资项目的年收益分别为20%和16%。同时，投资后总的风险损失随总投资和单项投资的增加而增加，应如何分配资金，才能使期望收益达最大，同时又使风险损失为最小？,引例:投资决策问题,问题假设,1、设x1,x2分别表示分配给项目A、B的投资资金；2、总的风险损失与总投资的平方成正比，也与单项投资的平方成正比，即风险损失函数为：

2、g(x1,x2)=(x1+x2)2+2x12+x223、收益函数为：f(x1,x2)=20 x1+16x2(高收益，高风险),数学模型,maxf(x1,x2)-g(x1,x2)max20 x1+16x2-(x1+x2)2+2x12+x22s.t.x1+x25000 x1,x20其中，0为权系数。特殊情形：=0，不考虑风险；=1，考虑收益和风险同等重要；1，表示风险最小是第一目标，其次才考虑收益目标。,投资决策问题另外一种提法:,某公司在一个时期内可用于投资的总资本为b万元,可供选择的项目有n个。假定对第i个项目的投资总额为ai万元，收益总额为ci万元。问如何确定投资方案，使总的利润率达最高？设

3、投资决策变量为：,数学模型,关于决策变量xi的非线性约束整数规划问题。,收益占总投资的比率,投资决策问题,一般模型与算法概述,Matlab软件求解简介,实验内容,主要内容,范例：选址问题,非线性规划模型的一般形式,特殊情形：无约束,非线性规划模型,无约束非线性规划算法简介,数值迭代法,1、选择初始解x0；2、对第k次迭代解xk，确定搜索方向dkRn，并在此方向上确定步长k，令xk+1=xk+kdk，使得f(xk+1)f(xk);3、若xk+1符合给定的迭代终止条件，如xk+1-xk，停止迭代，最优解近似为xk+1。,确定搜索方向有如下方法：1、最速下降法；2、牛顿法；3、拟牛顿法；在实际应用中

4、，真正无约束的情况是很少的。,约束非线性规划算法简介,1、可行方向法；2、罚函数法；3、梯度投影法；4、逐步二次规划法（SQP）（SequentialQuadraticProgramming）MATLAB软件中主要采用SQP算法。,投资决策问题,一般模型与算法概述,Matlab软件求解简介,实验内容,主要内容,范例：选址问题,一元函数极小MinF(x)s.t.x1xx2调用格式：x,fval=fminbnd(F,x1,x2),MATLAB优化工具箱的主要功能,无约束非线性规划MinF(X)调用格式:X,fval=fminunc(F,X0,options)或X,fval=fminsearch(F

5、,X0,options),二次规划Min0.5*XTHX+CTXs.t.AXb调用格式：X,fval=quadprog(H,c,A,b),约束非线性规划MinF(X)s.t.G(X)0,Geq=0AXb,Aeq.X=beq,lXu调用格式：X,fval=fmincon(F,X0,A,b,Aeq,beq,l,u,GGeq),MATLAB优化工具箱的主要功能,M文件Ggeq.m：FunctionG,Geq=GGeq(X)G=G(X);%计算非线性不等式约束在X的值Geq=Geq(X);%计算非线性等式约束在X的值,达到目标问题Minrs.t.F(X)-wrgoal,G(X)0,Geq=0AXb,A

6、eq.X=beq,lXuX,w,goal是向量，X,r是决策变量。这是多目标规划的一种描述模式。调用格式：X,fval=fgoalattain(F,X0,goal,w,A,b,Aeq,beq,l,u,GGeq),MATLAB优化工具箱的主要功能,MATLAB优化工具箱的主要功能,极小极大问题MinmaxFi(X)s.t.G(X)0,Geq=0AXb,Aeq.X=beq,lXu调用格式：X=fminimax(Fun,X0,A,b,Aeq,beq,l,u,GGeq),M文件F.m:FunctionF=Fun(X)F=F1(X),F2(X),Fn(X);%计算目标函数在X的值,MATLAB优化工具箱

7、的主要功能,半无限规划问题MinF(X)s.t.k(X,w)0，对所有w（半无限约束）G(X)0,Geq=0AXb,Aeq.X=beq,lXu调用格式：X=fseminf(F,x0,n,seminfcon,A,b,Aeq,beq,l,u),1、无约束非线性规划情形,标准形式MinF(x)MATLAB求解步骤首先建立一个M文件函数，如fun.m调用格式：x,fval=fminunc(fun,x0,options),例Rosenbrock函数,求f的最优解。初始值取（-1.9，2）。,2）x0=-1.9,2;options=optimset(display,iter)x,fval=fminunc(

8、fun1,x0,options),1）functionf=fun1(x)f=100*(x(2)-x(1)2)2+(1-x(1)2;,计算结果：x=0.99990.9997fval=1.9047e-008若想结果更精确，将options修改为options=optimset(display,iter,tolfun,1e-10);,在大多数优化程序中都有一个控制参数的结构options，它共有33个元素，包含了在优化程序中要用到的所有参数，供使用者在计算时控制精度要求、输出形式、算法选择、迭代次数等。若在对某优化程序的第一次调用中，options为空（即），则会自动使用一组缺省参数。,控制参数结构

9、options,控制参数结构options,利用帮助系统很容易查看到options中的各参数及其作用点击“？”选择“contents”在contents的目录树中选择“Optimizationreferencefunctionreferenceoptimizationoptionsparameters”在该节帮助文本中的表4-3给出了options中的各参数及其作用，用在哪些优化程序中。,控制参数结构options的设置,利用命令optimset来建立和编辑优化程序中options的参数结构。常用调用格式为：1）options=optimset(param1,value1,param2,val

10、ue2,.)例如：将display参数置为iter，将tolfun参数置为1e-10，其余参数为（即取缺省值）的参数结构options可用下面语句来建立。options=optimset(display,iter,tolfun,1e-10)2）options=optimset参数结构options中所有参数都置为，及取缺省值。,控制参数结构options的设置,在帮助文本的“optimizationoptionsparameters”一节点击链接“optimset”可查看到它的全部调用格式，以及各参数的各种可能取值，还有例子。,大规模和中等规模算法中用到的优化参数,只在大规模算法中用到的优化参

11、数,只在中等算法中用到的优化参数,2.二次规划的情形minZ=0.5*XHX+fXs.t.A.Xb,Aeq.X=beq,lbXub,求解格式,minz=5x1+6x2+-12x3+2x12+4x22+6x32-2x1x2-6x1x3+8x1x3s.t.x1+2x2+x36;x1+x2+x316;-x1+2x24;x10,x20,x30.写成矩阵形式:min0.5xHx+cxs.t.Axb;x0.,H=4-2-6;-288;-6812;f=56-12;A=-1-2-1;111;-120;b=-6164;lb=000;x,z=quadprog(H,f,A,b,lb);,或options=optim

12、set(largescale,off);x,z=quadprog(H,f,A,b,lb,options),x=3.250002.7500z=-3.8750,输出结果：,可能会提示你改用中等规模的算法，更正如下,3、约束非线性规划（多变量）情形,标准模型,Minf(X)s.t.c(X)0,ceq(X)=0AXb,Aeq.X=beq,lbXub,求解格式,建立m文件函数fun.mfunctionf=fun(x)f=f(x);,为函数fmincon的其余输入变量赋值，然后调用该函数求出约束规划问题的解。,解释,建立m文件函数nonlcon.mfunctionc,ceq=nonlcon(x)c=c(x

13、);ceq=ceq(x),例：求解以下约束非线性规划：Maxf(x)=x1x2s.t.2(x1+x2)x3500 x32xj0，j=1,2,MATLAB程序,functionf=fun2(x)f=-x(1)*x(2);functionc,ceq=nlcon(x)c=(x(1)+x(2)*x(3)-250;ceq=;x0=10102;L=002;x,fval=fmincon(fun2,x0,L,nlcon),计算结果,x=62.500062.50002.0000fval=-3.9063e+003,投资决策问题,一般模型与算法概述,Matlab软件求解简介,实验内容,主要内容,范例：选址问题,供应

14、与选址,某公司有6个建筑工地要开工，每个工地的位置（用平面坐标a，b表示，距离单位：千米）及水泥日用量d吨由下表给出。目前有两个临时料场位于A(5,1),B(2,7)，日储量各有20吨。假设从料场到工地均有直线道路相连，问题1：试制定每天A、B两料场向各工地供应水泥的供应计划，使总的吨千米数最小。,问题2：为进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量仍各为20吨，问应建在何处，节省的吨千米数有多大？,建立规划模型,记工地的位置为(ai,bi)，水泥日用量为di,i=1,6,料场位置为(xj,yj),日储量为ej,j=1,2；从料场j向工地i的运送量为cij。,（工地日用量）

15、,（料场日储量）,问题1：使用临时料场，即料场位置(xj,yj)为已知,决策变量为cij，上述模型为线性规划模型。记决策变量X=c11,c21,c61,c12,c62,a0=1.258.750.55.7537.25;b0=1.250.754.7556.57.75;c1=sqrt(5-a0).2+(1-b0).2);c2=sqrt(2-a0).2+(7-b0).2);c=c1,c2;A=ones(1,6),zeros(1,6);zeros(1,6),ones(1,6);b=20;20;Aeq=eye(6),eye(6);beq=3547611;L=zeros(1,12);X,val=linpro

16、g(c,A,b,Aeq,beq,L),求解线性规划的程序,线性规划求解结果：最优目标值f=136.2275（吨千米）料场A,B运往各工地的水泥的日运量分别为,问题2：要为新建料场选址,料场位置(xj,yj)为未知时,决策变量为cij，xj,yj，模型为非线性规划模型。,（工地日用量）,（料场日储量）,求解非线性规划，MATLAB程序,functionf=liaocmb(x)a0=1.258.750.55.7537.25;b0=1.250.754.7556.57.75;c1=sqrt(x(13)-a0).2+(x(14)-b0).2);c2=sqrt(x(15)-a0).2+(x(16)-b0)

17、.2);c=c1,c2;f=c*x(1:12,1);,functionc,ceq=liaocys(x)A=ones(1,6),zeros(1,6);zeros(1,6),ones(1,6);b=20;20;Aeq=eye(6),eye(6);beq=3547611;c=A*x(1:12,1)-b;ceq=Aeq*x(1:12,1)-beq;,目标函数,约束条件,求解非线性规划，MATLAB程序(liaoch2.m),clearL=zeros(16,1);x0=zeros(1,12),5,1,2,7;options=optimset(largescale,off,display,iter,Max

18、FunEval,2000);x,val,=fmincon(liaocmb,x0,L,liaocys,options),计算结果：最优目标值f=85.2660（吨千米）,新料场位置的改变，目标值比原来减少了50.9615吨千米。,新料场A,B的坐标为（3.2550，5.6522）和（7.2500，7.7500）。新料场A,B运往各工地的水泥的日运量分别为,优化结果是新料场应建在用量最大的工地旁边，你预先估计到这个结果了吗？,投资决策问题,一般模型与算法概述,Matlab软件求解简介,实验内容,主要内容,范例：选址问题,1、求解非线性规划,实验内容,2、桃李花园服务中心选址,P173,实验一。初始点x0=20，20,设(ai,bi)(i=120)为第i栋住宅楼的坐标；a=29.744.969.3265.098.355.2740.019.862.573.337.580.9841.9875.3779.3892.084.4736.7762.0873.13;b=19.3990.4856.9263.1823.4454.8893.1633.565.5