最优化-刘志斌-课后习题3-5参考答案(6)

可得X??[1.3,0.7]T；对应f1?f2?3.38从而X??[1.3,0.7]T为原问题的解。

附习题中用过的Matlab程序 1、bbmethod

function [x,y]=bbmethod(f,G,h,Geq,heq,lb,ub,x,id,options)

%整数线性规划分支定界法，可求解纯整数规划和混合整数规划。 %y=minf’*x s.t. G*x<=h Geq*x=heq x为全整数或混合整数列向量 %用法

%[x,y]=bbmethod(f,G,h,Geq,heq,lb,ub,x,id,options) %参数说明

%lb:解的下界列向量（Default:-int） %ub:解的上界列向量（Default:int） %x:迭代初值列向量

%id：整数变量指标列向量，1-整数，0-实数（Default:1） global upper opt c x0 A b Aeq beq ID options;

if nargin<10,options=optimset({});options.Display='off'; options.LargeScale='off';end if nargin<9,id=ones(size(f));end if nargin<8,x=[];end

if nargin<7 |isempty(ub),ub=inf*ones(size(f));end if nargin<6 |isempty(lb),lb=zeros(size(f));end if nargin<5,heq=[];end if nargin<4,Geq=[];end

upper=inf;c=f;A=G; b=h;Aeq=Geq;beq=heq;x0=x;ID=id; ftemp=IntLP(lb(:),ub(:)); x=opt;y=upper; %下面是子函数

function ftemp=IntLP(vlb,vub)

global upper opt c x0 A b Aeq beq ID options;

[x,ftemp,how]=linprog(c,A,b,Aeq,beq,vlb,vub,x0,options); if how <=0 return;

end;

if ftemp-upper>0.00005 %in order to avoid error return; end;

if max(abs(x.*ID-round(x.*ID)))<0.00005

if upper-ftemp>0.00005 %in order to avoid error opt=x';upper=ftemp; return; else

opt=[opt;x']; return; end; end;

notintx=find(abs(x-round(x))>=0.00005); %in order to avoid error intx=fix(x);tempvlb=vlb;tempvub=vub; if vub(notintx(1,1),1)>=intx(notintx(1,1),1)+1; tempvlb(notintx(1,1),1)=intx(notintx(1,1),1)+1; ftemp=IntLP(tempvlb,vub); end;

if vlb(notintx(1,1),1)<=intx(notintx(1,1),1) tempvub(notintx(1,1),1)=intx(notintx(1,1),1); ftemp=IntLP(vlb,tempvub); end;

2、golds.m

function [s,phis,k,G,E]=golds(phi,a,b,delta,epsilon) %功能: 0.618法精确线搜索

%输入: phi是目标函数, a, b 是搜索区间的两个端点 % delta, epsilon分别是自变量和函数值的容许误差 %输出: s, phis分别是近似极小点和极小值, G是nx4矩阵, % 其第k行分别是a,p,q,b的第k次迭代值[ak,pk,qk,bk], % E=[ds,dphi], 分别是s和phis的误差限.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% t=(sqrt(5)-1)/2; h=b-a; phia=feval(phi,a); phib=feval(phi,b); p=a+(1-t)*h; q=a+t*h; phip=feval(phi,p); phiq=feval(phi,q); k=1; G(k,:)=[a, p, q, b];

while(abs(phib-phia)>epsilon)|(h>delta) if(phip

b=q; phib=phiq; q=p; phiq=phip; h=b-a; p=a+(1-t)*h; phip=feval(phi,p); else

a=p; phia=phip; p=q; phip=phiq; h=b-a; q=a+t*h; phiq=feval(phi,q); end

k=k+1; G(k,:)=[a, p, q, b]; end

ds=abs(b-a); dphi=abs(phib-phia); if(phip<=phiq) s=p; phis=phip; else

s=q; phis=phiq; end E=[ds,dphi]; 3、grad.m

function [x,val,k]=grad(fun,gfun,x0)

% 功能: 用最速下降法求解无约束问题: min f(x) %输入: x0是初始点, fun, gfun分别是目标函数和梯度 %输出: x, val分别是近似最优点和最优值, k是迭代次数. maxk=5000; %最大迭代次数 rho=0.5;sigma=0.4; k=0; epsilon=1e-5; while(k

g=feval(gfun,x0); %计算梯度 d=-g; %计算搜索方向 if(norm(d)

while(m<20) %Armijo搜索

if(feval(fun,x0+rho^m*d)

x0=x0+rho^mk*d; k=k+1; end x=x0;

val=feval(fun,x0);

4、newton.m

function [x,val,k]=newton(fun,gfun,Hess,x0) %功能: 用尼牛顿法求解无约束问题: min f(x)