Hard Further Maths The simplex algorithm Questions

Challenging, exam-style Further Maths The simplex algorithm questions with worked solutions. Stretch yourself on the hardest simplex, optimal-solution, slack-variables, pivoting problems.

simplexoptimal-solutionslack-variablespivotingoptimality
Further Maths34 questionsStep-by-step solutions
Question 1
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}
Question 2
9 markschallenging
Maximise P=3x+7yP = 3x + 7y subject to the constraints 3x+y≤183x + y \le 18, 3x+2y≤363x + 2y \le 36, x+4y≤40x + 4y \le 40, where x≥0x \ge 0, y≥0y \ge 0. The objective row of the tableau is written as P−3x−7y=0P - 3x - 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. Use the simplex algorithm to solve this linear programme and write down the value of the slack variable s2s_{2} in the final tableau.
Show worked solution

Worked solution

  1. Introduce a slack variable in each constraint

    3x+y+s1=18,3x+2y+s2=36,x+4y+s3=40,s1, s2, s3≥03x + y + s_{1} = 18,\quad 3x + 2y + s_{2} = 36,\quad x + 4y + s_{3} = 40,\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−3x−7y=0P - 3x - 7y = 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.xys1s2s3PValues131100018s232010036s314001040P−3−700010\begin{array}{c|cccccc|c}\text{b.v.} & x & y & s_{1} & s_{2} & s_{3} & P & \text{Value} \\ \hline s_{1} & 3 & 1 & 1 & 0 & 0 & 0 & 18 \\ s_{2} & 3 & 2 & 0 & 1 & 0 & 0 & 36 \\ s_{3} & 1 & 4 & 0 & 0 & 1 & 0 & 40 \\ \hline P & -3 & -7 & 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=−7⇒pivot column=y\text{most negative objective-row entry} = -7 \Rightarrow \text{pivot column} = y

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

  5. Iteration 1: apply the ratio test

    181=18,362=18,404=10⇒pivot row=s3\frac{18}{1} = 18,\quad \frac{36}{2} = 18,\quad \frac{40}{4} = 10 \Rightarrow \text{pivot row} = s_{3}

    The smallest non-negative ratio picks the pivot row.

  6. Iteration 1: state the pivot element

    pivot element=4\text{pivot element} = 4

    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,Rs2→Rs2−2×Rpivot,RP→RP+7×RpivotR_{s_{1}} \to R_{s_{1}} - 1 \times R_{\text{pivot}},\quad R_{s_{2}} \to R_{s_{2}} - 2 \times R_{\text{pivot}},\quad R_{P} \to R_{P} + 7 \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.xys1s2s3PValues1114010−1408s252001−12016y1410014010P−5400074170\begin{array}{c|cccccc|c}\text{b.v.} & x & y & s_{1} & s_{2} & s_{3} & P & \text{Value} \\ \hline s_{1} & \frac{11}{4} & 0 & 1 & 0 & -\frac{1}{4} & 0 & 8 \\ s_{2} & \frac{5}{2} & 0 & 0 & 1 & -\frac{1}{2} & 0 & 16 \\ y & \frac{1}{4} & 1 & 0 & 0 & \frac{1}{4} & 0 & 10 \\ \hline P & -\frac{5}{4} & 0 & 0 & 0 & \frac{7}{4} & 1 & 70\end{array}

    The variable yy has entered the basis and s3s_{3} has left it.

  9. Iteration 2: choose the pivot column

    most negative objective-row entry=−54⇒pivot column=x\text{most negative objective-row entry} = -\frac{5}{4} \Rightarrow \text{pivot column} = x

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

  10. Iteration 2: apply the ratio test

    8114=3211,1652=325,1014=40⇒pivot row=s1\frac{8}{\frac{11}{4}} = \frac{32}{11},\quad \frac{16}{\frac{5}{2}} = \frac{32}{5},\quad \frac{10}{\frac{1}{4}} = 40 \Rightarrow \text{pivot row} = s_{1}

    The smallest non-negative ratio picks the pivot row.

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

    Rs2→Rs2−52×Rpivot,Ry→Ry−14×Rpivot,RP→RP+54×RpivotR_{s_{2}} \to R_{s_{2}} - \frac{5}{2} \times R_{\text{pivot}},\quad R_{y} \to R_{y} - \frac{1}{4} \times R_{\text{pivot}},\quad R_{P} \to R_{P} + \frac{5}{4} \times R_{\text{pivot}}

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

  12. Iteration 2: write down the new tableau

    b.v.xys1s2s3PValuex104110−11103211s200−10111−31109611y01−1110311010211P0051101811181011\begin{array}{c|cccccc|c}\text{b.v.} & x & y & s_{1} & s_{2} & s_{3} & P & \text{Value} \\ \hline x & 1 & 0 & \frac{4}{11} & 0 & -\frac{1}{11} & 0 & \frac{32}{11} \\ s_{2} & 0 & 0 & -\frac{10}{11} & 1 & -\frac{3}{11} & 0 & \frac{96}{11} \\ y & 0 & 1 & -\frac{1}{11} & 0 & \frac{3}{11} & 0 & \frac{102}{11} \\ \hline P & 0 & 0 & \frac{5}{11} & 0 & \frac{18}{11} & 1 & \frac{810}{11}\end{array}

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

  13. Check the stopping condition

    objective row=(0, 0, 511, 0, 1811, 1)≥0 in every variable column\text{objective row} = \left(0,\ 0,\ \frac{5}{11},\ 0,\ \frac{18}{11},\ 1\right) \ge 0 \text{ in every variable column}

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

  14. Read the solution from the final tableau

    x=3211,s2=9611,y=10211,s1=0,s3=0x = \frac{32}{11},\quad s_{2} = \frac{96}{11},\quad y = \frac{102}{11},\quad s_{1} = 0,\quad s_{3} = 0

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

  15. State the value of s2s_{2} at the optimum

    s2=9611s_{2} = \frac{96}{11}

    This slack is positive, so constraint 22 has \frac{96}{11} to spare at the optimum.

