Two-stage Simplex and big-M methods

Two-stage Simplex and big-M methods Test

Spec 5.4 · Edexcel 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

Edexcel A-Level Further Maths

Two-stage Simplex and big-M methods

Total 27 marks

Name

Class

Date

  1. 1
    A maximising problem has the constraint 2x+y≥82x+y\ge8, to which a surplus variable ss and an artificial variable tt are added. The objective is P=3x+2yP=3x+2y and the big-M method is used, where MM is a very large positive number.
    (a)
    Which equation is the constraint after ss and tt are introduced?
    [1 mark]
    • A2x+y−s+t=82x+y-s+t=8
    • B2x+y+s+t=82x+y+s+t=8
    • C2x+y−s=82x+y-s=8
    • D2x+y+s−t=82x+y+s-t=8
    (b)
    Which is the objective function used in the big-M method?
    [1 mark]
    • AP=3x+2y+MtP=3x+2y+Mt
    • BP=3x+2y−MtP=3x+2y-Mt
    • CP=3x+2y−MsP=3x+2y-Ms
    • DP=3x+2y−MP=3x+2y-M
    (c)
    Explain the purpose of the term −Mt-Mt, and what it means if t>0t>0 in the final optimal tableau.
    [2 marks]

    Total for question 1: 4 marks

  2. 2
    A maximising problem has the constraints x+y≤6x+y\le6 and x+y≥9x+y\ge9, with x,y≥0x,y\ge0. It is solved using the two-stage Simplex method, with a slack variable s1s_1 in the first constraint and a surplus variable s2s_2 and an artificial variable tt in the second.
    (a)
    What is the minimum value of the stage 1 objective I=tI=t?
    [1 mark]
    • A00
    • B66
    • C99
    • D33
    (b)
    What does the end of stage 1 show?
    [1 mark]
    • AThe optimal solution is x=6x=6, y=0y=0
    • BThe problem is unbounded
    • CThe problem has no feasible solution
    • DStage 2 starts from x=y=0x=y=0
    (c)
    Explain, without using the Simplex algorithm, why the stage 1 result is correct.
    [2 marks]

    Total for question 2: 4 marks

  3. 3
    A company makes xx tonnes of product X and yy tonnes of product Y. It wishes to maximise the profit P=3x+4yP=3x+4y subject to x+y≤12x+y\le12 and x+2y≥6x+2y\ge6, with x≥0x\ge0 and y≥0y\ge0. The big-M method is used, with slack variable s1s_1, surplus variable s2s_2 and artificial variable tt. Tableau columns are in the order xx, yy, s1s_1, s2s_2, tt, then the value.
    (a)
    Write the constraints as equations and write down the objective function for the big-M method.
    [3 marks]
    (b)
    Eliminate tt from the objective row to find the PP row of the initial tableau, and hence identify the first pivot.
    [4 marks]

    Total for question 3: 7 marks

  4. 4
    A company maximises P=2x+5yP=2x+5y subject to x+y≤10x+y\le10 and 3x+y≥63x+y\ge6, with x,y≥0x,y\ge0. The two-stage Simplex method is used, with slack variable s1s_1, surplus variable s2s_2 and artificial variable tt. In stage 1 the aim is to minimise I=tI=t, which is done by maximising Q=−tQ=-t. Tableau columns are in the order xx, yy, s1s_1, s2s_2, tt, then the value.
    (a)
    (i) Write the constraints as equations and the stage 1 objective row, with tt eliminated. Carry the PP row through stage 1.
    (ii) Perform the first iteration of stage 1 and write down the new tableau. State what it shows.
    [6 marks]
    (b)
    (i) Carry out stage 2 until an optimal tableau is reached.
    (ii) State the optimal solution and verify that it satisfies both constraints.
    [6 marks]

    Total for question 4: 12 marks

End of questions

Subtopic tests