资源描述：
《运筹学外点法.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、（一）实验目的熟练掌握外点法、内点法原理并可以在matlab熟练运行。（二）问题描述目标函数：z=minx1+x2s.t.–x12+x2≥0x1≥0(三)算法介绍外点法：对于混合约束问题minf(x)s.t.six≥0,i=1:mhjx=0,i=1:n可以转化为：minF(x,σ)=f(x)+σ([max{0,-s1x}]2+max0,-s2x2+……+max0,-smx2+h1x2+h2x2+…+hnx2)=f(x)+σ(i=1m[max{0,-smx}]2+j=1nhj2其中，P(x)=i=1mmax0
2、,-smx2+j=1nhj2F(x,σ)：增广目标函数P(x)：惩罚函数，σ：罚因子外部惩罚函数法迭代步骤：给定初始点x0，初始惩罚因子σ1，放大系数c>1，ε>0置k:=1Step1：以xk-1为初始点求解minF（x,σk）得极小点xkStep2：若σkPxk<ε,stopStep3：σk+1=cσk，置k≔k+1转step1注意外点法在选取初始点时要选取在可行域外的点。在本问题中x0=[-1;-1],c=10，ε=0.01，σ1=1内点法：这种解法只能用于不等式对于约束问题minf(x)s.t.six
3、≥0,i=1:m可以转化为：minF(x,σ)=f(x)+μ（1s1x+1s2x+…+1smx）其中μ为一个小正数内部惩罚函数法迭代步骤：已知f(x),six,取βx=1s1x+1s2x+…+1smx给定初始点x0，初始惩罚因子μ1，放大系数1>c>0，ε>0置k:=1Step1：以xk-1为初始点求解minF（x,μk）得极小点xkStep2：若μkPxk<ε,stopStep3：μk=cμk，置k≔k+1转step1在本问题中x0=[0.03;0.03],c=0.2，ε=0.001，μ1=0.1注意内点
4、法在选取初始点时要选取在可行域内的点。其中以xk-1为初始点求解minF（x,σk）得极小点xk的求解过程我们利用最速下降法得到（四）程序代码及运行结果：（1）外点法源程序代码：functionf=again(x,c,e)symsx1x2ta=1;f=x1+x2;y1=-x1^2+x2;y2=x1;y1=-subs(y1,{x1,x2},x);y2=-subs(y2,{x1,x2},x);P=(max(0,double(y1)))^2+(max(0,double(y2)))^2;ifdouble(y1)>0
5、&&double(y2)>0y11=-x1^2+x2;y22=x1;endifdouble(y1)<=0&&double(y2)>0y11=0;y22=x1;endifdouble(y2)<=0&&double(y1)>0y11=-x1^2+x2;y22=0;endFF=f+a*(y11^2+y22^2);a1=diff(FF,x1);b1=diff(FF,x2);a1=subs(a1,{x1,x2},x);b1=subs(b1,{x1,x2},x);g=[a1;b1];d=-g;whileP*a>ewhi
6、ledouble(sqrt(a1^2+b1^2))>0.5x=x+t*d;FF=subs(FF,{x1,x2},x);f1=diff(FF);f1=solve(f1);iff1~=0ti=double(f1);elsebreakendx=subs(x,t,ti(1,1));FF=f+a*(y11^2+y22^2);a11=diff(FF,x1);b11=diff(FF,x2);a11=subs(a11,{x1,x2},x);b11=subs(b11,{x1,x2},x);g11=[a11;b11];d=-g
7、11;a1=a11;b1=b11;enda=a*c;y1=-x1^2+x2;y2=x1;y1=-subs(y1,{x1,x2},x);y2=-subs(y2,{x1,x2},x);P=(max(0,double(y1)))^2+(max(0,double(y2)))^2;ifdouble(y1)>0&&double(y2)>0y11=-x1^2+x2;y22=x1;endifdouble(y1)<=0&&double(y2)>0y11=0;y22=x1;endifdouble(y2)<=0&&double(
8、y1)>0y11=-x1^2+x2;y22=0;endFF=f+a*(y11^2+y22^2);a1=diff(FF,x1);b1=diff(FF,x2);a1=subs(a1,{x1,x2},x);b1=subs(b1,{x1,x2},x);g=[a1;b1];d=-g;endx,a（2）在matlab对话框中输入again([-1;-1],10,0.01)，外点法得到结果为：x=1.0e-003*-0.467
