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

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

Download PDF Jump to mark scheme (page 6)Read the revision guide

Next in this strand

Revision Library

revisionlibrary.co.uk

A-Level · EDEXCEL

FP.D4 Decision Maths: Critical Path Analysis and Linear Programming

EDEXCEL 9FM0 · Calculator allowed · about 130 minutes

Total Marks

Name: _______________________________ Date: ____ / ____ / ______

Answer ALL questions. Show all your working.

This question concerns the vocabulary used when analysing an activity network for a project.

(a)State what is meant by a critical activity of a project network.(1)

(b)State what is meant by the total float of an activity.(1)

(c)State what is meant by the free float of an activity.(1)

(d)State why a dummy activity may be needed when drawing an activity-on-arc network.(1)

(Total for Question 1 is 4 marks)

Priya is planning a small kitchen renovation. The table below shows the activities involved.

Activity	Task	Duration (days)	Immediate predecessors
A	Strip out the old units	2	-
B	Order the new worktop (delivery lead time)	1	-
C	First-fix the plumbing and electrics	3	A
D	Fit the new worktop	2	A, B

Figure (to be drawn): Diagram space for an activity-on-arc network with 4 events and one dummy activity (dashed arrow).

(a)Explain why a dummy activity is required when drawing the activity-on-arc network for this project.(2)

(b)Draw the activity-on-arc network for the project. Label events with circled numbers, activities with their letter and duration, and show the dummy activity as a dashed arrow.(5)

(Total for Question 2 is 7 marks)

Elmswood Community Centre is having a new meeting room extension built. The table below shows the activities involved in the project, their duration, and their immediate predecessors. Time is measured in weeks from the start of the project (Week 0).

Activity	Task	Duration (weeks)	Immediate predecessors
A	Obtain planning permission	4	-
B	Order structural steel	6	-
C	Excavate foundations	3	A
D	Lay drainage	5	A
E	Erect the steel frame	7	B
F	Pour concrete foundations	4	C
G	Build external walls	6	D, E
H	Fit windows and doors	3	F
I	Roof the extension	5	G
J	Final internal fit-out	2	H, I

(a)Complete a forward pass through the network to find the earliest start time (EST) and earliest finish time (EFT) of each activity.(4)

(b)State the minimum time in which the project can be completed.(1)

(c)Complete a backward pass through the network to find the latest start time (LST) and latest finish time (LFT) of each activity.(4)

(d)Hence determine the critical path for the project, and state its length.(2)

(e)Calculate the total float for each non-critical activity (A, C, D, F, H).(2)

(Total for Question 3 is 13 marks)

The Elmswood Community Centre extension is as described in Question 3, using your forward pass and backward pass results from that question.

(a)Calculate the free float of activity A.(1)

(b)Calculate the free float of activity D.(2)

(c)Explain, with reference to your answers to parts (a) and (b), why the free float of an activity is not always equal to its total float.(2)

(Total for Question 4 is 5 marks)

The Elmswood Community Centre extension project is as described in Question 3.

Figure (to be drawn): A blank cascade (Gantt) chart grid: horizontal time axis from 0 to at least 26 weeks, one row per activity (A to J).

(a)Using your results from Question 3, draw a cascade (Gantt) chart for the project. Represent each activity by a horizontal bar starting at its earliest start time and lasting for its duration; show the total float of each non-critical activity as a dashed extension to its bar.(5)

(b)Using your cascade chart, state the earliest week in which activity I could start, and the latest week by which activity F must finish if the project is not to be delayed.(2)

(Total for Question 5 is 7 marks)

The Elmswood Community Centre extension project is as described in Question 3.

(a)State whether activity C could be delayed (that is, its duration increased) by 8 weeks without affecting the completion date of the project. Give a reason for your answer.(2)

(b)In fact, the planning permission activity A takes 9 weeks instead of the planned 4 weeks (an increase of 5 weeks). By carrying out a new forward pass, determine the new project completion time, and state which activities now form the critical path.(4)

(Total for Question 6 is 6 marks)

