单纯形法matlab

院（系） 指导教师 专业名称 姓 名 学 号 信息工程与自动化学院 王晓东 仪器仪表专业 李方前 2012704014

单纯形法的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

fval=-c(end,end);