《运筹学外点法》由会员分享，可在线阅读，更多相关《运筹学外点法（6页珍藏版）》请在金锄头文库上搜索。
1、（一） 实验目的熟练掌握外点法、内点法原理并可以在matlab熟练运行。（二） 问题描述目标函数：z=minx1+x2s.t. x12+x20 x10 (三) 算法介绍外点法： 对于混合约束问题 min f(x) s.t. six0,i=1:m hjx=0,i=1:n 可以转化为：min F(x,)=f(x)+ (max0,- s1x2+max0,- s2x2+max0,- smx2+ h1x2+h2x2+hnx2)= f(x)+ (i=1mmax0,- smx2+j=1nhj2其中，P(x)= i=1mmax0,- smx2+j=1nhj2F(x,)：增广目标函数P(x)：惩罚函数 ，：罚因
2、子外部惩罚函数法迭代步骤：给定初始点x0，初始惩罚因子1，放大系数c1，0置k:=1Step1：以xk-1为初始点求解min F（x,k）得极小点xkStep2：若kPxkc0，0置k:=1Step1：以xk-1为初始点求解min F（x,k）得极小点xkStep2：若kPxk0&double(y2)0 y11=-x12+x2; y22=x1;endif double(y1)0 y11=0; y22=x1;end if double(y2)0 y11=-x12+x2; y22=0;endFF=f+a*(y112+y222) ; a1=diff(FF,x1);b1=diff(FF,x2);a1=
3、subs(a1,x1,x2,x);b1=subs(b1,x1,x2,x);g=a1;b1;d=-g;while P*aewhile double(sqrt(a12+b12)0.5 x=x+t*d; FF=subs(FF,x1,x2,x); f1=diff(FF); f1=solve(f1); if f1=0 ti=double(f1); else break end x=subs(x,t,ti(1,1);FF=f+a*(y112+y222); a11=diff(FF,x1); b11=diff(FF,x2); a11=subs(a11,x1,x2,x); b11=subs(b11,x1,x2,
4、x); g11=a11;b11; d=-g11; a1=a11; b1=b11;enda=a*c;y1=-x12+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;if double(y1)0&double(y2)0 y11=-x12+x2; y22=x1;endif double(y1)0 y11=0; y22=x1;end if double(y2)0 y11=-x12+x2; y22=0;endFF=f+a*(y112+y222) ; a1=diff(F
5、F,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.4673 -0.5140a = 10000 其中a为惩罚因子。（3）内点法源程序代码：function f=neidian(x,c,e) syms x1 x2 ta=0.1;f=x1+x2;y1=-x12+x2;y2=x1; FF=f+a*(1/(y1)+(1/(y2) ) ; a1=diff(FF,x1)
6、;b1=diff(FF,x2);a1=subs(a1,x1,x2,x);b1=subs(b1,x1,x2,x);g=a1;b1;d=-g;y1=subs(y1,x1,x2,x);y2=subs(y2,x1,x2,x) ; P=1/double(y1)+1/double(y2);while P*aewhile double(sqrt(a12+b12)0.5 x=x+t*d; FF=subs(FF,x1,x2,x); f1=diff(FF); f1=solve(f1); if f1=0 ti=double(f1); else break end x=subs(x,t,ti(1,1); y1=-x1
7、2+x2; y2=x1; FF=f+a*(1/(y1)+(1/(y2) ) ; a11=diff(FF,x1); b11=diff(FF,x2); a11=subs(a11,x1,x2,x); b11=subs(b11,x1,x2,x); g11=a11;b11; d=-g11; a1=a11; b1=b11;enda=a*c;y1=-x12+x2;y2=x1; FF=f+a*(1/(y1)+(1/(y2) ) ; 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;y1=subs
8、(y1,x1,x2,x);y2=subs(y2,x1,x2,x) ; P=1/double(y1)+1/double(y2);endx,a（4）在matlab对话框中输入neidian(0.03;0.03,0.2,0.001)，内点法得到结果为 ：x = 0.0010 0.0013a = 2.5600e-007（六）结果分析 本题理论算法的最优解为min=0，x1=0，x2=0；但在matlab上运行不能得到理想解，但经过多步迭代我们已经得到了一个非常接近于最优解的值。如果想得到更接近的最优解可通过减小的值使迭代步数增加。（七）心得体会外点法的求解过程中会遇到max这一函数，但是由于max函数中与0比较的函数含有未知量，无法进行比较因此在每次循环前先赋值比较在利用if条件语句重新得到P(x)，而这一过程的获得需要我们在编程之初就进行考虑，否则问题多多。同时，由于我们在本题中进行了循环嵌套，内层循环是利用最速下降法求解每一步的极小点xk，外层循环是惩罚函数精度的限制，因此在每一步内层循环结束后函数的重新赋值需要弄明白否则会发生很多错误。对于内点法体会最深的一点就是初始点，惩罚因子，以及精度选择很重要，选择不当将会导致程序运行出错。