Newbridge Ltd is planning a small refurbishment project. The table below shows the activities involved. Time is measured in days from the start of the project (Day 0).

Activity	Task	Duration (days)	Immediate predecessors
P	Remove the old flooring	5	-
Q	Deliver the new floor tiles	3	-
R	Install the underfloor heating	6	P
S	Lay the new floor tiles	4	P, Q
T	Fit the skirting boards	2	R, S

(a)Carry out a forward pass and a backward pass on the network. Present your results as a table showing the EST, EFT, LST and LFT of each activity.(6)

(b)A project manager claims that the critical path is P - S - T, with a completion time of 11 days. By referring to your results in part (a), verify whether this claim is correct, explaining your reasoning.(3)

(Total for Question 7 is 9 marks)

Amina runs a small business making two types of scented candle: 'Meadow' candles and 'Harbour' candles, each week. Let m be the number of Meadow candles made per week, and h be the number of Harbour candles made per week.
Each Meadow candle uses 200 g of wax and takes 15 minutes of hand-pouring time. Each Harbour candle uses 350 g of wax and takes 10 minutes of hand-pouring time.
Each week, Amina has 21 kg of wax and 20 hours of hand-pouring time available.
Market research shows Amina should make at least twice as many Meadow candles as Harbour candles.
Amina must make at least 10 Harbour candles each week to fulfil a standing order.
The profit is £3.50 per Meadow candle and £4.20 per Harbour candle.

(a)Define the decision variables m and h.(1)

(b)Write down the objective function, stating whether it should be maximised or minimised.(1)

(c)Write down all the constraints for this linear programming problem, other than the restriction found in part (d).(4)

(d)State any further restriction that applies to m and h, and explain why it is necessary.(1)

(Total for Question 8 is 7 marks)

Bexley Outdoor Furniture makes garden benches (x) and garden tables (y) each week. Each bench needs 2 units of timber and 1 hour of labour; each table needs 1 unit of timber and 3 hours of labour. Each week, 20 units of timber and 30 hours of labour are available. The profit is £40 per bench and £60 per table. Bexley wants to maximise weekly profit P = 40x + 60y, subject to the constraints:
2x + y ≤ 20 (timber)
x + 3y ≤ 30 (labour)
x ≥ 0, y ≥ 0

Figure (to be drawn): A set of axes for x (benches, 0 to 12) and y (tables, 0 to 12), with gridlines at every 1 unit, for plotting the feasible region.

(a)On the grid provided, draw the lines 2x + y = 20 and x + 3y = 30, and shade the feasible region satisfying all the constraints.(4)

(b)Find the coordinates of each vertex of the feasible region.(5)

(c)Use the vertex method to determine the number of benches and tables Bexley should make each week to maximise weekly profit, and state the maximum weekly profit.(3)

(Total for Question 9 is 12 marks)

A greenkeeper at Fenwick Rugby Club mixes two fertilisers, GrowFast (f bags) and RootBoost (r bags), to treat the pitch. Each bag of GrowFast supplies 2 units of nitrogen and 1 unit of potash. Each bag of RootBoost supplies 1 unit of nitrogen and 3 units of potash. The pitch needs at least 10 units of nitrogen and at least 15 units of potash. GrowFast costs £12 per bag and RootBoost costs £9 per bag. The greenkeeper wants to minimise the total cost C = 12f + 9r, subject to the constraints:
2f + r ≥ 10 (nitrogen)
f + 3r ≥ 15 (potash)
f ≥ 0, r ≥ 0

Figure (to be drawn): A set of axes for f (GrowFast bags, 0 to 16) and r (RootBoost bags, 0 to 12), with gridlines at every 1 unit, for plotting the feasible region.

(a)On the grid provided, draw the lines 2f + r = 10 and f + 3r = 15, and shade the region representing all the constraints (including f ≥ 0 and r ≥ 0).(4)

(b)By drawing a suitable objective line and using the objective line (ruler) method, find the values of f and r that minimise the total cost C = 12f + 9r.(3)

(c)State the minimum total cost, and interpret your answer in the context of the problem.(2)

(Total for Question 10 is 9 marks)

