Library › Further Decision Mathematics 1 WDM11 › Simplex Algorithm

AS Level · Further Decision Mathematics 1 WDM11

Simplex Algorithm

Revise Simplex Algorithm for Further Decision Mathematics 1 WDM11 (AS Level) — revision notes and instant AI marking. Free to start.

📖 Revision notes · preview

Edexcel A Level Further Maths · Decision 1

The Simplex Algorithm

A step-by-step way to find the best possible answer (maximum profit, minimum cost) to a problem with lots of variables — by hopping between corners of a shape until you can't do any better.

Summary — What This Chapter Covers

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.

1. Why Do We Need the Simplex Algorithm?

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.

The core idea

The feasible region is a many-sided shape (a polytope). The optimal solution is always at a vertex (corner) of that shape. The simplex algorithm starts at one vertex (usually the origin) and keeps hopping to a better neighbouring vertex until no better neighbour exists. At that point, you've found the optimum.

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.

2. Slack Variables & the Initial Tableau

1 What is a slack variable?

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

Think of a slack variable as filling up the "gap" or "slack" left over when you don't use the full amount. If 2x + 3y only comes to 7, there's 3 units of "slack" unused out of the 10 available. So we introduce a variable — call it s₁ — that soaks up exactly that leftover amount:

Rule

2x + 3y ≤ 10 → 2x + 3y + s₁ = 10, where s₁ ≥ 0

You need one slack variable per ≤ constraint. Each slack variable only appears in its own constraint (coefficient 1) and has coefficient 0 in every other row — this is what makes the table work.

