The simplex algorithm Worked Solutions — Further Maths Maths

Fully worked, step-by-step solutions to Further Maths The simplex algorithm questions. See exactly how to solve problems on simplex, slack-variables, initial-tableau, pivot-column.

simplexslack-variablesinitial-tableaupivot-columnpivotingoptimality

Further Maths70 questionsStep-by-step solutions

Question 1

2 markseasy

Maximise

P = 3x + 5y

subject to the constraints

2x + 2y \le 21

2y \le 6

, where

x \ge 0

y \ge 0

. The objective row of the tableau is written as

P - 3x - 5y = 0

, so its entries in the variable columns are the negatives of the coefficients of the objective function. At each iteration the pivot column is the column with the most negative entry in the objective row, and the pivot row is the row with the smallest non-negative ratio, each ratio being the entry in the value column divided by the entry of that row in the pivot column, computed only for rows whose entry in the pivot column is strictly positive. How many slack variables are needed to write this linear programme in the form required by the simplex algorithm?

Worked solution

Count the constraints that need a slack variable
$2x + 2y \le 21,\quad 2y \le 6$
Only the $\le$ constraints (not the non-negativity conditions) need slack variables.
Turn each constraint into an equation
$2x + 2y + s_{1} = 21,\quad 2y + s_{2} = 6$
One new non-negative variable is introduced for each constraint.
State the number of slack variables
$\text{number of slack variables} = 2$
One slack variable is needed for each of the $2$ constraints.

Answer

2

Question 2

2 markseasy

Maximise

P = 9x + 4y

subject to the constraints

3x + y \le 16

x + 2y \le 16

, where

x \ge 0

y \ge 0

. The objective row of the tableau is written as

P - 9x - 4y = 0

s_{1}

, write constraint

1

, namely

3x + y \le 16

, as an equation.

Worked solution

Recall the definition of a slack variable
$3x + y \le 16 \iff s_{1} = 16 - \left(3x + y\right),\ s_{1} \ge 0$
The slack variable is the amount by which the constraint falls short of its limit.
Move the slack variable to the left-hand side
$3x + y + s_{1} = 16$
This is the form in which the constraint is entered into the tableau.
Recall what a slack variable does
$\text{constraint} \le \text{limit} \iff \text{constraint} + s = \text{limit},\ s \ge 0$
A slack variable measures the unused amount of the resource in that constraint.
State the constraint as an equation
$3x + y + s_{1} = 16$
The inequality has become an equation in the slack form used by the simplex algorithm.

Answer

3x + y + s_{1} = 16

Question 3

2 markseasy

Maximise

P = 5x + 4y

subject to the constraints

4x + y \le 9

3x + 3y \le 28

, where

x \ge 0

y \ge 0

. The objective row of the tableau is written as

P - 5x - 4y = 0

, so its entries in the variable columns are the negatives of the coefficients of the objective function. At each iteration the pivot column is the column with the most negative entry in the objective row, and the pivot row is the row with the smallest non-negative ratio, each ratio being the entry in the value column divided by the entry of that row in the pivot column, computed only for rows whose entry in the pivot column is strictly positive. Write down the entry of the objective row of the initial tableau in the

x

column.

Worked solution

Write the objective function as the objective row
$P - 5x - 4y = 0$
Every variable is taken to the left-hand side of $P = 5x + 4y$ .
Read the objective row as a list of coefficients
$\left(-5,\ -4,\ 0,\ 0,\ 1\right)$
The entries are taken in the column order $x$ , $y$ , $s_{1}$ , $s_{2}$ , $P$ .
Recall what a slack variable does
$\text{constraint} \le \text{limit} \iff \text{constraint} + s = \text{limit},\ s \ge 0$
A slack variable measures the unused amount of the resource in that constraint.
State the required entry
$\text{objective row}, \ x \text{ column} = -5$
The entry is the negative of the coefficient of $x$ in $P$ .

Answer

-5

Question 4

2 markseasy

Maximise

P = 4x + 6y

subject to the constraints

2x + 4y \le 9

4x + y \le 24

, where

x \ge 0

y \ge 0

. The objective row of the tableau is written as

P - 4x - 6y = 0

, so its entries in the variable columns are the negatives of the coefficients of the objective function. At each iteration the pivot column is the column with the most negative entry in the objective row, and the pivot row is the row with the smallest non-negative ratio, each ratio being the entry in the value column divided by the entry of that row in the pivot column, computed only for rows whose entry in the pivot column is strictly positive. Write down the objective row of the initial simplex tableau as an equation.

Worked solution

Start from the objective function
$P = 4x + 6y$
The simplex algorithm needs the objective written with everything on one side.
Subtract every variable term from both sides
$P - \left(4x + 6y\right) = 0$
This produces the row that is entered into the tableau.
State the objective row
$P - 4x - 6y = 0$
The coefficients of the variables in this row are negative, which is what makes a pivot possible.

Answer

P - 4x - 6y = 0

Question 5

2 markseasy

Maximise

P = 9x + 7y

subject to the constraints

2x \le 9

4y \le 32

, where

x \ge 0

y \ge 0

. The objective row of the tableau is written as

P - 9x - 7y = 0

, so its entries in the variable columns are the negatives of the coefficients of the objective function. At each iteration the pivot column is the column with the most negative entry in the objective row, and the pivot row is the row with the smallest non-negative ratio, each ratio being the entry in the value column divided by the entry of that row in the pivot column, computed only for rows whose entry in the pivot column is strictly positive. Which column is the pivot column for the first iteration of the simplex algorithm?

Worked solution

Introduce a slack variable in each constraint
$2x + s_{1} = 9,\quad 4y + s_{2} = 32,\quad s_{1},\ s_{2} \ge 0$
Each $\le$ constraint becomes an equation by adding a non-negative slack variable.
Write down the initial simplex tableau
$\begin{array}{c|ccccc|c}\text{b.v.} & x & y & s_{1} & s_{2} & P & \text{Value} \\ \hline s_{1} & 2 & 0 & 1 & 0 & 0 & 9 \\ s_{2} & 0 & 4 & 0 & 1 & 0 & 32 \\ \hline P & -9 & -7 & 0 & 0 & 1 & 0\end{array}$
The slack variables are the initial basic variables and the origin is the initial basic feasible solution.
Find the most negative entry
$\min\left\{-9,\ -7,\ 0,\ 0\right\} = -9$
The most negative entry is unique here, so the pivot column is unambiguous.
Select the pivot column
$\text{pivot column} = x$
The column with the most negative objective-row entry is the pivot column.

Answer

\text{pivot column} = x

Unlock 65 more The simplex algorithm questions

Create a free account to work through every Further Maths The simplex algorithm question with instant step-by-step worked solutions, progress tracking and interactive lessons.

Full worked solutions for every question
Interactive lessons and instant feedback
Track your mastery across every topic

Create a Free Account

No card required · Free forever

More The simplex algorithm practice

Hard Questions Practice Questions

The simplex algorithm Worked Solutions — Further Maths Maths

Worked solution

Worked solution

Worked solution

Worked solution

Worked solution

Unlock 65 more The simplex algorithm questions

More The simplex algorithm practice

Related Decision Maths topics