This question continues the fertiliser problem described in Question 10.

(a)An assistant suggests using (f, r) = (2, 5), pointing out that this gives a lower value of C than the solution found in Question 10. Show that this point does not satisfy all the constraints, and explain why the assistant's suggestion cannot be used.(4)

(b)By evaluating the objective function at each vertex of the feasible region, verify that (f, r) = (3, 4) does give the true minimum feasible cost.(4)

(Total for Question 11 is 8 marks)

Discuss the similarities and differences between the objective line (ruler) method and the vertex method for solving a two-variable linear programming problem graphically. Your answer should refer to how each method locates the optimal solution, how each method deals with a problem that has more than one optimal solution, and which method is generally more efficient when the feasible region has many vertices.

(Total for Question 12 is 7 marks)

State two limitations of the linear programming model used in Questions 10 and 11 as a representation of the greenkeeper's real decision-making, and briefly explain the effect of each in context.

(Total for Question 13 is 3 marks)

Mark scheme · FP.D4 Decision Maths: Critical Path Analysis and Linear Programming

Question 1

(a) B1 an activity with zero total float, so any delay to it delays the completion of the whole project (oe)
(a) Answer: An activity with zero total float; any delay to it delays the whole project.
(b) B1 the amount of time an activity may be delayed (or extended) without affecting the overall completion time of the project, assuming all other activities occur as originally planned (oe)
(b) Answer: The amount an activity can be delayed without delaying the whole project.
(c) B1 the amount of time an activity may be delayed without affecting the earliest start time of any following activity (oe)
(c) Answer: The amount an activity can be delayed without delaying the earliest start of any following activity.
(d) B1 to show a logical dependency between activities that would not otherwise be represented correctly by the network (for example when one activity depends on more than one predecessor, but another activity leaving the same event does not) (oe); accept: to avoid two activities sharing the same start and end events
(d) Answer: To represent a logical dependency correctly (or to avoid two activities sharing the same pair of events) when this cannot otherwise be shown.

Question 2

(a) M1 recognise that D depends on both A and B, whereas C depends on A alone, so A cannot simply end at the same event as B without wrongly forcing C to also wait for B (oe)
(a) A1 state that a dummy activity (zero duration) is used to carry the completion of A through to the event that D leaves from, without altering the earliest start time of C (oe)
(a) Answer: One dummy activity is needed, to feed A's completion into D's event without also delaying C.
(b) B1 single start event (event 1), with A and B both shown leaving it
(b) B1 C shown leaving the event reached only by A (event 2), with duration 3
(b) B1 dummy activity (dashed, 0 duration) drawn from the event reached by A (event 2) to the event reached by B (event 3)
(b) B1 D shown leaving event 3 (reached by both B directly and A via the dummy), with duration 2
(b) B1 single end event reached by both C and D, network fully connected with no redundant or crossing dummies
(b) Answer: Network: 1 -> 2 (A, 2 days); 1 -> 3 (B, 1 day); 2 -> 3 (dummy, 0 days); 2 -> 4 (C, 3 days); 3 -> 4 (D, 2 days).

Question 3

(a) M1 correct method applied at each merge activity (G takes max of EFT(D), EFT(E); J takes max of EFT(H), EFT(I))
(a) A1 EST/EFT correct for A(0,4), B(0,6), C(4,7), D(4,9), E(6,13)
(a) A1 EST/EFT correct for F(7,11), G(13,19), H(11,14)
(a) A1 EST/EFT correct for I(19,24), J(24,26), all ten activities correct
(a) Answer: A(0,4) B(0,6) C(4,7) D(4,9) E(6,13) F(7,11) G(13,19) H(11,14) I(19,24) J(24,26).
(b) B1 26 (weeks) cao
(b) Answer: 26 weeks.
(c) M1 correct method applied at each branch activity (A takes min of LST(C), LST(D))
(c) A1 LST/LFT correct for J(24,26), I(19,24), H(21,24)
(c) A1 LST/LFT correct for G(13,19), F(17,21), E(6,13)
(c) A1 LST/LFT correct for D(8,13), C(14,17), B(0,6), A(4,8), all ten activities correct
(c) Answer: J(24,26) I(19,24) H(21,24) G(13,19) F(17,21) E(6,13) D(8,13) C(14,17) B(0,6) A(4,8).
(d) M1 identify all activities with zero total float (LST = EST): B, E, G, I, J
(d) A1 critical path B - E - G - I - J, length 26 weeks cao
(d) Answer: B - E - G - I - J, length 26 weeks.
(e) B1 A = 4 weeks, D = 4 weeks
(e) B1 C = 10 weeks, F = 10 weeks, H = 10 weeks
(e) Answer: A: 4, C: 10, D: 4, F: 10, H: 10 (weeks).

