% This file was written by Mary Pugh, mpugh@math.toronto.edu, in
% February 2002 and rewritten 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 138 of Elementary Linear Programming with Applications
% by Bernard Kolman and Robert E. Beck, 2nd edition.  It's an example where
% two phases are needed --- because it's starting with Ax=b where there's no
% immediate basic solution to start the simplex method with.
%
% In canonical form:
%
% maximize z = x1 - 2 x2 - 3 x3 - x4 - x5 + 2 x6
% subject to
%             x1 + 2 x2 + 2 x3 + x4 +   x5      = 12
%             x1 + 2 x2 +   x3 + x4 + 2 x5 + x6 = 18
%           3 x1 + 6 x2 + 2 x3 + x4 + 3 x5      = 24
% where x_i >=0
%
% Need a basic solution to start.  Will do this with the phase 1, phase 2
% approach.  Phase 1: find a basic solution, Phase 2: solve the optimization
% problem starting w/ that basic solution.
%
% Phase 1: make sure that the linear system is all equalities (no inequalities)
% and that the RHS has all nonnegative entries.  Add one artificial variable 
% per equation and minimize the sum of the artificial variables.  If you're
% able to get that sum all the way to zero then this means you've found a
% basic solution to the original linear system.
%
% Introducing the artificial variables y1, y2, y3 the auxiliary problem is
%
% minimize z = y1 + y2 + y3
% subject to
%             x1 + 2 x2 + 2 x3 + x4 +   x5      + y1           = 12
%             x1 + 2 x2 +   x3 + x4 + 2 x5 + x6      + y2      = 18
%           3 x1 + 6 x2 + 2 x3 + x4 + 3 x5                + y3 = 24
% where x_i >=0 and y_i >= 0.
%
% Convert to a maximization problem:
%
% maximize z' = - y1 - y2 - y3
% subject to
%             x1 + 2 x2 + 2 x3 + x4 +   x5      + y1           = 12
%             x1 + 2 x2 +   x3 + x4 + 2 x5 + x6      + y2      = 18
%           3 x1 + 6 x2 + 2 x3 + x4 + 3 x5                + y3 = 24
% where x_i >=0 and y_i >= 0.
%
% We want to use the simplex method which requires that the the objective 
% function be written in the form z' + y1 + y2 + y3 = 0 *and* requires that
% the objective function not involve the current basic variables y1, y2, y3
% Using the equations, we get the new objective function equation:
%
%           z' - 5 x1 - 10 x2 - 5 x3 - 3 x4 - 6 x5 - x6 = -54
%
% first we type in the matrix in tableau 2.25 of section 2.3
%
% make sure you've got your commas and semicolons right.  Commas separate 
% entries in a row, semicolons separate rows...
%
A =[ 1,2,2,1,1,0,1,0,0,12;  1,2,1,1,2,1,0,1,0,18; 3,6,2,1,3,0,0,0,1,24; -5,-10,-5,-3,-6,-1,0,0,0,-54]

% now create the vector "bv" that will have the names of the basic variables
>> [A,bv] = LP_setup(A);
what is your basic variable?  x7
what is your basic variable?  x8
what is your basic variable?  x9
% note1: you have to input the x7, x8, x9 at the question.
% note2: I didn't bother with y1,y2,y3 --- I called them x7, x8, and x9.  In fact, if I were to
%          try calling them y1, y2, y3, the matlab routine would get confused.
 
          x1        x2        x3        x4        x5        x6        x7        x8        x9
  x7       1         2         2         1         1         0         1         0         0        12
  x8       1         2         1         1         2         1         0         1         0        18
  x9       3         6         2         1         3         0         0         0         1        24
 obj      -5       -10        -5        -3        -6        -1         0         0         0       -54

% We start at the extreme point (0,0,0,0,0,0,12,18,24)
% now we take the first step, going from tableau 2.25 to tableau 2.26: 
>> [A,bv] = pivot(A,bv);
what is the incoming variable?  x2
what is the outgoing variable?  x9
 
 
          x1        x2        x3        x4        x5        x6        x7        x8        x9
  x7       0         0    1.3333   0.66667         0         0         1         0  -0.33333         4
  x8       0         0   0.33333   0.66667         1         1         0         1  -0.33333        10
  x2     0.5         1   0.33333   0.16667       0.5         0         0         0   0.16667         4
 obj       0         0   -1.6667   -1.3333        -1        -1         0         0    1.6667       -14
 
% We're now at the extreme point (0,4,0,0,0,0,4,10,0)
% now we take the next step, going from tableau 2.26 to tableau 2.27:  
>> [A,bv] = pivot(A,bv);
what is the incoming variable?  x3
what is the outgoing variable?  x7
 
 
          x1        x2        x3        x4        x5        x6        x7        x8        x9
  x3       0         0         1       0.5         0         0      0.75         0     -0.25         3
  x8       0         0         0       0.5         1         1     -0.25         1     -0.25         9
  x2     0.5         1         0         0       0.5         0     -0.25         0      0.25         3
 obj       0         0         0      -0.5        -1        -1      1.25         0      1.25        -9
 
