# LPmatrix.wxmx

load(draw)$  set_draw_defaults(line_width=2, grid = [2,2], point_type = filled_circle,
          head_type = 'nofilled, head_angle = 20, head_length = 0.5,
             background_color = light_gray,  draw_realpart=false)$     
 fpprintprec : 5$  ratprint : false$

load (simplex);

load ("econ1.mac");

## Preface

In Example 1 of LPmatrix.wxmx we introduce a matrix simplex method in which the "z-row"
is the bottom row. In addition to the matrix functions Mdefine, Mdisplay, and Mratio
used in LPsimplex.wxmx, we introduce and use the new functions Mbtableau( ) and 
Mbpivot (nEnter, nLeave), in which the extra "b" denotes use with the z-row on the bottom.

In the second section of LPmatrix.wxmx are a number of examples which use Mbtableau
and Mbpivot (together with Mratio) for matrix simplex maximization and minimization using
both the Big M method and Butenko's Dual Simplex Method (the latter starts with solving
the "auxiliary problem" of minimizing the sum of the artificial variables in the problem).

The third section introduces the B/N Dual Simplex Method, in which all given constraints
are converted to <= constraints, and then slack variables are added to the left-hand side 
of each constraint to convert to constraint equations. When exhibited in the form of a 
simplex tableau, if the optimality condition is satisfied AND one or more basic variables 
have negative values, then this dual simplex method is applicable. 

The (regular) simplex method moves the initial feasible but nonoptimal solution to an 
optimal solution while maintaining feasibility through an iterative procedure. On the other 
hand, the B/N dual simplex method moves the initial optimal but infeasible solution to a 
feasible solution while maintaining optimality through an iterative procedure.

The basic variable with the most negative value becomes the departing variable (D.V.) - 
leaves the basis. Call the row in which this value appears the work row. If more than 
one candidate for D.V. exists, choose one. 

Form ratios by dividing the z-row coefficients of the non-basic variables by the 
corresponding negative coefficients of the work row. The nonbasic variable with the 
smallest absolute ratio becomes the entering variable (E.V.) - enters the basis. 
Designate this element in the work row as the pivot element and the corresponding column 
the work column. If more than one candidate for E.V. exists, choose one. If no element in 
the work row is negative, the problem has no feasible solution. 

Use elementary row operations to convert the pivot element to 1 and then to reduce all 
the other elements in the work column to zero. 

Repeat until all the variables have reached nonnegative values, so the optimal solution is 
feasible.

This B/N Dual Simplex Method is formulated in terms of matrices, and continues to use
our functions Mbtableau() and Mbpivot (nEnter, nLeave), as well as DMratio (rowNum) which
makes it easy to identify the entering variable starting with the work row number. The new
functions are in the updated Econ1.mac file.

Dec. 22, 2022

## References

Sergiy Butenko, ISEN 620, A Survey of Optimization, 82 videos
https://www.youtube.com/playlist?list=PLY9yf2-4yyeQTLkCVFnGedyERuCjKW7kI

(B/N) Richard Bronson & G. Naadimuthu, Operations Research, 2nd ed, Schaum's Outline
Series, McGraw-Hill, 1982.

## Example 1

This matrix simplex example was presented in LPsimplex.wxmx using the convention
that the "z-row" appears on top, using the functions Mtableau and Mpivot. Here we
use the convention that the "z-row" appears on the bottom, using the functions
Mbtableau and Mbpivot. With either convention we can use Mratio, Mdefine, and Mdisplay.

### Using Mdefine, Mdisplay, Mbtableau, Mratio, Mbpivot

We use a maximization example from Butenko's Video 42.

Maximize 4*x1 + 3*x2 + 5*x3,
subject to
  x1 + 2*x2 + 2*x3 <= 4,
  3*x1 + 4*x3 <= 6,
  2*x1 + x2 + 4*x3 <= 8,
   with  x1, x2, x3 >= 0.

We first use maximize_lp (objective, condL, posL) from the simplex package:

maximize_lp (4*x1 + 3*x2 + 5*x3, [x1 + 2*x2 + 2*x3 <= 4, 3*x1 + 4*x3 <= 6,
  2*x1 + x2 + 4*x3 <= 8], [x1,x2,x3]);

We get a different type of output using maxlp.

maxlp (4*x1 + 3*x2 + 5*x3, [x1 + 2*x2 + 2*x3 <= 4, 3*x1 + 4*x3 <= 6, 
        2*x1 + x2 + 4*x3 <= 8])$

Adding slack variables x4, x5, x6, this example becomes (c^t stands for the transpose of c):

Maximize z =  4*x1 + 3*x2 + 5*x3 + 0*x4 + 0*x5 + 0*x6  = c^t . X,
subject to A . X = b, or
  x1 + 2*x2 + 2*x3 + x4 + 0*x5 + 0*x6 = 4,
  3*x1 + 0*x2 +  4*x3 + 0*x4 +  x5 + 0*x6 = 6,
  2*x1 + x2 + 4*x3 + 0*x4 + 0*x5 + x6 = 8,
   with  x1, x2, x3, x4, x5, x6 >= 0, equivalent to X >= 0.

### Define Initial Global Entities: X, c, A, b, NV, BV

The matrix method functions use the following global matrices:
       c, X, A, b,  N, B, Xn, Xb, cN, cB,
and the global lists NV, BV.

The first four (c, X, A, b) remain the same throughout the optimum solution process.
c, X, and b are matrix column vectors. A is a matrix of coefficients of the
left-hand sides of the constraint equations.  b is a matrix column vector of the
right-hand side constants from the constraint equations. X is a matrix column vector whose
elements are the variable names.

The remaining eight global entities (NV, BV, N, B, Xn, Xb, cN, cB) are redefined in 
each simplex algorithm step (each pivot).
 
 We seek to optimize z = c^t . X =  transpose (c) . X, subject to:
         A . X = b, 
         with    X >= 0.

With N a matrix of the columns of A corresponding to the non-basic variables
 (in order left to right) and with B a matrix of the columns of A corresponding to the
 basic variables (in order left to right), the matrix equation A . X = b turns into the
 matrix equation  N . Xn + B . Xb = b, which can then be solved for Xb (the basic variables)
 in terms of the non-basic variables Xn:
       Xb = - invert(B) . N . Xn + invert(B) . b

NV is an ordered list of the numbers associated with the non-basic variables for a
particular tableau, and BV is an ordered list of the numbers associated with the basic 
variables of the same particular tableau.

cB is a matrix row vector with elements taken from the row vector transpose(c) which 
correspond to the variables in Xb. Likewise cN is a matrix row vector with elements taken 
from the row vector transpose(c) which correspond to the variables in Xn. Then we have 
the identity
     z = c^t . X =  transpose(c) . X = cB . Xb + cN . Xn.

Using Xb = - invert(B) . N . Xn + invert(B) . b, we can express z entirely in terms of the 
variables in Xn to get:
      z = cB . invert(B) . b  + (cN - cB . invert(B) . N) . Xn.

The first term is some number (a constant) and the second term is a function
of the non-basic variables at a given step. Since all non-basic variables, at a given step,
are equal to zero, the second term is zero, and the current value of z is the first term.