Question 4

(a) B1 0 (weeks) cao
(a) Answer: 0 weeks.
(b) M1 free float(D) = EST(G) - EFT(D)
(b) A1 = 13 - 9 = 4 weeks cao
(b) Answer: 4 weeks.
(c) B1 free float measures the delay possible without affecting the earliest start of the very next activity, whereas total float measures the delay possible without affecting the overall project completion date (oe)
(c) B1 apply to A: total float of A is 4 weeks, but its free float is 0, because A's only successors (C and D) are each due to start exactly when A finishes, so any delay to A immediately delays their earliest start, even though it need not delay the whole project (oe)
(c) Answer: Free float and total float need not match because free float accounts only for the knock-on delay to the next activity, while total float accounts for delay to the whole project; the difference arises when a successor still has slack elsewhere in the network.

Question 5

(a) B1 horizontal time axis drawn and labelled from 0 to at least 26 weeks
(a) B1 critical activities B, E, G, I, J plotted end-to-end with no gaps, correctly from week 0 to week 26
(a) B1 activity A plotted from week 0 to 4, with dashed float shown from week 4 to week 8
(a) B1 activities C, D plotted from their correct earliest start times (both week 4), with dashed float extending to their respective latest finish times (17 and 13)
(a) B1 activities F, H plotted from their correct earliest start times (7, 11), with dashed float extending to their latest finish times (21, 24)
(a) Answer: Bars: B[0-6], E[6-13], G[13-19], I[19-24], J[24-26] (critical, solid, no float); A[0-4] + float to 8; C[4-7] + float to 17; D[4-9] + float to 13; F[7-11] + float to 21; H[11-14] + float to 24.
(b) B1 activity I can start at week 19 (earliest) cao
(b) B1 activity F must finish by week 21 (latest) cao
(b) Answer: I: week 19; F: week 21.

Question 6

(a) B1 yes cao
(a) B1 because the total float of C is 10 weeks (Question 3(e)), and 8 ≤ 10, so a delay of 8 weeks remains within its float (oe)
(a) Answer: Yes; C's total float is 10 weeks, and 8 ≤ 10.
(b) M1 recompute the forward pass with duration(A) = 9: A(0,9), C(9,12), D(9,14), F(12,16), H(16,19), E unchanged (6,13), G: EST = max(EFT(D)=14, EFT(E)=13) = 14, so G(14,20), I(20,25), J: EST = max(EFT(H)=19, EFT(I)=25) = 25, so J(25,27)
(b) A1 new project completion time = 27 weeks cao
(b) A1 new critical path: A - D - G - I - J cao
(b) B1 note the project is delayed by only 1 week overall, since the 5-week increase to A exceeds its original float of 4 weeks (from Question 3(e)) by exactly 1 week (oe)
(b) Answer: New completion time = 27 weeks; new critical path A - D - G - I - J; the project is delayed by 1 week overall.

Question 7

