数 学 软 件 与 实 验 数学与信息科学学院 信息与计算科学 单纯形法的Matlab 程序如下： function [xx,fm]=myprgmh(m,n,A,b,c) B0=A(:,1:m); cb=c(:,1:m); xx=1:n; sgm=c-cb*B0^-1*A; h=-1; sta=ones(m,1); for i=m+1:n if sgm(i)>0 h=1; end end while h>0 [msg,mk]=max(sgm); for i=1:m sta(i)=b(i)/A(i,mk); end [mst,mr]=min(sta); zy=A(mr,mk); for i=1:m if i==mr for j=1:n A(i,j)=A(i,j)/zy; end b(i)=b(i)/zy; end end for i=1:m if i~=mr for j=1:n A(i,j)=A(i,j)-A(i,mk)*A(mr,j); end b(i)=b(i)-A(i,mk)*b(mr); end end B1=A(:,1:m); cb(mr)=c(mk); xx(mr)=mk; sgm=c-cb*B1*A; for i=m+1:n if sgm(i)>0 h=1; end end end fm=c*xx; 例题： 编写下列求解如下线性规划问题的单纯形法函数 min f'x s.t ax<=b(其中 b>=0) 函数形式 function [x,fval,it,op]=singl(f,a,b) 输出中 x 为最优解 fval 为最优值 it 为迭代次数 无最优解 op=0 有最优解 op=1 编写程序如下： function [x,fval,it,op]=singl(f,a,b) [m,n]=size(a); c=[a eye(m) b;f' zeros(1,m+1)]; fval=0; x=zeros(m+n,1); op=1; it=0; e=zeros(1,m); lie=find(f<0); l=length(lie); while(l>0) for j=1:l d=find(c(:,lie(j))); d_l=length(d); if d_l>0 for i=1:m if c(i,lie(j))>0 e(i)=c(i,end)/c(i,lie(j)); else e(i)=inf; end end [g,h]=min(e); for w =1:m+1 if w ==h c(w ,:)=c(w ,:)/c(h,lie(j)); else c(w ,:)=c(w ,:)-c(h,:)*c(w ,lie(j))/c(h,lie(j)); end end it=it+1; else op=0; end end lie=find(c(end,:)<0); l=length(lie); end for i=1:(m+n) ix =find(c(:,i)); if(length(ix )==1)&(ix <=m)&(c(ix ,i)==1) x (i)=c(ix ,end) else x (i)=0 end end fv al=-c(end,end);
