Simplex Algorithm

• The simplex algorithm solves linear programming problems with more than 2 variables — too many to draw on a graph.
• Slack variables turn ≤ inequalities into equations so we can put them in a table.
• The initial tableau organises all the equations and the objective function into a grid.
• One "iteration" of the algorithm = pivot column → θ-values → pivot row → row operations. Repeat until no negative numbers remain in the objective row.
• When a problem has ≥ constraints or asks you to minimise, plain simplex doesn't work directly — you need surplus and artificial variables.
• The two-stage method first finds *any* feasible starting point (by maximising a helper function I), then runs simplex normally to optimise P.
• The Big-M method is a one-stage shortcut alternative — it bakes a penalty for artificial variables straight into the objective function using a "very large number" M.
• Minimising C is done by maximising P = −C, then flipping the sign back at the end.

You've probably solved linear programming (LP) problems before using the graphical method: draw the constraints as lines, shade the feasible region, and test the vertices (corners) to find the best one. That works brilliantly — as long as you only have 2 decision variables, because you can draw them on x-y axes.

But what if your furniture company makes chairs, tables, and bookshelves? That's 3 variables — and you'd need a 3D graph. Add a fourth product and you're completely stuck with pictures. That's exactly where the simplex algorithm comes in: it does the same job as the graphical method (checking corner points of the feasible region) but algebraically, using a table instead of a picture. It can handle any number of variables.

There's one catch: to start hopping between vertices, the algorithm needs a vertex to start at — and it always wants to start at the origin (make 0 of everything). If the origin is inside your feasible region (true for problems where you're only ever constrained by "at most" limits, i.e. all ≤), you're good to go immediately. If the origin ISN'T in the feasible region (which happens when you have ≥ constraints, like "must produce at least 20 units"), you need extra machinery first — that's the two-stage method or Big-M method, covered later in this guide.

The simplex algorithm works with equations, not inequalities. But our constraints are things like 2x + 3y ≤ 10. We need to convert that ≤ into an =.

2x + 3y s₁

s₁ = 0 s₁

P = 8x + 5y + 7z