The Simplex algorithm

The Simplex algorithm

Spec 5.3 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • The Simplex algorithm moves from vertex to vertex without drawing, and handles up to four variables.
  • Write the objective row as P−2x−3y=0P-2x-3y=0, with slack variables as the starting basic variables.
  • Pivot column: most negative entry in the PP row. Pivot row: smallest non-negative ratio, ignoring zero and negative entries.
  • Divide the pivot row by the pivot, then use row operations to make the rest of the column 0.
  • Stop when the PP row has no negative entries. To minimise CC, maximise −C-C.

The initial tableau

Add a slack variable to each constraint, write the objective as P−2x−3y=0P-2x-3y=0, and list each equation as a row.

The Simplex algorithm solves a linear program by moving from vertex to vertex of the feasible region, improving the objective each time.

For a maximising problem with ≤\le constraints, add a slack variable to each. The objective P=2x+3yP=2x+3y becomes P−2x−3y=0P-2x-3y=0.

The tableau comes from x+y+r=10x+y+r=10, x+2y+s=16x+2y+s=16 and P−2x−3y=0P-2x-3y=0. The starting solution has r=10r=10, s=16s=16 as the basic variables and x=y=0x=y=0, P=0P=0.

(0, 0) P = 0(10, 0) P = 20(4, 6) P = 26(0, 8) P = 24
Maximise P = 2x + 3y subject to x + y ≤ 10 and x + 2y ≤ 16. The tableau starts at the vertex (0, 0), where P = 0.
  • P=2x+3yP=2x+3yP−2x−3y=0P-2x-3y=0

Row r

x:
1
y:
1
r:
1
s:
0
Value:
10

Row s

x:
1
y:
2
r:
0
s:
1
Value:
16

Row P

x:
-2
y:
-3
r:
0
s:
0
Value:
0

How is P=4x+7yP=4x+7y written in the objective row?

Choosing the pivot

The pivot column has the most negative PP-row entry; the pivot row has the smallest positive ratio.

Each iteration chooses a pivot in steps.

Ignore zero and negative entries in the ratio test: they would give an infeasible next solution. Choosing the smallest ratio keeps every value non-negative.

In the example, the most negative entry is −3-3 (column yy). The ratios are 101=10\frac{10}{1}=10 and 162=8\frac{16}{2}=8, so row ss is the pivot row and the pivot is the 2.

  1. 1

    Pivot column

    most negative entry in the P row; this variable enters

  2. 2

    Ratio test

    value divided by the positive entry in the pivot column

  3. 3

    Pivot row

    smallest ratio; this variable leaves

  4. 4

    Pivot element

    where they meet

Choosing the pivot

Entries in a pivot column are 2, 0 and 4 with values 6, 5 and 4. Which row is the pivot row?

Row operations

Divide the pivot row by the pivot, then subtract multiples of it from every other row to make the pivot column 0.

  1. Divide the pivot row by the pivot element so the pivot becomes 1: row ss becomes 12,1,0,12∣8\frac12,1,0,\frac12\mid8 (now row yy).
  2. For every other row, including PP, subtract a multiple of the new pivot row so the pivot column becomes 0.

Row rr minus row yy gives 12,0,1,−12∣2\frac12,0,1,-\frac12\mid2. Row PP plus 3×3\times row yy gives −12,0,0,32∣24-\frac12,0,0,\frac32\mid24.

Now y=8y=8, r=2r=2, x=s=0x=s=0 and P=24P=24, better than 0.

(0, 0) P = 0(10, 0) P = 20(4, 6) P = 26(0, 8) P = 24
The first iteration moves from (0, 0) to (0, 8), where y = 8 and P = 24. This improves the objective.

Row r

x:
1/2
y:
0
r:
1
s:
-1/2
Value:
2

Row y

x:
1/2
y:
1
r:
0
s:
1/2
Value:
8

Row P

x:
-1/2
y:
0
r:
0
s:
3/2
Value:
24

Which operation turns the PP entry −3-3 in the pivot column into 0?

Optimality

Repeat until the PP row has no negative entries. Then read the solution from the basic variables.

Repeat iterations until the PP row has no negative entries. The tableau is then optimal.

Continuing the example, xx (with −12-\frac12) enters. The ratios are 21/2=4\frac{2}{1/2}=4 and 81/2=16\frac{8}{1/2}=16, so row rr is the pivot row.

Basic variables take the value in their row and non-basic variables are 0. So x=4x=4, y=6y=6, r=s=0r=s=0 and P=26P=26.

Check: 4+6=104+6=10 and 4+12=164+12=16, both binding, and 2(4)+3(6)=262(4)+3(6)=26.

(0, 0) P = 0(10, 0) P = 20(4, 6) P = 26(0, 8) P = 24
The next iteration moves to (4, 6). Row P has no negative entries, so this is optimal: P = 26.

Row x

x:
1
y:
0
r:
2
s:
-1
Value:
4

Row y

x:
0
y:
1
r:
-1
s:
1
Value:
6

Row P

x:
0
y:
0
r:
1
s:
1
Value:
26

A tableau has PP row 0,0,3,−1∣200,0,3,-1\mid20. Is it optimal?

Minimising problems

Maximise P=−CP=-C instead, then give the minimum as C=−PC=-P.

The Simplex algorithm as set out maximises. To minimise CC, maximise P=−CP=-C, then state the minimum as C=−PC=-P.

With three or four variables the process is the same, with more columns. Keep fractions exact and check each row operation.

Substitute back into the original constraints to check your final answer.

−112345−6−4−2246xymin C = 1max P = −1CP = −C
Illustrative: minimising C = (x − 2)² + 1 gives C = 1. Maximising P = −C gives P = −1 at the same x. Then C = −P.
  • Minimise CCmaximise P=−CP=-C
  • Minimum of CC−P-P

Worked example

Minimise C=2x−3y−4zC=2x-3y-4z subject to x+y+z≤12x+y+z\le12 and 2x+y+3z≤182x+y+3z\le18.

Maximising −C-C gives P=15P=15. What is the minimum of CC?

Try an exam question

Maximise P=3x+2yP=3x+2y subject to x+y≤8x+y\le8 and x+3y≤12x+3y\le12, x,y≥0x,y\ge0. Use one iteration of the Simplex algorithm from the initial tableau, with slack variables rr and ss, and state the solution.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Which equation is the objective row of the initial tableau?

1 mark, marked against the mark scheme

Revision notes