Further Maths The simplex algorithm Practice Questions

Free Further Maths The simplex algorithm practice questions with full step-by-step worked solutions. Covers simplex, slack-variables, initial-tableau, pivot-column. Practise exam-style problems and check your method.

simplexslack-variablesinitial-tableaupivot-columnpivotingoptimality
Further Maths70 questionsStep-by-step solutions
Question 1
2 markseasy
Maximise P=3x+5yP = 3x + 5y subject to the constraints 2x+2y≤212x + 2y \le 21, 2y≤62y \le 6, where x≥0x \ge 0, y≥0y \ge 0. The objective row of the tableau is written as P−3x−5y=0P - 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?
Show worked solution

Worked solution

  1. Count the constraints that need a slack variable

    2x+2y≤21,2y≤62x + 2y \le 21,\quad 2y \le 6

    Only the ≤\le constraints (not the non-negativity conditions) need slack variables.

  2. Turn each constraint into an equation

    2x+2y+s1=21,2y+s2=62x + 2y + s_{1} = 21,\quad 2y + s_{2} = 6

    One new non-negative variable is introduced for each constraint.

  3. State the number of slack variables

    number of slack variables=2\text{number of slack variables} = 2

    One slack variable is needed for each of the 22 constraints.

Answer
22
Question 2
2 markseasy
Maximise P=7x+4yP = 7x + 4y subject to the constraints 4x≤84x \le 8, 3x+y≤283x + y \le 28, 3x≤253x \le 25, where x≥0x \ge 0, y≥0y \ge 0. The objective row of the tableau is written as P−7x−4y=0P - 7x - 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. Using the slack variable s3s_{3}, write constraint 33, namely 3x≤253x \le 25, as an equation.
Show worked solution

Worked solution

  1. Recall the definition of a slack variable

    3x≤25  ⟺  s3=25−(3x), s3≥03x \le 25 \iff s_{3} = 25 - \left(3x\right),\ s_{3} \ge 0

    The slack variable is the amount by which the constraint falls short of its limit.

  2. Move the slack variable to the left-hand side

    3x+s3=253x + s_{3} = 25

    This is the form in which the constraint is entered into the tableau.

  3. Recall what a slack variable does

    constraint≤limit  ⟺  constraint+s=limit, s≥0\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.

  4. State the constraint as an equation

    3x+s3=253x + s_{3} = 25

    The inequality has become an equation in the slack form used by the simplex algorithm.

Answer
3x+s3=253x + s_{3} = 25
Question 3
4 marksintermediate
Maximise P=7x+4y+9zP = 7x + 4y + 9z subject to the constraints 4x+3y+3z≤164x + 3y + 3z \le 16, 2x+4y+4z≤62x + 4y + 4z \le 6, 2x+4y+z≤182x + 4y + z \le 18, where x≥0x \ge 0, y≥0y \ge 0, z≥0z \ge 0. The objective row of the tableau is written as P−7x−4y−9z=0P - 7x - 4y - 9z = 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 second iteration of the simplex algorithm?
Show worked solution

