Skip to the worksheet
Revision Library
Choose a subject

Decision: Linear Programming and Critical Path Depth - Worksheets, Questions and Revision

24 original exam-style questions - 12 pages of questions with a full mark scheme - free printable PDF.

This topic is chapter 6 of A Level Further Maths Decision Topic Workbook and chapter 4 of A Level Further Maths 10-Minute Tests 2.

Revision Library
revisionlibrary.co.uk
A-Level · Further Decision Mathematics (Linear Programming and Critical Path Depth)

4.6 Decision: Linear Programming and Critical Path Depth

EDEXCEL 9FM0 · Calculator allowed · about 230 minutes
Total Marks
Name: _______________________________    Date: ____ / ____ / ______
Answer ALL questions. Show all your working.
1
Nishat runs a small stall, 'Kettle and Bean', selling gift hampers at a farmers' market each week. She makes two types of hamper: a Cosy hamper and a Harvest hamper. Let x be the number of Cosy hampers made per week and y be the number of Harvest hampers made per week.
Each Cosy hamper uses 3 jars of jam and 2 metres of ribbon. Each Harvest hamper uses 5 jars of jam and 1 metre of ribbon.
Each week, Nishat has 45 jars of jam and 20 metres of ribbon available.
She has a standing arrangement with a local bed and breakfast to supply at least 4 Harvest hampers every week.
The profit is £15 per Cosy hamper and £18 per Harvest hamper.
(a)Write down the objective function for the weekly profit P, stating whether it should be maximised or minimised.(1)
(b)Write down the constraints arising from the jam and from the ribbon.(2)
(c)Write down the constraint arising from the standing arrangement with the bed and breakfast.(1)
(d)State the further restriction(s) that apply to x and y, explaining briefly why each is necessary.(2)
(e)State, with a reason, whether (x, y) = (5, 3) is a feasible weekly production plan for Nishat.(2)
(Total for Question 1 is 8 marks)
2
Ridgeway Construction is considering ways to speed up a building project made up of two independent chains of activities converging at completion. Chain 1 comprises activity A (normal duration 6 days) followed by activity B (normal duration 4 days). Chain 2 comprises a single activity C (normal duration 8 days). The table below gives, for each activity, the cost per day of crashing (reducing its duration) and the maximum number of days by which it can be crashed.
ActivityNormal duration (days)Cost per day to crashMaximum crash (days)
A6£802
B4£1501
C8£603
(a)State the length of each chain, and hence identify the critical path and the project's normal completion time.(2)
(b)Explain why, in order to reduce the project's completion time by up to 2 days, activity A should be crashed rather than activity B, and calculate the total extra cost of crashing the project by 2 days.(3)
(c)Explain why, once activity A has been crashed by its full 2 days, both chains become critical, and state the two critical paths.(2)
(d)Hence explain why any further reduction in the project's completion time requires crashing both chains simultaneously, and calculate the extra cost of reducing the project's completion time by a further 1 day (to 7 days).(3)
(Total for Question 2 is 10 marks)
3
This question continues the Ridgeway Construction crashing problem described in Question 2.
(a)Calculate the total extra cost of reducing the project's completion time from its normal 10 days down to 7 days.(2)
(b)Determine the shortest possible completion time for the project achievable by crashing, explaining your reasoning.(4)
(c)Comment on whether it would ever be worthwhile for Ridgeway Construction to crash activity C by more than 1 day, given the cost-slopes involved.(2)
(Total for Question 3 is 8 marks)
4
Discuss two limitations of using linear programming to model a real business decision (such as Nishat's hamper production in Questions 1, 9 and 17), and two limitations of using critical path analysis to model a real project (such as the village hall renovation in Questions 23 and 24). Your answer should refer to specific features of the mathematical models used in this worksheet.
(Total for Question 4 is 6 marks)
5
A bakery makes x batches of rolls and y batches of loaves each day. The constraints are 4x + 3y ≤ 61, 3x + y ≤ 37, x ≥ 0 and y ≥ 0. The profit, in hundreds of pounds, is P = x + 5y, and the profit is to be maximised.
(a)Draw the feasible region and find the coordinates of each of its vertices.(3)
(b)Evaluate P at each vertex and hence find the maximum profit and the values of x and y which give it.(3)
(Total for Question 5 is 6 marks)
6
A bakery makes x batches of rolls and y batches of loaves each day. The constraints are 4x + y ≤ 47, x + 3y ≤ 31, x ≥ 0 and y ≥ 0. The profit, in hundreds of pounds, is P = 6x + 6y, and the profit is to be maximised.
(a)Draw the feasible region and find the coordinates of each of its vertices.(3)
(b)Evaluate P at each vertex and hence find the maximum profit and the values of x and y which give it.(3)
(Total for Question 6 is 6 marks)
7
A bakery makes x batches of rolls and y batches of loaves each day. The constraints are x + y ≤ 15, 3x + 4y ≤ 57, x ≥ 0 and y ≥ 0. The profit, in hundreds of pounds, is P = 5x + 4y, and the profit is to be maximised.
(a)Draw the feasible region and find the coordinates of each of its vertices.(3)
(b)Evaluate P at each vertex and hence find the maximum profit and the values of x and y which give it.(3)
(Total for Question 7 is 6 marks)
8
A project consists of activities A, B, C, D, E, F, G, H, I. Each activity is listed with its duration in days and the activities that must be completed before it can start: A (duration 5, after none); B (duration 6, after A); C (duration 5, after A); D (duration 5, after A); E (duration 2, after D); F (duration 7, after D); G (duration 7, after B); H (duration 6, after G); I (duration 5, after B).
(a)Carry out a forward pass to find the earliest start time of each activity, and state the minimum completion time of the project.(3)
(b)Carry out a backward pass and hence find the critical activities.(3)
(c)Find the total float of activity C.(2)
(d)Find a lower bound for the number of workers needed to complete the project in the minimum time, if each activity needs one worker.(2)
(Total for Question 8 is 10 marks)
9
This question uses Nishat's hamper model from Question 1: maximise P = 15x + 18y subject to
3x + 5y ≤ 45 (jam)
2x + y ≤ 20 (ribbon)
y ≥ 4 (standing arrangement)
x ≥ 0
0 2 4 6 8 10 12 14 16 0 2 4 6 8 10 12 x y
(a)On the grid provided, draw the lines 3x + 5y = 45 and 2x + y = 20, and the line y = 4, then shade the feasible region satisfying all the constraints.(4)
(b)Find the coordinates of each vertex of the feasible region.(4)
(c)Use the vertex method to find the values of x and y that maximise the weekly profit P, treating x and y as continuous, and state this maximum profit.(2)
(Total for Question 9 is 10 marks)
10
A farmer plants x hectares of wheat and y hectares of barley. The constraints are 4x + 2y ≤ 38, x + y ≤ 13, x ≥ 0 and y ≥ 0. The profit, in hundreds of pounds, is P = x + 2y, and the profit is to be maximised.
(a)Draw the feasible region and find the coordinates of each of its vertices.(3)
(b)Evaluate P at each vertex and hence find the maximum profit and the values of x and y which give it.(3)
(Total for Question 10 is 6 marks)
11
A factory makes x units of product P and y units of product Q each week. The constraints are 4x + 3y ≤ 62, 2x + 4y ≤ 56, x ≥ 0 and y ≥ 0. The profit, in hundreds of pounds, is P = 4x + 4y, and the profit is to be maximised.
(a)Draw the feasible region and find the coordinates of each of its vertices.(3)
(b)Evaluate P at each vertex and hence find the maximum profit and the values of x and y which give it.(3)
(Total for Question 11 is 6 marks)
12
A factory makes x units of product P and y units of product Q each week. The constraints are 2x + 3y ≤ 44, x + 2y ≤ 28, x ≥ 0 and y ≥ 0. The profit, in hundreds of pounds, is P = 3x + 3y, and the profit is to be maximised.
(a)Draw the feasible region and find the coordinates of each of its vertices.(3)
(b)Evaluate P at each vertex and hence find the maximum profit and the values of x and y which give it.(3)
(Total for Question 12 is 6 marks)
13
A bakery makes x batches of rolls and y batches of loaves each day. The constraints are x + 3y ≤ 32, x + y ≤ 16, x ≥ 0 and y ≥ 0. The profit, in hundreds of pounds, is P = 5x + 6y, and the profit is to be maximised.
(a)Draw the feasible region and find the coordinates of each of its vertices.(3)
(b)Evaluate P at each vertex and hence find the maximum profit and the values of x and y which give it.(3)
(Total for Question 13 is 6 marks)
14
A factory makes x units of product P and y units of product Q each week. The constraints are x + 4y ≤ 30, 2x + 2y ≤ 30, x ≥ 0 and y ≥ 0. The profit, in hundreds of pounds, is P = 3x + 4y, and the profit is to be maximised.
(a)Draw the feasible region and find the coordinates of each of its vertices.(3)
(b)Evaluate P at each vertex and hence find the maximum profit and the values of x and y which give it.(3)
(Total for Question 14 is 6 marks)
15
A bakery makes x batches of rolls and y batches of loaves each day. The constraints are 4x + 4y ≤ 76, 2x + 4y ≤ 54, x ≥ 0 and y ≥ 0. The profit, in hundreds of pounds, is P = 4x + y, and the profit is to be maximised.
(a)Draw the feasible region and find the coordinates of each of its vertices.(3)
(b)Evaluate P at each vertex and hence find the maximum profit and the values of x and y which give it.(3)
(Total for Question 15 is 6 marks)
16
A farmer plants x hectares of wheat and y hectares of barley. The constraints are x + 3y ≤ 30, 3x + 2y ≤ 48, x ≥ 0 and y ≥ 0. The profit, in hundreds of pounds, is P = 6x + y, and the profit is to be maximised.
(a)Draw the feasible region and find the coordinates of each of its vertices.(3)
(b)Evaluate P at each vertex and hence find the maximum profit and the values of x and y which give it.(3)
(Total for Question 16 is 6 marks)
17
This question continues Nishat's hamper problem from Questions 1 and 9. Remember that x and y must be non-negative integers.
(a)Explain why the solution found in Question 9(c) is not a valid production plan for Nishat.(1)
(b)A colleague suggests rounding the values found in Question 9(c) down to the nearest integer, giving (x, y) = (7, 4). Show that (7, 4) is a feasible solution to the constraints, and calculate the resulting weekly profit.(3)
(c)By checking all feasible integer points with x from 6 to 9 and y from 4 to 5, determine the true optimal integer solution and state the resulting maximum weekly profit. Comment on whether simply rounding down the continuous solution gives the best integer solution.(4)
(Total for Question 17 is 8 marks)
18
A factory makes x units of product P and y units of product Q each week. The constraints are 3x + y ≤ 12, 2x + 4y ≤ 18, x ≥ 0 and y ≥ 0. The profit, in hundreds of pounds, is P = 4x + 6y, and the profit is to be maximised.
(a)Draw the feasible region and find the coordinates of each of its vertices.(3)
(b)Evaluate P at each vertex and hence find the maximum profit and the values of x and y which give it.(3)
(Total for Question 18 is 6 marks)
19
Anders Print Shop makes two types of banner each day: Standard (x) and Premium (y). The linear programming problem is to maximise P = 4x + 3y subject to:
2x + y ≤ 18 (machine hours)
2x + 3y ≤ 30 (finishing hours)
x ≥ 0, y ≥ 0
(a)Introduce slack variables s1 (for machine hours) and s2 (for finishing hours) to write the constraints as equations suitable for the simplex method.(2)
(b)Write down the initial simplex tableau, and state the initial basic feasible solution.(3)
(c)Using the most negative coefficient in the objective row to choose the entering variable, perform one pivot, and hence write down the new simplex tableau. State the new basic feasible solution.(4)
(d)State, with a reason, whether the tableau found in part (c) represents the optimal solution. If not, state which variable should enter the basis at the next pivot.(1)
(Total for Question 19 is 10 marks)
20
This question refers back to Nishat's hamper problem (Questions 1, 9 and 17) and Anders Print Shop's simplex tableau (Question 19).
(a)Using the integer solution found in Question 17(c), calculate the number of jars of jam and metres of ribbon left over (unused) each week. Interpret your answer for the ribbon in context.(3)
(b)In the simplex method used in Question 19, explain what it means for a slack variable to take the value zero at a solution.(2)
(Total for Question 20 is 5 marks)
21
Oakfield Landscapes is planning a garden makeover project. The table below shows the activities involved, their duration in days, and their immediate predecessors.
ActivityTaskDuration (days)Immediate predecessors
AClear the site4-
BOrder and deliver paving slabs3-
CLevel the sub-base5A
DLay the drainage pipe2A
ELay the paving slabs6B
FBuild the raised flower bed3C, D
GPlant the borders4D, E
HFinal clean and handover2F, G
diagram space
(a)Explain why the activity-on-arc network for this project requires exactly two dummy activities.(3)
(b)Draw the activity-on-arc network for the project, labelling events with circled numbers and showing both dummy activities as dashed arrows.(5)
(Total for Question 21 is 8 marks)
22
The Oakfield Landscapes project is as described in Question 21, using the network you drew in that question.
(a)Carry out a forward pass through the network to find the earliest start time (EST) and earliest finish time (EFT) of each activity, and state the minimum time in which the project can be completed.(5)
(b)Carry out a backward pass through the network to find the latest start time (LST) and latest finish time (LFT) of each activity, and hence state the critical path for the project.(4)
(c)Calculate the total float of each non-critical activity (A, C, D, F).(3)
(Total for Question 22 is 12 marks)
23
A village hall renovation project has five activities, described in the table below. The 'workers required' column states how many workers must be available throughout each activity's duration.
ActivityDuration (days)Immediate predecessorsWorkers required
J3-4
K2-3
L4J2
M1K1
N2L, M2
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 time (days) number of workers
(a)Show that the critical path for this project is J - L - N, with a project duration of 9 days, and state the total float of activities K and M.(4)
(b)Construct a resource histogram showing the number of workers required on each day of the project, assuming every activity starts at its earliest start time. State the peak number of workers required, and the interval in which this peak occurs.(3)
(c)By delaying activity K (and, as a consequence, activity M) to start as late as possible within its float, show that the peak number of workers required can be reduced, and state the new peak.(2)
(Total for Question 23 is 9 marks)
24
This question continues the village hall renovation project described in Question 23.
(a)The site manager has only 5 workers available on any given day. Explain whether the project can still be completed in the original 9 days if all activities start at their earliest start times.(3)
(b)Using the revised schedule found in Question 23(c), determine whether the project can now be completed within 9 days using only 5 workers, justifying your answer.(4)
(Total for Question 24 is 7 marks)
Mark scheme · 4.6 Decision: Linear Programming and Critical Path Depth

Question 1

  • (a) maximise P = 15x + 18y oeB1
  • (a) Answer: Maximise P = 15x + 18y.
  • (b) 3x + 5y ≤ 45 [jam]B1
  • (b) 2x + y ≤ 20 [ribbon]B1
  • (b) Answer: 3x + 5y ≤ 45 (jam); 2x + y ≤ 20 (ribbon).
  • (c) y ≥ 4B1
  • (c) Answer: y ≥ 4.
  • (d) x ≥ 0 (and x, y integers)B1
  • (d) reason: it is not possible to make a negative or fractional number of hampers (oe)B1
  • (d) Answer: x ≥ 0, and x, y must both be integers, since Nishat cannot make a negative or fractional number of hampers.
  • (e) check (5,3) against all constraints: jam 3(5)+5(3)=30≤45 ok; ribbon 2(5)+3=13≤20 ok; but y=3M1
  • (e) not feasible, since y=3 < 4, so the standing arrangement constraint is violated caoA1
  • (e) Answer: Not feasible: although the jam and ribbon constraints are satisfied, y = 3 is less than 4, so it fails the standing arrangement constraint.

Question 2

  • (a) chain 1 (A-B) = 6+4=10 days, chain 2 (C) = 8 daysB1
  • (a) critical path is chain 1 (A-B), since 10 > 8; normal project completion time = 10 daysB1
  • (a) Answer: Chain 1 = 10 days, chain 2 = 8 days. Critical path: A-B, normal completion time = 10 days.
  • (b) A is cheaper to crash (£80/day) than B (£150/day), and only activities on the critical chain (chain 1) can reduce the project's completion time, since crashing C (chain 2) alone would not shorten the project while chain 1 remains longer (oe)B1
  • (b) crash A by its full 2 days, cost = 2 x 80 = £160M1
  • (b) total extra cost = £160, giving a new project duration of 10 - 2 = 8 daysA1
  • (b) Answer: Crash A by 2 days (cheaper than B, and on the critical chain); extra cost = £160; new project duration = 8 days.
  • (c) chain 1 is now 6-2+4=8 days, exactly equal to chain 2's 8 days (oe)B1
  • (c) both chain 1 (A-B) and chain 2 (C) are now critical, each of length 8 daysB1
  • (c) Answer: Chain 1 is now 8 days, equal to chain 2 (8 days), so both A-B and C are now critical paths.
  • (d) since both chains are now critical at 8 days, shortening only one chain would leave the other chain still at 8 days, so the project's completion time would not reduce (oe)B1
  • (d) crash B by its remaining 1 day (only option left on chain 1, cost £150) and crash C by 1 day (cost £60), simultaneouslyM1
  • (d) extra cost for this further 1-day reduction = 150 + 60 = £210A1
  • (d) Answer: Both chains must be crashed together; extra cost for the further 1-day reduction = £210.

Question 3

  • (a) method: £160 (first 2 days, crashing A) + £210 (next 1 day, crashing B and C together)B1
  • (a) total extra cost = £370B1
  • (a) Answer: Total extra cost = £370.
  • (b) maximum total crash on chain 1 = 2 (A) + 1 (B) = 3 days, giving chain 1 minimum length = 10 - 3 = 7 daysM1
  • (b) maximum total crash on chain 2 = 3 days (C), giving chain 2 minimum length = 8 - 3 = 5 daysM1
  • (b) shortest achievable project duration = 7 days caoA1
  • (b) explain that chain 1 cannot be reduced below 7 days regardless of how much chain 2 is crashed, since the project duration is always the length of the longer chain (oe)B1
  • (b) Answer: Shortest possible project duration = 7 days, limited by chain 1's total crash capacity.
  • (c) no: crashing C beyond the 1 day needed to keep pace with chain 1 would add cost (£60/day) without reducing the overall project duration, since this is capped by chain 1's floor of 7 days (oe)B1
  • (c) credit for a clear justification referencing the cost-slope of C and the binding nature of chain 1's crash limit (e.g. crashing C's remaining 2 days would cost a further £120 for no benefit)B1
  • (c) Answer: No; crashing C further than 1 day would cost more (£60/day) with no reduction in the overall project duration, since chain 1 already limits the project to a minimum of 7 days.

