Formulating linear programs

Formulating linear programs Test

Spec 5.1 · 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

Formulating linear programs

Total 27 marks

Name

Class

Date

  1. 1
    A workshop makes xx tables and yy chairs each week. Each table needs 3 hours of cutting time and each chair needs 2 hours. There are at most 20 hours of cutting time available each week.
    (a)
    Which inequality represents the cutting-time constraint?
    [1 mark]
    • A3x+2y≥203x+2y\ge20
    • B2x+3y≤202x+3y\le20
    • C3x+2y≤203x+2y\le20
    • D3x+2y=203x+2y=20
    Show the mark scheme

    Mark scheme

    Answer: C
    (b)
    A slack variable s1s_1 is introduced so that the constraint becomes an equation. Which equation is correct?
    [1 mark]
    • A3x+2y+s1=203x+2y+s_1=20
    • B3x+2y−s1=203x+2y-s_1=20
    • C3x+2y+s1≤203x+2y+s_1\le20
    • D3x+2y=20+s13x+2y=20+s_1
    Show the mark scheme

    Mark scheme

    Answer: A
    (c)
    Find the value of s1s_1 when x=4x=4 and y=3y=3, and state what it represents in context.
    [2 marks]
    Show the mark scheme

    Mark scheme

    B1: s1=20−3(4)−2(3)=2s_1=20-3(4)-2(3)=2
    B1: 2 hours of cutting time are unused

    Accept: 2 hours of spare cutting time

    Total for question 1: 4 marks

  2. 2
    A farmer mixes xx kg of feed A and yy kg of feed B. Each kilogram of either feed supplies 1 unit of a vitamin, and the mixture must supply at least 5 units of the vitamin in total.
    (a)
    Which inequality represents the vitamin requirement?
    [1 mark]
    • Ax+y≤5x+y\le5
    • Bx+y≥5x+y\ge5
    • Cx+y=5x+y=5
    • Dx−y≥5x-y\ge5
    Show the mark scheme

    Mark scheme

    Answer: B
    (b)
    A surplus variable s2s_2 is introduced to turn the constraint into an equation. Which equation is correct?
    [1 mark]
    • Ax+y+s2=5x+y+s_2=5
    • Bx+y+s2≥5x+y+s_2\ge5
    • C−x−y+s2=5-x-y+s_2=5
    • Dx+y−s2=5x+y-s_2=5
    Show the mark scheme

    Mark scheme

    Answer: D
    (c)
    An artificial variable t1t_1 is also added to this constraint. Write down the equation and explain why t1t_1 is needed.
    [2 marks]
    Show the mark scheme

    Mark scheme

    B1: x+y−s2+t1=5x+y-s_2+t_1=5
    B1: at
    x=y=0x=y=0 the equation without t1t_1 gives −s2=5-s_2=5 (infeasible), so t1t_1 gives an initial basic feasible solution (t1=5t_1=5)
    Accept:
    t1t_1 lets the Simplex algorithm start
    Do not accept:
    t1t_1 is a real quantity of feed

    Total for question 2: 4 marks

  3. 3
    A company makes xx standard gift boxes and yy deluxe gift boxes each day. A standard box needs 4 minutes of packing and 2 metres of ribbon; a deluxe box needs 6 minutes of packing and 5 metres of ribbon. Each day there are 240 minutes of packing time and 150 metres of ribbon available, and at least 10 boxes must be made. Profit is £3 per standard box and £5 per deluxe box. The company wishes to maximise its daily profit PP (in pounds).
    (a)
    Formulate this situation as a linear programming problem.
    [3 marks]
    Show the mark scheme

    Mark scheme

    B1: maximise P=3x+5yP=3x+5y
    B1:
    4x+6y≤2404x+6y\le240 (or 2x+3y≤1202x+3y\le120) and 2x+5y≤1502x+5y\le150
    B1:
    x+y≥10x+y\ge10, x≥0x\ge0, y≥0y\ge0
    Accept: any equivalent form of each constraint
    (b)
    Use the simplified packing constraint 2x+3y≤1202x+3y\le120. Write each constraint as an equation using slack, surplus and artificial variables as appropriate, and write the objective function in the form used in a Simplex tableau (ignore the artificial variable).
    [4 marks]
    Show the mark scheme

    Mark scheme

    M1: a slack variable added to each ≤\le constraint
    A1:
    2x+3y+s1=1202x+3y+s_1=120 and 2x+5y+s2=1502x+5y+s_2=150
    B1:
    x+y−s3+t1=10x+y-s_3+t_1=10 (surplus s3s_3, artificial t1t_1)
    B1:
    P−3x−5y=0P-3x-5y=0
    Accept:
    P−3x−5y+Mt1=0P-3x-5y+Mt_1=0

    Total for question 3: 7 marks

  4. 4
    A farmer plants xx hectares of wheat, yy hectares of barley and zz hectares of oats. There are 80 hectares available in total. Labour is limited to 200 hours: wheat needs 3 hours per hectare, barley 2 hours and oats 4 hours. A contract requires at least 20 hectares of wheat. Profit per hectare is £400 for wheat, £300 for barley and £350 for oats. The farmer wishes to maximise the total profit PP (in pounds).
    (a)
    (i) Formulate this as a linear programming problem.
    (ii) If every constraint is written as an equation, state how many slack, surplus and artificial variables are needed.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: (i) maximise P=400x+300y+350zP=400x+300y+350z
    B1: (i)
    x+y+z≤80x+y+z\le80
    B1: (i)
    3x+2y+4z≤2003x+2y+4z\le200
    B1: (i)
    x≥20x\ge20
    B1: (i)
    y≥0y\ge0, z≥0z\ge0
    B1: (ii) two slack, one surplus, one artificial variable

    Accept:
    x≥0x\ge0 also stated
    Do not accept: an artificial variable for each constraint
    (b)
    The farmer proposes planting x=30x=30, y=20y=20 and z=10z=10.
    (i) Show that this plan is feasible by finding the values of the slack variables
    s1s_1 (land) and s2s_2 (labour) and the surplus variable s3s_3 (wheat).
    (ii) Find the profit.

    (iii) Interpret
    s1s_1, s2s_2 and s3s_3 in context.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: (i) substitutes into the land and labour constraints, e.g. 30+20+10=6030+20+10=60 and 90+40+40=17090+40+40=170
    A1: (i)
    s1=20s_1=20 and s2=30s_2=30
    A1: (i)
    s3=30−20=10s_3=30-20=10
    B1: (i) all slack and surplus values are non-negative, so the plan is feasible

    B1: (ii)
    P=12000+6000+3500=21500P=12000+6000+3500=21500, i.e. £21 500
    B1: (iii) 20 hectares unused, 30 labour hours unused, wheat is 10 hectares above the contract minimum

    Accept: £21500

    Total for question 4: 12 marks

End of questions

Subtopic tests