(a) M1 correct forward-pass method at each merge activity (S takes max of EFT(P), EFT(Q); T takes max of EFT(R), EFT(S))
(a) A1 EST/EFT all correct: P(0,5), Q(0,3), R(5,11), S(5,9), T(11,13)
(a) M1 correct backward-pass method at the branch activity (P takes min of LST(R), LST(S))
(a) A1 LST/LFT all correct: T(11,13), R(5,11), S(7,11), Q(4,7), P(0,5)
(a) B1 project duration = 13 days stated or implied
(a) B1 fully correct, internally consistent table for all five activities (allow follow-through from one earlier slip)
(a) Answer: P: EST0 EFT5 LST0 LFT5 (float 0). Q: EST0 EFT3 LST4 LFT7 (float 4). R: EST5 EFT11 LST5 LFT11 (float 0). S: EST5 EFT9 LST7 LFT11 (float 2). T: EST11 EFT13 LST11 LFT13 (float 0). Project duration = 13 days.
(b) M1 length of path P-S-T = 5 + 4 + 2 = 11 days (or note that S has a total float of 2, so S is not a critical activity)
(b) A1 state that the true project duration is 13 days (from part (a)), not 11, so the manager's claim is incorrect
(b) B1 correctly identify the true critical path as P - R - T, explaining that S has positive float (2 days) and so is not critical, whereas the manager's path omits the genuinely critical activity R (oe)
(b) Answer: The claim is incorrect. The true critical path is P - R - T, length 13 days; S has total float 2 days, so P-S-T (length 11 days) is not the critical path.

Question 8

(a) B1 m = number of Meadow candles made per week; h = number of Harbour candles made per week
(a) Answer: m = number of Meadow candles made per week; h = number of Harbour candles made per week.
(b) B1 maximise P = 3.5m + 4.2h oe
(b) Answer: Maximise P = 3.5m + 4.2h.
(c) B1 200m + 350h ≤ 21000 oe (e.g. 4m + 7h ≤ 420) [wax]
(c) B1 15m + 10h ≤ 1200 oe (e.g. 3m + 2h ≤ 240) [hand-pouring time]
(c) B1 m ≥ 2h [ratio]
(c) B1 h ≥ 10 [standing order]
(c) Answer: 200m + 350h ≤ 21000; 15m + 10h ≤ 1200; m ≥ 2h; h ≥ 10.
(d) B1 m, h ≥ 0 and both integers, since it is not possible to make a negative or fractional number of candles (oe)
(d) Answer: m, h must be non-negative integers, since candles cannot be made in negative or fractional quantities.

Question 9

(a) B1 line 2x + y = 20 correctly drawn through (0,20) and (10,0)
(a) B1 line x + 3y = 30 correctly drawn through (0,10) and (15,5) or (30,0)
(a) B1 correct feasible region identified, bounded by the two lines and both axes
(a) B1 region unambiguously indicated (shaded or labelled R), consistent with x ≥ 0, y ≥ 0
(a) Answer: Feasible region bounded by (0,0), (10,0), (6,8), (0,10).
(b) B1 (0,0)
(b) B1 (10,0)
(b) B1 (0,10)
(b) M1 solving 2x + y = 20 and x + 3y = 30 simultaneously
(b) A1 (6,8) cao
(b) Answer: (0,0), (10,0), (6,8), (0,10).
(c) M1 evaluate P = 40x + 60y at each vertex (at least two shown)
(c) A1 (0,0): P=0; (10,0): P=400; (6,8): P=720; (0,10): P=600, with (6,8) correctly identified as giving the greatest value
(c) A1 conclusion: 6 benches and 8 tables, maximum profit £720 cao
(c) Answer: 6 benches and 8 tables; maximum weekly profit £720.

Question 10

(a) B1 line 2f + r = 10 correctly drawn through (0,10) and (5,0)
(a) B1 line f + 3r = 15 correctly drawn through (0,5) and (15,0)
(a) B1 correct feasible region identified as the unbounded region on or above/outside both lines, within f ≥ 0, r ≥ 0
(a) B1 vertices (0,10) and (3,4) correctly located and region unambiguously indicated (region R labelled)
(a) Answer: Feasible region bounded below-left by (0,10), (3,4), (15,0), unbounded above/right.
(b) B1 valid objective line drawn, e.g. 12f + 9r = 108 through (9,0) and (0,12), or any correct multiple of the objective function
(b) M1 ruler (straight edge) moved parallel to the objective line towards the origin (since minimising) until it last touches the feasible region
(b) A1 f = 3, r = 4 cao
(b) Answer: f = 3, r = 4.
(c) B1 minimum cost = £72 (ft from part (b))
(c) B1 interpretation: the greenkeeper should buy 3 bags of GrowFast and 4 bags of RootBoost for this treatment, at a total cost of £72, exactly meeting both the nitrogen and potash requirements (oe)
(c) Answer: Minimum cost = £72, using 3 bags of GrowFast and 4 bags of RootBoost.

