Two-stage Simplex Method (Edexcel A Level Further Maths: Decision Maths 1)

Revision Note

Test Yourself

Author

Paul

Expertise

Maths

Introduction to Two-Stage Simplex Method

What is the two-stage simplex method?

The simplex algorithm solves maximisation linear programming problems where all (non-negativity) constraints involve ≤
The two-stage simplex method adapts the simplex algorithm to solve linear programming problems
- involving constraints with ≥
- where the objective function is to be minimised
- In both cases the simplex algorithm cannot be used directly
  - it is based on the basic feasible region containing the basic feasible solution of the origin
The two-stage simplex method is two applications of the simplex algorithm
- The first stage of the two-stage simplex method finds a basic feasible solution (if one exists)
- If a basic feasible solution is found the second stage applies the simplex algorithm as usual

Surplus & Artificial Variables

What are surplus variables?

Surplus variables are used to turn inequalities involving ≥ into equations
- A surplus variable, as the name implies, takes up the excess (surplus) that a function has in "greater than or equal to" constraints
- A surplus variable will be subtracted from (the left hand side of) each constraint so will be non-negative
The number of surplus variables required in a problem will be the same as the number of (non-negativity) constraints that contain ≥
- Any inequalities involving ≤ will still require slack variables
Whenever a surplus variable is introduced, an artificial variable will also be needed

What are artificial variables?

Artificial variables are used to ensure each constraint with a surplus variable contains a basic variable
- A surplus variable is subtracted, so will have a coefficient of -1
  - basic variables have a coefficient of 1
- Artificial variables will always start with a coefficient of 1

Exam Tip

You need to be able to recognise when the simplex algorithm cannot (directly) be used to solve a linear programming problem
- This is due to the presence of constraints involving ≥ (or a mixture of ≤ and ≥)

Worked example

The following linear programming problem is to be solved using the two-stage simplex method.

Maximise

$P = 2 x + 4 y + 3 z$

subject to

$\begin{array}{rcl} x + y + z & \geq & 20 \\ 2 x - y + 2 z & \geq & 25 \\ 2 x + 3 y + 4 z & \leq & 80 \\ x, y, z & \geq & 0 \end{array}$

Use slack, surplus and artificial variables as necessary to write the constraints (except the non-negativity constraint) of the linear programming problem as equations.

Use $s_{1}$ and $a_{1}$ as surplus and artificial variables in the first constraint as it involves ≥

$x + y + z - s_{1} + a_{1} = 20$

The second constraint involves ≥ too so will also need a surplus and artificial variable

$2 x - y + 2 z - s_{2} + a_{2} = 25$

The third constraint involves ≤ so requires a slack variable

$2 x + 3 y + 4 z + s_{3} = 80$

The constraints as equations using slack, surplus and artificial variables are

$\begin{array}{rcl} x + y + z - s_{1} + a_{1} & = & 20 \\ 2 x - y + 2 z - s_{2} + a_{2} & = & 25 \\ 2 x + 3 y + 4 z + s_{3} & = & 80 \end{array}$

How do I set up the initial tableau for the two-stage simplex method?

To set up the initial tableau, the equations derived from the inequalities (constraints) are needed along with
- a rearrangement of the objective function such that zero is on one side
  - e.g. $P = 2 x + 4 y + 3 z$ becomes $P - 2 x - 4 y - 3 z = 0$
- a new objective function, $I$ . which is the negative sum of the artificial variables
  - e.g. where two artificial variables $a_{1}$ and $a_{2}$ have been introduced, $I = - (a_{1} + a_{2})$
  - In general, $I = - (a_{1} + a_{2} + . . . + a_{n})$ for $n$ artificial variables
  - artificial variables should be written in terms of the decision and surplus variables before being substituted into $I$
  - $I$ is then rearranged such that all variables are on one side and a constant is on the other
The initial tableau can then be constructed with two objective rows
- one for $P$ , one for $I$

Worked example

Construct the initial tableau for the two-stage simplex method for the objective function

