%
% This is an interactive program demonstrating the Simplex Method 
% via the extended simplex tableau
% Written by Ming Gu for Math 170
% March 2007
%

% input dimensions
%
m = input('How many constraints: ');
n = input('How many unknowns: ');
%
% setup LP
%
B =(1:m)';
A =rand(m,n);
x =zeros(n,1);
x(B)=rand(m,1);
b =A*x;
c =randn(n,1);
T = A(:,B)\[A b eye(m)];
%
% Starting Simplex Method
%
f = ['Starting Phase II Simplex Iteration... '];
disp(f);
disp('Initial Basis is');
disp(B');
simplex = 1;
ITER = 0;
obj = c'*x;
while (simplex == 1)
%
% determine the next s and r values.
%
   y = T(:,end-m+1:end)'*c(B);[zmin,s] = min(c-A'*y); 
   r = getr(n,s,B,T);
   if (r < 1)
       disp('LP has no lower bound');
       simplex = 0;
       continue;
   end
   x   = zeros(n,1);
   x(B)= T(:,n+1);
   ITER = ITER + 1;
   f = ['Iteration ', num2str(ITER), ' Obj ', num2str(c'*x), '. Smallest component in c-A^T*y: ', num2str(zmin), ' at s =', num2str(s), '. Component r = ', num2str(r), ' out of basis'];
   disp(f);
   obj1 = c'*x;
%
% update the simplex tableau.
%
   [T,B1,flg]=SimplexTableau(B,r,s,T);      
   if (flg == 1)
       disp('LP is degenerate');
       simplex = 0;
       continue;
   end
%
% check for convergence.
%
   FF  = setdiff(B1,B);
   if (length(FF) == 0 | (abs(obj1-obj) < 1e-14 & ITER  > 1))
       disp('Simplex Method has converged');
       simplex = 0;
       continue;
   end
   B   = B1;
   obj = obj1;
   disp('Current Basis is');
   disp(B');
   pause(5);
end