数
学
软
件
与
实
验
数学与信息科学学院
信息与计算科学
单纯形法的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);。