Answer
s2=9611s_{2} = \frac{96}{11}
Question 3
9 markschallenging
Maximise P=7x+5yP = 7x + 5y subject to the constraints 3x+2y≤103x + 2y \le 10, 2x≤252x \le 25, 3x+3y≤403x + 3y \le 40, where x≥0x \ge 0, y≥0y \ge 0. The objective row of the tableau is written as P−7x−5y=0P - 7x - 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. Use the simplex algorithm to solve this linear programme and find the value of yy at the optimum.
Show worked solution

Worked solution

  1. Introduce a slack variable in each constraint

    3x+2y+s1=10,2x+s2=25,3x+3y+s3=40,s1, s2, s3≥03x + 2y + s_{1} = 10,\quad 2x + s_{2} = 25,\quad 3x + 3y + s_{3} = 40,\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−7x−5y=0P - 7x - 5y = 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.xys1s2s3PValues132100010s220010025s333001040P−7−500010\begin{array}{c|cccccc|c}\text{b.v.} & x & y & s_{1} & s_{2} & s_{3} & P & \text{Value} \\ \hline s_{1} & 3 & 2 & 1 & 0 & 0 & 0 & 10 \\ s_{2} & 2 & 0 & 0 & 1 & 0 & 0 & 25 \\ s_{3} & 3 & 3 & 0 & 0 & 1 & 0 & 40 \\ \hline P & -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=−7⇒pivot column=x\text{most negative objective-row entry} = -7 \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

    103=103,252=252,403=403⇒pivot row=s1\frac{10}{3} = \frac{10}{3},\quad \frac{25}{2} = \frac{25}{2},\quad \frac{40}{3} = \frac{40}{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=3\text{pivot element} = 3

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

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

    Rs1→13Rs1=(1, 23, 13, 0, 0, 0, 103)R_{s_{1}} \to \frac{1}{3} R_{s_{1}} = \left(1,\ \frac{2}{3},\ \frac{1}{3},\ 0,\ 0,\ 0,\ \frac{10}{3}\right)

    This makes the pivot element equal to 11.

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

    Rs2→Rs2−2×Rpivot,Rs3→Rs3−3×Rpivot,RP→RP+7×RpivotR_{s_{2}} \to R_{s_{2}} - 2 \times R_{\text{pivot}},\quad R_{s_{3}} \to R_{s_{3}} - 3 \times R_{\text{pivot}},\quad R_{P} \to R_{P} + 7 \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.xys1s2s3PValuex12313000103s20−43−23100553s301−101030P0−1373001703\begin{array}{c|cccccc|c}\text{b.v.} & x & y & s_{1} & s_{2} & s_{3} & P & \text{Value} \\ \hline x & 1 & \frac{2}{3} & \frac{1}{3} & 0 & 0 & 0 & \frac{10}{3} \\ s_{2} & 0 & -\frac{4}{3} & -\frac{2}{3} & 1 & 0 & 0 & \frac{55}{3} \\ s_{3} & 0 & 1 & -1 & 0 & 1 & 0 & 30 \\ \hline P & 0 & -\frac{1}{3} & \frac{7}{3} & 0 & 0 & 1 & \frac{70}{3}\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=−13⇒pivot column=y\text{most negative objective-row entry} = -\frac{1}{3} \Rightarrow \text{pivot column} = y

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

  11. Iteration 2: apply the ratio test

    10323=5,301=30⇒pivot row=x\frac{\frac{10}{3}}{\frac{2}{3}} = 5,\quad \frac{30}{1} = 30 \Rightarrow \text{pivot row} = x

    The smallest non-negative ratio picks the pivot row. The s2s_{2} row is excluded because its entry in the pivot column is not positive.

  12. Iteration 2: state the pivot element

    pivot element=23\text{pivot element} = \frac{2}{3}

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

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

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

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

  14. Iteration 2: write down the new tableau

    b.v.xys1s2s3PValuey321120005s220010025s3−320−3201025P1205200125\begin{array}{c|cccccc|c}\text{b.v.} & x & y & s_{1} & s_{2} & s_{3} & P & \text{Value} \\ \hline y & \frac{3}{2} & 1 & \frac{1}{2} & 0 & 0 & 0 & 5 \\ s_{2} & 2 & 0 & 0 & 1 & 0 & 0 & 25 \\ s_{3} & -\frac{3}{2} & 0 & -\frac{3}{2} & 0 & 1 & 0 & 25 \\ \hline P & \frac{1}{2} & 0 & \frac{5}{2} & 0 & 0 & 1 & 25\end{array}

    The variable yy has entered the basis and xx has left it.

  15. Check the stopping condition

    objective row=(12, 0, 52, 0, 0, 1)≥0 in every variable column\text{objective row} = \left(\frac{1}{2},\ 0,\ \frac{5}{2},\ 0,\ 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.

  16. Read the solution from the final tableau

    y=5,s2=25,s3=25,x=0,s1=0y = 5,\quad s_{2} = 25,\quad s_{3} = 25,\quad x = 0,\quad s_{1} = 0

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

  17. State the value of yy at the optimum

    y=5y = 5

    The optimal value of yy is read from the final tableau.

Answer
y=5y = 5
Question 4
9 markschallenging
Maximise P=8x+7y+9zP = 8x + 7y + 9z subject to the constraints x+4y+3z≤18x + 4y + 3z \le 18, x+4y+z≤9x + 4y + z \le 9, 4y+z≤254y + z \le 25, where x≥0x \ge 0, y≥0y \ge 0, z≥0z \ge 0. The objective row of the tableau is written as P−8x−7y−9z=0P - 8x - 7y - 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. Use the simplex algorithm to solve this linear programme and find the value of yy at the optimum.
Show worked solution

Worked solution

  1. Introduce a slack variable in each constraint

    x+4y+3z+s1=18,x+4y+z+s2=9,4y+z+s3=25,s1, s2, s3≥0x + 4y + 3z + s_{1} = 18,\quad x + 4y + z + s_{2} = 9,\quad 4y + z + s_{3} = 25,\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−8x−7y−9z=0P - 8x - 7y - 9z = 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.xyzs1s2s3PValues1143100018s214101009s3041001025P−8−7−900010\begin{array}{c|ccccccc|c}\text{b.v.} & x & y & z & s_{1} & s_{2} & s_{3} & P & \text{Value} \\ \hline s_{1} & 1 & 4 & 3 & 1 & 0 & 0 & 0 & 18 \\ s_{2} & 1 & 4 & 1 & 0 & 1 & 0 & 0 & 9 \\ s_{3} & 0 & 4 & 1 & 0 & 0 & 1 & 0 & 25 \\ \hline P & -8 & -7 & -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.

  4. 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.

  5. Iteration 1: apply the ratio test

    183=6,91=9,251=25⇒pivot row=s1\frac{18}{3} = 6,\quad \frac{9}{1} = 9,\quad \frac{25}{1} = 25 \Rightarrow \text{pivot row} = s_{1}

    The smallest non-negative ratio picks the pivot row.

  6. Iteration 1: state the pivot element

    pivot element=3\text{pivot element} = 3

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

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

    Rs1→13Rs1=(13, 43, 1, 13, 0, 0, 0, 6)R_{s_{1}} \to \frac{1}{3} R_{s_{1}} = \left(\frac{1}{3},\ \frac{4}{3},\ 1,\ \frac{1}{3},\ 0,\ 0,\ 0,\ 6\right)

    This makes the pivot element equal to 11.

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

    Rs2→Rs2−1×Rpivot,Rs3→Rs3−1×Rpivot,RP→RP+9×RpivotR_{s_{2}} \to R_{s_{2}} - 1 \times R_{\text{pivot}},\quad R_{s_{3}} \to R_{s_{3}} - 1 \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.xyzs1s2s3PValuez13431130006s223830−131003s3−13830−1301019P−550300154\begin{array}{c|ccccccc|c}\text{b.v.} & x & y & z & s_{1} & s_{2} & s_{3} & P & \text{Value} \\ \hline z & \frac{1}{3} & \frac{4}{3} & 1 & \frac{1}{3} & 0 & 0 & 0 & 6 \\ s_{2} & \frac{2}{3} & \frac{8}{3} & 0 & -\frac{1}{3} & 1 & 0 & 0 & 3 \\ s_{3} & -\frac{1}{3} & \frac{8}{3} & 0 & -\frac{1}{3} & 0 & 1 & 0 & 19 \\ \hline P & -5 & 5 & 0 & 3 & 0 & 0 & 1 & 54\end{array}

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

  10. Iteration 2: choose the pivot column

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

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

  11. Iteration 2: apply the ratio test

    613=18,323=92⇒pivot row=s2\frac{6}{\frac{1}{3}} = 18,\quad \frac{3}{\frac{2}{3}} = \frac{9}{2} \Rightarrow \text{pivot row} = s_{2}

    The smallest non-negative ratio picks the pivot row. The s3s_{3} row is excluded because its entry in the pivot column is not positive.

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

    Rz→Rz−13×Rpivot,Rs3→Rs3+13×Rpivot,RP→RP+5×RpivotR_{z} \to R_{z} - \frac{1}{3} \times R_{\text{pivot}},\quad R_{s_{3}} \to R_{s_{3}} + \frac{1}{3} \times R_{\text{pivot}},\quad R_{P} \to R_{P} + 5 \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.xyzs1s2s3PValuez00112−120092x140−12320092s3040−121210412P025012152011532\begin{array}{c|ccccccc|c}\text{b.v.} & x & y & z & s_{1} & s_{2} & s_{3} & P & \text{Value} \\ \hline z & 0 & 0 & 1 & \frac{1}{2} & -\frac{1}{2} & 0 & 0 & \frac{9}{2} \\ x & 1 & 4 & 0 & -\frac{1}{2} & \frac{3}{2} & 0 & 0 & \frac{9}{2} \\ s_{3} & 0 & 4 & 0 & -\frac{1}{2} & \frac{1}{2} & 1 & 0 & \frac{41}{2} \\ \hline P & 0 & 25 & 0 & \frac{1}{2} & \frac{15}{2} & 0 & 1 & \frac{153}{2}\end{array}

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

  14. Check the stopping condition

    objective row=(0, 25, 0, 12, 152, 0, 1)≥0 in every variable column\text{objective row} = \left(0,\ 25,\ 0,\ \frac{1}{2},\ \frac{15}{2},\ 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

    z=92,x=92,s3=412,y=0,s1=0,s2=0z = \frac{9}{2},\quad x = \frac{9}{2},\quad s_{3} = \frac{41}{2},\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 value of yy at the optimum

    y=0y = 0

    The optimal value of yy is read from the final tableau.

Answer
y=0y = 0
Question 5
9 markschallenging
Maximise P=5x+8y+6zP = 5x + 8y + 6z subject to the constraints 2x+y+2z≤202x + y + 2z \le 20, 4x+y+3z≤304x + y + 3z \le 30, 4x+4y≤324x + 4y \le 32, where x≥0x \ge 0, y≥0y \ge 0, z≥0z \ge 0. The objective row of the tableau is written as P−5x−8y−6z=0P - 5x - 8y - 6z = 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. Applying the simplex algorithm to this linear programme produces the tableau b.v.xyzs1s2s3PValuez1201120−1806s23200−3211804y110001408P60030541100\begin{array}{c|ccccccc|c}\text{b.v.} & x & y & z & s_{1} & s_{2} & s_{3} & P & \text{Value} \\ \hline z & \frac{1}{2} & 0 & 1 & \frac{1}{2} & 0 & -\frac{1}{8} & 0 & 6 \\ s_{2} & \frac{3}{2} & 0 & 0 & -\frac{3}{2} & 1 & \frac{1}{8} & 0 & 4 \\ y & 1 & 1 & 0 & 0 & 0 & \frac{1}{4} & 0 & 8 \\ \hline P & 6 & 0 & 0 & 3 & 0 & \frac{5}{4} & 1 & 100\end{array}. Is this tableau optimal, and why?
Show worked solution

Worked solution

  1. Introduce a slack variable in each constraint

    2x+y+2z+s1=20,4x+y+3z+s2=30,4x+4y+s3=32,s1, s2, s3≥02x + y + 2z + s_{1} = 20,\quad 4x + y + 3z + s_{2} = 30,\quad 4x + 4y + s_{3} = 32,\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−5x−8y−6z=0P - 5x - 8y - 6z = 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.xyzs1s2s3PValues1212100020s2413010030s3440001032P−5−8−600010\begin{array}{c|ccccccc|c}\text{b.v.} & x & y & z & s_{1} & s_{2} & s_{3} & P & \text{Value} \\ \hline s_{1} & 2 & 1 & 2 & 1 & 0 & 0 & 0 & 20 \\ s_{2} & 4 & 1 & 3 & 0 & 1 & 0 & 0 & 30 \\ s_{3} & 4 & 4 & 0 & 0 & 0 & 1 & 0 & 32 \\ \hline P & -5 & -8 & -6 & 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=−8⇒pivot column=y\text{most negative objective-row entry} = -8 \Rightarrow \text{pivot column} = y

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

  5. Iteration 1: apply the ratio test

    201=20,301=30,324=8⇒pivot row=s3\frac{20}{1} = 20,\quad \frac{30}{1} = 30,\quad \frac{32}{4} = 8 \Rightarrow \text{pivot row} = s_{3}

    The smallest non-negative ratio picks the pivot row.

  6. Iteration 1: state the pivot element

    pivot element=4\text{pivot element} = 4

    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,Rs2→Rs2−1×Rpivot,RP→RP+8×RpivotR_{s_{1}} \to R_{s_{1}} - 1 \times R_{\text{pivot}},\quad R_{s_{2}} \to R_{s_{2}} - 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.xyzs1s2s3PValues110210−14012s230301−14022y110001408P30−6002164\begin{array}{c|ccccccc|c}\text{b.v.} & x & y & z & s_{1} & s_{2} & s_{3} & P & \text{Value} \\ \hline s_{1} & 1 & 0 & 2 & 1 & 0 & -\frac{1}{4} & 0 & 12 \\ s_{2} & 3 & 0 & 3 & 0 & 1 & -\frac{1}{4} & 0 & 22 \\ y & 1 & 1 & 0 & 0 & 0 & \frac{1}{4} & 0 & 8 \\ \hline P & 3 & 0 & -6 & 0 & 0 & 2 & 1 & 64\end{array}

    The variable yy has entered the basis and s3s_{3} has left it.

  9. Iteration 2: choose the pivot column

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

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

  10. Iteration 2: apply the ratio test

    122=6,223=223⇒pivot row=s1\frac{12}{2} = 6,\quad \frac{22}{3} = \frac{22}{3} \Rightarrow \text{pivot row} = s_{1}

    The smallest non-negative ratio picks the pivot row. The yy row is excluded because its entry in the pivot column is not positive.

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

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

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

  12. Iteration 2: write down the new tableau

    b.v.xyzs1s2s3PValuez1201120−1806s23200−3211804y110001408P60030541100\begin{array}{c|ccccccc|c}\text{b.v.} & x & y & z & s_{1} & s_{2} & s_{3} & P & \text{Value} \\ \hline z & \frac{1}{2} & 0 & 1 & \frac{1}{2} & 0 & -\frac{1}{8} & 0 & 6 \\ s_{2} & \frac{3}{2} & 0 & 0 & -\frac{3}{2} & 1 & \frac{1}{8} & 0 & 4 \\ y & 1 & 1 & 0 & 0 & 0 & \frac{1}{4} & 0 & 8 \\ \hline P & 6 & 0 & 0 & 3 & 0 & \frac{5}{4} & 1 & 100\end{array}

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

  13. Check the stopping condition

    objective row=(6, 0, 0, 3, 0, 54, 1)≥0 in every variable column\text{objective row} = \left(6,\ 0,\ 0,\ 3,\ 0,\ \frac{5}{4},\ 1\right) \ge 0 \text{ in every variable column}

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

  14. Read the solution from the final tableau

    z=6,s2=4,y=8,x=0,s1=0,s3=0z = 6,\quad s_{2} = 4,\quad y = 8,\quad x = 0,\quad s_{1} = 0,\quad s_{3} = 0

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

  15. Select the correct explanation

    objective row=(6, 0, 0, 3, 0, 54, 1)≥0⇒optimal\text{objective row} = \left(6,\ 0,\ 0,\ 3,\ 0,\ \frac{5}{4},\ 1\right) \ge 0 \Rightarrow \text{optimal}

    No column can be chosen as a pivot column, so the algorithm terminates.

Answer
optimal: no negative entries remain in the objective row\text{optimal: no negative entries remain in the objective row}

Unlock 29 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

Practice QuestionsWorked Solutions

Related Decision Maths topics

AlgorithmsAllocation (assignment)Critical path analysisDecision analysisDynamic programmingFlows in networks