二次-多目标-最大最小化.doc

二次、目标及动态规划1 二次规划模型数学模型：其中H为二次型矩阵，A、Aeq分别为不等式约束与等式约束系数矩阵，f,b,beq,lb,ub,x为向量。求解二次规划问题函数为quadprog( )调用格式：X= quadprog(H,f,A,b)X= quadprog(H,f,A,b,Aeq,beq)X= quadprog(H,f,A,b,Aeq,beq,lb,ub)X= quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)X= quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)x,fval= quadprog()x,fval,exitflag= quadprog()x,fval,exitflag,output= quadprog()x,fval,exitflag,output,lambda= quadprog()说明：输入参数中，x0为初始点；若无等式约束或无不等式约束，就将相应的矩阵和向量设置为空；options为指定优化参数。输出参数中，x是返回最优解；fval是返回解所对应的目标函数值；exitflag是描述搜索是否收敛；output是返回包含优化信息的结构。Lambda是返回解x入包含拉格朗日乘子的参数。例1：求解：二次规划问题min f(x)= x1-3x2+3x12+4x22-2x1x2s.t 2x1+x22 -x1+4x23程序：f=1;-3H=6 -2;-2 8A=2 1;-1 4b=2;3X,fval,exitflag=quadprog(H,f,A,b)结果：X = -0.0455 0.3636fval = -0.5682exitflag = 1例2：求解：二次规划问题min x12+2x22-2x1x2-4x1-12x2s.t x1+x22 -x1+2x22 2x1+x230x1, 0x2程序：H=2 -2;-2 4;f=-4;-12;A=1 1;-1 2;2 1;b=2;2;3;lb=zeros(2,1);x,fval,exitflag=quadprog(H,f,A,b,lb)结果：x = 0.6667 1.3333fval = -16.4444exitflag = 1练习1 求解下面二次规划问题sub.to 解：则，在MATLAB中实现如下：H = 1 -1; -1 2 ;f = -2; -6;A = 1 1; -1 2; 2 1;b = 2; 2; 3;lb = zeros(2,1);x,fval,exitflag,output,lambda = quadprog(H,f,A,b, , ,lb)结果为：x = %最优解 0.6667 1.3333fval = %最优值 -8.2222exitflag = %收敛 1output = iterations: 3 algorithm: medium-scale: active-set firstorderopt: cgiterations: lambda = lower: 2x1 double upper: 2x1 double eqlin: 0x1 double ineqlin: 3x1 double lambda.ineqlinans = 3.1111 0.4444 0 lambda.lowerans = 0 0说明 第1、2个约束条件有效，其余无效。练习2 求二次规划的最优解max f (x1, x2)=x1x2+3sub.to x1+x2-2=0解：化成标准形式： sub.to x1+x2=2在Matlab中实现如下：H=0,-1;-1,0;f=0;0;Aeq=1 1;beq=2;x,fval,exitflag,output,lambda = quadprog(H,f, , ,Aeq,beq)结果为：x = 1.0000 1.0000fval = -1.0000exitflag = 1output = firstorderopt: 0 iterations: 1 cgiterations: 1 algorithm: 1x58 charlambda = eqlin: 1.0000 ineqlin: lower: upper: 2 最小二乘最优问题1 约束线性最小二乘有约束线性最小二乘的标准形式为sub.to 其中：C、A、Aeq为矩阵；d、b、beq、lb、ub、x是向量。函数 lsqlin 格式 x = lsqlin(C,d,A,b) %求在约束条件下，方程Cx = d的最小二乘解x。x = lsqlin(C,d,A,b,Aeq,beq) %Aeq、beq满足等式约束，若没有不等式约束，则设A= ，b= 。x = lsqlin(C,d,A,b,Aeq,beq,lb,ub) %lb、ub满足，若没有等式约束，则Aeq= ，beq= 。x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0) % x0为初始解向量，若x没有界，则lb= ，ub= 。x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options) % options为指定优化参数x,resnorm = lsqlin() % resnorm=norm(C*x-d)2，即2-范数。x,resnorm,residual = lsqlin() %residual=C*x-d，即残差。x,resnorm,residual,exitflag = lsqlin() %exitflag为终止迭代的条件x,resnorm,residual,exitflag,output = lsqlin() % output表示输出优化信息x,resnorm,residual,exitflag,output,lambda = lsqlin() % lambda为解x的Lagrange乘子例1 求解下面系统的最小二乘解系统：Cx=d约束：；先输入系统系数和x的上下界：C = 0.9501 0.7620 0.6153 0.4057; 0.2311 0.4564 0.7919 0.9354; 0.6068 0.0185 0.9218 0.9169; 0.4859 0.8214 0.7382 0.4102; 0.8912 0.4447 0.1762 0.8936;d = 0.0578; 0.3528; 0.8131; 0.0098; 0.1388;A = 0.2027 0.2721 0.7467 0.4659; 0.1987 0.1988 0.4450 0.4186; 0.6037 0.0152 0.9318 0.8462;b = 0.5251; 0.2026; 0.6721;lb = -0.1*ones(4,1);ub = 2*ones(4,1);然后调用最小二乘命令：x,resnorm,residual,exitflag,output,lambda = lsqlin(C,d,A,b, , ,lb,ub);结果为：x = -0.1000 -0.1000 0.2152 0.3502resnorm = 0.1672residual = 0.0455 0.0764 -0.3562 0.1620 0.0784exitflag = 1 %说明解x是收敛的output = iterations: 4 algorithm: medium-scale: active-set firstorderopt: cgiterations: lambda = lower: 4x1 double upper: 4x1 double eqlin: 0x1 double ineqlin: 3x1 double通过lambda.ineqlin可查看非线性不等式约束是否有效。2 非线性数据（曲线）拟合非线性曲线拟合是已知输入向量xdata和输出向量ydata，并且知道输入与输出的函数关系为ydata=F(x, xdata)，但不知道系数向量x。今进行曲线拟合，求x使得下式成立：函数 lsqcurvefit格式 x = lsqcurvefit(fun,x0,xdata,ydata)x = lsqcurvefit(fun,x0,xdata,ydata,lb,ub)x = lsqcurvefit(fun,x0,xdata,ydata,lb,ub,options)x,resnorm = lsqcurvefit()x,resnorm,residual = lsqcurvefit()x,resnorm,residual,exitflag = lsqcurvefit()x,resnorm,residual,exitflag,output = lsqcurvefit()x,resnorm,residual,exitflag,output,lambda = lsqcurvefit()x,resnorm,residual,exitflag,output,lambda,jacobian =lsqcurvefit()参数说明：x0为初始解向量；xdata，ydata为满足关系ydata=F(x, xdata)的数据；lb、ub为解向量的下界和上界，若没有指定界，则lb= ，ub= ；options为指定的优化参数；fun为拟合函数，其定义方式为：x = lsqcurvefit(myfun,x0,xdata,ydata)，其中myfun已定义为 function F = myfun(x,xdata)F = % 计算x处拟合函数值fun的用法与前面相同；resnorm=sum (fun(x,xdata)-ydata).2)，即在x处残差的平方和；residual=fun(x,xdata)-ydata，即在x处的残差；exitflag为终止迭代的条件；output为输出的优化信息；lambda为解x处的Lagrange乘子；jacobian为解x处拟合函数fun的jacobian矩阵。例2 求解如下最小二乘非线性拟合问题已知输入向量xdata和输出向量ydata，且长度都是n，拟合函数为即目标函数为其中：初始解向量为x0=0.3, 0.4, 0.1。解：先建立拟合函数文件，并保存为ff4.mfunction F = ff4(x,xdata)F = x(1)*xdata.2 + x(2)*sin(xdata) + x(3)*xdata.3;然后给出数据xdata和ydataxdata = 3.6 7.7 9.3 4.1 8.6 2.8 1.3 7.9 10.0 5.4;ydata = 16.5 150.6 263.1 24.7 208.5 9.9 2.7 163.9 325.0 54.3;x0 = 10, 10, 10; %初始估计值x,resnorm = lsqcurvefit(ff4,x0,xdata,ydata)结果为：Optimization terminated successfully:Relative function value changing by less than OPTIONS.TolFunx = 0.2269 0.3385 0.3021resnorm = 6.29503 非线性最小二乘非线性最小二乘（非线性数据拟合）的标准形式为其中：L为常数在6.0版中使用函数lsqnonlin。设则目标函数可表达为其中：x为向量，F(x)为函数向量。函数 lsqnonlin格式 x = lsqnonlin(fun,x0) %x0为初始解向量；fun为，i=1,2,m，fun返回向量值F，而不是平方和值，平方和隐含在算法中，fun的定义与前面相同。x = lsqnonlin(fun,x0,lb,ub) %lb、ub定义x的下界和上界：。x = lsqnonlin(fun,x0,lb,ub,options) %options为指定优化参数，若x没有界，则lb= ，ub= 。x,resnorm = lsqnonlin() % resnorm=sum(fun(x).2)，即解x处目标函数值。x,resnorm,residual = lsqnonlin() % residual=fun(x)，即解x处fun的值。x,resnorm,residual,exitflag = lsqnonlin() %exitflag为终止迭代条件。x,resnorm,residual,exitflag,output = lsqnonlin() %output输出优化信息。x,resnorm,residual,exitflag,output,lambda = lsqnonlin() %lambda为Lagrage乘子。x,resnorm,residual,exitflag,output,lambda,jacobian =lsqnonlin() %fun在解x处的Jacobian矩阵。例3 求下面非线性最小二乘问题初始解向量为x0=0.3, 0.4。解：先建立函数文件，并保存为myfun.m，由于lsqnonlin中的fun为向量形式而不是平方和形式，因此，myfun函数应由建立： k=1,2,10function F = ff5(x)k = 1:10;F = 2 + 2*k-exp(k*x(1)-exp(k*x(2);然后调用优化程序：x0 = 0.3 0.4；x,resnorm = lsqnonlin(ff5,x0) 结果为：Optimization terminated successfully:Norm of the current step is less than OPTIONS.TolXx = 0.2578 0.2578resnorm = %求目标函数值 124.3622例4求 minf=4(x2-x1)2+(x2-4)2 ，选择初始点x0(1,1)程序：先建立m文件：Function f=ff6(x)f(1)=2*x(2)-2*x(1);f(2)=x(2)-4然后：调用x,resnorm，residual=lsqnonlin(ff6,1,1)结果：x = 3.9896 3.9912resnorm = 5.0037e-0094 非负线性最小二乘非负线性最小二乘的标准形式为：sub.to 其中：矩阵C和向量d为目标函数的系数，向量x为非负独立变量。在6.0版中则用函数lsqnonneg。函数 lsqnonneg格式 x = lsqnonneg(C,d) %C为实矩阵，d为实向量x = lsqnonneg(C,d,x0) % x0为初始值且大于0x = lsqnonneg(C,d,x0,options) % options为指定优化参数x,resnorm = lsqnonneg() % resnorm=norm (C*x-d)2x,resnorm,residual = lsqnonneg() %residual=C*x-dx,resnorm,residual,exitflag = lsqnonneg()x,resnorm,residual,exitflag,output = lsqnonneg()x,resnorm,residual,exitflag,output,lambda = lsqnonneg()例5 一个最小二乘问题的无约束与非负约束解法的比较。先输入数据：C = 0.0372 0.2869; 0.6861 0.7071; 0.6233 0.6245; 0.6344 0.6170;d = 0.8587; 0.1781; 0.0747; 0.8405; Cd, lsqnonneg(C,d)ans = -2.5627 0 3.1108 0.6929注意：1。当问题为无约束线性最小二乘问题时，使用MATLAB下的“”运算即可以解决。2对于非负最小二乘问题，调用lsqnonneg(C,d)求解。3 多目标规划模型多目标规划定义为在一组约束下，多个不同的目标函数进行优化设计。数学模型：s.t gj (x) 0 j=1, 2, ,k其中x=(x1 ,x2 , ,xn)为一个n维向量；fi(x)为目标函数，i=1, 2, ,m; gj (x)为系统约束, j=1, 2, ,k。当目标函数处于冲突状态时，不存在最优解使所有目标函数同时达到最优。于是我们寻求有效解(又称非劣解或非支配解或帕累托解)定义：若()的邻域内不存在x，使得(+x)，且则称为有效解。多目标规划问题的几种常用解法：(1) 主要目标法其基本思想是：在多目标问题中，根据问题的实际情况，确定一个目标为主要目标，而把其余目标作为次要目标，并且根据经验，选取一定的界限值。这样就可以把次要目标作为约束来处理，于是就将原来的多目标问题转化为一个在新的约束下的单目标最优化问题。(2) 线性加权和法其基本思想是：按照多目标fi(x) (i=1, 2, ,m)的重要程度，分别乘以一组权系数j(j=1, 2, ,m)然后相加作为目标函数而构成单目标规划问题。即 ，其中例1：某钢铁厂准备用5000万用于A、B两个项目的技术改造投资。设x1、x2分别表示分配给项目A、B的投资。据专家预估计，投资项目A、B的年收益分别为70%和66%。同时，投资后总的风险损失将随着总投资和单项投资的增加而增加，已知总的风险损失为0.02x12+0.01x22+0.04(x1+x2)2，问应如何分配资金才能使期望的收益最大，同时使风险损失为最小。建立数学模型max f1(x)=70x1+66x2min f2(x)= 0.02x12+0.01x22+0.04(x1+x2)2s.t x1+x250000x1, 0x2线性加权构造目标函数： max f=0.5f1(x) 0.5f2(x)化最小值问题： min (-f)=- 0.5f1(x) +0.5f2(x)首先编辑目标函数M文件ff11.mfunction f=ff11(x)f=-0.5*(70*x(1)+66*x(2)+0.5*(0.02*x(1)2+0.01*x(2)2+0.04*(x(1)+x(2)2);调用单目标规划求最小值问题的函数x0=1000,1000A=1 1;b=5000;lb=zeros(2,1);x,fval, exitflag=fmincon(ff11,x0, A,b,lb,)f1=70*x(1)+66*x(2)f2=0.02*x(1)2+0.01*x(2)2+0.04*(x(1)+x(2)2结果：x = 307.1428 414.2857fval = -1.2211e+004exitflag = 1f1 = 4.8843e+004f2 = 2.4421e+004(3) 极大极小法其基本思想是：对于极小化的多目标规划，让其中最大的目标函数值尽可能地小，为此，对每个 xR，我们先求诸目标函数值fi(x)的最大值，然后再求这些最大值中的最小值。即构造单目标规划：(4) 目标达到法对于多目标规划：s.t gj (x) 0 j=1, 2, ,n先设计与目标函数相应的一组目标值理想化向量，再设为一松弛因子标量。设为权值系数向量。于是多目标规划问题化为：在Matlab的优化工具箱中，fgoalattain函数用于解决此类问题。其数学模型形式为：min F(x)-weight goalc(x) 0ceq(x)=0A xbAeq x=beqlbxub其中，x,weight,goal,b,beq,lb和ub为向量，A和Aeq为矩阵，c(x),ceq(x)和F(x)为函数，调用格式：x=fgoalattain(F,x0,goal,weight)x=fgoalattain(F,x0,goal,weight,A,b)x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq)x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub)x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,options)x=fgoalattain(F,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2)x,fval=fgoalattain()x,fval,attainfactor=fgoalattain()x,fval,attainfactor,exitflag,output=fgoalattain()x,fval,attainfactor,exitflag,output,lambda=fgoalattain()说明：F为目标函数；x0为初值；goal为F达到的指定目标；weight为参数指定权重；A、b为线性不等式约束的矩阵与向量；Aeq、beq为等式约束的矩阵与向量；lb、ub为变量x的上、下界向量；nonlcon为定义非线性不等式约束函数c(x)和等式约束函数ceq(x)；options中设置优化参数。x返回最优解；fval返回解x处的目标函数值；attainfactor返回解x处的目标达到因子；exitflag描述计算的退出条件；output返回包含优化信息的输出参数；lambda返回包含拉格朗日乘子的参数。例2：某化工厂拟生产两种新产品A和B，其生产设备费用分别为2万元/吨和5万元/吨。这两种产品均将造成环境污染，设由公害所造成的损失可折算为A为4万元/吨，B为1万元/吨。由于条件限制，工厂生产产品A和B的最大生产能力各为每月5吨和6吨，而市场需要这两种产品的总量每月不少于7吨。试问工厂如何安排生产计划，在满足市场需要的前提下，使设备投资和公害损失均达最小。该工厂决策认为，这两个目标中环境污染应优先考虑，设备投资的目标值为20万元，公害损失的目标为12万元。 建立数学模型：设工厂每月生产产品A为x1吨，B为x2吨，设备投资费为f(x1),公害损失费为f(x2),则问题表达为多目标优化问题：min f1(x)=2x1+5x2min f2(x)=4x1+x2s.t x15 x26x1+x27x1 ,x20程序：首先编辑目标函数M文件ff12.mfunction f=ff12(x)f(1)=2*x(1)+5*x(2);f(2)= 4*x(1) +x(2);按给定目标取：goal=20,12;weight=20,12;x0=2,2A=1 0; 0 1;-1 -1;b=5 6 -7;lb=zeros(2,1);x,fval,attainfactor,exitflag=fgoalattain(ff12,x0,goal,weight,A,b,lb,)结果：x = 2.9167 4.0833fval = 26.2500 15.7500attainfactor = 0.3125exitflag = 1例3：某工厂生产两种产品甲和乙，已知生产甲产品100公斤需6个工时，生产乙产品100公斤需8个工时。假定每日可用的工时数为48工时。这两种产品每100公斤均可获利100元。乙产品较受欢迎，且若有个老顾客要求每日供应他乙种产品500公斤，问应如何安排生产计划？建立数学模型：设生产甲、乙两种产品的数量分别为x1和x2(以100公斤计)，要使生产计划比较合理，应考虑用工时尽量少，获利尽量大，其用多目标规划描述这：min f1=6x1+8x2max f2=100(x1+x2)max f3=x2s.t 6x1+8x248 x25 x1 ,x20将其标准化为：min f1=6x1+8x2min - f2=-100(x1+x2)min - f3=-x2s.t 6x1+8x248 -x2-5 x1 ,x20程序：首先编辑目标函数M文件ff13.mfunction f=ff13(x)f(1)=6*x(1)+8*x(2);f(2)= -100*(x(1) +x(2);f(3)=-x(2);按给定目标取：goal=48 -1000 -5;weight=48 -1000 -5;x0=2 2;A=6 8; 0 -1;b=48 -5;lb=zeros(2,1);x,fval,attainfactor,exitflag=fgoalattain(ff13,x0,goal,weight,A,b,lb,)结果：x = 1.3333 5.0000fval = 48.0000 -633.3333 -5.0000attainfactor = 1.6338e-008exitflag = 1即生产计划为每日生产甲产品133.33公斤，生产乙产品500公斤。4最大最小化模型基本思想：在对策论中，我们常遇到这样的问题：在最不利的条件下，寻求最有利的策略。在实际问题中也有许多求最大值的最小化问题。例如急救中心选址问题就是要规划其到所有地点最大距离的最小值。在投资规划中要确定最大风险的最低限度等等。为此，对每个xR,我们先求诸目标值fi(x)的最大值，然后再求这些最大值中的最小值。最大最小化问题的数学模型：求解最大最小化问题的函数为 fminimax调用格式：x=fminimax(F,x0,)x=fminimax(F,x0,A,b)x=fminimax(F,x0,A,b,Aeq,beq)x=fminimax(F,x0,A,b,Aeq,beq,lb,ub)x=fminimax(F,x0,A,b,Aeq,beq,lb,ub,nonlcon)x=fminimax(F,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)x=fminimax(F,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2)x,fval=fminimax()x,fval,maxfval=fminimax()x,fval,maxfval,exitflag,output=fminimax()x,fval,maxfval,exitflag,output,lambda=fminimax()说明：F为目标函数；x0为初值； A、b为线性不等式约束的矩阵与向量；Aeq、beq为等式约束的矩阵与向量；lb、ub为变量x的上、下界向量；nonlcon为定义非线性不等式约束函数c(x)和等式约束函数ceq(x)；options中设置优化参数。x返回最优解；fval返回解x处的目标函数值；maxfval返回解x处的最大函数值；exitflag描述计算的退出条件；output返回包含优化信息的输出参数；lambda返回包含拉格朗日乘子的参数。例1 求解下列最大最小值问题： 首先编辑M文件ff14.mfunction f=ff14(x)f(1)=3*x(1)2+2*x(2)2-12*x(1)+35;f(2)=5*x(1)*x(2)-4*x(2)+7;f(3)=x(1)2+6*x(2);f(4)=4*x(1)2+9*x(2)2-12*x(1)*x(2)+20;取初值x0=(1,1)调用优化函数x0=1 1;x,fval=fminimax(ff14,x0)结果：x = 1.7637 0.531