% 
% This file was written by Mary Pugh, mpugh@math.toronto.edu, in
% August 2024.  Please do not use it without her consent and 
% without attributing her.
%
% Here is an example how to use the matlab subroutines.
% step 1) start matlab on your machine.  type "pwd".  You'll see something
%         like "ans = c:\matlab\work  Remember this because this is where
%         you'll need to save the three files "LP_setup.m", "pivot.m", and
%         "LP_disp.m".
% step 2) download the three files "LP_setup.m", "pivot.m", and "LP_disp.m"
%         and save them in the correct directory.  (In my case, it's 
%         c:\matlab\work )
% step 3) start matlab.  Once it's started, type "ls".  Make sure you see
%         "LP_setup.m", "pivot.m", and "LP_disp.m" listed.
% step 4) open your book to page 138 and follow along with the following.  
%         In the following, the ">>" represents the matlab prompt.  You
%         have to type the words after the >> and then hit return.  You'll
%         then be given some questions to answer...
%
% Example from page 106 of Elementary Linear Programming with Applications
% by Bernard Kolman and Robert E. Beck, 2nd edition.  It's an example where
% only phases is needed --- because it's starting with Ax <= b where b >=0.
% Once we've introduced the slack variables, there's an immediate basic 
% solution to start the simplex method with.
%
% In standard form:
%
% maximize z = 120 x1 + 100 x2
% subject to
%           2 x1 + 2 x2 <= 8  
%           5 x1 + 3 x2 <= 15
% where x_i >=0
%
% Introducing the slack variables s1, s2 the auxiliary problem in canonical
% form is:
%
% maximize z = 120 x1 + 100 x2
% subject to
%           2 x1 + 2 x2 + s1      = 8  
%           5 x1 + 3 x2      + s2 = 15
% where x_i >=0 and s_i >=0
%
% The current basic variables are s1 and s2 and the initial extreme
% point is (0,0,8,15)
%
% first we type in the matrix in tableau 2.1 of section 2.1
%
% make sure you've got your commas and semicolons right.  Commas separate 
% entries in a row, semicolons separate rows...
%
A = [2,2,1,0,8;5,3,0,1,15;-120,-100,0,0,0]

% now create the vector "bv" that will have the names of the basic variables
>> [A,bv] = LP_setup(A);
what is your basic variable?  x3
what is your basic variable?  x4
          x1        x2        x3        x4
  x3       2         2         1         0         8
  x4       5         3         0         1        15
 obj    -120      -100         0         0         0

% note2: I didn't bother with s1 and s2 --- I called them x3 and x4.  In fact, if I were to
%          try calling them s1 and s2, the matlab routine would get confused.

% We're currently at the extreme point (0,0,8,15).
% now we take the first step, going from tableau 2.1 to tableau 2.1a: 
>> [A,bv] = pivot(A,bv);
what is the incoming variable?  x1
what is the outgoing variable?  x4

          x1        x2        x3        x4
  x3       0       0.8         1      -0.4         2
  x1       1       0.6         0       0.2         3
 obj       0       -28         0        24       360
 
% We're now at the extreme point (3,0,2,0).
% now we take the next step, going from tableau 2.3a to tableau 2.4:  
>> [A,bv] = pivot(A,bv);
what is the incoming variable?  x2
what is the outgoing variable?  x3

          x1        x2        x3        x4
  x2       0         1      1.25      -0.5       2.5
  x1       1         0     -0.75       0.5       1.5
 obj       0         0        35        10       430

% We're now at the extreme point (1.5,2.5,0,0).   
% The first four entries of the objective row are nonnegative 
% and so we're done!  
%
% The solution we've found is 
%   x1 = 1.5, x2 = 2.5, and s1=s2=0.  The maximal value of the objective
% function is 430.
