单纯形法：SimpleMthd.docxVIP

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