实验1解线性规划.docx

实 验 报 告 求解线性规划实验（运筹学与最优化方法，4 学时） 一 实验目的 掌握线性规划的求解，会用单纯形法法、大 M 法解线性规划。 二 实验内容 用单纯形法解线性规划： min z ? ?2x 1 3x 2 ? ?x ? x ? 2 ?x 1 2 s.t. ? ? 2x ? 10 ? 1 2 ?3x ? x ? 1 2 ? 15 ?? x , x ? 0 1 2 用大 M 法解线性规划： min z ? ?3x ? x 1 2 2x 3 ? 3x ? 2x ? 3x ? 6 ??s.t. ? 1 ? 2 2 ? x 3 ?4 ? ? x x ? ?1 2 3 ? ?x , x , x ? 0 ? 1 2 3 3.解下列线性规划，考虑其是哪一种特殊情况。 max z ? 50x 1 ? 40x 2 ?3x ? 5x ? 150 ? 1 x 2 （1） ? ? 20 2 （无解） s.t. ?8x ? 5x ? 300 ?x 1 2 2? 1 ? x ? 50 2 ?? x , x ? 0 1 2 max z ? 20x 1 ?10x 2 ? x ? 2 ?（2） 1 ? s.t. ? （没有边界） ? x 5 ?x ,2 ? 0 ?x ? 1 2 max z ? 30x 1 ? 50x 2 ?3x ? 5x ? 150 ?（3） ? 1 x 2 ? ? 20 （多个最优解） s.t. ?8x ?1 ? 2 5x 2 ? 300 ?? x , x ? 0 1 2 max z ? 50x 1 ? 40x 2 ?3x ? 5x ? 175 ?（4） ? 1 x 2 ? ? 20 s.t. ? ?8x 2 ? 5x ? 300 ?1 2 ? ? x , x ? 0 1 2 三 实验步骤（算法）与结果 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(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)==0sum(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,:)=B(i,:)-B(p,:)*B(i,q); end end if max(t)=0 break; end end D=[B;-t -minf]; for i=1:n-1 if D(m+1,i)==0 for j=1:m if D(j,i)==1 x(1,i)=D(j,n); end  end  end end if min(B(1:m-1,n))==0 disp(此目标规划的解退化) end x=x(1,1:length(c)),minf 运行结果如下： DCXF A=[-1,1;1,2;3,1]; b=[2,10,15]; c=[-2,-3]; E(单位矩阵)=[1,0,0;0,1,0;0,0,1]; y0=[0,0,0,0]; d=[0,0,0,0]; 输出结果为： x = 4 3 minf = -17 解:程序如下： function [x,minf]=DMF(A,c,b,baseVector,Mvector) sz=size(A); nVia=sz(2); n=sz(1); xx=1:nVia; nobase=zeros(1,1); m=1; if c=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; end end for i=1:nVia if(isempty(find(baseVector==xx(i),1))) nobase(m)=i; m=m+1; else end end bCon=1; M=0; B=A(:,baseVe