Maths › Decision Mathematics 1 › The Simplex algorithm
The Simplex algorithm
Graphs run out at two variables. Simplex walks from corner to corner algebraically instead, improving at every step, and stops when no move can improve the objective any further.
Builds on Linear programming: formulation and graphical solution and Matrix algebra and transformations.
IN THIS TOPIC
- Set up the initial tableau from a formulated problem.
- Choose the pivot column and row and carry out the row operations.
- Read the solution from a final tableau and recognise when to stop.
WHAT YOU PROBABLY THINK
The Simplex algorithm stops when the value in the bottom right corner stops increasing.
Setting up and pivoting
Add a slack variable to each constraint and write the objective as P − 4x − 5y = 0. The tableau then has a row per constraint and one for the objective, with the slack variables forming the starting basic solution: all the real variables zero, at the origin.
Each iteration has three steps. Choose the pivot column as the one with the most negative entry in the objective row, since increasing that variable improves P fastest. Choose the pivot row by the ratio test: divide each value by its entry in the pivot column and take the smallest non-negative result, skipping negative and zero entries entirely.
Then divide the pivot row by the pivot element and add multiples of it to the other rows so that the pivot column becomes a column of the identity.
WORKED EXAMPLE
The first pivot
Maximise P = 4x + 5y subject to x + y ≤ 10 and 2x + 3y ≤ 24.
The objective row is P − 4x − 5y = 0, so the most negative entry is −5 and the pivot column is y.
Ratio test: 10 ÷ 1 = 10 and 24 ÷ 3 = 8, so the pivot row is the second.
After pivoting, P = 40 with y = 8. The objective row still has a negative entry in x, so another iteration follows and finishes at P = 44 with x = 6, y = 4.
Stopping, and harder constraints
The algorithm stops when there are no negative entries left in the objective row: at that point no variable can be increased without reducing P. That is a condition on the row, not on the corner value changing, and the opening claim would stop early whenever an iteration happened to leave P unchanged, which degenerate problems do.
Reading the answer: each column that looks like a column of the identity gives a basic variable equal to its row's value, and every other variable is zero. To minimise instead of maximise, maximise the negative of the objective and change the sign back at the end.
With ≥ constraints the origin is not feasible, so a starting solution has to be manufactured. The two-stage method first minimises the sum of the artificial variables to reach a feasible corner, then runs ordinary Simplex from there. The big-M method instead subtracts a large multiple M of each artificial variable from the objective, which makes keeping them positive so expensive that the algorithm drives them out on its own.
YOUR TURN
Reading a final tableau
A final tableau has objective row P + 2s1 + s2 = 44, and rows giving x = 6 and y = 4. State the solution and explain how you know it is optimal.
Show the working
No entry in the objective row is negative, so no variable can be increased to improve P: the tableau is optimal.
x = 6, y = 4, and the slack variables are non-basic so s1 = s2 = 0.
P = 44, read from the value column of the objective row.
Both slacks being zero says both constraints are tight, which matches the graphical answer at the intersection.
THE EXAM BIT
- Write the objective row with the signs reversed, as P − 4x − 5y = 0.
- Show the ratio test in full, including the entries you skipped and why.
- State the row operations you performed, in the form 'row 1 minus row 2'.
- Stop only when no negative entries remain in the objective row, and say that is why you stopped.
CHECK YOURSELF
In a tableau the pivot column entries are 2, −1 and 4, with values 12, 8 and 20. Which row is the pivot row?
Show a hint
Skip the negative entry.
Show the answer
R
a
t
i
o
s
a
r
e
1
2
÷
2
=
6
a
n
d
2
0
÷
4
=
5
;
t
h
e
−
1
i
s
s
k
i
p
p
e
d
e
n
t
i
r
e
l
y
.
T
h
e
s
m
a
l
l
e
s
t
i
s
5
,
s
o
t
h
e
t
h
i
r
d
r
o
w
i
s
t
h
e
p
i
v
o
t
r
o
w
.
Pivot on the most negative entry in the objective row, choosing the row by the smallest non-negative ratio of value to pivot-column entry.
Stop when no negative entries remain in the objective row; ≥ constraints need the two-stage or big-M method to get started.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.
- Set up the initial tableau from a formulated problem.
- Choose the pivot column and row and carry out the row operations.
- Read the solution from a final tableau and recognise when to stop.
Open the full revision checklist to see every objective in the course in one place.
No animated video for this topic yet; these notes stand alone.