单纯形法SimpleMthd

1、单纯形法函数：SimpleMthd用单纯形算法解如下线性规划问题的步骤如下：（1） 确定初始基变量矩阵；求解方程；（2） 令，计算；其中和分别代表基变量和非基变量的值，表示基变量在目标函数中的系数；（3） 求解方程，对于所有非基变量计数判别数，其中为非基变量在约束系数矩阵中相对应的列，令，如果，则停止计算，输出最优解，否则转步骤4；（4） 求解方程，若的每个分量均大于0，则问题不存在最优解，否则转步骤5；（5） 令，其中，用代替，得到新的基变量矩阵再转步骤2计算。调用格式：其中，：约束矩阵； ：目标函数系数向量； ：约束右端向量； ：初始向量，basic； ：目标函数取最小值时自由变量值； ：

2、目标函数的最小值；单纯形法函数的MATLAB程序代码如下：function x,minf=SimpleMthd(A,c,b,baseVector)%约束矩阵：A;%目标函数系数向量:c;%约束右端向量:b;%初始基向量：baseVector;%目标函数取最小值时的自变量值:x;%目标函数最小值:minf;sz=size(A);nVia=sz(2);n=sz(1);xx=1:nVia;nobase=zeros(1,1);m=1;for i=1:nVia if(isempty(find(baseVector=xx(i),1) nobase(m)=i; m=m+1; else ; endendbCo

3、n=1;M=0;while bCon nB=A(:,nobase); %非基变量矩阵 ncb=c(nobase); %非基变量系数 B=A(:,baseVector);%基变量矩阵 cb=c(baseVector); %基变量系数 xb=inv(B)*b; f=cb*xb; w=cb*inv(B); for i=1:length(nobase) sigma(i)=w*nB(:,i)-ncb(i); end maxs,ind=max(sigma); %ind为进基变量下标 if maxs<=0 %最大值小于零，输出最优解 minf=cb*xb; vr=find(c=0,1,'las

4、t'); for l=1:vr ele=find(baseVector=l,1); if(isempty(ele) x(l)=0; else x(l)=xb(ele); end end bCon=0; else y=inv(B)*A(:,nobase(ind); if y<=0 %不存在最优解 disp('不存在最优解！'); x=NaN; minf=NaN; return; else %寻找出基变量 minb=inf; chagB=0; for j=1:length(y) if y(j)>0 bz=xb(j)/y(j); if bz<minb min

5、b=bz; chagB=j; end end end tmp=baseVector(chagB);%更新基矩阵和非基矩阵 baseVector(chagB)=nobase(ind); noase(ind)=tmp; end end M=M+1; if (M=1000000) %迭代步数限制 disp('找不到最优解'); x=NaN; minf=NaN; return; endend当目标函数的自变量系数全都大于0时，一定要小心。为解决这个问题，可以在代码中加入如下语句：if c>=0 vr=find(c=0,1,'last'); rgv=inv(A(:,

6、(nVia-n+1):nVia)*b; if rgv>=0 else disp('不存在最优解！'); x=NaN; minf=NaN; return; endend因此完整的单纯形的MATLAB程序如下：function x,minf=CmpSimpleMthd(A,c,b,baseVector)%约束矩阵：A;%目标函数系数向量:c;%约束右端向量:b;%初始基向量：baseVector;%目标函数取最小值时的自变量值:x;%目标函数最小值:minf;sz=size(A);nVia=sz(2);n=sz(1);xx=1:nVia;nobase=zeros(1,1);m

7、=1;if c>=0 vr=find(c=0,1,'last'); rgv=inv(A(:,(nVia-n+1):nVia)*b; if rgv>=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 ; endendbCon=1;M=0;while bCon nB=A(:,nobase); %非基变量矩阵 ncb=c(nobase); %非基变量系

8、数 B=A(:,baseVector);%基变量矩阵 cb=c(baseVector); %基变量系数 xb=inv(B)*b; f=cb*xb; w=cb*inv(B); for i=1:length(nobase) sigma(i)=w*nB(:,i)-ncb(i); end maxs,ind=max(sigma); %ind为进基变量下标 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 bCon=0; else y=inv(B)*A(:,nobase(ind); if y<=0 %不存在最优解 disp('不存在最优解！'); x=NaN; minf=NaN; return; else %寻找出基变量 minb=inf; chagB=0; for j=1:length(y) if y(j)>0 bz=xb(j)/y(j); if bz<minb minb=bz; chagB=j; end end end tmp=baseVector(chagB);%更新基矩阵和非基矩阵