function [B,R]=AdmissibleBasis(B,R,S,t)
% ADMISSIBLEBASIS Finds an admissible basis for a linear program
%   [B,R]=AdmissibleBasis(B,R,S,t) computes the sets of basis and
%   slack variables that yield an admissible basis solution. This is
%   done by solving an auxiliary linear program using SIMPLEX. The
%   result can then be used by SIMPLEX to find the minimum of the
%   original linear program.  A warning is produced if no admissible
%   solution exists.

u=find(t>=0);
l=find(t<0);
A=zeros(length(t),length(B)+length(R)+length(l));
[m,n]=size(A);

A(:,R)=S;
A(:,B)=eye(length(B));
A(l,:)=-A(l,:);
A(l,n-length(l)+1:end)=eye(length(l));
t(l)=-t(l);

Ba=[B(u),n-length(l)+1:n];
Ra=setdiff(1:n,Ba);
Sa=A(:,Ba)\A(:,Ra);
ta=A(:,Ba)\t;
ca=[zeros(n-length(l),1);ones(length(l),1)];
ua=ca(Ra)'-ca(Ba)'*(A(:,Ba)\A(:,Ra));
za=ca(Ba)'*(A(:,Ba)\t);
[0 Ra 0
 Ba' Sa ta
 0 ua za]
Ra=Simplex(Ba,Ra,Sa,ta,ua,za);
Ba=setdiff(1:n,Ra);
z=ca(Ba)'*(A(:,Ba)\t);
if (z>0),
  warning('no admissible solution exists');
else
  R=setdiff(Ra,(n-length(l)+1:n));
  B=Ba;
end;