$P - 2 x - 4 y - 3 z = 0$

and equations (constraints)

$\begin{array}{rcl} x + y + z - s_{1} + a_{1} & = & 20 \\ 2 x - y + 2 z - s_{2} + a_{2} & = & 25 \\ 2 x + 3 y + 4 z + s_{3} & = & 80 \end{array}$

Introduce $I$ ( $P$ is already in the required form)

$I = - (a_{1} + a_{2})$

Rewrite $a_{!}$ and $a_{2}$ in terms of $x, y, z, s_{1}$ and $s_{2}$ ( $s_{3}$ is a slack variable)

$\begin{array}{rcl} a_{1} & = & 20 - x - y - z + s_{1} \\ a_{2} & = & 25 - 2 x + y - 2 z + s_{2} \end{array}$

Substitute into $I$

$\begin{array}{rcl} I & = & - (20 - x - y - z + s_{1} + 25 - 2 x + y - 2 z + s_{2}) \\ I & = & - (45 - 3 x - 3 z + s_{1} + s_{2}) \end{array}$

Rearrange so all variables are on the same side as (positive) $I$ and a constant on the other

$I - 3 x - 3 z + s_{1} + s_{2} = - 45$

Set up the initial tableau two objective rows for $P$ and $I$

b.v.	$x$	$y$	$z$	$s_{1}$	$s_{2}$	$s_{3}$	$a_{1}$	$a_{2}$	Value
$a_{1}$	1	1	1	-1	0	0	1	0	20
$a_{2}$	2	-1	2	0	-1	0	0	1	25
$s_{3}$	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

Maximising Problems

How do I apply the first-stage of the two-stage simplex method to maximising problems?

In the first-stage, $I$ will be maximised
- the maximum $I$ can be is 0
- this is when each artificial variable equals 0
  - artificial variables cannot be negative
At the end of the first-stage
- if then a basic feasible region does not exist and the linear programming problem cannot be solved
  - there will be no need (or point) in progressing to the second-stage
- if then a basic feasible region does exist
  - the objective row $I$ and the artificial variable columns can be removed from the tableau before commencing the second stage

Worked example

The initial tableau for using the two-stage simplex method is given below.
Apply the first-stage of the two-stage simplex method to maximise $I$ .
Give your final answer as the tableau with $I, a_{1}$ and $a_{2}$ removed.

b.v.	$x$	$y$	$z$	$s_{1}$	$s_{2}$	$s_{3}$	$a_{1}$	$a_{2}$	Value
$a_{1}$	1	1	1	-1	0	0	1	0	20
$a_{2}$	2	-1	2	0	-1	0	0	1	25
$s_{3}$	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

Apply the simplex algorithm to maximise $I$

There is a negative entry in the ( $I$ ) objective row
-3 is the most negative

C1 is the pivot column, the $θ$ -values are

$\begin{array}{rcl} θ_{1} & = & 20 \div 1 = 20 \\ θ_{2} & = & 25 \div 2 = 12.5 \\ θ_{3} & = & 80 \div 2 = 40 \end{array}$

$θ_{2}$ is the least positive so R2 is the pivot row
The pivot element is in cell R2C1 (highlighted in tableau above)

Pivot is 2

Apply the appropriate row operations, starting with the pivot row, R2

b.v.	$x$	$y$	$z$	$s_{1}$	$s_{2}$	$s_{3}$	$a_{1}$	$a_{2}$	Value	Row Op.
$a_{1}$	0	1.5	0	-1	0.5	0	1	-0.5	7.5	$' R 1' - R 2$
$x$	1	-0.5	1	0	-0.5	0	0	0.5	12.5	$0.5' R 2'$
$s_{3}$	0	4	2	0	1	1	0	-1	55	$' R 3' - 2 R 2$
$P$	0	-5	-1	0	-1	0	0	1	25	$0.5' R 4' + 2 R 2$
$I$	0	-1.5	0	1	-0.5	0	0	1.5	-7.5	$' R 5' + 3 R 2$

