一、线性规划算法
MATLAB优化算法
调用格式：[x,fval,exitflag]=linprog(f,A,b,Aeq,beq,lb,ub,x0)说明：返回值x为最优解向量，fval为最优值；若没有不等式约束，则令A=[]、b=[]；lb,ub为变量x的下界和上界，x0为初值点；exitflag描述函数计算的退出条件：若为正值，表示目标函数收敛于解x处；若为负值，表示目标函数不收敛；若为零值，表示已经达到函数评价或迭代的最大次数。例1、求解线性规划问题maxf=70x1+120x2s.t9x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000x1,x2≥0将其转换为标准形式：minf=-70x1-120x2s.t9x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000x1,x2≥0算法如下：f=[-70-120];A=[94;45;310];b=[3600;2000;3000];lb=[00];ub=[];[x,fval,exitflag]=linprog(f,A,b,[],[],lb,ub)maxf=-fval例2、求解线性规划问题maxf=0.15x1+0.1x2+0.08x3+0.12x4s.tx1-x2-x3-x4≤0x2+x3-x4≥0x1+x2+x3+x4=1xj≥0，j=1,2,3,4将其转换为标准形式：minz=-0.15x1-0.1x2-0.08x3-0.12x4s.tx1-x2-x3-x4≤0-x2-x3+x4≤0x1+x2+x3+x4=1xj≥0，j=1,2,3,4算法如下：f=[-0.15;-0.1;-0.08;-0.12];A=[1-1-1-1；0-1-11];b=[0;0];Aeq=[1111];beq=[1];lb=zeros(4,1);[x,fval,exitflag]=linprog(f,A,b,Aeq,beq,lb)f=-fval二、二次规划算法
调用格式：[x,fval,exitflag]=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)说明：输入参数中，x0为初始点；若无等式约束或无不等式约束，就将相应的矩阵和向量设置为空。输出参数中，x是返回最优解；fval是返回解所对应的目标函数值；exitflag是描述搜索是否收敛。例3、求解二次规划问题minf(x)=x1-3x2+3x1+4x2-2x1x2s.t2x1+x2≤22
2
-x1+4x2≤3算法如下：f=[1;-3];H=[6-2;-28];A=[21;-14];b=[2;3];[X,fval,exitflag]=quadprog(H,f,A,b)例4、求解二次规划问题mins.tx12+2x22-2x1x2-4x1-12x2x1+x2≤2-x1+2x2≤22x1+x2≤3x1≥0,x2≥0算法如下：H=[2-2;-24];f=[-4;-12];A=[11;-12;21];b=[2;2;3];lb=zeros(2,1);[x,fval,exitflag]=quadprog(H,f,A,b,[],[],lb)三、非线性规划算法
调用格式:[x,fval,exitflag]=fmincon(f,x0,A,b,Aeq,beq,lb,ub,nonlcon)说明：返回值x为最优解向量，fval是返回解所对应的目标函数值；exitflag是描述搜索是否收敛。f为目标函数，x0为初始点，A,b为不等式约束的系数矩阵和右端列向量，若没有不等式约束，则令A=[]、b=[]。lb,ub为变量x的下界和上界；nonlcon=@fun，由M文件fun.m给定非线性不等式约束c(x)≤0和非线性等式约束g(x)=0。例5、求解非线性规划问题min100(x2-x1)+(1-x1)s.tx1≤2;2
2
2
x2≤2首先建立ff6.m文件：functionf=ff6(x)f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;然后在命令窗口键入命令：x0=[1.1,1.1];A=[10;01];b=[2;2];[x,fval,exitflag]=fmincon(@ff6,x0,A,b)例6、求解非线性规划问题minf=e(6x1+3x2+2x1x2+4x2+1)s.tx1x2-x1-x2+1≤0-2x1x2-5≤0首先建立目标函数文件ff8.m文件：functionf=ff8(x)f=exp(x(1))*(6*x(1)^2+3*x(2)^2+2*x(1)*x(2)+4*x(2)+1);再建立非线性的约束条件文件：ff8g.mfunction[c,g]=ff8g(x)c(1)=x(1)*x(2)-x(1)-x(2)+1;c(2)=-2*x(1)*x(2)-5;g=[];然后在命令窗口键入以下命令：x0=[1,1];nonlcon=@ff8g[x,fval,exitflag]=fmincon(@ff8,x0,[],[],[],[],[],[],nonlcon)x1
2
2
四、整数线性规划算法
说明：下面给出用分枝定界法求解整数线性规划的M函数文件ILp.m，其中返回值x为最优解向量，f为最优值；x0为初值点，可以用[]代替；neqcstr表示约束条件Axb中的前neqcstr个是等式，neqcstr=0时可以省略，此时也可以省略x0；vlb,vub为变量x的下界和上界；pre是精度。M函数文件ILp.m如下：function[x,f]=ILp(c,A,b,vlb,vub,x0,neqcstr,pre)ifnargin<8,pre=0;ifnargin<7,neqcstr=0;ifnargin<6,x0=[];ifnargin<5,vub=[];ifnargin<4,vlb=[];end,end,end,end,endx0=x0(:);c=c(:);b=b(:);vlb=vlb(:);vub=vub(:);mm=1;j=1;nvars=length(c’);fvub=inf;xall=[];fall=[];x_f_b=[];[xtempztemp,how]=lp(c,A,b,vlb,vub,x0,neqcstr,-1);ftemp=c’*xtemp;ifstrcmp(how,‘ok’),temp0=round(xtemp);temp1=floor(xtemp);temp2=find(abs(xtemp-temp0)>pre);mtemp=length(temp2);if~isempty(temp2)x_f_b=[xtemp;ftemp;vlb;vub];whilej<=mmi=1;whilei<=mtempifx_f_b(nvars+1,j)<=fvubvlb1=x_f_b(nvars+2:2*nvars+1,j);vub1=x_f_b(2*nvars+2:3*nvars+1,j);vub1(temp2(i))=temp1(temp2(i));[xtempz,how]=lp(c,[A;c’],[b;fvub],vlb1,vub1,x0,neqcstr,-1);ftemp=c’*xtemp;ifstrcmp(how,‘ok’),temp10=round(xtemp);temp11=floor(xtemp);temp12=find(abs(xtemp-temp10)>pre);ifisempty(temp12),xall=[xall,xtemp];fall=[fall,ftemp];fvub=min([fvub,fall]);elseifftemp<=fvubx_f_b=[x_f_b,[xtemp;ftemp;vlb1;vub1]];end,end,endifx_f_b(nvars+1,j)<=fvubvlbr=x_f_b(nvars+2:2*nvars+1,j);vlbr(temp2(i))=temp1(temp2(i))+1;vubr=x_f_b(2*nvars+2:3*nvars+1,j);[xtempz,how]=lp(c,[A;c’],[b;fvub],vlbr,vubr,x0,neqcstr,-1);ftemp=c’*xtemp;ifstrcmp(how,‘ok’),tempr0=round(xtemp);tempr1=floor(xtemp);tempr2=find(abs(xtemp-tempr0)>pre);ifisempty(tempr2),xall=[xall,xtemp];fall=[fall,ftemp];fvub=min([fvub,fall]);elseifftemp<=fvubx_f_b=[x_f_b,[xtemp;ftemp;vlbr;vubr]];end,end,endi=i+1;endxint=x_f_b(1:nvars,:);[m,mm]=size(xint);j=j+1;ifj>mm,break,endtemp0=round(xint(:,j));temp1=floor(xint(:,j));temp2=find(abs(xint(:,j)-temp0)>pre);mtemp=length(temp2);end,else,x=xtemp;f=ftemp;end,if~isempty(fall)fmin=min(fall);nmin=find(fall==fmin);x=xall(:,nmin);f=fmin;end,else,x=nan*ones(1,nvars);end例7、求解整数线性规划问题maxf=20x1+10x2s.t5x1+4x2≤242x1+5x2≤13xj≥0，i=1,2x1,x2为整数先建立M函数文件ILp.m，然后在MATLAB命令窗口键入：clear;c=[-20,-10];%求max转换为求mina=[5,4;2,5];b=[24;13];[x,f]=ILp(c,a,b,[0;0],[inf;inf],[],0,0.0001)f=-f五、0-1整数线性规划算法
说明：下面的隐枚举法求解0—1线性规划的M函数文件L01p_ie.m中用到命令B=de2bi(D)，其作用是将十进制数向量D转换为相应的二进制数按位构成的以0，1为元素的矩阵B。M函数文件de2bi.m如下：functionb=de2bi(d,n,p)d=d(:);len_d=length(d);ifmin(d)<0,error(‘Cannotconvertanegativenumber’);elseif~isempty(find(d==inf)),error(‘InputmustbeanInf.’);elseiffind(d~=floor(d)),error(‘Inputmustbeaninteger.’);end;ifnargin<2,tmp=max(d);b1=[];whiletmp>0b1=[b1rem(tmp,2)];tmp=floor(tmp/2);end;n=length(b1);end;ifnargin<3,p=2;end;b=zeros(len_d,n);fori=1:len_dj=1;tmp=d(i);while(j<=n)&(tmp>0)b(i,j)=rem(tmp,p);tmp=floor(tmp/p);j=j+1;end;end;说明：下面给出用隐枚举法求解0—1线性规划的M函数文件L01p_ie.m，其中返回值x为最优解向量，f为最优值；N表示约束条件Axb中的前N个是等式，N=0时可以省略。M函数文件L01p_ie.m如下：function[x,f]=L01p_ie(c,A,b,N)ifnargin<4,N=0;endc=c(:);b=b(:);A=[-A(1:N,:);A];b=[-b(1:N);b];[m,n]=size(A);x=[];f=abs(c’)*ones(n,1);A=[c’;A];b=[f;b];i=1;whilei<=2^nB=de2bi(i-1,n)’;j=1;t1=A(j,:)*B-b(j);while(t1<=0&j 因篇幅问题不能全部显示，请点此查看更多更全内容