function [tab] = simplex(tab)
%
% Inputs:
%     tab = the initial tableau
% Outputs: 
%     tab = the final tableau
% 
% Written by:
% -- 
% John L. Weatherwax                2007-07-01
% 
% email: wax@alum.mit.edu
% 
% Please send comments and especially bug reports to the
% above email address.
% 
%-----

printf('Initial tableau:\n'); tab

while( have_negative_in_objective_row(tab) )

  % Compute the pivot column:
  %
  objective_row = tab(end,1:(end-1));
  [mv,pivot_column_indx] = min( objective_row ); % pick the most negative element in the objective row 
  pivot_column = tab(1:(end-1),pivot_column_indx);

  % Compute the pivot row: 
  %
  possible_pivot_rows = find( pivot_column > 0 );
  [mv,spot] = min( tab(possible_pivot_rows,end) ./ pivot_column(possible_pivot_rows) ); % pick the smallest ratio
  pivot_row_indx = possible_pivot_rows(spot);

  % Perform Gaussian ellimination on this pivot row and pivot column: 
  %
  tab(pivot_row_indx,:) = tab(pivot_row_indx,:)/tab(pivot_row_indx,pivot_column_indx);
  for ii=1:size(tab,1)
      if( ii==pivot_row_indx ) continue; end 
      tab(ii,:) = tab(ii,:) - tab(ii,pivot_column_indx) * tab(pivot_row_indx,:);
  end

  printf('Pivot column= %5d; row= %5d; gives the tableau\n', pivot_column_indx, pivot_row_indx); tab

end
printf('finished\n');

% 
% Auxiliary functions: 
%

function [have_any] = have_negative_in_objective_row(tab)

    objective_row = tab(end,1:(end-1));
    if( any( objective_row < 0 ) )
      have_any = 1;
    else
      have_any = 0;
    end