Question 4

  • Level 0 No relevant comments made, or the response fails to address the question.0
  • Level 1 A basic, generic limitation is stated for at most one of the two models, with little reference to the specific contexts used in this worksheet.1-2
  • Level 2 At least one clear, well-explained limitation is given for each model (linear programming and critical path analysis), each linked to a specific feature of the models used in this worksheet, but the discussion may be incomplete or one-sided.3-4
  • Level 3 At least two distinct, clearly explained limitations are given for each model (four in total), each explicitly linked to the specific contexts used in this worksheet (for example Nishat's hampers, or the village hall project), with correct terminology used throughout.5-6
  • Indicative content:
    • Linear programming assumes all relationships (resource use, profit) are linear, so resources and profit scale exactly in proportion to the quantity produced; in reality there may be bulk discounts, diminishing returns, or fixed setup costs that make this untrue.
    • As shown in Question 17, linear programming's continuous graphical solution can be non-integer; naive rounding (as in Question 17(b)) does not always give the best integer solution, so a separate integer-programming search is needed for decisions that must be whole numbers.
    • Linear programming assumes all data (resource availability, profit per unit, demand constraints) are known with certainty and fixed in advance; in reality Nishat's demand, ingredient costs, or available jam and ribbon could fluctuate from week to week.
    • Critical path analysis assumes activity durations are fixed and known in advance; in reality durations can vary (for example due to weather or late deliveries), which could change which activities are critical and invalidate the schedule found.
    • The resource levelling used in Questions 23 and 24 assumes workers are freely interchangeable between activities and can be reallocated instantly; in reality workers may need particular skills for particular activities, limiting how freely float can really be used.
    • The critical path model assumes precedence relationships between activities are fixed and fully known in advance, and that activities cannot be split or interrupted once started; missing, wrong, or changing precedence data would invalidate the whole analysis.

Question 5

  • (a) plots both constraint lines and shades the unwanted regionM1
  • (a) finds the intercepts with the axes and the intersection of the two linesM1
  • (a) vertices: (0, 0), (0, 61/3), (10, 7), (37/3, 0)A1
  • (a) Answer: (0, 0), (0, 61/3), (10, 7), (37/3, 0)
  • (b) evaluates P at each vertexM1
  • (b) values: 0, 305/3, 45, 37/3A1
  • (b) maximum P = 305/3 at (0, 61/3)A1
  • (b) Answer: P = 305/3 at (0, 61/3)

Question 6

  • (a) plots both constraint lines and shades the unwanted regionM1
  • (a) finds the intercepts with the axes and the intersection of the two linesM1
  • (a) vertices: (0, 0), (0, 31/3), (10, 7), (47/4, 0)A1
  • (a) Answer: (0, 0), (0, 31/3), (10, 7), (47/4, 0)
  • (b) evaluates P at each vertexM1
  • (b) values: 0, 62, 102, 141/2A1
  • (b) maximum P = 102 at (10, 7)A1
  • (b) Answer: P = 102 at (10, 7)

Question 7

  • (a) plots both constraint lines and shades the unwanted regionM1
  • (a) finds the intercepts with the axes and the intersection of the two linesM1
  • (a) vertices: (0, 0), (0, 57/4), (3, 12), (15, 0)A1
  • (a) Answer: (0, 0), (0, 57/4), (3, 12), (15, 0)
  • (b) evaluates P at each vertexM1
  • (b) values: 0, 57, 63, 75A1
  • (b) maximum P = 75 at (15, 0)A1
  • (b) Answer: P = 75 at (15, 0)

Question 8

  • (a) earliest start = latest earliest finish of the immediate predecessorsM1
  • (a) earliest starts: A 0, B 5, C 5, D 5, E 10, F 10, G 11, H 18, I 11A1
  • (a) minimum completion time = 24 daysA1
  • (a) Answer: 24 days
  • (b) latest finish = smallest latest start of the successorsM1
  • (b) latest finishes: A 5, B 11, C 24, D 17, E 24, F 24, G 18, H 24, I 24A1
  • (b) critical activities (zero float): A, B, G, HA1
  • (b) Answer: A, B, G, H
  • (c) total float = latest finish - earliest start - durationM1
  • (c) 24 - 5 - 5 = 14 daysA1
  • (c) Answer: 14 days
  • (d) total duration of all activities = 48M1
  • (d) 48/24 = 2.00, so at least 2 workersA1
  • (d) Answer: 2

Question 9

  • (a) line 3x + 5y = 45 correctly drawn through (0,9) and (15,0)B1
  • (a) line 2x + y = 20 correctly drawn through (0,20) and (10,0)B1
  • (a) line y = 4 drawn, and x ≥ 0 respectedB1
  • (a) correct feasible region identified and unambiguously indicated (shaded or labelled R), bounded by all three lines and the y-axisB1
  • (a) Answer: Feasible region is the quadrilateral with vertices (0,4), (0,9), (55/7, 30/7), (8,4).
  • (b) (0,4), found from x=0 and y=4B1
  • (b) (0,9), found from x=0 and 3x+5y=45B1
  • (b) solving 3x + 5y = 45 and 2x + y = 20 simultaneouslyM1
  • (b) (55/7, 30/7) [awrt (7.86, 4.29)] and (8,4), found from y=4 and 2x+y=20, both caoA1
  • (b) Answer: (0,4), (0,9), (55/7, 30/7), (8,4).
  • (c) evaluate P = 15x + 18y at all four verticesM1
  • (c) maximum at x = 55/7, y = 30/7, giving P = 195 cao, greater than at the other three verticesA1
  • (c) Answer: x = 55/7 (awrt 7.86), y = 30/7 (awrt 4.29), maximum profit (continuous) = £195.

Question 10

  • (a) plots both constraint lines and shades the unwanted regionM1
  • (a) finds the intercepts with the axes and the intersection of the two linesM1
  • (a) vertices: (0, 0), (0, 13), (6, 7), (19/2, 0)A1
  • (a) Answer: (0, 0), (0, 13), (6, 7), (19/2, 0)
  • (b) evaluates P at each vertexM1
  • (b) values: 0, 26, 20, 19/2A1
  • (b) maximum P = 26 at (0, 13)A1
  • (b) Answer: P = 26 at (0, 13)

Question 11

  • (a) plots both constraint lines and shades the unwanted regionM1
  • (a) finds the intercepts with the axes and the intersection of the two linesM1
  • (a) vertices: (0, 0), (0, 14), (8, 10), (31/2, 0)A1
  • (a) Answer: (0, 0), (0, 14), (8, 10), (31/2, 0)
  • (b) evaluates P at each vertexM1
  • (b) values: 0, 56, 72, 62A1
  • (b) maximum P = 72 at (8, 10)A1
  • (b) Answer: P = 72 at (8, 10)

Question 12

  • (a) plots both constraint lines and shades the unwanted regionM1
  • (a) finds the intercepts with the axes and the intersection of the two linesM1
  • (a) vertices: (0, 0), (0, 14), (4, 12), (22, 0)A1
  • (a) Answer: (0, 0), (0, 14), (4, 12), (22, 0)
  • (b) evaluates P at each vertexM1
  • (b) values: 0, 42, 48, 66A1
  • (b) maximum P = 66 at (22, 0)A1
  • (b) Answer: P = 66 at (22, 0)

Question 13

  • (a) plots both constraint lines and shades the unwanted regionM1
  • (a) finds the intercepts with the axes and the intersection of the two linesM1
  • (a) vertices: (0, 0), (0, 32/3), (8, 8), (16, 0)A1
  • (a) Answer: (0, 0), (0, 32/3), (8, 8), (16, 0)
  • (b) evaluates P at each vertexM1
  • (b) values: 0, 64, 88, 80A1
  • (b) maximum P = 88 at (8, 8)A1
  • (b) Answer: P = 88 at (8, 8)

Question 14

  • (a) plots both constraint lines and shades the unwanted regionM1
  • (a) finds the intercepts with the axes and the intersection of the two linesM1
  • (a) vertices: (0, 0), (0, 15/2), (10, 5), (15, 0)A1
  • (a) Answer: (0, 0), (0, 15/2), (10, 5), (15, 0)
  • (b) evaluates P at each vertexM1
  • (b) values: 0, 30, 50, 45A1
  • (b) maximum P = 50 at (10, 5)A1
  • (b) Answer: P = 50 at (10, 5)

Question 15

  • (a) plots both constraint lines and shades the unwanted regionM1
  • (a) finds the intercepts with the axes and the intersection of the two linesM1
  • (a) vertices: (0, 0), (0, 27/2), (11, 8), (19, 0)A1
  • (a) Answer: (0, 0), (0, 27/2), (11, 8), (19, 0)
  • (b) evaluates P at each vertexM1
  • (b) values: 0, 27/2, 52, 76A1
  • (b) maximum P = 76 at (19, 0)A1
  • (b) Answer: P = 76 at (19, 0)

Question 16

  • (a) plots both constraint lines and shades the unwanted regionM1
  • (a) finds the intercepts with the axes and the intersection of the two linesM1
  • (a) vertices: (0, 0), (0, 10), (12, 6), (16, 0)A1
  • (a) Answer: (0, 0), (0, 10), (12, 6), (16, 0)
  • (b) evaluates P at each vertexM1
  • (b) values: 0, 10, 78, 96A1
  • (b) maximum P = 96 at (16, 0)A1
  • (b) Answer: P = 96 at (16, 0)

Question 17

  • (a) x and y must be whole numbers of hampers, but 55/7 and 30/7 are not integers (oe)B1
  • (a) Answer: x and y must be whole numbers of hampers, but the continuous solution 55/7, 30/7 is not an integer point.
  • (b) check (7,4) against all constraints: jam 3(7)+5(4)=41≤45; ribbon 2(7)+4=18≤20; y=4≥4M1
  • (b) all three constraints satisfied, so (7,4) is feasibleA1
  • (b) profit P = 15(7) + 18(4) = £177B1
  • (b) Answer: (7,4) is feasible (jam 41≤45, ribbon 18≤20, y=4≥4); weekly profit = £177.
  • (c) systematically test the remaining candidates: (7,5): 3(7)+5(5)=46>45 infeasible; (8,4): 3(8)+5(4)=44≤45 and 2(8)+4=20≤20, feasible; (8,5): 3(8)+5(5)=49>45 infeasible; (9,4): 2(9)+4=22>20 infeasibleM1
  • (c) true optimal integer solution is (8,4), with profit P = 15(8)+18(4) = £192 caoA1
  • (c) 192 correctly identified as greater than the 177 found by rounding down in part (b)A1
  • (c) conclude that rounding down the continuous optimum does not necessarily give the best integer solution; here it gives a lower profit (177) than the true integer optimum (192) found by checking all nearby feasible points (oe)B1
  • (c) Answer: Optimal integer solution: x=8, y=4, maximum weekly profit = £192. Rounding down (7,4) gives only £177, so naive rounding does not give the best integer solution.

Question 18

  • (a) plots both constraint lines and shades the unwanted regionM1
  • (a) finds the intercepts with the axes and the intersection of the two linesM1
  • (a) vertices: (0, 0), (0, 9/2), (3, 3), (4, 0)A1
  • (a) Answer: (0, 0), (0, 9/2), (3, 3), (4, 0)
  • (b) evaluates P at each vertexM1
  • (b) values: 0, 27, 30, 16A1
  • (b) maximum P = 30 at (3, 3)A1
  • (b) Answer: P = 30 at (3, 3)

Question 19

  • (a) 2x + y + s1 = 18B1
  • (a) 2x + 3y + s2 = 30B1
  • (a) Answer: 2x + y + s1 = 18; 2x + 3y + s2 = 30.
  • (b) row 1: x=2, y=1, s1=1, s2=0, RHS=18; row 2: x=2, y=3, s1=0, s2=1, RHS=30B1
  • (b) objective row: P - 4x - 3y = 0 (i.e. x=-4, y=-3, s1=0, s2=0, RHS=0)B1
  • (b) initial basic feasible solution x=0, y=0, s1=18, s2=30, P=0B1
  • (b) Answer: Tableau rows: [x=2,y=1,s1=1,s2=0 | 18], [x=2,y=3,s1=0,s2=1 | 30], objective [x=-4,y=-3,s1=0,s2=0 | 0]. Initial BFS: x=0, y=0, s1=18, s2=30, P=0.
  • (c) identify x as the entering variable, since -4 is more negative than -3M1
  • (c) ratio test: 18/2=9 and 30/2=15; minimum ratio 9, so row 1 (with s1 basic) is the pivot rowM1
  • (c) new row 1 (divide by 2): x + 0.5y + 0.5s1 = 9; new row 2 (subtract 2 x new row 1 from old row 2): 2y - s1 + s2 = 12; new objective row (add 4 x new row 1 to old objective row): P - y + 2s1 = 36A1
  • (c) new basic feasible solution x=9, y=0, s1=0, s2=12, P=36 caoA1
  • (c) Answer: New tableau: row1 x+0.5y+0.5s1=9; row2 2y-s1+s2=12; objective P-y+2s1=36. New BFS: x=9, y=0, s1=0, s2=12, P=36.
  • (d) not optimal, since the objective row still contains a negative coefficient (-1, under y); y should enter the basis nextB1
  • (d) Answer: Not optimal (the objective row has a negative coefficient, -1, under y); y should enter next.

Question 20

  • (a) jam used = 3(8)+5(4) = 44, so leftover = 45 - 44 = 1 jar; ribbon used = 2(8)+4 = 20, so leftover = 20 - 20 = 0 mM1
  • (a) 1 jar of jam and 0 m of ribbon left overA1
  • (a) interpretation: the ribbon constraint is exactly met (binding), so Nishat uses all her available ribbon, whereas she has 1 spare jar of jam each week (oe)B1
  • (a) Answer: 1 jar of jam left over; 0 m of ribbon left over (ribbon is fully used).
  • (b) it means the corresponding resource (constraint) is used up completely, i.e. the constraint is binding at that solution (oe)B1
  • (b) applied to Question 19(c): s1=0 means all 18 machine hours are used, while s2=12 (not zero) means 12 finishing hours remain unused (oe)B1
  • (b) Answer: A zero slack variable means that resource's constraint is exactly met (binding). In Question 19(c), s1=0 means all machine hours are used, while s2=12 means 12 finishing hours are still spare.

Question 21

  • (a) recognise that D is a predecessor of both F and G, while C is a predecessor of F only and E is a predecessor of G only (oe)M1
  • (a) explain that a dummy activity is needed to carry D's completion forward into the merge event with C, so that F can correctly depend on both C and D (oe)A1
  • (a) explain that a second dummy activity is needed to carry D's completion forward into the (separate) merge event with E, so that G can correctly depend on both D and E, without wrongly forcing G to also wait for C (or F to wait for E); hence exactly two dummies in totalB1
  • (a) Answer: Two dummies are needed because D feeds into two different merges (with C for F, and with E for G) that must be kept logically separate; a single shared merge would wrongly force F to depend on E, or G to depend on C.
  • (b) single start event (event 1), with A and B both leaving itB1
  • (b) C and D both shown leaving the event reached only by A (event 2), since both depend on A aloneB1
  • (b) D shown ending at its own event (event 4, say), with a dummy (dashed) from event 4 into the merge event for F (event 5, also reached directly by C)B1
  • (b) a second dummy (dashed) shown from event 4 into a separate merge event for G (event 6, also reached directly by E, which leaves the event reached by B)B1
  • (b) F (from event 5) and G (from event 6) both shown converging at a single event (event 7), with H leaving event 7 to a single end event (event 8), network fully connected with no redundant or crossing dummiesB1
  • (b) Answer: Network: 1-A(4)->2; 1-B(3)->3; 2-C(5)->5; 2-D(2)->4; 4-dummy(0)->5; 4-dummy(0)->6; 3-E(6)->6; 5-F(3)->7; 6-G(4)->7; 7-H(2)->8.

Question 22

  • (a) correct method applied at each merge event (event 5 = max of EFT(C), EFT(D); event 6 = max of EFT(D), EFT(E); event 7 = max of EFT(F), EFT(G))M1
  • (a) EST/EFT correct for A(0,4), B(0,3), C(4,9), D(4,6)A1
  • (a) EST/EFT correct for E(3,9), F(9,12), G(9,13)A1
  • (a) EST/EFT correct for H(13,15), all eight activities correctA1
  • (a) minimum project completion time = 15 days caoB1
  • (a) Answer: A(0,4) B(0,3) C(4,9) D(4,6) E(3,9) F(9,12) G(9,13) H(13,15). Minimum completion time = 15 days.
  • (b) correct method applied at each branch event (event 4 = min of LST via event 5, LST via event 6; event 2 = min of LST(C), LST(D))M1
  • (b) LST/LFT correct for H(13,15), F(10,13), G(9,13), D(7,9)A1
  • (b) LST/LFT correct for E(3,9), C(5,10), B(0,3), A(1,5)A1
  • (b) critical path B - E - G - H, length 15 days caoB1
  • (b) Answer: H(13,15) F(10,13) G(9,13) D(7,9) E(3,9) C(5,10) B(0,3) A(1,5). Critical path: B - E - G - H, length 15 days.
  • (c) A = 1 day, C = 1 dayB1
  • (c) D = 3 daysB1
  • (c) F = 1 dayB1
  • (c) Answer: A: 1 day, C: 1 day, D: 3 days, F: 1 day.

Question 23

  • (a) forward pass: J(0,3), K(0,2), L(3,7), M(2,3), N(7,9)M1
  • (a) backward pass: N(7,9), L(3,7) [float 0], M(6,7) [float 4], K(4,6) [float 4], J(0,3) [float 0]A1
  • (a) critical path J - L - N confirmed, since J and L both have total float 0, length 3+4+2=9 daysB1
  • (a) total float of K = 4 days, total float of M = 4 daysB1
  • (a) Answer: Critical path J - L - N, project duration 9 days; total float of K = 4 days, total float of M = 4 days.
  • (b) correct day-by-day totals at earliest start times: [0,2) J+K=7; [2,3) J+M=5; [3,7) L=2; [7,9) N=2M1
  • (b) peak = 7 workersA1
  • (b) peak occurs during days 0 to 2 (when J and K overlap)A1
  • (b) Answer: Histogram (at EST): [0,2) 7 workers; [2,3) 5 workers; [3,7) 2 workers; [7,9) 2 workers. Peak = 7 workers, during days 0 to 2.
  • (c) reschedule K to start at its LST=4, occupying [4,6); M then starts at EST=6 (immediately after K), occupying [6,7), using up its own remaining float exactly to its LFT=7M1
  • (c) new histogram: [0,3) J=4; [3,4) L=2; [4,6) L+K=5; [6,7) L+M=3; [7,9) N=2; new peak = 5 workers caoA1
  • (c) Answer: Delaying K to [4,6) and M to [6,7) reduces the peak from 7 workers to 5 workers.

Question 24

  • (a) refer to the histogram in Question 23(b): during days 0 to 2, 7 workers are required (J and K overlapping)M1
  • (a) since 7 > 5, there are not enough workers available under the earliest-start-time scheduleA1
  • (a) conclude the project cannot proceed exactly as originally scheduled with only 5 workers; some activity (K) must be delayed within its float (oe)B1
  • (a) Answer: No: at earliest start times, 7 workers are needed on days 0 to 2, exceeding the 5 available, so K (at least) must be delayed.
  • (b) check every interval of the revised histogram against the 5-worker cap: [0,3) 4≤5; [3,4) 2≤5; [4,6) 5≤5; [6,7) 3≤5; [7,9) 2≤5M1
  • (b) every interval satisfies the 5-worker limit (with [4,6) exactly meeting it, using all 5 available workers)A1
  • (b) conclude yes, the project can still be completed in 9 days with only 5 workers, using the revised schedule from Question 23(c)A1
  • (b) note this relies on using all of K's (and hence M's) available float; no further activity could also be delayed without risking exceeding 9 days or the worker limit (oe)B1
  • (b) Answer: Yes: with K delayed to [4,6) and M to [6,7), every interval requires at most 5 workers (peak exactly 5, in [4,6)), so the project still completes in 9 days.