Question 11

(a) M1 substitute (2,5) into the nitrogen constraint: 2(2) + 5 = 9
(a) A1 since 9 < 10, the nitrogen constraint is not satisfied, so (2,5) is not a feasible point cso
(a) B1 [check potash for completeness] 2 + 3(5) = 17 ≥ 15, satisfied, but this does not matter since the nitrogen constraint already fails
(a) B1 explain that although C = 12(2) + 9(5) = 69, which is less than 72, this point cannot be used because it does not provide enough nitrogen for the pitch, so it is not a valid solution to the linear programming problem (oe)
(a) Answer: (2,5) is infeasible: 2(2)+5 = 9 < 10 fails the nitrogen constraint. Its lower cost (£69) is therefore irrelevant, since it does not satisfy the pitch's actual requirements.
(b) M1 evaluate C at (0,10): C = 12(0) + 9(10) = 90
(b) A1 evaluate C at (15,0): C = 12(15) + 9(0) = 180
(b) A1 evaluate C at (3,4): C = 72, correctly identified as the smallest of the three values
(b) B1 conclude that, since the feasible region is unbounded away from these vertices (where C only increases further), (3,4) is confirmed as the true minimum-cost feasible solution (oe)
(b) Answer: C(0,10)=90, C(3,4)=72, C(15,0)=180. The minimum is confirmed at (3,4), cost £72.

Question 12

Level 0 (0): No relevant comments made, or the response fails to address the question.
Level 1 (1-2): A basic description of at most one method is given, with little or no valid comparison between the two.
Level 2 (3-5): Both methods are described with reasonable accuracy, and at least one valid comparison point is made (for example relating to efficiency or multiple optima), but the discussion is not fully developed or contains minor inaccuracies.
Level 3 (6-7): Both methods are described accurately and at least three distinct, well-explained comparison points are made (for example locating the optimum, efficiency for many vertices, and recognising multiple optimal solutions), with correct terminology used throughout.
Indicative content:
- Both methods require the feasible region to be drawn accurately first, and both are guaranteed to find the same optimal solution, since the optimum of a linear objective function over a polygonal feasible region always occurs at a vertex (or along a whole edge, in the case of multiple optima).
- The vertex method finds the coordinates of every vertex of the feasible region, then evaluates the objective function at each one directly, selecting the vertex giving the best (maximum or minimum) value.
- The objective line method instead draws one sample line of the objective function (for a convenient value), then slides a ruler parallel to this line across the feasible region, in the direction that improves the objective, identifying the last vertex the ruler touches before leaving the feasible region.
- The vertex method can become slow for a feasible region with many vertices, since every vertex's coordinates must be found (often by solving simultaneous equations) and the objective evaluated at each one; the objective line method avoids this, since the ruler can be moved directly to the optimal vertex without evaluating the objective everywhere else.
- The objective line method requires care in drawing the sample objective line accurately and in judging its gradient correctly relative to the constraint lines; a poorly drawn line can lead to the wrong vertex being identified, whereas the vertex method's evaluations are more mechanical and less prone to this type of error.
- If the objective line is parallel to one of the edges of the feasible region, there are infinitely many optimal solutions (every point on that edge, not just a single vertex); this is easy to spot with the objective line method, since the ruler lies flat along the whole edge at the optimal position, whereas with the vertex method it only becomes apparent when two adjacent vertices are found to give exactly equal objective values.
- In practice, the vertex method is often preferred for a feasible region with few vertices (since it is systematic and easy to check), while the objective line method is generally more efficient, and more revealing about the structure of the optimal solution, when the feasible region has many vertices.