From graph to algebra: why simplex?
In the graphical method, the best value of a linear objective always lies at a corner (vertex) of the feasible region. With 3 or more variables you cannot draw the region, so we need an algebraic way to walk from corner to corner.
The simplex algorithm starts at one corner (usually the origin) and moves along an edge to a neighbouring corner that improves the objective. It stops when no neighbour is better.
Slack variables and the initial tableau
A slack variable measures the unused amount of a resource. For x + y β€ 4 write x + y + r = 4 with r β₯ 0.
Example: maximise P = 3x + 2y subject to x + y β€ 4, x + 3y β€ 9, x β€ 3, x, y β₯ 0. Rewrite the objective as P β 3x β 2y = 0.
| Basic | x | y | r | s | t | Value |
|---|---|---|---|---|---|---|
| r | 1 | 1 | 1 | 0 | 0 | 4 |
| s | 1 | 3 | 0 | 1 | 0 | 9 |
| t | 1 | 0 | 0 | 0 | 1 | 3 |
| P | β3 | β2 | 0 | 0 | 0 | 0 |
The basic variables (r, s, t) have a column with one 1 and zeros. Non-basic variables (x, y) are 0. So this tableau describes the corner (0, 0) with P = 0.
The pivot: column, ratio test, row operations
- Pivot column: the most negative entry in the objective row (here x, β3). Increasing x raises P fastest per unit.
- Ratio test: for each row with a positive entry in that column, find value Γ· entry: 4/1, 9/1, 3/1. The smallest (3, row t) is the pivot row. It is the first constraint to run out.
- Make the pivot 1: divide the pivot row by the pivot element.
- Clear the column: add or subtract multiples of the pivot row so every other entry in the column is 0.
- The entering variable (x) replaces the leaving one (t) in the basic list.
After pivot 1: x = 3, r = 1, s = 6, P = 9 (corner (3, 0)). P row: 0, β2, 0, 0, 3 | 9. Still negative (β2), so pivot on y: ratios 1/1 = 1 and 6/3 = 2, so row r. After pivot 2 the P row is 0, 0, 2, 0, 1 | 11.
Reading a simplex tableau
- Optimal? When maximising, the tableau is optimal when no entry in the objective row is negative.
- Values: each basic variable equals the value in its row; all non-basic variables are 0. Final: y = 1, s = 3, x = 3, r = t = 0, P = 11.
- Slack meaning: s = 3 means 3 units of the second resource are left unused; r = t = 0 means those resources are fully used (binding).
- Objective row numbers under slack columns (2 for r, 1 for t) show how much P would rise per extra unit of that resource (the shadow price).
- A 0 under a non-basic variable in the final P row signals other optimal solutions; a pivot column with no positive entries means P is unbounded.
Minimising with simplex, and β₯ constraints
To minimise C, maximise P = βC and use the same steps; at the end, C = βP.
Example: minimise C = x β 2y with x + y β€ 6, y β€ 4. Maximise P = βx + 2y: P row is 1, β2. Pivot on y (ratios 6 and 4 β row 2): y = 4, P = 8, so the minimum C = β8 at (0, 4).
If a constraint is β₯, the origin is not feasible. Then you subtract a surplus variable and add an artificial variable, and use the two-stage method (first remove the artificials) or the big-M method (give artificials a huge penalty M).
Try it: check with corners
List all corners of the feasible region for the example: (0, 0), (3, 0), (3, 1), (1.5, 2.5), (0, 3). Work out P = 3x + 2y at each. Does the largest match the simplex answer 11? Now change the objective to P = x + 2y and run the simplex again. Which corner wins? (Use the slider in the 3D to check.)
Key formulas and definitions
- Slack: aΒ·x + bΒ·y β€ c β aΒ·x + bΒ·y + s = c, s β₯ 0
- Objective row: P β 3x β 2y = 0
- Pivot column = most negative entry in the P row
- Ratio test: value Γ· positive pivot-column entry; choose the smallest
- Optimal (max) when the P row has no negative entries
- Minimise C β maximise P = βC
Worked examples
1. Write the constraints x + 2y β€ 10 and 3x + y β€ 15 with slack variables.
x + 2y + sβ = 10 and 3x + y + sβ = 15, with sβ, sβ β₯ 0.
2. Maximise P = 5x + 4y subject to 2x + y β€ 8, x + 2y β€ 7, x, y β₯ 0. Do the first pivot.
P row: β5, β4. Pivot column x (β5). Ratios: 8/2 = 4, 7/1 = 7 β row 1, pivot 2. Divide row 1 by 2: x + 0.5y + 0.5r = 4. Row 2 β row 1: 1.5y β 0.5r + s = 3. P row + 5Γrow 1: β1.5y + 2.5r = 20. So x = 4, s = 3, P = 20.
3. Finish the problem in example 2.
P row still has β1.5 under y. Ratios: 4/0.5 = 8, 3/1.5 = 2 β row 2, pivot 1.5. Divide: y β r/3 + 2s/3 = 2. Row 1 β 0.5Γnew row: x + 2r/3 β s/3 = 3. P row + 1.5Γnew row: 2r + s = 23. No negatives, so optimal: x = 3, y = 2, P = 23.
4. Minimise C = x β 2y subject to x + y β€ 6, y β€ 4, x, y β₯ 0.
Maximise P = βx + 2y, so P + x β 2y = 0. Pivot column y (β2). Ratios 6/1 = 6, 4/1 = 4 β row 2. Then y = 4, first slack = 2, P row: 1, 0, 0, 2 | 8. Optimal: P = 8, so C = β8 at x = 0, y = 4.
5. A final tableau has rows: x | 1 0 0.5 β0.5 | 6; y | 0 1 β0.25 0.75 | 2; P | 0 0 1.5 0.5 | 42 (columns x, y, sβ, sβ). Read the solution.
No negatives in the P row β optimal. Basic: x = 6, y = 2. Non-basic: sβ = sβ = 0 (both resources fully used). P = 42. Each extra unit of resource 1 would add 1.5 to P.
6. Maximise P = 3x + 2y + 4z subject to x + y + 2z β€ 4, 2x + y + 3z β€ 5, x, y, z β₯ 0.
Pivot 1: z (β4); ratios 4/2 = 2, 5/3 β 1.67 β row 2. Gives P = 20/3 with P row β1/3 (x), β2/3 (y). Pivot 2: y; ratios 2 (row 1) and 5 β row 1. P = 8 but x still has β1. Pivot 3: x; only row z has a positive entry (ratio 1). Final: x = 1, y = 3, z = 0, P = 9. Check: 1 + 3 = 4 β, 2 + 3 = 5 β.
Common mistakes
- Choosing the largest positive number in the P row as the pivot column. When maximising, pick the most negative.
- Including rows with zero or negative entries in the ratio test. Only positive entries count.
- Forgetting to update the P row during a pivot, or the "basic variable" label.
- Reading a value for a non-basic variable. Non-basic variables are always 0.