Worked solution

  1. Introduce a slack variable in each constraint

    4x+3y+3z+s1=16,2x+4y+4z+s2=6,2x+4y+z+s3=18,s1, s2, s3≥04x + 3y + 3z + s_{1} = 16,\quad 2x + 4y + 4z + s_{2} = 6,\quad 2x + 4y + z + s_{3} = 18,\quad s_{1},\ s_{2},\ s_{3} \ge 0

    Each ≤\le constraint becomes an equation by adding a non-negative slack variable.

  2. Write down the initial simplex tableau

    b.v.xyzs1s2s3PValues1433100016s224401006s3241001018P−7−4−900010\begin{array}{c|ccccccc|c}\text{b.v.} & x & y & z & s_{1} & s_{2} & s_{3} & P & \text{Value} \\ \hline s_{1} & 4 & 3 & 3 & 1 & 0 & 0 & 0 & 16 \\ s_{2} & 2 & 4 & 4 & 0 & 1 & 0 & 0 & 6 \\ s_{3} & 2 & 4 & 1 & 0 & 0 & 1 & 0 & 18 \\ \hline P & -7 & -4 & -9 & 0 & 0 & 0 & 1 & 0\end{array}

    The slack variables are the initial basic variables and the origin is the initial basic feasible solution.

  3. Iteration 1: choose the pivot column

    most negative objective-row entry=−9⇒pivot column=z\text{most negative objective-row entry} = -9 \Rightarrow \text{pivot column} = z

    The rule is to pivot on the column with the most negative entry in the objective row.

  4. Iteration 1: write down the new tableau

    b.v.xyzs1s2s3PValues152001−3400232z12110140032s332300−1410332P−525009401272\begin{array}{c|ccccccc|c}\text{b.v.} & x & y & z & s_{1} & s_{2} & s_{3} & P & \text{Value} \\ \hline s_{1} & \frac{5}{2} & 0 & 0 & 1 & -\frac{3}{4} & 0 & 0 & \frac{23}{2} \\ z & \frac{1}{2} & 1 & 1 & 0 & \frac{1}{4} & 0 & 0 & \frac{3}{2} \\ s_{3} & \frac{3}{2} & 3 & 0 & 0 & -\frac{1}{4} & 1 & 0 & \frac{33}{2} \\ \hline P & -\frac{5}{2} & 5 & 0 & 0 & \frac{9}{4} & 0 & 1 & \frac{27}{2}\end{array}

    The variable zz has entered the basis and s2s_{2} has left it.

  5. Read the objective row of the current tableau

    (−52, 5, 0, 0, 94, 0, 1)\left(-\frac{5}{2},\ 5,\ 0,\ 0,\ \frac{9}{4},\ 0,\ 1\right)

    The pivot column is chosen from the objective row of the tableau in front of us.

  6. Find the most negative entry

    min⁡{−52, 5, 0, 0, 94, 0}=−52\min\left\{-\frac{5}{2},\ 5,\ 0,\ 0,\ \frac{9}{4},\ 0\right\} = -\frac{5}{2}

    The most negative entry is unique here, so the pivot column is unambiguous.

  7. Select the pivot column

    pivot column=x\text{pivot column} = x

    The column with the most negative objective-row entry is the pivot column.

Answer
pivot column=x\text{pivot column} = x
Question 4
6 markshard
Maximise P=8x+2yP = 8x + 2y subject to the constraints x+y≤14x + y \le 14, x+3y≤9x + 3y \le 9, where x≥0x \ge 0, y≥0y \ge 0. The objective row of the tableau is written as P−8x−2y=0P - 8x - 2y = 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. Use the simplex algorithm to solve this linear programme and write down the value of the slack variable s1s_{1} in the final tableau.
Show worked solution

Worked solution

  1. Introduce a slack variable in each constraint

    x+y+s1=14,x+3y+s2=9,s1, s2≥0x + y + s_{1} = 14,\quad x + 3y + s_{2} = 9,\quad s_{1},\ s_{2} \ge 0

    Each ≤\le constraint becomes an equation by adding a non-negative slack variable.

  2. Write the objective function as the objective row

    P−8x−2y=0P - 8x - 2y = 0

    Moving every variable to the left makes the objective-row entries the negatives of the coefficients.

  3. Write down the initial simplex tableau

    b.v.xys1s2PValues11110014s2130109P−8−20010\begin{array}{c|ccccc|c}\text{b.v.} & x & y & s_{1} & s_{2} & P & \text{Value} \\ \hline s_{1} & 1 & 1 & 1 & 0 & 0 & 14 \\ s_{2} & 1 & 3 & 0 & 1 & 0 & 9 \\ \hline P & -8 & -2 & 0 & 0 & 1 & 0\end{array}

    The slack variables are the initial basic variables and the origin is the initial basic feasible solution.

  4. Iteration 1: choose the pivot column

    most negative objective-row entry=−8⇒pivot column=x\text{most negative objective-row entry} = -8 \Rightarrow \text{pivot column} = x

    The rule is to pivot on the column with the most negative entry in the objective row.

  5. Iteration 1: apply the ratio test

    141=14,91=9⇒pivot row=s2\frac{14}{1} = 14,\quad \frac{9}{1} = 9 \Rightarrow \text{pivot row} = s_{2}

    The smallest non-negative ratio picks the pivot row.

  6. Iteration 1: state the pivot element

    pivot element=1\text{pivot element} = 1

    The pivot element sits where the pivot column meets the pivot row.

  7. Iteration 1: clear the rest of the pivot column

    Rs1→Rs1−1×Rpivot,RP→RP+8×RpivotR_{s_{1}} \to R_{s_{1}} - 1 \times R_{\text{pivot}},\quad R_{P} \to R_{P} + 8 \times R_{\text{pivot}}

    Row operations reduce every other entry of the pivot column to zero.

  8. Iteration 1: write down the new tableau

    b.v.xys1s2PValues10−21−105x130109P02208172\begin{array}{c|ccccc|c}\text{b.v.} & x & y & s_{1} & s_{2} & P & \text{Value} \\ \hline s_{1} & 0 & -2 & 1 & -1 & 0 & 5 \\ x & 1 & 3 & 0 & 1 & 0 & 9 \\ \hline P & 0 & 22 & 0 & 8 & 1 & 72\end{array}

    The variable xx has entered the basis and s2s_{2} has left it.

  9. Check the stopping condition

    objective row=(0, 22, 0, 8, 1)≥0 in every variable column\text{objective row} = \left(0,\ 22,\ 0,\ 8,\ 1\right) \ge 0 \text{ in every variable column}

    There are no negative entries left in the objective row, so the tableau is optimal.

  10. Read the solution from the final tableau

    s1=5,x=9,y=0,s2=0s_{1} = 5,\quad x = 9,\quad y = 0,\quad s_{2} = 0

    Basic variables take the value in their row of the value column; non-basic variables are zero.

  11. State the value of s1s_{1} at the optimum

    s1=5s_{1} = 5

    This slack is positive, so constraint 11 has 5 to spare at the optimum.