The association of variables names with variable numbers (defined by our definition of
the matrix column vector X), is (for this problem):
    [x1,x2,x3,x4,x5,x6]  <==>  [1,2,3,4,5,6].

We convert
Maximize z = 4*x1 + 3*x2 + 5*x3
subject to
  x1 + 2*x2 + 2*x3 + x4 = 4,
  3*x1 + 4*x3 + x5 = 6,
  2*x1 + x2 + 4*x3 + x6 = 8,
   with  x1, x2, x3, x4, x5, x6 >= 0,
into matrix form.
Our initial feasible solution is x1 = x2 = x3 = 0 (so x1,x2,x3 are nonbasic variables for the
initial tableau), and x4 = 4, x5 = 6, x6 = 8 (so x4, x5, x6 are basic variables for the initial
tableau).

X : cvec ([x1,x2,x3,x4,x5,x6])$
c : cvec ([4,3,5,0,0,0])$
A : matrix ( [1,2,2,1,0,0], [3,0,4,0,1,0], [2,1,4,0,0,1] )$
b : cvec ([4,6,8])$
NV : [1,2,3]$
BV : [4,5,6]$

The above definitions of X, c, A, and b will remain unaltered throughout the optimization
process. The definitions of NV and BV will change, swapping a basic and non-basic 
variable to produce the next simplex step (pivot).

### Mdefine()$ to define global N, B, Xb, Xn, cB, cN

Mdefine() uses global X, c, A, b, NV, and BV to define global N, B, Xn, Xb, cN, and cB.
Unless details is set to true (default is false), the results are not displayed.

Here is a look at the Maxima code for Mdefine():

display2d:false$
fundef (Mdefine);
display2d:true$

Here we call Mdefine():

Mdefine()$

### Mdisplay()$ to see NV, BV, N, B, Xb, Xn, cB, cN values

Since Mdefine(), by default, does not display the current definitions of N, B, Xn, Xb,
cN, and cB, you can use Mdisplay()$ to have the current values of these global
variables displayed, and as a bonus, a reminder of NV and BV.

We first show our definition of the matrix A.

display (A)$

Mdisplay()$

cN and cB are each matrix row vectors.

### Mbtableau(); to see current Matrix tableau with z-row on 
bottom

Once the lists NV and BV have been defined, and the values of N, B, Xn, Xb, cN,
and cB have been defined, the function Mbtableau() creates a "matrix tableau" of the 
current state of the optimization process, with the "z-row" on the bottom.

Mbtableau() creates a matrix display in which the basic variables and their coefficients
are on the left-hand side, the non-basic variables and their coefficients come next,
reading left to right, and then comes the "rhs" values as a column, and finally a column
showing the symbols standing for the current basic variables.

cB is a matrix row vector with elements taken from the row vector transpose(c) which 
correspond to the variables in Xb. Likewise cN is a matrix row vector with elements taken 
from the row vector transpose(c) which correspond to the variables in Xn. Then we have 
the identity
     z = transpose(c) . X = cB . Xb + cN . Xn.
Using Xb = - invert(B) . N . Xn + invert(B) . b, we can express z entirely in terms of the 
variables in Xn to get:
      z = cB . invert(B) . b  + (cN - cB . invert(B) . N) . Xn.
The first term is some number (a constant) and the second term is a function
of the non-basic variables at a given step. Since all non-basic variables, at a given step,
are equal to zero, the second term is zero, and the current value of z is the first term.