Mark your answers

Check answers without an account. Some answers can be checked automatically; use the mark scheme to mark the rest.

Question 1

8 marks
Did your answer earn the marks?

Question 2

10 marks
Did your answer earn the marks?

Question 3

8 marks
Did your answer earn the marks?

Question 4

6 marks
Did your answer earn the marks?

Question 5

6 marks
Did your answer earn the marks?

Question 6

6 marks
Did your answer earn the marks?

Question 7

6 marks
Did your answer earn the marks?

Question 8

10 marks
Did your answer earn the marks?

Question 9

10 marks
Did your answer earn the marks?

Question 10

6 marks
Did your answer earn the marks?

Question 11

6 marks
Did your answer earn the marks?

Question 12

6 marks
Did your answer earn the marks?

Question 13

6 marks
Did your answer earn the marks?

Question 14

6 marks
Did your answer earn the marks?

Question 15

6 marks
Did your answer earn the marks?

Question 16

6 marks
Did your answer earn the marks?

Question 17

8 marks
Did your answer earn the marks?

Question 18

6 marks
Did your answer earn the marks?

Question 19

10 marks
Did your answer earn the marks?

Question 20

5 marks
Did your answer earn the marks?

Question 21

8 marks
Did your answer earn the marks?

Question 22

12 marks
Did your answer earn the marks?

Question 23

9 marks
Did your answer earn the marks?

Question 24

7 marks
Did your answer earn the marks?
Mark my answers

Worksheets are written for Revision Library and come with a full mark scheme; a few English packs quote an out-of-copyright text, and name it on the page. Exam board names and specification codes say which qualification a pack suits: we are not affiliated with, endorsed by or approved by any exam board, and no past-paper question is reproduced here. Rights queries: hello@revisionlibrary.co.uk