Answer
s1=5s_{1} = 5
Question 5
9 markschallenging
Maximise P=9x+7y+5zP = 9x + 7y + 5z subject to the constraints 2x+4y+z≤92x + 4y + z \le 9, 3x+4y+3z≤203x + 4y + 3z \le 20, 3x+y+3z≤283x + y + 3z \le 28, where x≥0x \ge 0, y≥0y \ge 0, z≥0z \ge 0. The objective row of the tableau is written as P−9x−7y−5z=0P - 9x - 7y - 5z = 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. Use the simplex algorithm to solve this linear programme and find the maximum value of PP.
Show worked solution

Worked solution

  1. Introduce a slack variable in each constraint

    2x+4y+z+s1=9,3x+4y+3z+s2=20,3x+y+3z+s3=28,s1, s2, s3≥02x + 4y + z + s_{1} = 9,\quad 3x + 4y + 3z + s_{2} = 20,\quad 3x + y + 3z + s_{3} = 28,\quad s_{1},\ s_{2},\ s_{3} \ge 0

    Each ≤\le constraint becomes an equation by adding a non-negative slack variable.

  2. Write the objective function as the objective row

    P−9x−7y−5z=0P - 9x - 7y - 5z = 0

    Moving every variable to the left makes the objective-row entries the negatives of the coefficients.

  3. Write down the initial simplex tableau

    b.v.xyzs1s2s3PValues124110009s2343010020s3313001028P−9−7−500010\begin{array}{c|ccccccc|c}\text{b.v.} & x & y & z & s_{1} & s_{2} & s_{3} & P & \text{Value} \\ \hline s_{1} & 2 & 4 & 1 & 1 & 0 & 0 & 0 & 9 \\ s_{2} & 3 & 4 & 3 & 0 & 1 & 0 & 0 & 20 \\ s_{3} & 3 & 1 & 3 & 0 & 0 & 1 & 0 & 28 \\ \hline P & -9 & -7 & -5 & 0 & 0 & 0 & 1 & 0\end{array}

    The slack variables are the initial basic variables and the origin is the initial basic feasible solution.

  4. Iteration 1: choose the pivot column

    most negative objective-row entry=−9⇒pivot column=x\text{most negative objective-row entry} = -9 \Rightarrow \text{pivot column} = x

    The rule is to pivot on the column with the most negative entry in the objective row.

  5. Iteration 1: apply the ratio test

    92=92,203=203,283=283⇒pivot row=s1\frac{9}{2} = \frac{9}{2},\quad \frac{20}{3} = \frac{20}{3},\quad \frac{28}{3} = \frac{28}{3} \Rightarrow \text{pivot row} = s_{1}

    The smallest non-negative ratio picks the pivot row.

  6. Iteration 1: state the pivot element

    pivot element=2\text{pivot element} = 2

    The pivot element sits where the pivot column meets the pivot row.

  7. Iteration 1: divide the pivot row by the pivot element

    Rs1→12Rs1=(1, 2, 12, 12, 0, 0, 0, 92)R_{s_{1}} \to \frac{1}{2} R_{s_{1}} = \left(1,\ 2,\ \frac{1}{2},\ \frac{1}{2},\ 0,\ 0,\ 0,\ \frac{9}{2}\right)

    This makes the pivot element equal to 11.

  8. Iteration 1: clear the rest of the pivot column

    Rs2→Rs2−3×Rpivot,Rs3→Rs3−3×Rpivot,RP→RP+9×RpivotR_{s_{2}} \to R_{s_{2}} - 3 \times R_{\text{pivot}},\quad R_{s_{3}} \to R_{s_{3}} - 3 \times R_{\text{pivot}},\quad R_{P} \to R_{P} + 9 \times R_{\text{pivot}}

    Row operations reduce every other entry of the pivot column to zero.

  9. Iteration 1: write down the new tableau

    b.v.xyzs1s2s3PValuex12121200092s20−232−32100132s30−532−32010292P011−1292001812\begin{array}{c|ccccccc|c}\text{b.v.} & x & y & z & s_{1} & s_{2} & s_{3} & P & \text{Value} \\ \hline x & 1 & 2 & \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & \frac{9}{2} \\ s_{2} & 0 & -2 & \frac{3}{2} & -\frac{3}{2} & 1 & 0 & 0 & \frac{13}{2} \\ s_{3} & 0 & -5 & \frac{3}{2} & -\frac{3}{2} & 0 & 1 & 0 & \frac{29}{2} \\ \hline P & 0 & 11 & -\frac{1}{2} & \frac{9}{2} & 0 & 0 & 1 & \frac{81}{2}\end{array}

    The variable xx has entered the basis and s1s_{1} has left it.

  10. Iteration 2: choose the pivot column

    most negative objective-row entry=−12⇒pivot column=z\text{most negative objective-row entry} = -\frac{1}{2} \Rightarrow \text{pivot column} = z

    The rule is to pivot on the column with the most negative entry in the objective row.

  11. Iteration 2: apply the ratio test

    9212=9,13232=133,29232=293⇒pivot row=s2\frac{\frac{9}{2}}{\frac{1}{2}} = 9,\quad \frac{\frac{13}{2}}{\frac{3}{2}} = \frac{13}{3},\quad \frac{\frac{29}{2}}{\frac{3}{2}} = \frac{29}{3} \Rightarrow \text{pivot row} = s_{2}

    The smallest non-negative ratio picks the pivot row.

  12. Iteration 2: clear the rest of the pivot column

    Rx→Rx−12×Rpivot,Rs3→Rs3−32×Rpivot,RP→RP+12×RpivotR_{x} \to R_{x} - \frac{1}{2} \times R_{\text{pivot}},\quad R_{s_{3}} \to R_{s_{3}} - \frac{3}{2} \times R_{\text{pivot}},\quad R_{P} \to R_{P} + \frac{1}{2} \times R_{\text{pivot}}

    Row operations reduce every other entry of the pivot column to zero.

  13. Iteration 2: write down the new tableau

    b.v.xyzs1s2s3PValuex18301−130073z0−431−12300133s30−300−1108P03130413011283\begin{array}{c|ccccccc|c}\text{b.v.} & x & y & z & s_{1} & s_{2} & s_{3} & P & \text{Value} \\ \hline x & 1 & \frac{8}{3} & 0 & 1 & -\frac{1}{3} & 0 & 0 & \frac{7}{3} \\ z & 0 & -\frac{4}{3} & 1 & -1 & \frac{2}{3} & 0 & 0 & \frac{13}{3} \\ s_{3} & 0 & -3 & 0 & 0 & -1 & 1 & 0 & 8 \\ \hline P & 0 & \frac{31}{3} & 0 & 4 & \frac{1}{3} & 0 & 1 & \frac{128}{3}\end{array}

    The variable zz has entered the basis and s2s_{2} has left it.

  14. Check the stopping condition

    objective row=(0, 313, 0, 4, 13, 0, 1)≥0 in every variable column\text{objective row} = \left(0,\ \frac{31}{3},\ 0,\ 4,\ \frac{1}{3},\ 0,\ 1\right) \ge 0 \text{ in every variable column}

    There are no negative entries left in the objective row, so the tableau is optimal.

  15. Read the solution from the final tableau

    x=73,z=133,s3=8,y=0,s1=0,s2=0x = \frac{7}{3},\quad z = \frac{13}{3},\quad s_{3} = 8,\quad y = 0,\quad s_{1} = 0,\quad s_{2} = 0

    Basic variables take the value in their row of the value column; non-basic variables are zero.

  16. State the maximum value of PP

    Pmax⁡=1283P_{\max} = \frac{128}{3}

    This is the value in the bottom-right corner of the final tableau.

Answer
Pmax⁡=1283P_{\max} = \frac{128}{3}

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 QuestionsWorked Solutions

Related Decision Maths topics

AlgorithmsAllocation (assignment)Critical path analysisDecision analysisDynamic programmingFlows in networks