There is a negative entry in the ( $I$ ) objective row
-1.5 is the most negative

C2 is the pivot column, the $θ$ -values are

$\begin{array}{rcl} θ_{1} & = & 7.5 \div 1.5 = 5 \\ θ_{2} & = & 12.5 \div (- 0.5) = - 25 \\ θ_{3} & = & 55 \div 4 = 13.75 \end{array}$

$θ_{1}$ is the least positive so R1 is the pivot row
The pivot element is in cell R1C2

Pivot is 1.5

Apply the appropriate row operations, starting with the pivot row, R1

b.v.	$x$	$y$	$z$	$s_{1}$	$s_{2}$	$s_{3}$	$a_{1}$	$a_{2}$	Value	Row Op.
$y$	0	1	0	-2/3	1/3	0	2/3	-1/3	5	$1.5' R 1'$
$x$	1	0	1	-1/3	-1/3	0	1/3	1/3	15	$' R 2' + 0.5 R 1$
$s_{3}$	0	0	2	8/3	-1/3	1	-8/3	1/3	35	$' R 3' - 4 R 1$
$P$	0	0	-1	-10/3	2/3	0	10/3	-2/3	50	$' R 4' + 5 R 1$
$I$	0	0	0	0	0	0	1	1	0	$' R 5' + 1.5 R 1$

There are no negative values in the ( $I$ ) objective row so $I$ has been maximised and the first-stage of the method is complete
Reading from the tableau, we see that neither $a_{1}$ nor $a_{2}$ are basic variables so both have the value 0, and the value of $I$ is 0

The final answer is required as the tableau with $I, a_{1}$ and $a_{2}$ removed

b.v.	$x$	$y$	$z$	$s_{1}$	$s_{2}$	$s_{3}$	Value
$y$	0	1	0	-2/3	1/3	0	5
$x$	1	0	1	-1/3	-1/3	0	15
$s_{3}$	0	0	2	8/3	-1/3	1	35
$P$	0	0	-1	-10/3	2/3	0	50

How do I apply the second-stage of the two-stage simplex method to maximising problems?

After the first-stage, the value of $I$ should be zero
- If it is not then a feasible region does not exist and the linear programming problem cannot be solved
In the second-stage, the simplex algorithm is applied as usual to maximise the objective function $P$

Worked example

After the first-stage of the two-stage simplex method has been applied to a linear programming problem the following tableau is formed. Apply the second-stage of the two-stage simplex method to find the optimal solution.

b.v.	$x$	$y$	$z$	$s_{1}$	$s_{2}$	$s_{3}$	Value
$y$	0	1	0	-2/3	1/3	0	5
$x$	1	0	1	-1/3	-1/3	0	15
$s_{3}$	0	0	2	8/3	-1/3	1	35
$P$	0	0	-1	-10/3	2/3	0	50

The second-stage of the two stage simplex method is to apply the simplex algorithm

There is a negative entry in the objective row
-10/3 is the most negative

C4 is the pivot column, the $θ$ -values are

$\begin{array}{rcl} θ_{1} & = & 5 \div (- 2 / 3) = - 7.5 \\ θ_{2} & = & 15 \div (- 1 / 3) = - 45 \\ θ_{3} & = & 35 \div 8 / 3 = 13.125 \end{array}$

$θ_{3}$ is the least positive so R3 is the pivot row
The pivot element is in cell R3C4 (highlighted in tableau above)

Pivot is 8/3

Apply the appropriate row operations, starting with the pivot row, R3

b.v.	$x$	$y$	$z$	$s_{1}$	$s_{2}$	$s_{3}$	Value	Row Op.
$y$	0	1	0.5	0	0.25	0.25	13.75	$' R 1' + 2 / 3 R 3$
$x$	1	0	1.25	0	-0.375	0.125	18.375	$' R 2' + 1 / 3 R 3$
$s_{1}$	0	0	0.75	1	-0.125	0.375	13.126	$8 / 3' R 3'$
$P$	0	0	1.5	0	0.25	1.25	93.75	$' R 4' + 10 / 3 R 1$