% We're now at the extreme point (0,3,3,0,0,0,0,9,0)
% now we take the next step, going from tableau 2.27 to tableau 2.28:  
>> [A,bv] = pivot(A,bv);
what is the incoming variable?  x6
what is the outgoing variable?  x8
 
 
          x1        x2        x3        x4        x5        x6        x7        x8        x9
  x3       0         0         1       0.5         0         0      0.75         0     -0.25         3
  x6       0         0         0       0.5         1         1     -0.25         1     -0.25         9
  x2     0.5         1         0         0       0.5         0     -0.25         0      0.25         3
 obj       0         0         0         0         0         0         1         1         1         0

% We're now at the extreme point (0,3,3,0,0,9,0,0,0).
% The first nine entries of the objective row are nonnegatve 
% and so phase one terminates!  The solution we've found is 
%   x2 = 3, x3 = 3, and x6 = 9, x1=x4=x5=y1=y2=y3=0.  
% We've managed the original objective function all the way down to zero
% because y1+y2+y3 = 0.  Alternately, we can check that 
% 
%          - 5 x1 - 10 x2 - 5 x3 - 3 x4 - 6 x5 - x6 = -54
%          - 5*0 - 10*3 - 5*3 - 3*0 - 6*0 - 9 = -54
%
% We now have a basic solution for the original linear programing
% problem 
%
% maximize z = x1 - 2 x2 - 3 x3 - x4 - x5 + 2 x6
% subject to
%             x1 + 2 x2 + 2 x3 + x4 +   x5      = 12
%             x1 + 2 x2 +   x3 + x4 + 2 x5 + x6 = 18
%           3 x1 + 6 x2 + 2 x3 + x4 + 3 x5      = 24
% where x_i >=0
%
% The problem now is that if we want to use the simplex method we need to 
% rewrite the objective function so that it doesn't use the basic variables
% x2, x3, and x6.
%
% z = x1 - 2 x2 - 3 x3 - x4 - x5 + 2 x6 
% 
% The final tableaux of Phase 1 told us
%
%    0 x1 + 0 x2 +   x3 + 1/2 x4 +   0 x5 + 0 x6 = 3
%    0 x1 + 0 x2 + 0 x3 + 1/2 x4 +     x5 +   x6 = 9
%  1/2 x1 +   x2 + 0 x3 +   0 x4 + 1/2 x5 + 0 x6 = 3
%
% This is another way of describing the set of feasible solutions --- we've
% simply applied elementary row operations to the first linear system to get
% to this linear system.  The nice thing about this new linear system is
% that we can easily write the basic variables x2, x3, x6 in terms of the
% nonbasic variables x1, x4, x5.  
%
% And so   x3 = -1/2 x4 + 3
%          x6 = -1/2 x4 - x5 + 9
%          x2 = -1/2 x1 - 1/2 x5 + 3
%
% Now we can write the objective function for the original LP problem using
% only the nonbasic variables, which will allow us to then use the simplex
% method for the original problem.
%
% z = x1 - 2 x2 - 3 x3 - x4 - x5 + 2 x6 
%   = x1 - 2(-1/2 x1 - 1/2 x5 + 3)-3(-1/2 x4 + 3)-x4-x5+2(-1/2 x4 - x5 + 9)
%   = x1 + x1 + x5 - 6 + 1.5 x4 - 9 - x4 - x5 - x4 - 2 x5 + 18
%   = x1 + x1  + 1.5 x4 - x4  - x4  + x5 - x5 - 2 x5 - 6 + 18 - 9
%   = 2 x1 - .5 x4 - 2 x5 + 3
%
% and can continue on to phase two by simply changing the objective row of the
% matrix.  Note: in doing this I simpy overwrote the final row of the matrix
% from phase 1.  This means that I'm carrying around the columns for the three
% artificial variables, even though I don't need them anymore.  I just visually
% ignore them and only focus on the first six entries of the objective row when
% choosing incoming and outgoing variables.
%
% Note: A has 4 rows and 10 columns with columns 7, 8, 9 coming from the
% artificial variables.  And so when assigning the final row, we need to
% have entries for x7, x8, x9.  Because these three columns don't actually
% matter for phase 2, it would be fine to have A(4,7)=A(4,8)=A(4,9)=0.  If
% you're curious where the A(4.7)=-2.25, A(4,8)=2, A(4,9)=-.25 came from
% read the material after the end of phase 2.

>> A(4,:) = [-2,0,0,1/2,2,0,-2.25,2,-.25,3]