If s₁ = 0, it means the constraint is being used up completely (it's "tight" or "binding"). If s₁ is large, there's lots of spare capacity in that constraint.

2 Building the initial tableau

Once every constraint is an equation, and the objective function is rearranged so everything is on one side (P = 8x + 5y + 7z becomes P − 8x − 5y − 7z = 0), we're ready to build the table — called the initial tableau.

Columns: basic variable (b.v.), each decision variable, each slack variable, and "Value" (the right-hand side of each equation).
Rows: one row per constraint equation, using the coefficients exactly as written, plus a final row for the objective function.
Basic variable column (fill in LAST): for each row, find the column that has a 1 in that row and 0 everywhere else — that variable is the "basic variable" for that row. At the start, this is always the slack variables, since each one only appears once.

What does "basic variable" mean?

The basic variables are the ones that are currently "active" — sitting at whatever value is in the Value column. Every variable not listed as a basic variable is automatically 0. At the very start, x, y, z are all 0 (we're at the origin!) and the slack variables hold all the constraint totals.

Worked Example. Maximise P = 8x + 5y + 7z subject to:

2x + 3y ≤ 10 x + 2y + 5z ≤ 60 5y + 3z ≤ 40

b.v.	x	y	z	s₁	s₂	s₃	Value
s₁	2	3	0	1	0	0	10
s₂	1	2	5	0	1	0	60
s₃	0	5	3	0	0	1	40
P	−8	−5	−7	0	0	0	0

Practice Question

Write the constraint 3a + 4b + c ≤ 24 as an equation using a slack variable, and state what it means if that slack variable equals 0.

3. Applying the Simplex Algorithm (One Iteration)

Once your initial tableau is ready, you repeat the same 4-step cycle ("an iteration") until you're done. Think of each iteration as hopping to a better vertex of the feasible region.

STEP 1 — Find the pivot column. Look along the objective row (ignore the Value column) and find the most negative entry. That column is the pivot column — it tells you which variable would improve P the most if you increased it.
Calculate θ-values. For every other row, divide "Value" by the entry in the pivot column: θ = Value ÷ (pivot column entry). If the entry is 0 or negative, that row's θ is "n/a" (ignore it).
STEP 2 — Find the pivot row & pivot element. The pivot row is whichever row has the smallest non-negative θ. Where the pivot row meets the pivot column is the "pivot element."
STEP 3 — Row operations. Turn the pivot element into 1 (divide the whole pivot row by itself). Then use multiples of this new pivot row to make every other entry in the pivot column (including the objective row!) equal to 0.
STEP 4 — Update the basic variable column. After the row operations, find the columns that now have a single 1 and 0s elsewhere — those are your new basic variables.

When are you finished?

Stop when there are NO negative entries left in the objective row.

That tableau is called the final tableau. Read the optimal solution straight from it: each basic variable takes the value in its Value column; every other variable (non-basic) is 0. The maximum of P is the number in the bottom-right corner.

Why "least positive" θ, not "smallest number"?

You pick the smallest non-negative θ because that row is the "tightest" constraint — the one that would run out first (go negative) if you pushed the pivot variable any further. Picking the wrong row would create an infeasible (negative) solution.

Worked Example — Iteration 1 (continuing the tableau above):

Most negative in objective row = −8 (column x). θ₁ = 10÷2 = 5, θ₂ = 60÷1 = 60, θ₃ = n/a. Smallest θ is 5, so R1 is the pivot row, pivot = 2.

b.v.	x	y	z	s₁	s₂	s₃	Value
x	1	1.5	0	0.5	0	0	5
s₂	0	0.5	5	−0.5	1	0	55
s₃	0	5	3	0	0	1	40
P	0	7	−7	4	0	0	40

Still a negative (−7 in the z column) — not finished yet, so we'd run another iteration.

Practice Question

In a tableau, the objective row reads: x: −3, y: −6, s₁: 0, s₂: 0, Value: 0. Which column is the pivot column, and why?

4. The Two-Stage Simplex Method

Plain simplex only works when the origin (make 0 of everything) is inside the feasible region — which is true only when every constraint is ≤. But real problems often have constraints like x + y ≥ 20 ("must produce at least 20"), and the origin fails that constraint (0 + 0 is not ≥ 20). Also, plain simplex can only maximise, not minimise.

The two-stage simplex method fixes both problems by running simplex twice:

Stage 1: Find any valid starting vertex (a "basic feasible solution") by maximising a helper objective function called I.
Stage 2: Once a valid starting point exists, run the normal simplex algorithm on the real objective function P, as usual.

1 Surplus variables (for ≥ constraints)

For a ≥ constraint like x + y + z ≥ 20, we can't add a slack (that only works for ≤). Instead we subtract a surplus variable, which represents the excess above the minimum requirement:

Rule

x + y + z ≥ 20 → x + y + z − s₁ = 20, where s₁ ≥ 0

One surplus variable per ≥ constraint. Any ≤ constraints in the same problem still get ordinary slack variables.

2 Artificial variables — why we need them too

Here's the snag: in x + y + z − s₁ = 20, there's no column with a clean "1 here, 0 everywhere else" pattern to use as a starting basic variable (unlike slack variables, which are naturally "ready to go"). So we bolt on an artificial variable, a₁, purely to give that row a basic variable to start with:

Rule

x + y + z − s₁ + a₁ = 20

Surplus variables always have coefficient −1. Artificial variables always have coefficient +1. Whenever you add a surplus variable, you must also add an artificial variable in the same constraint.

Artificial variables are a bit like scaffolding on a building — useful for getting started, but they must be "torn down" (forced back to 0) before you can trust the final answer. That's exactly the job of Stage 1.

Building the helper function I

I = −(a₁ + a₂ + …) for however many artificial variables you introduced. Since artificial variables must be ≥ 0, the biggest I can ever be is 0 (when every artificial variable is exactly 0). Stage 1 uses simplex to maximise I, chasing it up toward 0.

Before it can go in the tableau, rewrite each aᵢ in terms of the decision/surplus variables (rearrange its constraint), substitute into I, then rearrange I so all variables are on one side.

3 Setting up the initial two-stage tableau

Worked Example. Maximise P = 2x + 4y + 3z subject to x+y+z ≥ 20, 2x−y+2z ≥ 25, 2x+3y+4z ≤ 80.

Constraints become: x+y+z−s₁+a₁=20, 2x−y+2z−s₂+a₂=25, 2x+3y+4z+s₃=80. Working out I: I − 3x − 3z + s₁ + s₂ = −45.

The tableau now has two objective rows — one for P, one for I:

b.v.	x	y	z	s₁	s₂	s₃	a₁	a₂	Value
a₁	1	1	1	−1	0	0	1	0	20
a₂	2	−1	2	0	−1	0	0	1	25
s₃	2	3	4	0	0	1	0	0	80
P	−2	−4	−3	0	0	0	0	0	0
I	−3	0	−3	1	1	0	0	0	−45

Notice that a₁ and a₂ are automatically the starting basic variables — that's exactly the problem they were designed to solve.

4 Stage 1: maximise I

Run ordinary simplex, but treat the I row as the objective row (ignore the P row entries for pivot-choosing purposes during Stage 1). Keep going until the I row has no negative entries.

Two possible outcomes

I = 0 → feasible region exists → proceed to Stage 2

I ≠ 0 → no feasible region → problem CANNOT be solved, stop here

If I = 0: check that a₁ and a₂ are no longer basic variables (or if they still are, their value is 0). You can now delete the I row and both artificial variable columns — their job is done.

Worked result

Running the algorithm on the example above eventually gives I = 0 with x and y as basic variables. Removing I, a₁, a₂ leaves a clean tableau with just x, y, z, s₁, s₂, s₃ — ready for Stage 2.

5 Stage 2: maximise P as normal

This is just the ordinary simplex algorithm again, applied to the cleaned-up tableau from the end of Stage 1, using the P row. Keep pivoting until no negative entries remain in the P row — then read off the optimal solution exactly as before.

Practice Question

A problem has constraint 4x − y ≥ 12. Write this as an equation using a surplus and an artificial variable, and explain the role each one plays.

5. Minimising Problems

The simplex algorithm (and the two-stage method) is built to maximise. So what if the question asks you to minimise a cost function C? Use a neat trick: minimising C gives exactly the same solution as maximising −C.

Rule

Minimise C = 4x + 2y is the same as Maximise P = −C = −4x − 2y

Solve for P as normal (rearrange to P + 4x + 2y = 0 for the tableau). At the very end, flip the sign back: C_min = −P_max.

Don't forget the final flip!

A very common slip-up: students solve everything correctly, get "P has a maximum of −6," and then forget to negate it. The actual answer is C is minimised at C = 6. Always double check whether the question wants P or C (or whatever the cost variable is called) in your final answer.

Everything else about the two-stage method (surplus/artificial variables, Stage 1 maximising I, Stage 2 maximising P) works exactly the same way for minimisation problems — you're just working with −C the whole time instead of C.

6. The Big-M Method

The Big-M method solves exactly the same kinds of problems as the two-stage method (≥ constraints, minimisation) but does it in a single continuous run instead of two separate stages. It's an alternative approach, not a different type of problem.

Two-stage vs Big-M

Two-stage: two separate objective rows and two separate simplex runs — more steps, but each step is conceptually simple.
Big-M: just one objective row and one run — fewer stages, but the algebra involves an "arbitrarily large number" M, which can get fiddly to track.

1 What is M?

M is a symbol representing "an enormous positive number" — bigger than any number you could realistically write down. It's never given a numerical value. It's just there to guarantee that any expression like 1 − M is definitely negative, and M − 12 is definitely positive, no matter how the rest of the numbers work out. This lets the algorithm "punish" any solution that still relies on an artificial variable, forcing them to zero automatically.

2 Setting up the Big-M tableau

STEP 1: Use slack, surplus and artificial variables to convert every constraint into an equation, exactly as before.
STEP 2: Rearrange each constraint that contains an artificial variable, making that artificial variable the subject (e.g. a₁ = 18 − 2x − 3y + s₃).
STEP 3: Let A = the sum of all artificial variables. Subtract MA from the objective function P, substitute in your expressions from Step 2, and simplify.

The idea in one line

P_new = P − M(a₁ + a₂ + …)

Because M is huge, the algorithm will always try to shrink a₁ and a₂ down to 0 first (to avoid losing a giant chunk of P) — automatically doing the job that Stage 1 did in the two-stage method.

3 Running the algorithm

From here, it's the ordinary simplex algorithm — pivot column (most negative, now some entries are algebraic in M), θ-values, pivot row, row operations. The only tricky part is the arithmetic: you're adding/subtracting terms like −(4M+3) instead of plain numbers. Just treat M like an unknown you're collecting terms for, e.g. −4M+3 combined with +8M gives 4M+3.

Spotting "negative" with M in the mix

Since M is arbitrarily large and positive: any expression like −(4M+3) or M − 12 — wait, M−12 is actually positive (M dominates). Only expressions where the M-term itself is negative (like −4M+3 or 3−M) count as negative overall. Focus on the sign in front of the M first — that's what decides whether the whole term is negative.

The tableau is optimal (finished) when there are no negative entries in the objective row — same rule as always. At that point, any leftover terms containing M in the P value itself should have cancelled out to exactly 0 if the solution is truly feasible.

4 Big-M for minimising

Same trick as the two-stage method: introduce Q = −P, write Q in the tableau-ready form, and maximise Q using Big-M. At the end, P_min = −Q_max.

Practice Question

In a Big-M objective row you see the entry −(2M + 2) under column y. Is this negative? What does that mean for the algorithm?

What to Memorise

Slack variable

Added to a ≤ constraint to turn it into an equation. Coefficient always +1. One per ≤ constraint.

Surplus variable

Subtracted from a ≥ constraint to turn it into an equation. Coefficient always −1. One per ≥ constraint.

Artificial variable

Added alongside a surplus variable to give that row a basic variable to start with. Coefficient always +1. Must reach 0 by the end.

Basic variable

The variable in a row's column that has a 1 in that row and 0 in every other row. Its value = that row's Value entry. All other variables are 0.

Pivot column

The column with the most negative entry in the objective row. Chosen at the start of every iteration.

θ-value

θ = Value ÷ pivot column entry, for each row. Ignore rows where this is negative or undefined.

Pivot row / element

The row with the smallest non-negative θ-value is the pivot row. Where it meets the pivot column is the pivot element.

Stopping condition

Stop when the objective row has NO negative entries left. That's the final (optimal) tableau.

Two-stage method

Stage 1: maximise I = −(sum of artificial variables). If I = 0, delete I row & artificial columns. Stage 2: maximise P as normal.

Big-M method

Subtract M×(sum of artificial variables) from P directly. One tableau, one objective row, run simplex as usual.

Minimising trick

To minimise C, maximise P = −C instead. At the end: C_min = −P_max.

No feasible region

If Stage 1 (or Big-M) finishes with I ≠ 0 (or leftover M-terms that can't cancel), the LP problem has no solution — stop, don't proceed further.

Concepts Checklist

I can explain why the simplex algorithm is needed instead of the graphical method.
I can convert a ≤ constraint into an equation using a slack variable.
I can build a correct initial tableau from a set of constraints and an objective function.
I can correctly identify the pivot column, calculate θ-values, and find the pivot row.
I can perform the row operations to update a tableau, including the objective row.
I know how to tell when a tableau is "final" (optimal) and can read off the solution from it.
I can convert a ≥ constraint into an equation using a surplus AND artificial variable.
I can build and simplify the helper objective function I for the two-stage method.
I understand what it means if Stage 1 ends with I ≠ 0.
I can carry out Stage 2 of the two-stage method after removing I and the artificial variable columns.
I can convert a minimisation problem into a maximisation problem and flip the answer back at the end.
I can set up a Big-M tableau, including rearranging artificial variables and substituting into P.
I can run simplex iterations correctly when entries involve the symbol M.
I can identify which variables are basic vs non-basic in a final tableau and state all their values.

Exam Tips & Common Mistakes

Forgetting non-basic variables are 0. After finding the final tableau, students often only state the values that appear in the table and forget to explicitly say the remaining variables (the ones NOT in the basic variable column) are all 0. Examiners want you to state every variable's value.

Mixing up slack, surplus, and artificial coefficients. Slack: +1. Surplus: −1. Artificial: +1. Getting these backwards (e.g. adding a surplus variable to a ≤ constraint) will produce a completely wrong tableau from the very first step.

Picking the wrong row for the pivot. Always divide Value by the pivot COLUMN entry, and always choose the smallest non-negative θ. A negative or "n/a" (zero or negative pivot entry) θ must be ignored — picking it creates an invalid (negative) tableau.

Forgetting to update the objective row. Every row operation that clears the pivot column must also be applied to the objective row(s) — including the I row in the two-stage method. Missing this is one of the most common ways students lose marks halfway through a long tableau chain.

Forgetting to flip the sign for minimisation. If you maximised P = −C, your final answer for the minimum of C is −P_max, NOT the value you read straight off the tableau. Always sanity check: a "maximum" of a negative number, once flipped, becomes a sensible positive minimum cost.

Not checking I = 0 (or M-terms cancel) before moving on. If Stage 1 finishes with I ≠ 0, or your Big-M tableau can't fully eliminate the M terms, the linear programming problem has NO feasible solution — state this clearly rather than pressing on to a meaningless Stage 2.

Sign errors with M. Remember M is always positive and arbitrarily large. −(4M+3) is negative; M−12 is positive (M wins); 3−M is negative (M wins). Always look at the sign attached to the M-term first to decide overall sign.

Showing your row operations. Mark schemes reward writing the row operation used (e.g. 'R2' − R1, or 0.5'R1') next to each new row — it lets the examiner follow (and award method marks for) your working even if a later arithmetic slip creeps in.

Also in the full note

2. Slack Variables & the Initial Tableau
Exam Tips & Common Mistakes

What's inside

📖 Revision notes ✦ AI flashcards ✓ Instant AI marking

Read the full Simplex Algorithm notes free

That's the preview — create a free account to read the rest, plus flashcards and practice questions with instant AI marking. No credit card.

Unlock the full notes free →

Simplex Algorithm

The Simplex Algorithm

Summary — What This Chapter Covers

1. Why Do We Need the Simplex Algorithm?

2. Slack Variables & the Initial Tableau

1 What is a slack variable?

2 Building the initial tableau

3. Applying the Simplex Algorithm (One Iteration)

4. The Two-Stage Simplex Method

1 Surplus variables (for ≥ constraints)

2 Artificial variables — why we need them too

3 Setting up the initial two-stage tableau

4 Stage 1: maximise I

5 Stage 2: maximise P as normal

5. Minimising Problems

6. The Big-M Method

1 What is M?

2 Setting up the Big-M tableau

3 Running the algorithm

4 Big-M for minimising

What to Memorise

Concepts Checklist

Exam Tips & Common Mistakes

More Further Decision Mathematics 1 topics