《优化问题实例解析》PPT课件.ppt

实例解析,【例11-1】有两种液体产品P1和P2，每件产品P1在第一车间的处理时间为1小时，在第二车间的处理时间为1.25小时；每件产品P2在第一车间的处理时间为1小时，在第二车间的处理时间为0.75小时。每个车间每月有200小时的时间可以利用，而且P2产品的市场需求量最大为150件，假定P1产品和P2产品的利润每件分别为4美元和5美元，问P1产品和P2产品的生产量分别为多少时生产商所获得的利润最大。解：设P1产品和P2产品的生产量分别为x1和x2时生产商所获得的利润最大，则目标函数和约束条件可以写为：,编写如下程序：f=-4;-5;A=1,1;1.25,0.75;0,1;b=200;200;150;lb=00;x,fval,exitflag=linprog(f,A,b,lb)%线性规划问题求解为更直观地理解线性规划的几何意义，这里又编写了LP_demo.m函数文件。,运行结果：x=50.0000150.0000fval=-950.0000exitflag=1,【例11-3】计算下面函数在上的极值。,解：首先绘制该二元函数在z=0上下两部分的曲面图，,下面编写求极值的主函数，这里由于不知道初始点，所以借助ginput()函数在等高线图形上取点作为初始点的横纵坐标，得到的结果如图：,peaks_jizhi.m,【例11-4】Banana函数优化。,解：首先绘制出Banana函数的曲面图。,下面进行优化求解，为获得更好的效果，这里采用动态图形来显示每一步迭代的过程，这里首先介绍一个专门绘制“Banana”函数优化求解迭代点的函数bandemoutfcn()。调用函数fminsearch()求解上述优化问题，在原绘图程序的基础上输入如下代码：plot3(-1.9,2,267.62,ko,markersize,12,linewidth,1,erasemode,none)text(-1.9,2.3,267.62,fontname隶书fontsize16开始,color,0,0,0)plot3(1,1,0,ko,markersize,12,linewidth,1,erasemode,none)text(1,1.3,100,fontname隶书fontsize16结束,color,0,0,0)set(gcf,Color,w)x0=-1.9,2;f=100*(x(2)-x(1)2)2+(1-x(1)2;%利用字符串定义函数表达式OPTIONS=optimset(OutputFcn,bandemoutfcn);%设置优化控制参数OutputFcnx,fval,exitflag,output=fminsearch(f,x0,OPTIONS),example_11_4_1.m,下面再利用fminunc()函数求解上述优化问题，编写如下程序代码：x0=-1.9,2;OPTIONS=optimset(LargeScale,off,OutputFcn,bandemoutfcn);%设置优化参数grad=100*(4*x(1)3-4*x(1)*x(2)+2*x(1)-2;100*(2*x(2)-2*x(1)2);%梯度表达式描述f=100*(x(2)-x(1)2)2+(1-x(1)2;%函数表达式OPTIONS=optimset(OPTIONS,HessUpdate,bfgs,gradobj,on,MaxFunEvals,200,InitialHessType,scaled-identity,LineSearchType,quadcubic);%更新优化参数x,fval,exitflag,output=fminunc(f,grad,x0,OPTIONS)%优化问题求解,example_11_4_2.m,【例11-5】求解humps()函数在区间0,1内的极小值。,解：为显示该优化问题的每一步的迭代过程，先编写优化方法的输出函数myoutput.m并在优化参数中进行设置。functionstop=myoutput(x,optimvalues,state);%优化方法的输出函数history=;stop=false;ifstate=iterhistory=history;x;endfplot(humps,0,2)holdonplot(history,humps(history),r.,.MarkerSize,14)%绘制迭代点pause(1)%暂停1秒,再编写如下主程序：options=optimset(OutputFcn,myoutput);%设置优化参数OutputFcnxfval=fminbnd(humps,0,1,options)%单变量优化求解plot(x,fval,kv,markersize,8,MarkerFaceColor,k)%绘制最优解text(x-0.4,fval-7,极小值点：(,num2str(x),num2str(fval),)%添加标注,example_11_5.m,【例11-7】求解下面的多变量约束优化问题。,解：首先编写非线性约束条件的描述函数NonLinear_constr()，再编写如下主程序：x0=1,1,1;sigma=105;lb=100;ub=3,inf,inf;%变量上下界f=(x,sigma)x(2)*sqrt(16+x(1)2)+x(3)*sqrt(1+x(1)2);options=optimset(Algorithm,interior-point);%设置优化算法为interior-pointx,fval=fmincon(f,x0,lb,ub,.NonLinear_constr,options,sigma)%非线性约束优化,输出结果：x=2.00000.00040.0009fval=0.0040,【例11-8】求解下面的二次规划问题。,解：首先将目标函数转换为的形式，,编写如下语句：H=1-1;-12;f=-2;-6;A=11;-12;21;b=2;2;3;lb=zeros(2,1);ff=optimset;ff.LargeScale=off;%设置不使用大规模算法x,fval=quadprog(H,f,A,b,lb,ff)%二次规划问题的求解,运行结果：x=0.66671.3333fval=-8.2222,【例11-10】求解下面一维情形的半无限优化问题。,解：首先建立非线性约束和半无限约束条件的函数描述文件myseminfcon.m,再编写如下主程序：fun=(x)sum(x-0.5).2);x0=0.5;0.2;0.3;x,fval=fseminf(fun,x0,2,myseminfcon),运行结果：x=0.66750.30120.4022fval=0.0771,【例11-12】试求解下面的极小极大问题。,解：首先编写非线性约束条件描述函数NLconstr.m：functionc,ceq=NLconstr(x)c=x(1)2+x(2)2-8;%不等式约束ceq=;%设置等式约束为空再编写如下主程序：f=(x)2*x(1)2+x(2)2-48*x(1)-40*x(2)+304;%目标函数-x(1)2-3*x(2)2;x(1)+3*x(2)-18;-x(1)-x(2);x(1)+x(2)-8;x0=0.1;0.1;%初始值x,fval=fminimax(f,x0,1,1,3,-3,-2,3,2,NLconstr)%极小极大化问题求解,【例11-13】利用目标规划方法重新求解【例11-1】。,解：首先设置目标函数相应的目标函数值向量-950,-50，编写如下语句：A=1,1;1.25,0.75;0,1;b=200;200;150;goal=-950,-50;weight=abs(goal);x0=50,50;lb=00;ub=inf,inf;options=optimset(GoalsExactAchieve,2);%设置独立变量数f=(x)-4*x(1)-5*x(2),-x(1);%定义函数表达式x,fval=fgoalattain(f,x0,goal,weight,A,b,lb,ub,options)%求解目标规划问题,运行结果：x=50150fval=-950-50,【例11-14】求解下面的超定方程组。,所有变量的上下界均为2和-0.1。,解：编写如下语句：n=4;x=(-1).(1:n)-1)./(1:n);C=gallery(circul,x);%利用向量x生成循环矩阵C=repmat(C,2,1);%复制矩阵Cd=n-1:-1:-n;%构造向量dlb=-0.1*ones(n,1);ub=2*ones(n,1);options=optimset(LargeScale,off);%设置不使用大型算法x,resnorm,residual=lsqlin(C,d,lb,ub,options)%线性最小二乘问题求解,运行结果：x=1.39850.3326-0.1000-0.1000resnorm=39.2272,【例11-16】求解下面的非线性最小二乘优化问题。,解：为了便于比较，这里分别利用函数lsqnonlin()和fmincon()求解，编写如下程序代码：%利用lsqnonlin函数求解f=(x,k)2+2.*(1:k)-exp(1:k)*x(1)-exp(1:k)*x(2);%目标函数描述x0=0.3,0.4;%初始值lb=zeros(2,1);ub=ones(2,1);%变量的上下界x1,resnorm,residual=lsqnonlin(x)f(x,10),x0,lb,ub)%lsqnonlin函数求解%利用fmincon函数求解G=(x,k)f(x,k)*f(x,k);%目标函数描述options=optimset(LargeScale,off,Algorithm,active-set);%设置优化参数x2,fval=fmincon(x)G(x,10),x0,lb,ub,options)%fmincon函数求解,运行结果：x1=0.25780.2578resnorm=124.3622residual=1.41182.65053.66544.39064.74084.60573.84282.2672-0.3600-4.3482x2=0.25780.2578fval=124.3622,【例11-19】求解下面线性整数规划问题。,解：调用函数miprog()编写如下程序代码：c=-40,90;A=9,7;7,20;b=56;70;Aeq=;beq=;lb=0;0;yidx=logical(1;1);%yidx为逻辑量x=miprog(c,A,b,Aeq,beq,lb,yidx)%线性整数规划求解,运行结果：It.1.Bestintegersolution:InfDelta100%It.1.F-val(It):-355.8779Delta100%.Queuelen.2It.2.F-val(It):-341.4286Delta100%.Queuelen.3It.3.F-val(It):-349Delta100%.Queuelen.4It.4.F-val(It):-327.1429Delta100%.Queuelen.5It.5.Bestintegersolution:-340Delta0.20964%It.5.F-val(It):-340Delta0.20964%.Queuelen.4It.6.F-val(It):InfDelta0.20964%.Queuelen.3It.7.F-val(It):-307.7778Delta0%.Queuelen.2Iteration7.Optimizationended.Foundoptimalsolution!Timespent0.15116secondsObjectivefunctionvalue:-340 x=4.00002.0000,【例11-20】求解下面的非线性整数规划问题。,解：首先编写目标函数文件objfun.m和非线性约束函数文件nonlcon.m。%=目标函数=%functionf=objfun(x)f=100.*(x(2)-x(1).2).2+(4.5543-x(1).2;%=非线性约束=%functionc,ceq=nonlcon(x)c=-8.63*x(1)+x(2)3;%非线性不等式条件约束ceq=;%非线性等式约束,再编写如下主程序：x0=1;1;%初值，必须是列向量xstatus=1;1;lb=-100*1;1;ub=-lb;A=;b=;Aeq=;beq=;settings=;%优化选项，必须给出TolX和MaxSQPIter两个参数options=optimset(display,off,MaxSQPIter,1000,TolX,1e-6);%调用bnb20函数求解errmsg,f,x,t,c,fail=bnb20(objfun,x0,xstatus,lb,ub,A,b,.Aeq,beq,nonlcon,settings,options)%调用优化工具箱验证x1,fval,exitflag,output=fmincon(objfun,x0,A,b,Aeq,beq,.lb,ub,nonlcon,options),运行结果：x=1.00001.0000f=12.6330,x1=1.54342.3705fval=9.0791,【例11-21】试求解下面给出的0-1线性规划问题。,解：编写如下程序代码：f=-9,-5,-6,-4;A=6352;0011;-1010;0-101;b=9;1;0;0;x,fval=bintprog(f,A,b),运行结果：x=1100fval=-14,【例11-22】考虑如下图所示的网络图，连线上的数字表示两点之间的距离(或费用)，试寻求一条由A到G距离最短(或费用最省)的路线。,解：首先编写决策变量值的求解函数dynfun1.m，各阶段的指标函数值计算函数dynfun2.m和状态转移方程描述函数dynfun3.m。%=决策变量值的求解函数=%functionu=dynfun1(k,x)%在阶段k由状态变量x的值求出其相应的决策变量所有的取值ifx=1u=2;3;elseifx=2u=4;5;6;elseifx=3u=5;6;7;elseifx=4|x=5u=8;9;elseifx=6|x=7u=9;10;,elseifx=8u=11;12;elseifx=9|x=10u=12;13;elseifx=11|x=12|x=13u=14;15;elseifx=14|x=15u=16;elseifx=16u=16;end,%=各阶段的指标函数值求解函数=%functionv=dynfun2(k,x,u)%求解各阶段指标函数值tt=5;3;2;3;6;8;7;16;6;8;3;5;3;3;8;4;2;2;1;2;3;3;3;5;5;2;6;6;4;3;tmp=x=1,再编写如下主程序：x=nan*ones(4,7);%初始化，7个状态变量，每个最多4种取值x(1,1)=1;x(1:2,2)=2;3;x(1:4,3)=(4:7);x(1:3,4)=(8:10);x(1:3,5)=(11:13);x(1:2,6)=14;15;x(1,7)=16;p,f=dynprog(x,dynfun1,dynfun2,dynfun3),运行结果：p=%p的第二列为最短路径11252253358348122512152615163716160f=18%最短路径距离,可见最短路径按节点序号为,【例11-24】资源分配问题。,解：将问题按项目分成3个阶段，A,B,C三个项目分别编号1、2和3。设状态变量xk表示投资第k个项目前的资金数，决策变量dk表示第k个项目的投资，决策允许集合为。则状态转移方程：设阶段指标函数表示投资到第k个项目所获得的利润，表示资金投资到第k个项目至n个项目所获得的最大利润。则基本方程为：编写程序Resource_allocation.m。由输出结果可知，有4万元投资金额时，A,B,C项目的投资金额分别为1,0和3万元时获最大利润60万元，有3万元投资金额时，A,B,C项目的投资金额分别为1,0和2万元时获最大利润45万元，有2万元投资金额时，A,B,C项目的投资金额分别为0,0和2万元时获最大利润30万元，有1万元投资金额时，A,B,C项目的投资金额分别为0,0和1万元时获最大利润11万元。,实验范例：投资的收益与风险,要使净收益尽可能大，而总体风险尽可能小，可以建立如下多目标规划模型：对于该模型若直接求解则显得十分复杂，故此对上述模型作相关简化：,模型一：固定风险水平，优化收益,若将风险水平固定，则前述模型变为如下模型：,模型二：固定盈利水平，极小化风险,模型三：对风险、收益赋予权重,下面仅对模型一进行求解，至于其他的模型读者可以依据优化模型的类型而调用前面介绍的相关的求解函数求解。由于a是任意给定的风险度，而且不同的投资者有不同的风险度。故此我们从a=0开始，以步长进行循环搜索，编写程序example_11_end.m。,【练1】由题可得优化模型如下：根据上述模型编写如下程序：f=0.02;0.07;0.04;0.03;0.05;A=-0.3210.61.8;0.10.050.020.20.05;0.050.10.020.20.08;b=-70;-3;-10;lb=zeros(5,1);x,fval,exitflag=linprog(f,A,b,lb)%线性规划问题求解,运行结果：x=0.00000.00000.000039.743625.6410fval=2.4744,【练2】由题意可得到本题的优化模型如下：编写如下语句：functionexercise_11_2x0=10;10;2;lb=0;0;2;%变量上下界f=(x)-x(1)*x(2);options=optimset(Algorithm,interior-point);%设置优化算法为interior-pointx,fval=fmincon(f,x0,lb,.NonLinear_constr,options)%非线性约束优化functionC,Ceq=NonLinear_constr(x)C=(x(1)+x(2)*x(3)-120;Ceq=;%将非线性等式约束设置为空,运行结果：x=30.000030.00002.0000,【练3】由题可得优化模型为：编写如下语句：fun=4*x12+36*x22+100*x32+5*x1*x2-20*x1*x3-30*x2*x3;H,f=quad_coef(fun);%计算二次型的系数A=-5,-8,-10;20,25,30;b=-1000;5000;Aeq=;beq=;lb=zeros(3,1);options=optimset(LargeScale,off);%设置优化参数不适用大型算法x,fval=quadprog(H,f,A,b,Aeq,beq,lb,options)%二次规划问题求解,运行结果：x=131.114115.285322.2147fval=6.8105e+004,【练4】分析题目可得如下优化模型：,编写如下程序：f=ones(1,18);A=-5,-5,-4,-4,-3,-3,-3,-2,-3,-3,-3,-2,-2,-2,-1,-1,-1,-1;5,5,4,4,3,3,3,2,-15,-15,-15,-10,-10,-10,-5,-5,-5,-5;6,6,6,4,4,4,2,2,2,2,-5,-5,-4,-4,-3,-3,-3,-2;-1,0,0,0,1,zeros(1,13);0,-1,0,0,0,0,1,zeros(1,11);zeros(1,7),-1,1,zeros(1,9);zeros(1,5),-1,0,0,0,1,zeros(1,8);0,0,0,-1,zeros(1,6),1,zeros(1,7);zeros(1,4),-1,zeros(1,6),1,zeros(1,6);zeros(1,6),-1,zeros(1,5),1,zeros(1,5);zeros(1,5),-1,zeros(1,7),1,0,0,0,0;b=-18;-2;2;zeros(8,1);x,fval=bintprog(f,A,b),运行结果：x=010101000010011000fval=6,【练6】将问题按工厂分为三个阶段，甲、乙和丙3个工厂分别编号为1，2和3。设状态变量xk表示分配给第k个工厂至第n个工厂的设备台数。决策变量uk表示分配给第k个工厂的设备台数。则状态转移方程阶段指标函数表示uk台设备分配到第k个工厂所获得的盈利值。表示xk台设备分配给第k个工厂至第n个工厂所获得的最大盈利值。则基本方程为：根据上面的方程编写程序exercise_11_6.m。,