How the Simplex Algorithm works
[math]\displaystyle{ }[/math]Let's consider a simple linear programming problem.
Maximize \(2x+y\) subject to
- \(x, y \geq 0\),
- \(x-y\leq 3\),
- \(x+y\leq 7\),
- \(3y-x\leq 9\).
[Figure 1]
The feasible region is always a convex polygon/polyhedron/polytope.
We turn the constraints int equations by introducing slack variables \(s\), \(t\), \(u\):
Maximise \(P = 2x+y\) subject to
- \(x, y, s, t, u \geq 0\),
- \(x-y+s = 3\),
- \(x+y+t = 7\),
- \(-x+3y+u = 9\).
[Figure 2]
Each point of the feasible region now has five non-negative coordinates \((x, y, s, t, y)\), each measuring its perpendicular distance from an axis or a constraint line. For the point shown, \((x, y, s, t, u) = (2, 2, 3, 3, 5)\).
[Figure 3]
Unless the problem is degenerate, the optimum is reached at one vertex of the feasible region. We can find it geometrically by plotting lines of constant \(P\) and sliding down until the line hits the feasible region.
To use the simplex algorithm, we write the definition of \(P\) and the constraint equations in tabular form.
| \(x\) | \(y\) | \(s\) | \(t\) | \(u\) | ||
|---|---|---|---|---|---|---|
| \(P\) | −2 | −1 | 0 | 0 | 0 | 0 |
| \(s\) | 1 | −1 | 1 | 0 | 0 | 3 |
| \(t\) | 1 | 1 | 0 | 1 | 0 | 7 |
| \(u\) | −1 | 3 | 0 | 0 | 1 | 9 |
We can start at any vertex, but let's start at the origin. At any vertex of the feasible region, two variables are zero: in this case, \(x\) and \(y\). The others will be non-zero in a way that satisfies the constraint equations.
In the algorithm, we move from vertex to vertex along the edges of the feasible region, always increasing the objective function. If we move right from the origin, increasing \(x\), that will increase \(P\) by 2 units for each unit increase in \(x\).