A =

         0         0    1.0000    0.5000         0         0    0.7500         0   -0.2500    3.0000
         0         0         0    0.5000    1.0000    1.0000   -0.2500    1.0000   -0.2500    9.0000
    0.5000    1.0000         0         0    0.5000         0   -0.2500         0    0.2500    3.0000
   -2.0000         0         0    0.5000    2.0000         0   -2.2500    2.0000   -0.2500    3.0000


>> [A,bv] = pivot(A,bv);
what is the incoming variable?  x1
what is the outgoing variable?  x2
 
 
          x1        x2        x3        x4        x5        x6        x7        x8        x9
  x3       0         0         1       0.5         0         0      0.75         0     -0.25         3
  x6       0         0         0       0.5         1         1     -0.25         1     -0.25         9
  x1       1         2         0         0         1         0      -0.5         0       0.5         6
 obj       0         4         0       0.5         4         0     -3.25         2      0.75        15

% We're now at the extreme point (6,0,3,0,0,9,0
% of the objective row are nonnegative and so
% phase two terminates and we're done!
%
% The optimal solution of the problem is 
%   x1=6, x2 = 0, x3 = 3, x4 = 0, x5 = 0, x6 = 9
% and the maximum value is 15.
%
%
%
% An alternate approach, when we were finished with phase 1 would have been
% to create a new matrix, B, which only had the original six variables and
% the right-hand side, c, and then proceeded applying the simplex method
% to that, after fixing the objective row:

>> B = A(:,1:6);
>> B(:,7) = A(:,10);
% need to replace the final row of B with the original objective row:
>> B(4,:) = [-1,2,3,1,1,-2,0]
B =
  Columns 1 through 7

         0         0    1.0000    0.5000         0         0	3.0000  
         0         0         0    0.5000    1.0000    1.0000	9.0000
    0.5000    1.0000         0         0    0.5000         0	3.0000
   -1.0000    2.0000    3.0000    1.0000    1.0000   -2.0000	0

% Now do elementary row operations on B to transform the objective row
% so that it doesn't involve the basic variables x2, x3, x6
>> B(4,:)=B(4,:)-2*B(3,:)
B =
         0         0    1.0000    0.5000         0         0    3.0000
         0         0         0    0.5000    1.0000    1.0000    9.0000
    0.5000    1.0000         0         0    0.5000         0    3.0000
   -2.0000         0    3.0000    1.0000         0   -2.0000   -6.0000
>> B(4,:)=B(4,:)-3*B(1,:)
B =
         0         0    1.0000    0.5000         0         0    3.0000
         0         0         0    0.5000    1.0000    1.0000    9.0000
    0.5000    1.0000         0         0    0.5000         0    3.0000
   -2.0000         0         0   -0.5000         0   -2.0000  -15.0000
>> B(4,:)=B(4,:)+2*B(2,:)
B =
         0         0    1.0000    0.5000         0         0    3.0000
         0         0         0    0.5000    1.0000    1.0000    9.0000
    0.5000    1.0000         0         0    0.5000         0    3.0000
   -2.0000         0         0    0.5000    2.0000         0    3.0000

% Note the objective row is the same thing that I'd gotten by doing it by
% hand.  
%
% If, instead, we had first worked with the Matrix at the end of phase 1
% in the above way:
%
% >> A(4,:) = [-1,2,3,1,1,-2,0,0,0,0]
% >> A(4,:)=A(4,:)-2*A(3,:)
% >> A(4,:)=A(4,:)-3*A(1,:)
% >> A(4,:)=A(4,:)+2*A(2,:)
%
% then A would have had the final row that we used above when starting
% phase 2: 
%
% >> A(4,:) 
% ans =
%   Columns 1 through 10
%
%    -2.0000         0         0    0.5000    2.0000         0   -2.2500    2.0000   -0.2500	3.0000
%
%

% I'm now ready to start the simplex method for phase 2! 
>> [B,bv] = LP_setup(B);
what is your basic variable?  x3
what is your basic variable?  x6
what is your basic variable?  x2
 
          x1        x2        x3        x4        x5        x6
  x3       0         0         1       0.5         0         0         3
  x6       0         0         0       0.5         1         1         9
  x2     0.5         1         0         0       0.5         0         3
 obj      -2         0         0       0.5         2         0         3

% x1 is the incoming variable and x2 is the outgoing variable.
>> [B,bv] = pivot(B,bv);
what is the incoming variable?  x1
what is the outgoing variable?  x2
 
 
          x1        x2        x3        x4        x5        x6
  x3       0         0         1       0.5         0         0         3
  x6       0         0         0       0.5         1         1         9
  x1       1         2         0         0         1         0         6
 obj       0         4         0       0.5         4         0        15

% Phase two terminates and we're done!
