# Matrix Presentation of Simplex Method When it comes to Operations Research, we are mainly talking about optimization problems, so the theories are mainly optimality conditions. They basically mean for an optimization problem, somehow there should be an optimal solution. We want to get the conditions which will make the optimal solution satisfy. Typically we search for the necessary conditions, while sometimes we search for sufficient conditions. In general, analysis generate theories, which then guide us to develop algorithms.

``analysis → theory → algorithm → models → applications``

We have optimality conditions for linear programming, integer programming, and nonlinear programming, they are Duality, Total unimodularity, and the KKT condition, correspondingly.

## The Simplex Method

Simplex method is a popular algorithm for linear programming. In the previous course, we have known how to use simplex method in the form of tableau to solve linear programs, however the problem is that you are doing lots of calculation in the tableau that is actually not necessary.

Another way of doing simplex method is to use the matrix representation. Using the matrix representation is exactly the same as using the tableau. But you don’t need to calculate the whole tableau, you just need to focus on the things that you need.

Consider a standard form of linear program:

``````max cT x
s.t. A x = b
x ≥ 0
where
A ∈ Rm×n : matrix
m : the number of constraints
n : the number of variables
b ∈ Rm×1 : right hand side column
c ∈ Rn×1 : coefficients of variables
x ∈ Rn×1 : decision variable``````

By dividing `x` to `xB` (basis variables) and `xN` (nonbasis variables), we have:

``````max cBT xB + cNT xN
s.t. AB xB + AN xN = b
xB, xN ≥ 0``````

Next, we could rearrange the constraints, and objective function to get the standard form linear program:

``````max cBT [AB-1 (b - AN xN)] + cNT xN
⟹ max cBT AB-1 b - [cBT AB-1 AN - cNT] xN

s.t. xB = AB-1 (b - AN xN)
⟹ I xB + AB-1 AN xN = AB-1 b
xB, xN ≥ 0``````

Let’s ignore the sign constraints and let `z` be the objective value, we then have:

``````z +       [cBT AB-1 AN - cNT] xN = cBT AB-1 b
I xB +           AB-1 AN xN =     AB-1 b``````

Therefore, given any valid choice of B (basis variables) and N (nonbasis variables), we may use the following table to calculate the simplex tableau:

We want to use matrix notations to represent everything that we need to have in the tableau. When we later run simplex iterations, we don’t need to do row operations, pivoting, reduced cost check, nor the ratio testing. Instead, we are going to work on the these matrices.

### An Example

Consider the example:

``````max    x1
s.t. 2 x1 - x2 + x3           = 4
2 x1 + x2      + x4      = 8
x2           + x5 = 3
xi ≥ 0, ∀ i = 1, ..., 5``````

In the matrix representation, we have:

``````cT = [1 0 0 0 0]
A = 2 -1 1 0 0      b = 4
2  1 0 1 0          8
0  1 0 0 1          3``````

#### Iteration 1

Given basis variables `xB = (x1, x4, x5)`, and nonbasis variables `xN = (x2, x3)`, we then have:

``````cBT = [1 0 0] cNT = [0 0]
AB = 2  0 0   AN = -1 1   b = 4
2  1 0        1 0       8
0  0 1        1 0       3``````

Next we want to use them to get a tableau (sometimes we don’t need to construct the whole tableau, we just need part of it):

``````z +       [cBT AB-1 AN - cNT] xN = cBT AB-1 b
I xB +           AB-1 AN xN =     AB-1 b``````

Given the basis `xB = (x1, x4, x5)`, we may see what’s the current basic feasible solution by calculating all the values for the xB:

``````xB = AB-1 b = 1/2 0 0 × 4 = 2 = x1
-1  1 0   8   4   x4
0  0 1   3   8   x5

z = cBT AB-1 b = [1 0 0] 2 = 2
4
3``````

At this moment, the basic feasible solution is `x = (2, 0, 0, 4, 3)`.

For the nonbasis `xN = (x2, x3)`, the reduced costs `c-NT` are

``````c-NT = cBT AB-1 AN - cNT = [1 0 0] 1/2 0 0 × -1 1 - [0 0] = [-1/2 1/2]
-1  1 0    1 0
0  0 1    1 0``````

Since the first -1/2 is negative, according the rules of tableau, `x2` should enter. For `xB = (x1, x2, x3)` we have:

``````AB-1 A2 = 1/2 0 0 × -1 = -1/2    AB-1 b = 2   ratio test x1:  2 / -1/2 ⟹ 0
-1  1 0    1     2             4              x4:  4 / 2 = 2
0  0 1    1     1             3              x5:  3 / 1 = 3``````

According to the ratio test, `x4` should leave.

#### Iteration 2

Now we have x4 left and x2 entered, the new basis `xB = (x1, x2, x5)`, and `xN = (x3, x4)`. Repeat the procedure above:

``````cBT = [1 0 0] cNT = [0 0]
AB = 2  -1 0   AN = 1 0   b = 4
2  1  0        0 1       8
0  1  1        0 0       3``````

For the basis variables `xB`:

``````xB = AB-1 b = 1/4  1/4 0 × 4 = 3 = x1
-1/2  1/2 0   8   2   x2
1/2 -1/2 1   3   1   x5

z = cBT AB-1 b = [1 0 0] 3 = 3
2
1``````

The objective value (3) is greater than that of previous iteration (2), and the current best feasible solution is `x = (x1, x2, x3, x4, x5) = (3, 2, 0, 0, 1)`.

For the nonbasis variables `xN`, calculate its reduced costs:

``````c-NT = cBT AB-1 AN - cNT = [1 0 0]  1/4  1/4 0 × 1 0 - [0 0] = [1/4 1/4]
-1/2  1/2 0   0 1
1/2 -1/2 1   0 0``````

Since both of reduced costs are positive, no variable should enter the basis. The best feasible solution we have got is optimal.

### Caveats

The bottleneck of this method is the calculation of `AB-1`, which explains why the execution time of simplex method is usually proportional to `m3`, where m is the number of constraints.

Actually we can be faster, because the only difference between the current basis B and the previous version of basis B is one variable, i.e. there is only one column that is different between the current AB and previous AB. Calculating current AB-1 can be faster using the previous AB-1. However you need to make sure that the AB is still invertible after changing one column.

## My Certificate

For more on Matrix Presentation of Simplex Method, please refer to the wonderful course here https://www.coursera.org/learn/operations-research-theory

## Related Quick Recap

I am Kesler Zhu, thank you for visiting my website. Check out more course reviews at https://KZHU.ai

All of your support will be used for maintenance of this site and more great content. I am humbled and grateful for your generosity. Thank you!

 Your generosity and kindness is overwhelming!Donate \$1.99 - Good job!Donate \$4.99 - Keep it up!Donate \$14.99 - Very helpful!Donate \$29.99 - Looking forward to more! 