function [xm,fm,noi] = Dcxf(A,b,c)
% 单纯形法
% 输入参数:
% c为目标函数系数
% A为约束方程组系数矩阵,
% b为约束方程组常数项
% 输出参数:
% xm：最求解
% fm为最优函数值
% noi为迭代次数
format rat
[m,n] = size(A);
v=nchoosek(1:n,m);
index_Basis=[];
for i=1:size(v,1)
if A(:,v(i,:))==eye(m)
index_Basis=v(i,:);
end
end
ind_Nonbasis = setdiff(1:n, index_Basis);
noi=0;
while true
x0 = zeros(n,1);
x0(index_Basis) = b;
cB = c(index_Basis);
Sigma = zeros(1,n);
Sigma(ind_Nonbasis) = c(ind_Nonbasis)' - cB'*A(:,ind_Nonbasis);
[~, s] = min(Sigma);
Theta = b ./ A(:,s);
Theta(Theta<=0) = 10000;
[~, q] = min(Theta);
q = index_Basis(q);
if ~any(Sigma < 0)
xm = x0;
fm = c' * xm;
return
break
end
if all(A(:,s) <= 0)
xm = [];
break
end
index_Basis(index_Basis == q) = s;
ind_Nonbasis = setdiff(1:n, index_Basis);
A(:,ind_Nonbasis) = A(:,index_Basis) \ A(:,ind_Nonbasis);
b = A(:,index_Basis) \ b;
A(:,index_Basis) = eye(m,m);
noi=noi+1;
end
end
