Linear Programming Simplex Method: A Complete Guide

The simplex method is an algorithm for solving linear programming problems: optimising a linear objective function subject to linear constraints. Developed by George Dantzig in 1947, it moves along the corners (vertices) of the feasible region to find the best solution.

It matters because linear programming runs behind countless decisions: how factories schedule production, how airlines crew flights, how investors allocate money. The simplex method is one of the most used algorithms of the 20th century.

Key Concepts

• Objective function: the linear expression to maximise or minimise, e.g. Z = 3x + 5y.
• Feasible region: the set of points satisfying all constraints; its optimum lies at a vertex.
• Standard form: maximisation with ≤ constraints converted to equations by adding slack variables.
• Basic feasible solution (BFS): a vertex of the feasible region used as a candidate answer.
• Optimality condition: when all net evaluations Zⱼ − Cⱼ ≤ 0 (for maximisation), the current solution is optimal.

Formulas

Standard form: maximise Z = cTx subject to Ax = b, x ≥ 0.

• Add slack variable sᵢ ≥ 0 to each ≤ constraint: aᵢx ≤ bᵢ becomes aᵢx + sᵢ = bᵢ.
• Entering variable: the non-basic variable with the largest positive Zⱼ − Cⱼ.
• Leaving variable: minimum ratio test — min{bᵢ/aᵢⱼ} over rows with aᵢⱼ > 0.

Assumptions: all relationships are linear and variables are continuous (not restricted to whole numbers).

Worked Example

Maximise Z = 3x + 5y subject to x + 2y ≤ 10, x + y ≤ 6, x, y ≥ 0. Add slacks s₁, s₂. Initial tableau basic variables: s₁ = 10, s₂ = 6, Z = 0.

1. Zⱼ − Cⱼ for x is 3, for y is 5 → y enters. Ratios: 10/2 = 5, 6/1 = 6 → row 1 leaves.
2. After pivoting on the y-column row-1 element (2): new solution y = 5, s₂ = 1, Z = 25. Zⱼ − Cⱼ for x is now 0.5 > 0, so x enters; ratio 1/0.5 = 2 → row 2 leaves.
3. After the second pivot: x = 2, y = 4, Z = 3·2 + 5·4 = 26, all Zⱼ − Cⱼ ≤ 0 → optimal.

Check feasibility: 2 + 8 = 10 ≤ 10 ✓ and 2 + 4 = 6 ≤ 6 ✓. Maximum profit Z = 26 at (x, y) = (2, 4).

Common Misconceptions

• "The optimum is in the middle of the feasible region." For linear problems it is always at a vertex (corner).
• "Simplex checks every corner." It walks from corner to corner, each step improving the objective.
• "It handles ≥ constraints directly." They need surplus and artificial variables (see Big M / two-phase).

Real-World Applications

• Manufacturers choose product mixes to maximise profit under machine-hour limits.
• Logistics companies plan cheapest delivery routes and warehouse allocations.
• Diet-planning software finds the cheapest food combination meeting nutrition targets.

The simplex method converts inequality constraints into equations with slack variables, then walks the vertices of the feasible region, improving the objective at every step. It is the engine under modern optimisation, from factory scheduling to airline crew planning.