The simplex method is the most fundamental tool in linear programming, it is a single algorithm that is able to solve any kinds of linear program regardless of its format, number of variables and constraints. We firstly transform the linear program to a standard form, then we focus on the standard form. The idea of the Simplex method is to search the corners or extreme points of feasible region (also called basic feasible solutions). If it can not find a corner where all the neighboring corners are as good as this one, then it says this is the optimal.
Extreme Points
For a set S โ Rn , a point x is an extreme point, if there does NOT exist a three-tuple (x1, x2, ฮป) such that x1 โ S \ {x}, x2 โ S \ {x}, ฮป โ (0, 1), and x = ฮป x1 + (1 - ฮป) x2 . It mean if x can be represented as a convex combination of x1 and x2, then x is not an extremer point.
For any linear program, if there is an optimal solution, there is an extreme point optimal solution. The simplex algorithm is built on this proposition. Warning, it is not true that “if a solution is optimal, it is an extreme point.”
Standard Form of Linear Programs
If a linear program is in the standard form if:
- all right hand side values are non-negative
- all variables are non-negative, and
- all constraints are equalities
There is no restriction on the objective function. All the requiremnts are on the constraints. For any linear program, we may convert it to standard form:
| Before transform | After transform | |
| RHS | 2 x1 + 3 x2 โค -4 | -2 x1 – 3 x2 โฅ 4 |
| variables | 2 x1 + 3 x2 โค -4 , x1 โค 0 xi is free | -2 x1 – 3 x2 โฅ 4 , x1 โฅ 0 xi‘ – xi”, where xi‘, xi” โฅ 0 |
| equality | 2 x1 + 3 x2 โค 4 2 x1 + 3 x2 โฅ 4 | 2 x1 + 3 x2 + x3 = 4, x3 โฅ 0 2 x1 + 3 x2 – x3 = 4, x3 โฅ 0 |
We may express a standard form in matrices, the general form is always in this way, where A โ Rm*n is coefficient matrix, b โ Rm is RHS vector, and c โ Rn is objective vector:
max or min cT x , such that A x = b, x โฅ 0Basic Solutions
In a linear program with m constraints and n variables, usually m < n (which means more columns than rows of A) , because if it is m โฅ n, there is either one or zero solution, then we do not need optimization. We may assume that A has m pivots, i.e. all rows of A are independent to each other. In the case that there are dependent rows, you need to check whether the solution is feasible and eliminate the redundant constraints. It is important that all the rows (constraints) are independent.
A basic solution to a standard form of linear program is a solution that both has n-m variables being equal to 0, and satisfies A x = b. First, we select n-m (non-basic) variables and set them to zero. Then, we try to solve the remaining m (basic) variables. The set of variables is called basis. As long as the m columns form a non-singular (invertible) m-by-m matrix AB (there are n-choose-m ways to define the AB), we are able to solve AB x = b. Then we could just focus on basic variables, since all non-basic variables are just 0.
xB = AB-1 b (basic variables)
xN = 0 (non-basic variables)Basic Feasible Solutions
Among all basic solutions, if a solution also satisfies x โฅ 0, then it is a basic feasible solution. So a basic feasible solution to a standard form linear program is a basic solution whose basic variables are all non-negative.
Basic feasible solutions are just extreme points! These 2 things are equivalent. Extreme points are defined geometrically, basic feasible solutions are defined algebraically. To search among basic feasible solutions, we keep moving to a better adjacent basic feasible solution from the current one.
Adjacent bases and adjacent basic feasible solutions
Two bases are adjacent if exactly one of their variables, not values, is different (n-1 variables are the same). Two basic feasible solutions are adjacent if their associated bases are adjacent. Around the current basic feasible solution, there should be some improving direction, otherwise, current basic feasible solution is optimal.
The Simplex Method
All we need is to search among basic feasible solutions, which means geometrically we search among extreme points. Algebraically, to move to an adjacent basic feasible solution, we need to replace one basic variable with a non-basic variable. We shall select two things:
- one non-basic variable to enter the basis
- one basic variable to leave the basis
Selecting 1 non-basic variable to enter means making it nonzero: increasing its value from zero to a positive number. While this new variable increases, we identify existing basic variables that decrease. The first one that hits zero will be selected to leave the basis and become non-basic variable.
We keep changing the basis, meanwhile keep track of the objective value (also called z-value), until we find an optimal solution.
System of Equalities
Besides all of the constraints in the standard form of linear program, the objective function is also included and called 0th constraint. This is becomes another equation that must be satisfied through out the whole process. We keep modifying the value for x, so that we may find feasible solutions with higher values of z.
In general, a linear program is solved in two stages:
- Find the initial basic feasible solution
- Keep improving current basic feasible solution until find the optimal basic feasible solution
Keep improving the current basic feasible solution
The 0th constraint helps us identify which non-basic variable should be selected to enter the basis. We look for positive coefficient for a min problem, or negative coefficient for max problem. When none of non-basic variables can help further improve the objective function, the optimal solution is found.
The ratio between “right hand side value” and the entering column of selected non-basic variable helps us identify which basic variable will hit zero first, then leaving the basis.
But this method tedious, because increasing a non-basic variable will affect all basic variables and z value, this method won’t work find when there are thousands of variables and constraints. We need a better way.
Keep improving with updating the system
We found the process can be easily done, when these conditions hold true:
- The 0th constraint contains no basic variable.
- The 1st to m-th constraint contains exactly 1 basic variable.
In other words, for basic columns, we want these characteristics:
- A zero vector in 0th constraint.
- Identity matrix in 1st to m-th constraints.
Every time we get a new basis, we need to update the system using elementary row operations, so that the system exhibits characteristics above.
Identifying Unboundedness
Unboundedness of a linear program will be found when doing ratio test, there is no basic variable can leave the basis.
Feasibility of Linear Programs
If you randomly pick a few columns as basic columns to build a matrix AB, it is not easy to make sure the matrix is invertible before you try Gaussian elimination. Even though the matrix is invertible, you can not guarantee AB b โฅ 0 unless you already solve it. So, it is hard to tell whether the initial feasible solution exists.
The two-phase implementation
Given a standard form of linear program:
(P) min CT x such that A x = b, x โฅ 0we construct a phase-I linear program, by adding artificial variables y and change the objective function:
(Q) min 1T y such that A x + I y = b, x โฅ 0, y โฅ 0Immediately (Q) has a trivial basic feasible solution (x, y) = (0, b). We then apply the simplex method on the phase-I linear program, we want to see whether it is possible to find an optimal solution such that no y is positive.
The (P) is feasible if and only if (Q) has an optimal basic feasible solution (x, y) = (x’, 0). In this case, the x’ is a basic feasible solution of (P).
Once we get all the y’s zero, then x’ can be treated as an initial basic feasible solution for (P). Then we run simplex method on (P) – this is phase-II.
My Certificate
For more on The Simplex Method, please refer to the wonderful course here https://www.coursera.org/learn/operations-research-algorithms
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
