The simplex algorithm

The simplex algorithm Test

Spec DD3–DD4 · AQA A-Level Further Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

AQA A-Level Further Maths

The simplex algorithm

Total 27 marks

Name

Class

Date

  1. 1
    Maximise P=2x+yP=2x+y subject to x+y≤8x+y\leq8, 3x+y≤183x+y\leq18, x≥0x\geq0 and y≥0y\geq0. The simplex algorithm is to be used, with slack variables rr and ss added to the first and second constraints.
    (a)
    Which equation results from adding the slack variable rr to the constraint x+y≤8x+y\leq8?
    [1 mark]
    • Ax+y−r=8x+y-r=8
    • Bx+y+r=8x+y+r=8
    • Cx+y+r≤8x+y+r\leq8
    • Dr=x+y+8r=x+y+8
    Show the mark scheme

    Mark scheme

    Answer: B
    (b)
    Which entry is the pivot in the first iteration?
    [1 mark]
    • AThe 3 in the ss row
    • BThe 1 in the rr row
    • CThe −2-2 in the objective row
    • DThe 18 in the ss row
    Show the mark scheme

    Mark scheme

    Answer: A
    (c)
    Carry out the first iteration. State the values of xx, yy and PP after it.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: divides the ss row by 3, giving x+13y+13s=6x+\frac13y+\frac13s=6 (pivot on the 3)
    A1:
    x=6x=6, y=0y=0, P=12P=12
    Accept:
    P−13y+23s=12P-\frac13y+\frac23s=12 for the objective row

    Total for question 1: 4 marks

  2. 2
    The simplex algorithm is used to maximise P=2x+3yP=2x+3y subject to x+2y≤14x+2y\leq14 and 3x+y≤183x+y\leq18, with slack variables rr and ss. After the first iteration the equations are 12x+y+12r=7\frac12x+y+\frac12r=7, 52x−12r+s=11\frac52x-\frac12r+s=11 and P−12x+32r=21P-\frac12x+\frac32r=21.
    (a)
    What are the values of the variables after the first iteration?
    [1 mark]
    • Ax=7x=7, y=0y=0, r=0r=0, s=11s=11, P=21P=21
    • Bx=0x=0, y=7y=7, r=11r=11, s=0s=0, P=21P=21
    • Cx=0x=0, y=7y=7, r=0r=0, s=11s=11, P=21P=21
    • Dx=0x=0, y=7y=7, r=0r=0, s=11s=11, P=−21P=-21
    Show the mark scheme

    Mark scheme

    Answer: C
    (b)
    What should be done next?
    [1 mark]
    • AStop, because every basic variable is positive
    • BDo another iteration with the rr column as the pivot column
    • CStop, because PP has reached 21
    • DDo another iteration with the xx column as the pivot column
    Show the mark scheme

    Mark scheme

    Answer: D
    (c)
    Find the pivot row for the next iteration, giving a reason.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: ratios for the xx column: 71/2=14\frac{7}{1/2}=14 and 115/2=225\frac{11}{5/2}=\frac{22}{5}
    A1: pivot row is the
    ss row (pivot 52\frac52), because 225\frac{22}{5} is the smaller ratio

    Total for question 2: 4 marks

  3. 3
    Maximise P=4x+3yP=4x+3y subject to 2x+y≤102x+y\leq10, x+y≤8x+y\leq8, x≥0x\geq0 and y≥0y\geq0. The simplex algorithm is to be used with slack variables rr and ss added to the first and second constraints.
    (a)
    Write down the initial simplex tableau as equations, and state which entry is the pivot in the first iteration, with a reason.
    [3 marks]
    Show the mark scheme

    Mark scheme

    B1: 2x+y+r=102x+y+r=10 and x+y+s=8x+y+s=8, and P−4x−3y=0P-4x-3y=0
    B1: pivot column
    xx, because −4-4 is the most negative objective-row entry
    B1: pivot is the 2 in the
    rr row, because 102=5\frac{10}{2}=5 is smaller than 81=8\frac81=8
    (b)
    Complete the simplex algorithm to find the optimal values of xx, yy and PP.
    [4 marks]
    Show the mark scheme

    Mark scheme

    M1: first iteration: x+12y+12r=5x+\frac12y+\frac12r=5, 12y−12r+s=3\frac12y-\frac12r+s=3, P−y+2r=20P-y+2r=20
    M1: second pivot in the
    yy column, with ratios 51/2=10\frac{5}{1/2}=10 and 31/2=6\frac{3}{1/2}=6, so the ss row is chosen
    A1:
    x=2x=2, y=6y=6
    A1:
    P=26P=26, optimal because the objective row P+r+2s=26P+r+2s=26 has no negative coefficients

    Total for question 3: 7 marks

  4. 4
    A bakery makes xx trays of buns and yy trays of loaves. Each tray of buns needs 3 hours of oven time, 4 kg of flour and 1 hour of packing. Each tray of loaves needs 2 hours of oven time, 1 kg of flour and 3 hours of packing. There are 23 hours of oven time, 29 kg of flour and 18 hours of packing available. The profit is £5 per tray of buns and £3 per tray of loaves. The bakery uses the simplex algorithm to maximise the profit PP, with slack variables rr, ss and tt for the oven, flour and packing constraints.
    (a)
    Use the simplex algorithm to find how many trays of each to make for the greatest profit, and the maximum profit.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: initial equations 3x+2y+r=233x+2y+r=23, 4x+y+s=294x+y+s=29, x+3y+t=18x+3y+t=18, P−5x−3y=0P-5x-3y=0
    M1: first pivot in the
    xx column, with ratios 233\frac{23}{3}, 294\frac{29}{4}, 1818, so the ss row is chosen
    A1: after the first iteration
    P−74y+54s=1454P-\frac74y+\frac54s=\frac{145}{4}
    M1: second pivot in the
    yy column, with ratios 11, 2929, 4311\frac{43}{11}, so the rr row is chosen
    A1: final objective row
    P+75r+15s=38P+\frac75r+\frac15s=38
    A1:
    x=7x=7, y=1y=1, P=38P=38, optimal because no coefficient in the objective row is negative
    (b)
    (i) Interpret the final tableau in (a) in terms of the oven, the flour and the packing. (ii) The bakery also considers minimising Q=2x−3yQ=2x-3y subject to the same constraints. Explain how to use the simplex algorithm for this, and find the minimum value of QQ.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: (i) r=0r=0 and s=0s=0, so the oven time and the flour are fully used
    B1: (i)
    t=8t=8, so 8 hours of packing are unused
    B1: (i) the objective row has no negative coefficients, so the plan is optimal

    B1: (ii) maximise
    P′=−Q=−2x+3yP'=-Q=-2x+3y, then the minimum of QQ is −P′-P'
    M1: (ii) pivots on the
    yy column, with the smallest ratio 183=6\frac{18}{3}=6 in the tt row
    A1: (ii)
    y=6y=6, x=0x=0, giving P′=18P'=18 and a minimum value Q=−18Q=-18

    Total for question 4: 12 marks

End of questions

Subtopic tests