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

**conditions, while sometimes we search for**

*necessary***conditions. In general, analysis generate theories, which then guide us to develop algorithms.**

*sufficient*`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 c`^{T} x
s.t. A x = b
x โฅ 0
where
A โ R^{mรn} : matrix
m : the number of constraints
n : the number of variables
b โ R^{mร1} : right hand side column
c โ R^{nร1} : coefficients of variables
x โ R^{nร1} : decision variable

By dividing `x`

to `x`

(basis variables) and _{B}`x`

(nonbasis variables), we have:_{N}

`max c`_{B}^{T} x_{B} + c_{N}^{T} x_{N}
s.t. A_{B} x_{B} + A_{N} x_{N} = b
x_{B}, x_{N} โฅ 0

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

`max c`_{B}^{T} [A_{B}^{-1} (b - A_{N} x_{N})] + c_{N}^{T} x_{N}
โน max c_{B}^{T} A_{B}^{-1} b - [c_{B}^{T} A_{B}^{-1} A_{N} - c_{N}^{T}] x_{N}
s.t. x_{B} = A_{B}^{-1} (b - A_{N} x_{N})
โน I x_{B} + A_{B}^{-1} A_{N} x_{N} = A_{B}^{-1} b
x_{B}, x_{N} โฅ 0

Let’s ignore the sign constraints and let `z`

be the objective value, we then have:

`z + [c`_{B}^{T} A_{B}^{-1} A_{N} - c_{N}^{T}] x_{N} = c_{B}^{T} A_{B}^{-1} b
I x_{B} + A_{B}^{-1} A_{N} x_{N} = A_{B}^{-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:

Basis `X` | Nonbasis `X` | Right-hand side | ||

Reduced cost | 0 | `c` | `c` | 0 |

Constraint coefficient | `I` | `A` | `A` | 1, …, m |

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 x`_{1}
s.t. 2 x_{1} - x_{2} + x_{3} = 4
2 x_{1} + x_{2} + x_{4} = 8
x_{2} + x_{5} = 3
x_{i} โฅ 0, โ i = 1, ..., 5

In the matrix representation, we have:

`c`^{T} = [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 `x`

, and nonbasis variables _{B} = (x_{1}, x_{4}, x_{5})`x`

, we then have:_{N} = (x_{2}, x_{3})

`c`_{B}^{T} = [1 0 0] c_{N}^{T} = [0 0]
A_{B} = 2 0 0 A_{N} = -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 + [c`_{B}^{T} A_{B}^{-1} A_{N} - c_{N}^{T}] x_{N} = c_{B}^{T} A_{B}^{-1} b
I x_{B} + A_{B}^{-1} A_{N} x_{N} = A_{B}^{-1} b

Given the basis `x`

, we may see what’s the current basic feasible solution by calculating all the values for the x_{B} = (x_{1}, x_{4}, x_{5})_{B}:

`x`_{B} = A_{B}^{-1} b = 1/2 0 0 ร 4 = 2 = x_{1}
-1 1 0 8 4 x_{4}
0 0 1 3 8 x_{5}
z = c_{B}^{T} A_{B}^{-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 `x`

, the reduced costs _{N} = (x_{2}, x_{3})`c`

are^{-}_{N}^{T}

`c`^{-}_{N}^{T} = c_{B}^{T} A_{B}^{-1} A_{N} - c_{N}^{T} = [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, `x`

should _{2}** enter**. For

`x`_{B} = (x_{1}, x_{2}, x_{3})

we have:`A`_{B}^{-1} A_{2} = 1/2 0 0 ร -1 = -1/2 A_{B}^{-1} b = 2 ratio test x_{1}: 2 / -1/2 โน 0
-1 1 0 1 2 4 x_{4}: 4 / 2 = 2
0 0 1 1 1 3 x_{5}: 3 / 1 = 3

According to the ratio test, `x`

should _{4}** leave**.

**Iteration 2**

Now we have x_{4} left and x_{2} entered, the new basis `x`

, and _{B} = (x_{1}, x_{2}, x_{5})`x`

. Repeat the procedure above:_{N} = (x_{3}, x_{4})

`c`_{B}^{T} = [1 0 0] c_{N}^{T} = [0 0]
A_{B} = 2 -1 0 A_{N} = 1 0 b = 4
2 1 0 0 1 8
0 1 1 0 0 3

For the basis variables `x`

:_{B}

`x`_{B} = A_{B}^{-1} b = 1/4 1/4 0 ร 4 = 3 = x_{1}
-1/2 1/2 0 8 2 x_{2}
1/2 -1/2 1 3 1 x_{5}
z = c_{B}^{T} A_{B}^{-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 = (x`

._{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (3, 2, 0, 0, 1)

For the nonbasis variables `x`

, calculate its reduced costs:_{N}

`c`^{-}_{N}^{T} = c_{B}^{T} A_{B}^{-1} A_{N} - c_{N}^{T} = [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 `A`

, which explains why the execution time of simplex method is _{B}^{-1}** usually** proportional to

`m`^{3}

, 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 A_{B} and previous A_{B}. Calculating current A_{B}^{-1} can be faster using the previous A_{B}^{-1}. However you need to make sure that the A_{B} 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*

Don't forget to sign up newsletter, don't miss any chance to learn.

Or share what you've learned with friends!

Tweet