There are no negative values in the objective row so the algorithm is complete and the optimal solution can be read from the final tableau
$x, y, s_{1}$ are basic variables, $s_{2}, s_{3}$ are non-basic

$x = 18.375, y = 13.75, s_{1} = 13.126$
$z = s_{2} = s_{3} = 0$
$P$ has a maximum value of 93.75

Minimising Problems

How do I apply the two-stage simplex method to minimising problems?

Minimising the objective function is the same as maximising the negative of the objective function
So in minimisation problems, we maximise the negative of the objective function
- e.g. Minimising $C = 4 x + 2 y$ is the same as maximising $P = - C = - (4 x + 2 y) = - 4 x - 2 y$
The two-stage simplex method for minimisation problems is otherwise the same as for maximisation problems
- The first-stage maximises the (new) objective function, $I$
  - where $I$ is the negative sum of the artificial variables
  - $I = - (a_{1} + a_{2} + . . . + a_{n})$
- At the end of the first-stage, if $I = 0$ a feasible region exists
  - the tableau can have the row for $I$ and the columns for the artificial variable removed
  - the second-stage of applying the simplex algorithm will then maximise $P$
For minimisation problems, the maximum $P$ will need interpreting as the minimum for $C$
- $C$ is often used as 'costs' require minimising ( $P$ is often for profit)

Worked example

Solve the following linear programming problem using the two-stage simplex method.

Minimise

$C = 4 x + 2 y$

subject to

$\begin{array}{rcl} x + 8 y & \geq & 9 \\ x + y & \leq & 9 \\ 6 x - y & \geq & 5 \\ x, y & \geq & 0 \end{array}$

Minimising $C$ is the same as maximising $P$ , where

$P = - C = - 4 x - 2 y$

$P$ will need rewriting in the correct form for the initial tableau

$P + 4 x + 2 y = 0$

Use slack, surplus and artificial variables to rewrite the constraints as equations

$\begin{array}{rcl} x + 8 y - s_{1} + a_{1} & = & 9 \\ x + y + s_{2} & = & 9 \\ 6 x - y - s_{3} + a_{2} & = & 5 \end{array}$

Introduce, find and write $I$ in the correct format for the initial tableau

Let $\begin{array}{rcl} I & = & - (a_{1} + a_{2}) \end{array}$

$\begin{array}{rcl} I & = & - (9 - x - 8 y + s_{1} + 5 - 6 x + y + s_{3}) \\ I & = & - (14 - 7 x - 7 y + s_{1} + s_{3}) \end{array}$

$\begin{array}{rcl} I - 7 x - 7 y + s_{1} + s_{3} & = & - 14 \end{array}$

Construct the initial tableau

b.v.	$x$	$y$	$s_{1}$	$s_{2}$	$s_{3}$	$a_{1}$	$a_{2}$	Value
$a_{1}$	1	8	-1	0	0	1	0	9
$s_{2}$	1	1	0	1	0	0	0	9
$a_{2}$	6	-1	0	0	-1	0	1	5
$P$	4	2	0	0	0	0	0	0
$I$	-7	-7	1	0	1	0	0	-14

Apply the simplex algorithm to maximise $I$

