%% Define the LP
% minimize    -x1 - 2*x2
% subject to  -2*x1 + x2 <= 2
%             -x1 + 2*x2 <= 7
%              x1        <= 3
%              x1, x2 >= 0
%
% Except, we need this in standard form:
% minimize f'*x subject to. A*x <= b

c = [-1 -2];
A = [-2 1; -1 2; 1 0];
b = [2; 7; 3];
lb = [0; 0];
ub = []; % No upper bound

%% Plot the LP polytope
clf; 
plotregion(-A,-b,lb,ub); 
box off; hold on;
plot(x(1), x(2), 'ro','MarkerSize',16);
hold off;

%% Convert the LP into standard form
cs = [-1 -2 0 0 0]';
AS = [A eye(3)];

%% Start with a simple feasible point
x = [zeros(2,1); b]; 
Bind = [3,4,5];
Nind = [1,2];

simplex_step(cs,AS,b,Bind,Nind,1)

%% Show all iterates
x = [zeros(2,1); b]; 
Bind = [3,4,5];
Nind = [1,2];
sol = 0;

clf; 
plotregion(-A,-b,lb,ub); 
box off; hold on;
while ~sol
  plot(x(1), x(2), 'ro','MarkerSize',16);
  [x,Bind,Nind,sol] = simplex_step(cs,AS,b,Bind,Nind,0);
end
plot(x(1), x(2), 'r*','MarkerSize',16);
hold off;

