% 求解标准型线性规划:max c*x; s.t. A*x=b;x>=0
%A1是标准系数矩阵及最后一列是资源向量，C是目标函数的系数向量
% N是(初始的)基变量的下标
%M=10000 人工变量系数
% 本函数中的A是单纯形表，包括:最后一行是初始的检验数，最后一列是资源向量b
%c1是基变量系数
%输出变量sol是最优解
%输出变量val是最优值，k是迭代次数
%flag1的值代表有无最优解，0无界解，1无可行解，2无穷多解，3唯一最优解
function [sol,val,k,flag1]=ssimplex(A1,C,N)
M=10000;
[mA1,nA1]=size(A1);
C1=[C,0];
val=zeros(1,length(C));
for i=1:length(N)
c1(i)=C1(N(i));
end
for i=1:nA1
a(i)=C1(i)-c1*A1(:,i);%计算初始检验数
end
A=[A1;a]; %构造初始单纯形表
[mA,nA]=size(A);
k=0; % 迭代次数
flag=1;
while flag
for i=1:(nA-1)
if A(mA,i)<=0
flag=0;
else
flag=1;
break;
end
end
if flag==0 % 已找到最优解
val1=A(1:(mA-1),nA)';
for i=1:length(N)
if (val1(i)~=0&&abs(C(N(i)))==M)
disp('无可行解');
sol=inf;val=inf;
flag3=0;
flag1=1;
break;
else
flag3=1;
end
end
if flag3
if length(find(A(mA,1:(nA-1))==0))>length(N)
disp('存在无穷多最优解');
flag1=2;
else
disp('存在最优解');
flag1=3;
end
sol=c1*val1';
end
elseif flag==1
for j=1:(mA-1)
if A(j,i)<=0
flag2=1;
else
flag2=0;break;
end
end
if flag==1&&flag2==1
disp('此线性规划问题存在无界解');
sol=inf;
val=inf;
flag1=0;
flag=0; %跳出while循环
break;
end
maxq=max(A(mA,1:(nA-1)));
[m,nb]=find(A(mA,:)==maxq); %确定入基变量的纵坐标
for s=1:(mA-1)
if A(s,nb)>0
temp(s)=A(s,nA)/A(s,nb);
else
temp(s)=10000;
end
end
k=k+1;
mino=min(temp);
[n,mb]=find(temp==mino); %确定入基变量的横坐标
if length(mb)>1
mb=mb(1);
end
ab=A(mb,nb);
A2=A;
for i=1:(mA-1)
for j=1:nA
if i==mb
A(mb,j)=A2(mb,j)/ab;
else
A(i,j)=A2(i,j)-A2(i,nb)*(A2(mb,j)/ab);
end
end
end
for i=1:length(N)
if i==mb
N(i)=nb;
end
end
for i=1:length(N)
c1(i)=C(N(i));
end
for i=1:nA
A(mA,i)=C1(i)-c1*A(1:(mA-1),i);
end
end
end
if sol~=inf
for i=1:length(C)
for j=1:length(N)
if i==N(j)
val(i)=val1(j);
end
end
end
end