There is a negative entry in the ( $I$ ) objective row
-7 is the most negative (either can be chosen, we're choosing the first)

C1 is the pivot column, the $θ$ -values are

$\begin{array}{rcl} θ_{1} & = & 9 \div 1 = 9 \\ θ_{2} & = & 9 \div 1 = 9 \\ θ_{3} & = & 5 \div 6 = 0.833 . . . \end{array}$

$θ_{3}$ is the least positive so R3 is the pivot row
The pivot element is in cell R3C1

Pivot is 6

Apply the appropriate row operations, starting with the pivot row, R3

b.v.	$x$	$y$	$s_{1}$	$s_{2}$	$s_{3}$	$a_{1}$	$a_{2}$	Value	Row Op.
$a_{1}$	0	49/6	-1	0	1/6	1	-1/6	49/6	$' R 1' - R 3$
$s_{2}$	0	7/6	0	1	1/6	0	-1/6	49/6	$' R 2' - R 3$
$x$	1	-1/6	0	0	-1/6	0	1/6	5/6	$1 / 6' R 3'$
$P$	0	8/3	0	0	2/3	0	-2/3	-10/3	$' R 4' - 4 R 3$
$I$	0	-49/6	1	0	-1/6	0	-7/6	-49/6	$' R 5' + 7 R 3$

There is a negative entry in the ( $I$ ) objective row
-49/6 is the most negative

C2 is the pivot column, the $θ$ -values are

$\begin{array}{rcl} θ_{1} & = & 49 / 6 \div 49 / 6 = 1 \\ θ_{2} & = & 49 / 6 \div 7 / 6 = 7 \\ θ_{3} & = & 5 / 6 \div (- 1 / 6) = - 5 \end{array}$

$θ_{1}$ is the least positive so R1 is the pivot row
The pivot element is in cell R1C2

Pivot is 49/6

Apply the appropriate row operations, starting with the pivot row, R1

b.v.	$x$	$y$	$s_{1}$	$s_{2}$	$s_{3}$	$a_{1}$	$a_{2}$	Value	Row Op.
$y$	0	1	-6/49	0	1/49	6/49	-1/49	1	$6 / 49' R 1'$
$s_{2}$	0	0	1/7	1	1/7	-1/7	-1/7	7	$' R 2' - 7 / 6 R 1$
$x$	1	0	-1/49	0	-8/49	1/49	8/49	1	$' R 3' + 1 / 6 R 1$
$P$	0	0	16/49	0	30/49	-16/49	-30/49	-6	$' R 4' - 8 / 3 R 1$
$I$	0	0	0	0	0	1	1	0	$' R 5' + 49 / 6 R 1$

There are no negative entries in the ( $I$ ) objective row so the first-stage is complete, $a_{1} = a_{2} = I = 0$

Remove $a_{1}, a_{2}, I$ from the tableau to complete the first-stage

b.v.	$x$	$y$	$s_{1}$	$s_{2}$	$s_{3}$	Value
$y$	0	1	-6/49	0	1/49	1
$s_{2}$	0	0	1/7	1	1/7	7
$x$	1	0	-1/49	0	-8/49	1
$P$	0	0	16/49	0	30/49	-6

There are no negative values in the objective row so the method is complete (no second-stage required) and the optimal solution can be read from the final tableau

$x, y, s_{2}$ are basic variables, $s_{1}, s_{3}$ are non-basic

Change from maximising $P$ to minimising $C$

$C_{m i n} = - P_{m a x} = - (- 6) = 6$

The solution to the linear programming problem is
$x = 1, y = 1$
with $C$ minimised at $C = 6$
( $s_{1} = s_{3} = 0, s_{2} = 7$ )

You've read 0 of your 0 free revision notes

Get unlimited access

to absolutely everything:

Downloadable PDFs
Unlimited Revision Notes
Topic Questions
Past Papers
Model Answers
Videos (Maths and Science)

Join the 100,000+ Students that ❤️ Save My Exams

the (exam) results speak for themselves:

Test yourself Next topic

Did this page help you?

Two-stage Simplex Method (Edexcel A Level Further Maths: Decision Maths 1)

Revision Note

What is the two-stage simplex method?

What are surplus variables?

What are artificial variables?

How do I set up the initial tableau for the two-stage simplex method?

How do I apply the first-stage of the two-stage simplex method to maximising problems?

How do I apply the second-stage of the two-stage simplex method to maximising problems?

How do I apply the two-stage simplex method to minimising problems?

You've read 0 of your 0 free revision notes

Get unlimited access

Join the 100,000+ Students that ❤️ Save My Exams

Author: Paul