The pure matrix form was used in LPsimplex.wxmx. Putting the z-row on the bottom here,
that pure form matrix display has the form:
         transpose (Xb)                   transpose(Xn)                   "rhs"                  "Basis"
         ident (length(Xb)                 invert(B) . N                  invert(B) . b             Xb
  makelist(0,j,1,length(Xb))     -(cN - cB . invert(B) . N)      cB . invert(B) . b      "z"

In this file, Mbtableu() is used which converts the above pure matrix display into a matrix
of numbers and symbols which is easier to read when the number of basic variables is
large (a large number of conditions).

The first set of rows can be read off as a set of equations which must be satisfied in the
current tableau. The last row is called the "z-row". The z-row coefficients of the basic
variables Xb are all equal to zero, and the z-row coefficients of the non-basic variables Xn
in the middle section provide possible further maximizing opportunities, provided at least
one of the coefficients is negative.

In each step of the simplex algorithm, one non-basic variable and one basic variable
trade roles, and appear in the opposite set of columns, maintaining the established
order set by the constant vector X. 

Here is the Step 0 tableau, the initial feasible solution tableau, with the basic variables
(x4,x5,x6) appearing first on the left, and then the non-basic variables (x1,x2,x3) at this
stage appearing in the middle section, with the condition coefficients appearing underneath
in the next three rows (we have three conditions in this LP).

Mbtableau();

The bottom row, the z-row, is meant to be read as:
      z - 4*x1 - 3*x2 - 5*x3 = 0,  (since x1 = x2 = x3 = 0).
The three constraint condition rows can be read off in a manner not too different
from our previous work with tableau.

The first constraint row says:
   x1 + 2*x2 + 2*x3 + x4 = 4  (with x4 = 4 since x1 = x2 = x3 = 0 ), and so on.

If you put a dollar sign on the end instead of a semi-colon you do not see the output.

### Mratio(colNum); to see ratios for the minimum ratio test

The coefficient of the current non-basic variable in the z-row which is most negative is
normally used to define which of the non-basic variables will enter the Basis. Here 
column 3, the x3 column here, is used as the column number to use with Mratio(Ncol).
 The x3 variable will be the "pivot variable", and "x3 enters the Basis" with a positive value.

In more detail, the code for Mratio(colNum) has the line:
       NC : col ( invert (B) . N, colNum),
in which if colNum is 3, NC is the third column of the matrix invert(B) . N

invert(B) . N;

col (invert(B) . N, 3);

The individual elements of this column are then divided into the corresponding elements 
of invert(B) . b:

invert(B) . b;

Then an extra column with the elements of the current Xb are added on the right.

Xb;

Mratio(3);

The "minimum ratio test" is won by the variable x5, which is the fifth variable in X (variable
number 5).

### Mbpivot (n_Enter, n_Leave); for one simplex step

In Mbpivot(n_Enter, n_Leave), n_Enter is the number of the variable entering the
Basis and n_Leave is the number of the variable leaving the basis, based on the
choice of the user. The simplex algorithm says make this choice based on the
non-basic variable with the most negative coefficient in the z-row and the basic variable
for which the ratio test produces the smallest value. The "variable number" depends on
the order of the variable in the constant vector X.

Step 1 tableau with the third variable in X entering and the fifth variable in X leaving:

Mbpivot (3, 5);

The first simplex pivot operation has caused z to increase from 0 to 15/2 = 7.5. The 
variable x3 has increased from 0 to 3/2 = 1.5.

The most negative coefficient among the non-basic z-row coefficients is in column 2 of the
non-basic variable set, the x2 variable.

Mratio(2);

Since the most negative coefficient in the z-row corresponds to the second variable
in the matrix vector X, and the  minimum ratio test is won by the row corresponding to
the fourth variable in X, we have n_Enter = 2, n_Leave = 4.

Step 2 tableau:

Mbpivot (2, 4);

The second simplex pivot operation has caused z to increase from 7.5 to 9.

At this stage, there is only one negative coefficient in the z-row, corresponding to the
first column of the non-basic variables, and in that first column there is only one positive 
coefficient (3/4) corresponding to the variable x3, the third variable in X.

Mratio(1);

Step 3 tableau:

Mbpivot (1,3);

In this matrix tableau, there are no negative coefficients in the z-row, z has reached the
value 11, and the variables have the values:
  x1 = 2, x2 = 1, x3 = 0, x4 = 0, x5 = 0, x6 = 3.
This is an optimum solution and agrees with the optimum found by maximize_lp or maxlp.

## Example 2 : Matrix Maximization with Artificial Var.
B/N Prob. 3.4

This is B/N Prob. 3.4.
maximize z = 2*x1 + 3*x2,
  subject to
    x1 + 2*x2 <= 2,
   6*x1 + 4*x2 >= 24,
with x1,x2 >= 0.

maxlp (2*x1 + 3*x2, [x1 + 2*x2 <= 2, 6*x1 + 4*x2 >= 24] );

### Matrix Big M Method

Put this problem in standard form by introducing slack variable x3 in the first constraint
and both a surplus variable x4  and an artificial variable x5 in the second constraint, to get
maximize z = 2*x1 + 3*x2 + 0*x3 + 0*x4 - M*x5
  subject to
    x1 + 2*x2 + x3 = 2,
   6*x1 + 4*x2 - x4 + x5 = 24,
with x1,x2,x3,x4,x5 >= 0.

An initial feasible solution is x1 = x2 = x4 = 0, x3 = 2, x5 = 24.
X^t = (x1,x2,x3,x4,x5), c^t = (2,3,0,0, - M),

X : cvec ([x1,x2,x3,x4,x5])$
c : cvec ([2,3,0,0,- M])$
z = transpose (c) . X;
A : matrix ( [1, 2, 1, 0, 0], [6, 4, 0, -1, 1] )$
b : cvec ([2, 24])$
A . X = b;
NV : [1, 2, 4]$
BV : [ 3, 5]$
Mdefine()$
Mbtableau();

Mratio (1);

Mbpivot (1, 3);

There are no negative z-row coefficients of the nonbasic variables x2,x3,x4, so optimality
has been achieved but the artificial variable is still basic (x5 = 12). The original program has
no solution since the constraint conditions and the nonnegativity conditions cannot be
satisfied simultaneously. We have x1 = 2, x2 = 0, x3 = 0, x4 = 0, x5 = 12.
The first constraint condition reads
   x1 + 2*x2 + x3 = 2, or since x2 = x3 = 0, x1 = 2.
The second constraint condition reads
  x5 - 8*x2 - 6*x3 - x4 = 12, or since  x2 = x3 = x4 = 0, x5 = 12.

We need x1 + 2*x2 <= 2, or x1 <=2 (since x2 = 0), so the first condition is satisfied.
We then need 6*x1 + 4*x2 >= 24, or since x2 = 0, we need x1 >= 24/6 = 4. But x1 = 2
does not satisfy this second condition.

### Matrix (Butenko) Dual Simplex Method

Step 1 (Phase I) is the Auxiliary problem of Butenko's dual simplex method:
We minimize the sum of the artificial variables subject to the constraints, and with only
one artificial variable, we minimize w = x5, or maximize z = -w = -x5.

Auxiliary Problem:
maximize z = -x5, 
  subject to
    x1 + 2*x2 + x3 = 2,
   6*x1 + 4*x2 - x4 + x5 = 24,
with x1,x2,x3,x4,x5 >= 0.

We don't need to redefine X, A, nor b.

display (X,A,b)$

The initial feasible solution has x1 = x2 = x4 = 0 (three non-basic variables to start) and
x3 = 2, x5 = 24 (two basic variables).

c : cvec ([0, 0, 0, 0, -1])$
z = transpose (c) . X;
A . X = b;
NV : [1, 2, 4]$
BV : [ 3, 5]$
Mdefine()$
Mbtableau();

We need to drive z to a zero value, starting with z = -24.

Mratio (1);

Mbpivot (1, 3);

Since there are no negative coefficients of the current nonbasic variables x2,x3,x4 in the 
bottom z-row, this is an optimum solution of the Auxiliary problem, and the maximum 
value of z = -x5 is -12, the minimum value of x5 is 12 > 0. The original problem is not 
feasible.

## Example 3: Matrix Minimization with Artificial Var.

minimize w = 80*x1 + 60*x2
  subject to
   0.2*x1 + 0.32*x2 <= 0.25,
   x1       +         x2  = 1, 
    x1,x2 >= 0.

minimize_lp likes whole number fractions better than decimals.

rat(0.32);

minimize_lp (80*x1 + 60*x2, [x1/5 + 8*x2/25 <= 1/4, x1 + x2 = 1], [x1, x2]);

float(%);

maxlp (- 80*x1 - 60*x2, [x1/5 + 8*x2/25 <= 1/4, x1 + x2 = 1] );

### Convert to a Maximization Problem in Standard Form

1. Convert to a maximization problem with z = - w:
  maximize z = - 80*x1 - 60*x2
  subject to
   0.2*x1 + 0.32*x2 <= 0.25,
   x1       +         x2  = 1, 
    x1,x2 >= 0.
2. Write in standard form. Use slack variable x3 in the first constraint condition.
   We need an artificial variable x4 in the second constraint in order to have a second
non-zero basic variable (x4 = 1) in the initial feasible solution (x1 = 0, x2 = 0, x3 = 1/4,
 x4 = 1), since we have two constraint conditions.

### Matrix Big M Method

   maximize z = - 80*x1 - 60*x2 - M*x4,
  subject to
   0.2*x1 + 0.32*x2 + x3 = 0.25,
   x1       +         x2  + x4 = 1, 
    x1,x2,x3,x4 >= 0.

To be able to compare with the output of minimize_lp, we will use:
0.2 = 2/10 = 1/5, 0.32 = 8/25, 0.25 = 1/4 in the constraint equations.

rat(0.32);

The initial feasible solution is x1 = x2 = 0, x3 = 1/4, x4 = 1.

X : cvec ([x1,x2,x3,x4 ])$
c : cvec ([-80,-60,0, - M ])$
A : matrix ( [1/5,8/25,1,0 ], [1,1,0,1] )$
b : cvec ([1/4,1])$
NV : [1,2 ]$
BV : [3, 4 ]$
z = transpose(c) . X;
A . X = b;
Mdefine()$
Mbtableau();

In the Big M method, M is an arbitrarily large positive number.

The coefficient of x2, (60 - M), is more negative than the coefficient of x1, (80 - M), in 
the z-row. We then use Mratio (colNum) (here the second column of the Xn matrix) to 
perform the minimum ratio test for the second column (which happens to be the x2 column):

Mratio(2);

We then call Mbpivot (n_Enter, n_Leave) with n_Enter = 2 (variable x2, the second
variable in X, and with n_Leave = 3 (variable x3, the third variable in X):

Mbpivot(2, 3);

Mratio(1);

Mbpivot (1, 4);

The large positive parameter M has disappeared the current value of z and from the
values of the decision variables x1 and x2. The values of both the slack variable x3 
and the artificial variable x4 are zero. This is the optimum solution since in the limit that
M is an arbitrarily large positive number, there is no negative nonbasic variable 
coefficient in the bottom z row.

Since z* = -215/3, the minimum value of w = -z is w* = 215/3 with x1* = 7/12, x2* = 5/12
in agreement with minimize_lp.

float(%);

### Matrix (Butenko) Dual Simplex Method

X, A, and b have not been altered in the above steps.

display (X,A,b)$

Phase 1 of Butenko's dual simplex method tests feasibility of given problem by seeking to 
minimize w = x4 (the single artificial variable in the problem), or maximize z = -w = -x4 
subject to the two given constraint equations.

c : cvec ([0,0,0, -1])$
NV : [1,2 ]$
BV : [3, 4 ]$
"maximize";
z = transpose(c) . X;
"subject to ";
A . X = b;
Mdefine()$
Mbtableau();

 We arbitrarily choose the first column of the nonbasic variable coefficients, corresponding
to variable x1 (#1 in X) entering the Basis.

Mratio (1);

Mbpivot (1, 4);

With no more negative coefficients of the nonbasic variables in the bottom z-row, we have
the optimum tableau with x4 nonbasic and hence x4 = 0. Hence the original LP is feasible.

Phase II of the dual simplex method.

From the final matrix tableau of Phase I of the dual simplex method, we eliminate the 
artificial variable (x4) column, work now with the three remaining variables x1, x2, x3, 
and rewrite the z-row in the original maximization form
  max z = - 80*x1 - 60*x2 + 0*x3,
and continue using the condition equations governing x1,x2,x3 as they appear in the final
tableau of Phase I.
Reading off the condition rows of the final Phase I matrix tableau (ignoring the x4 column):
    x1 + x2 = 1,
    x3 + (3/25)*x2 = 1/20,
to define the matrices A and b. Because the basic variables in the final Phase I matrix
tableau are x1 and x3, we set BV = [1,3]. The variable x2 is a nonbasic variable in the 
final Phase I matrix tableau, so we set NV = [2].

X : cvec([x1,x2,x3])$
c : cvec ([-80, -60, 0])$
A : matrix ( [1, 1, 0], [0, 3/25, 1])$
b : cvec ([1, 1/20])$
NV : [2]$
BV : [1, 3]$
"maximize";
z = transpose(c) . X;
"subject to";
A . X = b;
Mdefine()$
Mbtableau();

Mratio (Ncol) calculates the ratios of the rhs elements to the elements in column Ncol of the
nonbasic variable coefficients. Here there is only one column, so we use Mratio (1). The
coefficients in this column are the coefficients of x2 (variable #2 in X), so x2 will enter the
basis.

Mratio (1);

The minimum ratio test is won by the second constraint row, corresponding to x3 (variable
#3 in X), so x3 leaves the basis. We then call Mbpivot (Enter, Leave) = Mbpivot (2, 3).

Mbpivot (2, 3);

No more x3 negative coefficient in the bottom z-row implies a maximum of z = -w:
z* = -215/3 with x1* = 7/12, x2* = 5/12. This implies a minimum of w with
w* = 215/3 at the same point.

## B/N Prob. 3.5

Maximize z = - x5
  subject to five conditions:
  3*x1 - 2*x2 - 4*x3 + 6*x4 - x5 <= 0,
  -4*x1 + 2*x2 - x3 - 8*x4 - x5 <= 0,
           - 3*x2 -2*x3 -x4 - x5 <= 0,
   x1  + x2  + x3  + x4          <= 1,
  -x1 - x2 - x3 - x4                <= -1,
  with x1,x2,x3,x4 >= 0, and x5 unrestricted.

maximize_lp ( - x5, [3*x1 - 2*x2 - 4*x3 + 6*x4 - x5 <= 0,
  -4*x1 + 2*x2 - x3 - 8*x4 - x5 <= 0,
           - 3*x2 -2*x3 -x4 - x5 <= 0,
   x1  + x2  + x3  + x4          <= 1,
  -x1 - x2 - x3 - x4                <= -1],
    [x1,x2,x3,x4]);

float(%);

Since x5 is unrestricted, we set x5 = x6 - x7, where both x6 and x7 are nonnegative; 
then all variables left are nonnegative. We multiply the last constraint by –1, thereby forcing 
a positive right-hand side. Finally, we achieve standard form by adding slack variables 
x8 through x11, respectively, to the left-hand sides of the first four constraints, and 
subtracting surplus variable x12 and adding artificial variable x13 to the left-hand side 
of the last constraint. We then have the standard form
Maximize z = - x6 + x7,
  subject to
  3*x1 - 2*x2 - 4*x3 + 6*x4 - x6 + x7 + x8 = 0,
  -4*x1 + 2*x2 - x3 - 8*x4 - x6 + x7 + x9  = 0,
          - 3*x2 -2*x3 -x4 - x6 + x7 + x10 = 0,
  x1  + x2  + x3  + x4  + x11               = 1,
   x1 + x2 + x3 + x4  - x12 + x13        = 1,
  with x1,x2,x3,x4,x6,x7,x8,x9,x10,x11,x12,x13 >= 0, and x13 is an artificial variable.

An initial feasible solution is
  x1,x2,x3,x4,x6,x7,x12 = 0, with five basis variables associated with the five constraints:
  x8 = 0, x9 = 0, x10 = 0, x11 = 1,x13 = 1.

### Nonmatrix Big M "two phase" tableau pivot1 method

B/N's "two phase" Big M procedure:
The bottom "z-row" is split into two rows, with the second row being the coefficients of M.
The simplex method is applied to that second "z-row", until this bottom row contains no 
negative elements. Then the simplex method is applied to those elements in the next-to-last
row that are positioned over zeros in the last row

Whenever an artificial variable ceases to be basic, it is deleted from the top row of the 
tableau, as is the entire column under it. (This modification simplifies hand calculations 
but is not implemented in many computer programs.) The last row can be deleted from 
the tableau whenever it contains all zeros. 

If nonzero artificial variables are present in the final basic set, then the program has no 
solution. Zero-valued artificial variables may appear as basic variables in the final solution 
when one or more of the original constraint equations is redundant.

With Xs^t = (x1,x2,x3,x4,x6,x7,x8,x9,x10,x11,x12,x13), x6 is the fifth element of Xs, and
x13 is the twelfth element of Xs. Using the Big M method, we have the objective:
 Maximize z = -x6 + x7 - M*x13 = Cs^t . Xs, subject to the conditions above, As . Xs = E.
We have Cs^t = (0,0,0,0,-1,1,0,0,0,0,0,-M), E^t = (0,0,0,1,1),
Xso^t = (x8,x9,x10,x11,x13), and Cso^t = (0,0,0,0,-M). [see below for definition of Xso and
Cso].

Given the Step 0 LP: maximize z = Cs^t . Xs, such that  As . Xs = E, with Xs >= 0,

Xso is the known initial feasible solution Basis vector of symbols. 
Xso is defined using the Basis variable order in the constraint equations, and not 
necessarily with the order in Xs. 
Xso has the same number of variables as the rhs vector E.
Cso is the vector of objective coefficients, taken from Cs, associated with the initial basis 
vector Xso, and in the same order as Xso. 

With these conventions, the step 0 maximization tableau is, using these matrices:
                |           Xs^t                 |    rhs       |  Basis   
              -----------------------------------------------------------
                |            As                   |   E          |  Xso      
              -----------------------------------------------------------
                |   Cso^t . As - Cs^t        | Cso^t . E  |   z

With X^t = (x1,x2,x3,x4,x6,x7,x8,x9,x10,x11,x12,x13), x6 is the fifth element of X, and
x13 is the twelfth element of X. Using the Big M method, we have the objective:
 Maximize z = -x6 + x7 - M*x13, subject to the conditions above.

Xs : cvec ([x1,x2,x3,x4,x6,x7,x8,x9,x10,x11,x12,x13 ])$
Cs : cvec ([0,0,0,0,-1,1,0,0,0,0,0, - M ])$
" maximize z  " = transpose (Cs) . Xs;
Xso : cvec([x8,x9,x10,x11,x13])$
Cso :  cvec ([0,0,0,0,-M])$
As : matrix ( [3,-2,-4,6,-1,1,1,0,0,0,0,0 ],
                  [-4,2,-1,-8,-1,1,0,1,0,0,0,0],
                  [0,-3,-2,-1,-1,1,0,0,1,0,0,0],
                  [1,1,1,1,0,0,0,0,0,1,0,0],
                  [1,1,1,1,0,0,0,0,0,0,-1,1] )$
E : cvec ([0,0,0,1,1])$
"subject to";
As . Xs = E;
"Cso^t . As - Cs^t" = transpose(Cso) . As - transpose(Cs);
"Cso^t . E " =  transpose(Cso) . E;

The last "z-row" is split into two rows (r6 and r7) according to B/N's "two phase method",
page 33, see examples in LPduality.wxmx. With two "z-rows" on the bottom, we can use
b2ratio(RL, ncol) to see the ratios needed in the minimum ratio test.

Tableau 1

vL : [x1,x2,x3,x4,x6,x7,x8,x9,x10,x11,x12,x13,rhs,Basis]$
bL : [x8,x9,x10,x11,x13,z1,z2]$
r1 : endcons (E[1,1], As[1])$
r2 : endcons (E[2,1], As[2])$
r3 : endcons (E[3,1], As[3])$
r4 : endcons (E[4,1], As[4])$
r5 : endcons (E[5,1], As[5])$
r6 : [0,0,0,0,1,-1,0,0,0,0,0,0,0]$
r7 : [-1,-1,-1,-1,0,0,0,0,0,0,1,0,-1]$
RL : [r1,r2,r3,r4,r5,r6,r7]$
tableau(RL);

Choose the x1 column as the pivot column so x1 enters the Basis. With two "z-rows", we
need to use b2ratio instead of bratio.

b2ratio (RL, 1);

The minimum ratio test is won by row 1, the x8 row, so x8 leaves the Basis.

Tableau 2 using pivot1 (RL, [row, col]):

RL : pivot1 (RL, [1, 1])$

b2ratio (RL, 3);

Choose row 4, corresponding to x11 leaving the Basis, as the pivot row.

Tableau 3 using pivot1 (RL, [row, col]):

RL : pivot1 (RL, [4, 3])$

With no more negative coefficients in the bottom z-row, we look at coefficients in the upper
z-row which are over the zero. The sixth column, the x7 column, is chosen as the pivot
column. We still need to use b2ratio since we have two z-rows.

b2ratio (RL, 6);

Tableau 4

RL : pivot1 (RL, [3, 6])$

b2ratio (RL, 4);

Tableau 5

RL : pivot1 (RL, [1, 4])$

b2ratio (RL, 2);

Tableau 6

RL : pivot1 (RL, [2, 2])$

This is the optimum tableau. z* = 29/15 = 1.93, x1 = 0, x2 = 7/60 = 0.117, x3 = 7/10 = 0.7,
x4 = 11/60 = 0.183, x5 = x6 - x7 = - x7 = - 29/15 = - 1.93, which is the same maximum
as found by maxima_lp.

Note that the artificial variable x13, although still a basic variable, is equal to 0. In contrast,
if nonzero artificial variables are present in the final basic set, then the LP has no
solution.

### Matrix Big M method

With X^t = (x1,x2,x3,x4,x6,x7,x8,x9,x10,x11,x12,x13), x6 is the fifth element of X, and so
on, finally x13 is the twelfth element of X. Using the Big M method, we have the objective:
 Maximize z = -x6 + x7 - M*x13 = c^t . X, subject to the conditions A . X = b, with X >= 0.

An initial feasible solution is
  x1,x2,x3,x4,x6,x7,x12 = 0, with five basis variables associated with the five constraints:
  x8 = 0, x9 = 0, x10 = 0, x11 = 1,x13 = 1. Note the definitions of NV and BV take into 
account the missing x5 variable in X.

X : cvec ([x1,x2,x3,x4,x6,x7,x8,x9,x10,x11,x12,x13 ])$
c : cvec ([0,0,0,0,-1,1,0,0,0,0,0, - M ])$
A : matrix ( [3,-2,-4,6,-1,1,1,0,0,0,0,0 ],
                  [-4,2,-1,-8,-1,1,0,1,0,0,0,0],
                  [0,-3,-2,-1,-1,1,0,0,1,0,0,0],
                  [1,1,1,1,0,0,0,0,0,1,0,0],
                  [1,1,1,1,0,0,0,0,0,0,-1,1] )$
b : cvec ([0,0,0,1,1])$
NV : [1,2,3,4,5,6,11 ]$
BV : [7,8,9,10,12 ]$
z = transpose(c) . X;
A . X = b;
Mdefine()$
Mbtableau();

Taking into account that in the Big M method, M is an arbitrarily large positive number,
we choose x1, ncol = 1 (which looks only at the non-basic variables in the center section)
to enter the Basis, and use Mratio (ncol) to show results of the minimum ratio test.

The second block of coefficients are the coefficients of the current non-basic variables
in Xn.

transpose (Xn);

and the current matrix N holds these coefficients:

N;

so the column number (1) we are using refers to the first column of the matrix N.
This is because B is the identity matrix (1's on the diagonal, 0's elsewhere), and
its inverse is also the identity matrix, so invert(B) . N = N. In the code for Mratio, 
the column chosen is that of the matrix invert(B) . N.

B;
invert(B);

Mratio (1);

We have chosen variable x1 (element 1 of X) to enter the Basis.
Choose x11 to leave the Basis (x11 = element 10 of X), then Mbpivot (nEnter, nLeave)
is Mbpivot (1, 10).

Mbpivot (1, 10);

x7 (ncol = 5 of the new N) has the most negative coefficient in the bottom z-row. 
x7 (element 6 in X) will enter the Basis.

Mratio(5);

The x8 row wins the minimum ratio test; x8 (element 7 in X) leaves the Basis, 
so Mbpivot (nEnter, nLeave) is Mbpivot (6, 7).

Mbpivot (6, 7);

x3 (ncol = 2, element 3 in X) has the most negative coefficient in the z-row. x3 is the
third element in X.

Mratio (2);

The x10 row wins the minimum ratio test. x10 (element 9 in X) leaves the Basis:

Mbpivot (3, 9);

Mratio (2);

Mbpivot (4, 1);

Mratio (2);

Mbpivot (2, 8);

This is the optimum tableau. z* = 29/15 = 1.93, x1 = 0, x2 = 7/60 = 0.117, x3 = 7/10 = 0.7,
x4 = 11/60 = 0.183, x5 = x6 - x7 = - x7 = - 29/15 = - 1.93, which is the same maximum
as found by maxima_lp.

Note that the artificial variable x13, although still a basic variable, is equal to 0. In contrast,
if nonzero artificial variables are present in the final basic set, then the LP has no
solution.

## B/N Prob. 3.9 using the Big M Method

Minimize w = 2*x1 + x2 + 3*x3,
  subject to
   x1 - 2*x2 + x3 >= 4,
  2*x1 + x2 + x3 <= 8,
    x1 - x3 >= 0, 
        with x1,x2,x3 >= 0.

minimize_lp (2*x1 + x2 + 3*x3, [x1 - 2*x2 + x3 >= 4, 2*x1 + x2 + x3 <= 8,
                                                    x1 - x3 >= 0], [x1,x2,x3] );

maxlp (- 2*x1 - x2 - 3*x3, [x1 - 2*x2 + x3 >= 4, 2*x1 + x2 + x3 <= 8,  x1 - x3 >= 0]);

Subtract suplus variable x4 and add artificial variable x5 to left-hand side of the first
condition. Add slack variable x6 to left-hand side of the the second condition,
Subtract surplus variable x7 from left-hand side of cond. 3.

Maximize z = - w = - 2*x1 - x2 - 3*x3 + 0*x4  - M*x5 + 0*x6 + 0*x7  = c^t . X
  subject to A . X = b, X >=0, or
   x1 - 2*x2 + x3 - x4 + x5 = 4,
  2*x1 + x2 + x3 + x6 = 8,
    x1 - x3 - x7   = 0, 
       with x1,x2,x3,x4,x5,x6,x7 >= 0.

Initial feasible solution is then x1 = x2 = x3 = x4 = x7 = 0, x5 = 4, x6 = 8, in a solution
that does not add an artificial variable x8 to the lhs of cond. 3. The basic variables in the
initial tableau are x5,x6,x7, with the last basic variable (x7) equal to 0.

X : cvec ([x1,x2,x3,x4,x5,x6,x7 ])$
c : cvec ([-2,-1,-3, 0, -M, 0, 0 ])$
A : matrix ( [1, -2,1,-1,1,0,0 ], [2,1,1,0,0,1,0], [1,0,-1,0,0,0,-1])$
b : cvec ([4,8,0])$
NV : [1,2, 3, 4 ]$
BV : [5, 6, 7 ]$
z = transpose(c) . X;
A . X = b;
Mdefine()$
Mbtableau();

With M a positive number, 2 - M is more negative than 3 - M, so choose x1 to enter the basis.

Mratio(1);

Choose x5 (the single artificial variable) to leave the basis and use Mbpivot(Enter, Leave).

Mbpivot (1,5);

The artificial variable has left the basis with value 0 (down from x5 = 4) and x1 has 
entered the basis with value x1 = x4. No more negative non-basic variable coefficients
in the z-row, optimum soln for max z = - w is z* = -8 (w* = 8) with x1 = 4,x2 = x3 = 0,
in agreement with the solution found by mimimize_lp with w.

## B/N Prob. 3.11 using the Big M Method

Minimize w = 4*x1 + 3*x2 + 2*x3 + 5*x4,
  subject to
  x1 + 2*x2 + 3*x3 + x4 >= 5,
2*x1 - x2 + 5*x3 - x4 >= 1,
2*x1 + x2  + x3 + 3*x4 >= 10,
  with x1,x2,x3,x4 >= 0. 

minimize_lp (4*x1 + 3*x2 + 2*x3 + 5*x4, [x1 + 2*x2 + 3*x3 + x4 >= 5, 
        2*x1 - x2 + 5*x3 - x4 >= 1, 2*x1 + x2  + x3 + 3*x4 >= 10], [x1,x2,x3,x4]);

float(%);

Convert to a maximization problem, subtract surplus variable x5 and add artificial
variable x6 to the left-hand side of the first constraint to convert to an equality constraints,
and proceed to so similar on the second and third constraints.

Maximize z = - w = - 4*x1 - 3*x2 - 2*x3 - 5*x4 + 0*x5 - M*x6 + 0*x7 - M*x8 + 0*x9 - M*x10 
                                 = c^t . X,
  subject to  A . X = b, X >= 0, or

  x1 + 2*x2 + 3*x3 + x4 - x5 + x6 = 5,
2*x1 - x2 + 5*x3 - x4 - x7 + x8 = 1,
2*x1 + x2  + x3 + 3*x4 - x9 + x10 = 10,

  with x1,x2,x3,x4,x5,x6,x7,x8,x9,x10 >= 0. 

X : cvec ([x1,x2,x3,x4,x5,x6,x7,x8,x9,x10 ])$
c : cvec ([-4,-3,-2, -5, 0, -M, 0, -M, 0, -M ])$
A : matrix ( [1, 2, 3, 1, -1, 1, 0, 0, 0, 0 ], 
                  [2,-1,5,-1, 0, 0, -1, 1, 0, 0],
                  [2, 1,  1, 3, 0, 0, 0, 0, -1, 1])$
b : cvec ([5, 1, 10])$
NV : [1,2, 3, 4, 5, 7, 9 ]$
BV : [6, 8, 10 ]$
z = transpose(c) . X;
A . X = b;
Mdefine()$
Mbtableau();

The x3 column has the most negative coefficient in the z-row, ncol = 3, use Mratio(ncol):

Mratio (3);

The x8 row wins the minimum ratio test, variable x8 leaves the basis. 
Use Mbpivot (Enter, Leave):

Mbpivot (3, 8);

The x4 variable (ncol = 3) has the most negative coefficient in the z-row.

Mratio (3);

Mbpivot (4, 6);

The x5 variable (ncol = 3) has the most negative coefficient in the z-row.

Mratio (3);

Mbpivot (5, 10);

In the limit of large positive M, no more negative non-basic variable coefficients in the
z-row, optimum solution for w = - z is w* = 271/16 with x1 = x2 = 0, x3 = 13/16, x4 = 49/16,
no artificial variables left in the basis, in agreement with solution found by minimize_lp.

## B/N Dual Simplex Method, DMratio (rowNum)

On p. 34, B/N list the elements of their Dual Simplex Method. We quote, with some editing:

THE DUAL SIMPLEX METHOD 

The (regular) simplex method moves the initial feasible but nonoptimal solution to an 
optimal solution while maintaining feasibility through an iterative procedure. On the other 
hand, the dual simplex method moves the initial optimal but infeasible solution to a 
feasible solution while maintaining optimality through an iterative procedure.

Iterative procedure of the B/N Dual Simplex Method for maximization.

STEP 1: Rewrite the linear programming problem by expressing all the constraints 
in ≤ form and transforming them into equations through slack variables. If a particular
given constraint has the form (for example)
      a1*x1 + a2*x2 = d, 
replace that constraint by the two conditions
     a1*x1 + a2*x2 <=  d,
     a1*x1 + a2*x2 >=  d.

Then continue to replace >= conditions by <= conditions, getting
    a1*x1 + a2*x2 <=  d,
  - a1*x1 - a2*x2 <= - d.

STEP 2: Exhibit the above problem in the form of a simplex tableau. IF the optimality 
condition is satisfied AND one or more basic variables have negative values, the dual 
simplex method is applicable. 

STEP 3: Feasibility Condition: The basic variable with the most negative value becomes 
the departing variable (D.V.) - leaves the basis. Call the row in which this value appears 
the work row. If more than one candidate for D.V. exists, choose one. 

STEP 4: Optimality Condition: Form ratios by dividing the z-row coefficients of the non-basic
variables by the corresponding negative coefficients of the work row. The nonbasic variable 
with the smallest absolute ratio becomes the entering variable (E.V.) - enters the basis. 
Designate this element in the work row as the pivot element and the corresponding column 
the work column. If more than one candidate for E.V. exists, choose one. If no element in 
the work row is negative, the problem has no feasible solution. 

STEP 5: Use elementary row operations to convert the pivot element to 1 and then to 
reduce all the other elements in the work column to zero. 

STEP 6: Repeat steps 3 through 5 until all the variables have reached nonnegative values, 
so the optimal solution is feasible.

### B/N Prob. 3.9 using B/N Dual Simplex Method

We worked B/N Prob. 3.9 above using the Big M Method.

Minimize w = 2*x1 + x2 + 3*x3,
  subject to
   x1 - 2*x2 + x3 >= 4,
  2*x1 + x2 + x3 <= 8,
    x1 - x3 >= 0, 
        with x1,x2,x3 >= 0.

minimize_lp (2*x1 + x2 + 3*x3, [x1 - 2*x2 + x3 >= 4, 2*x1 + x2 + x3 <= 8,
                                                    x1 - x3 >= 0], [x1,x2,x3] );

Step 1a:
Convert to a maximization problem, and convert >= inequality conditions to <= conditions

Maximize z = - w = - 2*x1 - x2 - 3*x3,
subject to
  - x1 + 2*x2 - x3 <= - 4,
  2*x1 + x2 + x3 <= 8,
   - x1 + x3 <= 0,
  with x1,x2,x3 >= 0.

Step1b:
Add slack variables x4,x5,x6 to the left-hand sides of the three constraint conditions
 (respectively) to arrive at constraint equations.

Maximize z = - w = - 2*x1 - x2 - 3*x3 + 0*x4 + 0*x5 + 0*x6 = c^t . X,
subject to  A . X = b, X >= 0, or:
  - x1 + 2*x2 - x3 + x4 = - 4,
  2*x1 + x2 + x3 + x5 = 8,
   - x1 + x3 + x6  = 0,
  with x1,x2,x3,x4,x5,x6 >= 0.

Take x4,x5,x6 as the basic variables, x1,x2,x3 as the non-basic variables in the initial
tableau.

X : cvec ([x1,x2,x3,x4,x5,x6 ])$
c : cvec ([-2,-1,-3, 0, 0, 0 ])$
A : matrix ( [-1, +2, -1,1, 0, 0 ], [2,1,1, 0,1, 0], [ -1, 0,1, 0, 0, 1])$
b : cvec ([- 4, 8, 0])$
NV : [1, 2, 3 ]$
BV : [4, 5, 6 ]$
z = transpose(c) . X;
A . X = b;
Mdefine()$
Mbtableau();

The B/N dual simplex method is applicable since the optimality condition is satisfied (no
z-row negative coefficients of the non-basic variables) AND one or more of the basic
variables have negative values.

The "work row" is row 1, x4 is the "departing value" (D.V.) - leaves the basis, since only
basic variable x4 has a negative value. To determing the "entering variable" (E.V.) which
enters the basis, we first check that there is at least one negative coefficient in the work
row coefficients of the non-basic variables x1,x2,x3. (If there are none, the LP is NOT 
feasible). Here there are two negative coefficients corresponding to x1 and x3. We can 
make a table.
    
x1    x2   x3
2      1     3  |   z -row
-1     2   -1   |   x4 - work row
-2    --    -3  |  z-row/work-row
 2    --     3  |  abs(zr/wr)
The column with the minimum absolute ratio is the x1 column, so x1 is the E.V., the
"entering variable".

We can use our function DMratio (rowNum) in which rowNum is the number of the
work row (top row = 1, next lower row = 2, etc.) and a two rowed matrix is returned with
the non-basic variable names as the first row and the absolute values of the needed
ratios as the second row.

DMratio (1);

We then call  Mbpivot (nEnter, nLeave), in which nEnter refers to the number of the
entering variable according to its place in the vector X, and likewise nLeave refers to the
number of the leaving variable according to its place in the vector X.

Mbpivot (1, 4);

Since all the variables have reached nonnegative values, the above optimal solution is 
feasible. z* = - w* = -8 with x1 = 4, x2 = x3 = 0 in agreement with our
previous optimum solutions for this problem.

### B/N Prob. 3.10 using B/N Dual Simplex Method

Use the Dual simplex method to solve:
  maximize z = -2*x1 - 3*x2,
   subject to
    x1 + x2 >= 2,
  2*x1 + x2 <= 10,
  x1 + x2 <= 8,
with x1,x2 >= 0,

maxlp (-2*x1 - 3*x2, [x1 + x2 >= 2, 2*x1 + x2 <= 10, x1 + x2 <= 8] );

Convert first constraint to <= form and add slack variables x3,x4,x5 to get equations.

maximize z = -2*x1 - 3*x2 + 0*x3 + 0*x4 + 0*x5,
   subject to
   - x1 - x2 + x3 = - 2,
  2*x1 + x2 + x4 = 10,
  x1 + x2 + x5 = 8,
with x1,x2,x3,x4,x5 >= 0.

X : cvec ([x1,x2,x3,x4,x5 ])$
c : cvec ([-2,-3, 0, 0, 0 ])$
A : matrix ( [-1, -1, 1,0, 0 ], [ 2,1,0, 1,0 ], [1,1,0, 0, 1])$
b : cvec ([- 2, 10, 8])$
NV : [1, 2 ]$
BV : [3, 4, 5 ]$
z = transpose(c) . X;
A . X = b;
Mdefine()$
Mbtableau();

DMratio (1);

Mbpivot (1, 3);

Since all the variables have reached nonnegative values, the above optimal solution is 
feasible,  with z* = -4, x1 = 2, x2 = 0.

### B/N Prob. 3.11 using B/N Dual Simplex Method

Minimize w = 4*x1 + 3*x2 + 2*x3 + 5*x4,
  subject to
  x1 + 2*x2 + 3*x3 + x4 >= 5,
2*x1 - x2 + 5*x3 - x4 >= 1,
2*x1 + x2  + x3 + 3*x4 >= 10,
  with x1,x2,x3,x4 >= 0. 

Convert to a maximization problem and convert >='s to <='s. Then add slack variables
x5,x6,x7 to left-hand sides.

Maximize z = - w =  - 4*x1 - 3*x2 - 2*x3 - 5*x4 + 0*x5 + 0*x6 + 0*x7 = c^t . X,
  subject to A . X = b, X >= 0, or
  - x1 - 2*x2 - 3*x3 - x4 + x5 = - 5,
- 2*x1 + x2 - 5*x3 + x4 + x6  = - 1,
- 2*x1 - x2  - x3 - 3*x4 + x7  = - 10,
  with x1,x2,x3,x4,x5,x6,x7 >= 0. 

X : cvec ([x1,x2,x3,x4,x5,x6,x7 ])$
c : cvec ([-4,-3,-2, -5, 0, 0, 0 ])$
A : matrix ( [-1, -2, -3, -1, 1, 0, 0 ], [ - 2, 1,- 5,1, 0,1, 0], [ -2, -1,-1, -3, 0, 0, 1])$
b : cvec ([- 5, -1, -10])$
NV : [1, 2, 3,4 ]$
BV : [ 5, 6, 7 ]$
z = transpose(c) . X;
A . X = b;
Mdefine()$
Mbtableau();

The optimality condition is satisfied and one or more basic variables are negative, so the
dual simplex method is applicable.

The most negative basic variable is x7 = -10 so the work row is row 3 which contains four
negative coefficients.

DMratio (3);

The minimum absolute value of the needed ratios is in column 4, corresponding to x4
so x4 is the entering variable and x7 is the leaving variable.

Mbpivot (4, 7), numer;

The most negative basic variable is x6 in row 3 which becomes the work row, x6 leaves
the basis. The work row has two negative non-basic variable coefficients.

DMratio (3);

The non-basic variable with the smallest absolute ratio is x3 with becomes the entering
variable.

Mbpivot (3, 6);

float(%);

Since all the variables have reached nonnegative values, the above optimal solution is 
feasible, and we have the same solution as found earlier.

The B/N dual simplex method requires 2 pivots as compared with 3 pivots using the Big M
method above.

### B/N Prob. 3.13 using B/N Dual Simplex Method

Use the dual simplex method to solve
  minimize w = 2*x1 + x2,
subject to
  x1 + x2  = 4,
  2*x1 - x2 >= 3,
 with x1,x2 >= 0.

The above problem is rewritten as follows:
minimize w = 2*x1 + x2,
subject to
  x1 + x2  <= 4,
  x1 + x2  >= 4,
  2*x1 - x2 >= 3,
 with x1,x2 >= 0.

We then convert to a maximization problem and convert >= conditions to <= conditions.
The above problem is rewritten as follows:
maximize z = - w = - 2*x1 - x2,
subject to
  x1 + x2  <= 4,
 - x1 - x2  <= -4,
 - 2*x1 + x2 <= - 3,
 with x1,x2 >= 0.

Convert inequality conditions to equality conditions using slack variables x3,x4,x5.
maximize z = - w = - 2*x1 - x2 +0*x3  + 0*x4  + 0*x5 = c^t . X,
subject to A . X = b, X >= 0, or
  x1 + x2 + x3  = 4,
 - x1 - x2 + x4 = -4,
 - 2*x1 + x2 + x5 = - 3,
 with x1,x2,x3,x4,x5 >= 0.

X : cvec ([x1,x2,x3,x4,x5 ])$
c : cvec ([-2,-1,0, 0, 0 ])$
A : matrix ( [ 1, 1, 1, 0, 0 ], [ -1,-1,0, 1,0 ], [ -2, 1,0, 0, 1])$
b : cvec ([4, - 4, -3 ])$
NV : [1, 2 ]$
BV : [3,4, 5  ]$
z = transpose(c) . X;
A . X = b;
Mdefine()$
Mbtableau();

The optimality condition is satisfied and at least one of the basic variables is negative, so
the dual simplex method is applicable. The basic variable with the most negative value 
becomes the departing variable (D.V.) - leaves the basis; that is x4 in row 2.

DMratio (2);

The nonbasic variable with the smallest absolute ratio becomes the entering variable 
(E.V.) - enters the basis; that is x2. Use Mbpivot (nEnter, nLeave).

Mbpivot (2, 4);

The optimality condition is satisfied and one basic variable is negative (x5 in row 3).

DMratio (3);

The non-basic variable with the smallest absolute ratio (x1) is the entering variable.

Mbpivot (1, 5);

float(%);

Since all the variables have reached nonnegative values, the above optimal solution is 
feasible. w* = -z* = 19/3 with x1 = 7/3 = 2.33, x2 = 5/3 = 1.67.

### B/N Prob. 3.14 using B/N Dual Simplex Method

minimize w = 6*x1 + 3*x2 + 4*x3,
 subject to
  x1 + 6*x2 + x3 = 10,
  2*x1 + 3*x2 + x3 = 15,
with x1,x2,x3 >= 0.

maximize z = - w = - 6*x1 - 3*x2 - 4*x3,
 subject to
 x1 + 6*x2 + x3 <= 10,
 x1 + 6*x2 + x3 >= 10,
  2*x1 + 3*x2 + x3 <= 15,
  2*x1 + 3*x2 + x3 >= 15,
with x1,x2,x3 >= 0.

maximize z = - w = - 6*x1 - 3*x2 - 4*x3,
 subject to
 x1 + 6*x2 + x3 <= 10,
 - x1 - 6*x2 - x3 <= - 10,
  2*x1 + 3*x2 + x3 <= 15,
 - 2*x1 - 3*x2 - x3 <= - 15,
with x1,x2,x3 >= 0.

maximize z = - w = - 6*x1 - 3*x2 - 4*x3 + 0*x4 + 0*x5 + 0*x6 + 0*x7 = c^t . X,
 subject to A . X = b, X >= 0, or
 x1 + 6*x2 + x3 + x4 = 10,
 - x1 - 6*x2 - x3 + x5 = - 10,
  2*x1 + 3*x2 + x3 + x6 = 15,
 - 2*x1 - 3*x2 - x3 + x7 = - 15,
with x1,x2,x3,x4,x5,x6,x7 >= 0.

X : cvec ([x1,x2,x3,x4,x5,x6,x7 ])$
c : cvec ([-6,-3,-4, 0, 0, 0, 0 ])$
A : matrix ( [1, 6, 1, 1, 0, 0, 0 ], [ - 1, -6,-1,0, 1, 0, 0], [ 2, 3, 1, 0, 0, 1, 0],
     [ - 2, - 3, - 1, 0, 0, 0, 1])$
b : cvec ([10, -10, 15, -15])$
NV : [1, 2, 3 ]$
BV : [4, 5, 6, 7 ]$
z = transpose(c) . X;
A . X = b;
Mdefine()$
Mbtableau();

DMratio(4);

Mbpivot (2, 7);

DMratio (2);

Mbpivot (1, 4);

Since all the variables have reached nonnegative values, the above optimal solution is 
feasible. w* = -z* = 125/3 with x1 = 20/3, x2 = 5/9, x3 = 0.