Description of the Simplex Algorithm
Here I'm explaining the simplex algorithm, which is hard to understand, although simple to implement once you understood. I have also supplied some links I found useful while studying the subject. I hope you won't need them, but they are there for precaution newertheless.
The simplex algorithm can be used to solve linear programming problems. You're looking for a largest or smallest value for a variable, which is constrained by linear inequalities. Or possibly you're looking for a solution that follows the constraints in the first place. Here's an example of such problem:
maximize z = 50a + 30ba/3 + b/5 <= 1a/2 + b/7 <= 5a, b >= 0
To solve it using simplex algorithm, you rewrite it into it's matrix form:
| = | z | a | b | s1 | s2 | solution ||---|---|-----|-----|----|----|----------|| 0 | 1 | -50 | -30 | | | z = 0 || 1 | | 1/3 | 1/5 | 1 | | s1 = 1 || 5 | | 1/2 | 1/7 | | 1 | s2 = 5 |
When carrying out the simplex algorithm, you're pivoting through this table. It means you select a variable on the objective row and add it into the solution. For instance. Say you would enter with the variable a here, the simplex algorithm would determine the exiting variable. The result would be this:
| = | z | a | b | s1 | s2 | solution ||-----|---|-----|--------|------|----|----------|| 150 | 1 | | 0 | 150 | | z = 150 || 3 | | 1 | 3/5 | 3 | | a = 3 || 7/2 | | | -11/70 | -3/2 | 1 | s2 = 7/2 |
To understand the algorithm, you need to understand what this table means, how to produce such table out of your problem, how the pivot operation is carried out and which variable to enter into the solution to maximize or minimize the z.
The table of the simplex algorithm is always in a basic feasible solution.
Basic Feasible Solution
The solution space formed by inequality constraints can be thought as convex. It means that the local maxima is the optimal solution. It still might be unbounded and there might be multiple solutions. But if you have one basic feasible solution, you can iteratively pivot it into a better solution and eventually reach one of the best solutions.
The basic feasible solution consists of variables that are in basis. Every variable that is not in a basis is zero. It means you can read the solution from the table directly. Here's the above table, only with the basis variable columns:
| = | z | a | s2 ||-----|---|-----|----|| 150 | 1 | | || 3 | | 1 | || 7/2 | | | 1 |
Pivoting the table is equivalent to changing a "perspective". The system of linear inequalities stays the same, but after the pivot operation you've got a different viewpoint and a solution.
Why every variable needs to be larger than zero? I guess that's because they can be then treated as same. In the basic feasible solution the only inequality constraints are of form: s >= 0. Every row in the table denotes a linear equality. Therefore if the every variable in the solution stays nonnegative, the constraints are satisfied.
Pivoting algorithm
The pivoting in simplex algorithm exploits elementary row operations, as every row in the table represents a linear equation. If you multiply any of the equations with a nonzero constant, you get an equivalent system of equations. Also if you then add that row to an another, the system still stays the same.
Whenever you pivot with a variable, you pick the leaving variable such that the table stays in basic feasible solution. It happens by comparing what the value of the entering variable becomes, and selecting the smallest value. This way none of the variables in basis end up below zero.
Lets consider how the leaving row was selected in the table beginning of this blog post. I marked the entering and leaving variable with a colon:
| = | z |:a | b | s1 | s2 | solution | =/a ||---|---|-----|-----|----|----|----------|-----|| 0 | 1 | -50 | -30 | | | z = 0 | || 1 | | 1/3 | 1/5 | 1 | |:s1 = 1 | 1*3 || 5 | | 1/2 | 1/7 | | 1 | s2 = 5 | 5*2 |
We can't select the s2 as leaving variable, because the table would become:
| = | z | a | b | s1 | s2 | solution || 500 | 1 | | -110/7 | | | z = 0 || -7/3 | | | -23/35 | 1 | 6 | s1 = -7/3 || 10 | | 1 | 2/7 | | 2 | a = 5*2 |
s1 is negative, so this is no longer a basic feasible solution.
So which entering variable to select? It depends if you're maximizing or minimizing. If you select a negative variable from the objective row, z increases. If you select positive, z decreases.
Finding the initial basic feasible solution
So you need to get your system into basic feasible solution. If you can set every variable zero, that is all your constraints allow every variable you have to be zero. You can create a solution by adding slack variables:
maximize z = 50a + 30ba/3 + b/5 <= 1a/2 + b/7 <= 5a, b >= 0Add slack variables s1 and s2maximize z = 50a + 30ba/3 + b/5 + s1 = 1a/2 + b/7 + s2 = 5a, b, s1, s2 >= 0| = | z | a | b | s1 | s2 | solution ||---|---|-----|-----|----|----|----------|| 0 | 1 | -50 | -30 | | | z = 0 || 1 | | 1/3 | 1/5 | 1 | | s1 = 1 || 5 | | 1/2 | 1/7 | | 1 | s2 = 5 |
But if the another equation would be a/2 + b/7 >= 5, you could no longer do this, as the slack variable would become negative. Also if your row is an equality already, you wouldn't have a slack variable! Well when you don't have slack variables that are already in basis, you can create error variables:
maximize z = 50a + 30ba/3 + b/5 <= 1a/2 + b/7 >= 5a, b >= 0Add slack variables s1 and s2, and error variable e1maximize z = 50a + 30bbut first minimize w = e1a/3 + b/5 + s1 = 1a/2 + b/7 - s2 + e1 = 5a, b, s1, s2, e1 >= 0| = | z | w | a | b | s1 | s2 | e1 ||---|---|---|-----|-----|----|----|----|| 0 | 1 | | -50 | -30 | | | || 0 | | 1 | | | | | -1 || 1 | | | 1/3 | 1/5 | 1 | | || 5 | | | 1/2 | 1/7 | | -1 | 1 |pricing out the e1, so it can enter the basis| = | z | w | a | b | s1 | s2 | e1 | solution ||---|---|---|-----|-----|----|----|----|----------|| 0 | 1 | | -50 | -30 | | | | z = 0 || 5 | | 1 | 1/2 | 1/7 | | -1 | | w = 5 || 1 | | | 1/3 | 1/5 | 1 | | | s1 = 1 || 5 | | | 1/2 | 1/7 | | -1 | 1 | e1 = 5 |
Next you would attempt to minimize the w, if w doesn't end up zero, it means that the original system was infeasible. Otherwise you could remove the error variable columns, the error objective and continue to solving the original system.
Many sources I had when studying failed to mention the pricing out -part of the algorithm. The error variable isn't in basis initially, because it appears in your objective. So you need to apply the row addition to eliminate it from your objective row.
Further help and an example
I have written and pasted the simplex.py along this post. The code is explained and documented. It isn't complete example but I hope it steers into the right direction in understanding the algorithm.
To figure out the simplex method, I found the gatech.edu -description and later the examples in the wikipedia useful. To continue, the page about matrices seem also quite good.