单纯形法：simplemthd

单纯形法函数：SimpleMthd用单纯形算法解如下线性规划问题 的步骤如下：min,.0AxbfCst（1 ） 确定初始基变量矩阵 ；求解方程；B（2 ） 令 ，计算 ；其中 和 分别代表基变量和非基变量的值， 表0NxfcxBNx Bc示基变量在目标函数中的系数；（3 ） 求解方程 ，对于所有非基变量计数判别数 ，其中 为Bjjzcpjp非基变量在约束系数矩阵中相对应的列，令 ，如果max()kj，则停止计算，输出最优解，否则转步骤 4；0kzc（4 ） 求解方程 ，若 的每个分量均大于 0，则问题不存在最优解，否则转步kBypky骤 5；（5 ） 令 ，其中 ，用 代替 ，得到新的基变量矩阵min|0siskkbyBbxkpBs再转步骤 2 计算。B调用格式： ,in(,)xfSipleMthdAcbaseVtor其中， ：约束矩阵；A：目标函数系数向量；c：约束右端向量；b：初始向量，basic；aseVtor：目标函数取最小值时自由变量值；x：目标函数的最小值；minf单纯形法函数的 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:nViaif(isempty(find(baseVector=xx(i),1)nobase(m)=i;m=m+1;else;endendbCon=1;M=0;while bConnB=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);endmaxs,ind=max(sigma); %ind 为进基变量下标if maxs0bz=xb(j)/y(j);if bz=0vr=find(c=0,1,last);rgv=inv(A(:,(nVia-n+1):nVia)*b;if rgv=0else 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=1;if c=0vr=find(c=0,1,last);rgv=inv(A(:,(nVia-n+1):nVia)*b;if rgv=0else disp(不存在最优解！);x=NaN;minf=NaN;return;endendfor i=1:nViaif(isempty(find(baseVector=xx(i),1)nobase(m)=i;m=m+1;else;endendbCon=1;M=0;while bConnB=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);endmaxs,ind=max(sigma); %ind 为进基变量下标if maxs0bz=xb(j)/y(j);if bzminbminb=bz;chagB=j;endendendtmp=baseVector(chagB);%更新基矩阵和非基矩阵baseVector(chagB)=nobase