1、实验1解线性规划实 验 报 告求解线性规划实验(运筹学与最优化方法,4学时)一 实验目的掌握线性规划的求解,会用单纯形法法、大M法解线性规划。二 实验内容1 用单纯形法解线性规划:2 用大M法解线性规划:3.解下列线性规划,考虑其是哪一种特殊情况。(1)(无解)(2)(没有边界)(3)(多个最优解)(4)三 实验步骤(算法)与结果1解:程序如下:A=input(A=);b=input(b=);c=input(c=);E=input(E(单位矩阵)=);y0=input(y0=);d=input(d=);N=10000;B=A,E,b;c,d;m,n=size(B);C=c,d;x=zeros(
2、1,length(c);for k=1:N z=B(:,end); for j=1:n-1 t(j)=y0*B(:,j)-C(j); end for i=1:n-1 if t(i)=0&sum(abs(B(:,i)=1 disp(此目标规划有无数个最优解) end end minf=y0*z; ,q=max(t); W(k)=q; for p=1:m-1 if B(p,W(k)=0 r(p)=N; else r(p)=z(p)/B(p,W(k); end end ,p=min(r); y0(p)=C(q); B(p,:)=B(p,:)/B(p,q); for i=1:m if i=p B(i,
3、:)=B(i,:)-B(p,:)*B(i,q); end end if max(t)=0 vr=find(c=0,1,last); rgv=(A(:,(nVia-n+1):nVia)b; if rgv=0 x=zeros(1,vr); minf=0; else disp(不存在最优解); x=NaN; minf=NaN; return; endendfor i=1:nVia if(isempty(find(baseVector=xx(i),1) nobase(m)=i; m=m+1; else endend bCon=1;M=0;B=A(:,baseVector);invB=inv(B); w
4、hile bCon nB=A(:,nobase); ncb=c(nobase); B=A(:,baseVector); cb=c(baseVector); xb=Bb; w=cb/B; for i=1:length(nobase) sigma(i)=w*nB(:,i)-ncb(i); end maxs,ind=max(sigma); if maxs=0 minf=cb*xb; vr=find(c=0,1,last); for l=1:vr ele=find(baseVector=l,1); if(isempty(ele) x(l)=0; else x(l)=xb(ele); end end b
5、Con=0; else y=BA(:,nobase(ind); if y0 bz=xb(j)/y(j); if bzminb minb=bz; chagB=j; end end end tmp=baseVector(chagB); baseVector(chagB)=nobase(ind); nobase(ind)=tmp; for j=1:chagB-1 if y(j)=0 invB(j,:)=invB(j,:)-invB(chagB,:)*y(j)/y(chagB); end end for j=chagB+1:length(y) if y(j)=0 invB(j,:)=invB(j,:)
6、-invB(chagB,:)*y(j)/y(chagB); end end invB(chagB,:)=invB(chagB,:)/y(chagB); end end M=M+1; if(M=1000000) disp(找不到最优解); x=NaN; minf=NaN; return; endendfor i=1:length(Mvector) if x(Mvector(i)=0 x=NaN; minf=NaN; disp(此目标规划无解); endend运行如下:3.解:后面的题选用matlab自带求解函数求解,以熟悉matlab的最优化求解操作;(1)首先建立目标函数文件夹:functio
7、n f=F(x)f=-50*x(1)+40*x(2);在运行窗口输入:x0=1,1;A=3,5;0,1;8,5;-1,-1;b=150;20;300;-50;lb=0;0;x,f=fmincon(F,x0,A,b,lb,)运行得:x = 29.9373 12.2257f = -1.9859e+03但是注意到运行结果提示:No feasible solution found.也就是说这个优化问题没有最有解。(2)建立目标函数文件:function f=F(x)f=-20*x(1)-10*x(2);在运行窗口输入:x0=1,1;A=-1,0;0,1;b=-2;5;lb=0;0;x,f=fminco
8、n(F,x0,A,b,lb,)输出结果为:x = 1.0e+18 * 8.1148 0.0000f = -1.6230e+20提示是:Problem appears unbounded.也就是说目标函数无边界。(3) 建立目标函数文件:function f=F(x)f=-30*x(1)-50*x(2);在运行窗口输入:x0=1,1;A=3,5;0,1;8,5;b=150;20;300;lb=0;0;x,f=fmincon(F,x0,A,b,lb,)输出结果为:x = 16.6764 19.9942f = -1.5000e+03提示为:Local minimum found that satis
9、fies the constraints.满足局部的最小值,也就是目标函数有多个最优解。(4) 建立目标函数文件:function f=F(x)f=-50*x(1)-40*x(2);在运行窗口输入:x0=1,1;A=3,5;0,1;8,5;b=175;20;300;lb=0;0;x,f=fmincon(F,x0,A,b,lb,)输出结果和第(3)一样。四 实验收获与教师评语收获:运用自己编写的程序来解题确实不够完善,只能针对部分类型的题目,与软件本身设计的函数有很大不同。通过这次实验发现自己的编译能力还是很差,很多问题找不到在哪,怎么解决,于是在参考同学后得以解决。最后通过软件自带函数解决问题熟悉软件的操作收益也是良多。