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 → applicationsWe 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 variableBy 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 ≥ 0Next, 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 ≥ 0Let’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 bTherefore, given any valid choice of B (basis variables) and N (nonbasis variables), we may use the following table to calculate the simplex tableau:
Basis XB | Nonbasis XN | Right-hand side | ||
| Reduced cost | 0 | cBT AB-1 AN - cNT | cBT AB-1 b | 0 |
| Constraint coefficient | I | AB-1 AN | AB-1 b | 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 x1
s.t. 2 x1 - x2 + x3 = 4
2 x1 + x2 + x4 = 8
x2 + x5 = 3
xi ≥ 0, ∀ i = 1, ..., 5In 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 3Iteration 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 3Next 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 bGiven 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
3At 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 0Since 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 = 3According 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 3For 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
1The 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 0Since 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
Don't forget to sign up newsletter, don't miss any chance to learn.
Or share what you've learned with friends!
Tweet
