Decision Maths: Critical Path Analysis and Linear Programming - Worksheets, Questions and Revision
24 original exam-style questions - 11 pages of questions with a full mark scheme - free printable PDF.
Decision Maths: Critical Path Analysis and Linear Programming revision guideMore A Level Further Maths practiceMock exams
This topic is chapter 4 of A Level Further Maths Decision Topic Workbook and chapter 2 of A Level Further Maths 10-Minute Tests 2.
4.4 Decision Maths: Critical Path Analysis and Linear Programming
2f + r ≥ 10 (nitrogen)
f + 3r ≥ 15 (potash)
f ≥ 0, r ≥ 0
| 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 |
| 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 |
| 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 |
Question 1
- the model assumes any non-negative value of f and r is allowed, but fertiliser is only sold in whole bags, so a non-integer optimal solution may not be usable in practice (oe)B1
- the model assumes the cost per bag is constant regardless of quantity bought, but bulk-buying discounts in reality might reduce the true cost of buying larger quantities, so the model may overstate the minimum achievable cost (oe)B1
- credit for a clear explanation, in context, of the effect of either limitation (for example: rounding a non-integer solution up could waste money or leave a requirement unmet, or ignoring bulk discounts means the true minimum cost could be lower than £72); accept any two valid limitations, fully explained in context, for full marksB1
- Answer: For example: (1) non-integer optimal solutions may not be practical, since fertiliser is bought in whole bags; (2) the linear cost assumption ignores possible bulk-buying discounts, so the true minimum cost could be lower than the model predicts.
Question 2
- (a) line 2f + r = 10 correctly drawn through (0,10) and (5,0)B1
- (a) line f + 3r = 15 correctly drawn through (0,5) and (15,0)B1
- (a) correct feasible region identified as the unbounded region on or above/outside both lines, within f ≥ 0, r ≥ 0B1
- (a) vertices (0,10) and (3,4) correctly located and region unambiguously indicated (region R labelled)B1
- (a) Answer: Feasible region bounded below-left by (0,10), (3,4), (15,0), unbounded above/right.
- (b) valid objective line drawn, e.g. 12f + 9r = 108 through (9,0) and (0,12), or any correct multiple of the objective functionB1
- (b) ruler (straight edge) moved parallel to the objective line towards the origin (since minimising) until it last touches the feasible regionM1
- (b) f = 3, r = 4 caoA1
- (b) Answer: f = 3, r = 4.
- (c) minimum cost = £72 (ft from part (b))B1
- (c) 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)B1
- (c) Answer: Minimum cost = £72, using 3 bags of GrowFast and 4 bags of RootBoost.
Question 3
- (a) substitute (2,5) into the nitrogen constraint: 2(2) + 5 = 9M1
- (a) since 9 < 10, the nitrogen constraint is not satisfied, so (2,5) is not a feasible point csoA1
- (a) [check potash for completeness] 2 + 3(5) = 17 ≥ 15, satisfied, but this does not matter since the nitrogen constraint already failsB1
- (a) 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)B1
- (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) evaluate C at (0,10): C = 12(0) + 9(10) = 90M1
- (b) evaluate C at (15,0): C = 12(15) + 9(0) = 180A1
- (b) evaluate C at (3,4): C = 72, correctly identified as the smallest of the three valuesA1
- (b) 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)B1
- (b) Answer: C(0,10)=90, C(3,4)=72, C(15,0)=180. The minimum is confirmed at (3,4), cost £72.
Question 4
- (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, 16), (8, 8), (12, 0)A1
- (a) Answer: (0, 0), (0, 16), (8, 8), (12, 0)
- (b) evaluates P at each vertexM1
- (b) values: 0, 48, 56, 48A1
- (b) maximum P = 56 at (8, 8)A1
- (b) Answer: P = 56 at (8, 8)
Question 5
- (a) earliest start = latest earliest finish of the immediate predecessorsM1
- (a) earliest starts: A 0, B 5, C 12, D 5, E 12, F 17, G 12, H 12A1
- (a) minimum completion time = 23 daysA1
- (a) Answer: 23 days
- (b) latest finish = smallest latest start of the successorsM1
- (b) latest finishes: A 5, B 12, C 23, D 23, E 17, F 23, G 23, H 23A1
- (b) critical activities (zero float): A, B, E, FA1
- (b) Answer: A, B, E, F
- (c) total float = latest finish - earliest start - durationM1
- (c) 23 - 12 - 2 = 9 daysA1
- (c) Answer: 9 days
- (d) total duration of all activities = 47M1
- (d) 47/23 = 2.04, so at least 3 workersA1
- (d) Answer: 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, 23), (12, 11), (81/4, 0)A1
- (a) Answer: (0, 0), (0, 23), (12, 11), (81/4, 0)
- (b) evaluates P at each vertexM1
- (b) values: 0, 92, 80, 243/4A1
- (b) maximum P = 92 at (0, 23)A1
- (b) Answer: P = 92 at (0, 23)
Question 7
- (a) earliest start = latest earliest finish of the immediate predecessorsM1
- (a) earliest starts: A 0, B 9, C 11, D 9, E 16, F 16, G 24, H 9A1
- (a) minimum completion time = 31 daysA1
- (a) Answer: 31 days
- (b) latest finish = smallest latest start of the successorsM1
- (b) latest finishes: A 9, B 24, C 31, D 16, E 24, F 31, G 31, H 31A1
- (b) critical activities (zero float): A, D, E, GA1
- (b) Answer: A, D, E, G
- (c) total float = latest finish - earliest start - durationM1
- (c) 24 - 9 - 2 = 13 daysA1
- (c) Answer: 13 days
- (d) total duration of all activities = 41M1
- (d) 41/31 = 1.32, so at least 2 workersA1
- (d) Answer: 2
Question 8
- (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, 8), (4, 7), (25, 0)A1
- (a) Answer: (0, 0), (0, 8), (4, 7), (25, 0)
- (b) evaluates P at each vertexM1
- (b) values: 0, 16, 34, 125A1
- (b) maximum P = 125 at (25, 0)A1
- (b) Answer: P = 125 at (25, 0)
Question 9
- (a) 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)M1
- (a) 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)A1
- (a) Answer: One dummy activity is needed, to feed A's completion into D's event without also delaying C.
- (b) single start event (event 1), with A and B both shown leaving itB1
- (b) C shown leaving the event reached only by A (event 2), with duration 3B1
- (b) dummy activity (dashed, 0 duration) drawn from the event reached by A (event 2) to the event reached by B (event 3)B1
- (b) D shown leaving event 3 (reached by both B directly and A via the dummy), with duration 2B1
- (b) single end event reached by both C and D, network fully connected with no redundant or crossing dummiesB1
- (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 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, 7), (8, 5), (13, 0)A1
- (a) Answer: (0, 0), (0, 7), (8, 5), (13, 0)
- (b) evaluates P at each vertexM1
- (b) values: 0, 7, 29, 39A1
- (b) maximum P = 39 at (13, 0)A1
- (b) Answer: P = 39 at (13, 0)
Question 11
- (a) earliest start = latest earliest finish of the immediate predecessorsM1
- (a) earliest starts: A 0, B 7, C 16, D 16, E 16, F 7, G 24, H 11, I 11A1
- (a) minimum completion time = 30 daysA1
- (a) Answer: 30 days
- (b) latest finish = smallest latest start of the successorsM1
- (b) latest finishes: A 7, B 16, C 30, D 30, E 24, F 25, G 30, H 30, I 30A1
- (b) critical activities (zero float): A, B, E, GA1
- (b) Answer: A, B, E, G
- (c) total float = latest finish - earliest start - durationM1
- (c) 30 - 16 - 5 = 9 daysA1
- (c) Answer: 9 days
- (d) total duration of all activities = 50M1
- (d) 50/30 = 1.67, so at least 2 workersA1
- (d) Answer: 2
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, 16), (8, 8), (32/3, 0)A1
- (a) Answer: (0, 0), (0, 16), (8, 8), (32/3, 0)
- (b) evaluates P at each vertexM1
- (b) values: 0, 32, 56, 160/3A1
- (b) maximum P = 56 at (8, 8)A1
- (b) Answer: P = 56 at (8, 8)
Question 13
- (a) earliest start = latest earliest finish of the immediate predecessorsM1
- (a) earliest starts: A 0, B 5, C 10, D 16, E 24, F 24, G 28, H 28A1
- (a) minimum completion time = 36 daysA1
- (a) Answer: 36 days
- (b) latest finish = smallest latest start of the successorsM1
- (b) latest finishes: A 5, B 10, C 16, D 24, E 28, F 36, G 36, H 36A1
- (b) critical activities (zero float): A, B, C, D, E, HA1
- (b) Answer: A, B, C, D, E, H
- (c) total float = latest finish - earliest start - durationM1
- (c) 36 - 24 - 4 = 8 daysA1
- (c) Answer: 8 days
- (d) total duration of all activities = 46M1
- (d) 46/36 = 1.28, so at least 2 workersA1
- (d) Answer: 2
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, 6), (4, 4), (6, 0)A1
- (a) Answer: (0, 0), (0, 6), (4, 4), (6, 0)
- (b) evaluates P at each vertexM1
- (b) values: 0, 36, 44, 30A1
- (b) maximum P = 44 at (4, 4)A1
- (b) Answer: P = 44 at (4, 4)
Question 15
- (a) earliest start = latest earliest finish of the immediate predecessorsM1
- (a) earliest starts: A 0, B 7, C 7, D 7, E 7, F 11, G 15, H 15, I 7A1
- (a) minimum completion time = 24 daysA1
- (a) Answer: 24 days
- (b) latest finish = smallest latest start of the successorsM1
- (b) latest finishes: A 7, B 24, C 15, D 15, E 24, F 24, G 24, H 24, I 24A1
- (b) critical activities (zero float): A, D, GA1
- (b) Answer: A, D, G
- (c) total float = latest finish - earliest start - durationM1
- (c) 24 - 7 - 4 = 13 daysA1
- (c) Answer: 13 days
- (d) total duration of all activities = 57M1
- (d) 57/24 = 2.38, so at least 3 workersA1
- (d) Answer: 3
Question 16
- (a) earliest start = latest earliest finish of the immediate predecessorsM1
- (a) earliest starts: A 0, B 6, C 6, D 6, E 15, F 17, G 17, H 17, I 14A1
- (a) minimum completion time = 26 daysA1
- (a) Answer: 26 days
- (b) latest finish = smallest latest start of the successorsM1
- (b) latest finishes: A 6, B 15, C 23, D 26, E 17, F 26, G 26, H 26, I 26A1
- (b) critical activities (zero float): A, B, E, HA1
- (b) Answer: A, B, E, H
- (c) total float = latest finish - earliest start - durationM1
- (c) 23 - 6 - 8 = 9 daysA1
- (c) Answer: 9 days
- (d) total duration of all activities = 50M1
- (d) 50/26 = 1.92, so at least 2 workersA1
- (d) Answer: 2
Question 17
- (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, 16), (11, 5), (43/3, 0)A1
- (a) Answer: (0, 0), (0, 16), (11, 5), (43/3, 0)
- (b) evaluates P at each vertexM1
- (b) values: 0, 32, 54, 172/3A1
- (b) maximum P = 172/3 at (43/3, 0)A1
- (b) Answer: P = 172/3 at (43/3, 0)
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, 10), (8, 4), (12, 0)A1
- (a) Answer: (0, 0), (0, 10), (8, 4), (12, 0)
- (b) evaluates P at each vertexM1
- (b) values: 0, 60, 32, 12A1
- (b) maximum P = 60 at (0, 10)A1
- (b) Answer: P = 60 at (0, 10)
Question 19
- (a) correct method applied at each merge activity (G takes max of EFT(D), EFT(E); J takes max of EFT(H), EFT(I))M1
- (a) EST/EFT correct for A(0,4), B(0,6), C(4,7), D(4,9), E(6,13)A1
- (a) EST/EFT correct for F(7,11), G(13,19), H(11,14)A1
- (a) EST/EFT correct for I(19,24), J(24,26), all ten activities correctA1
- (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) 26 (weeks) caoB1
- (b) Answer: 26 weeks.
- (c) correct method applied at each branch activity (A takes min of LST(C), LST(D))M1
- (c) LST/LFT correct for J(24,26), I(19,24), H(21,24)A1
- (c) LST/LFT correct for G(13,19), F(17,21), E(6,13)A1
- (c) LST/LFT correct for D(8,13), C(14,17), B(0,6), A(4,8), all ten activities correctA1
- (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) identify all activities with zero total float (LST = EST): B, E, G, I, JM1
- (d) critical path B - E - G - I - J, length 26 weeks caoA1
- (d) Answer: B - E - G - I - J, length 26 weeks.
- (e) A = 4 weeks, D = 4 weeksB1
- (e) C = 10 weeks, F = 10 weeks, H = 10 weeksB1
- (e) Answer: A: 4, C: 10, D: 4, F: 10, H: 10 (weeks).
Question 20
- (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, 44/3), (8, 12), (14, 0)A1
- (a) Answer: (0, 0), (0, 44/3), (8, 12), (14, 0)
- (b) evaluates P at each vertexM1
- (b) values: 0, 176/3, 56, 14A1
- (b) maximum P = 176/3 at (0, 44/3)A1
- (b) Answer: P = 176/3 at (0, 44/3)
Question 21
- (a) 0 (weeks) caoB1
- (a) Answer: 0 weeks.
- (b) free float(D) = EST(G) - EFT(D)M1
- (b) = 13 - 9 = 4 weeks caoA1
- (b) Answer: 4 weeks.
- (c) 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)B1
- (c) 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)B1
- (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 22
- (a) horizontal time axis drawn and labelled from 0 to at least 26 weeksB1
- (a) critical activities B, E, G, I, J plotted end-to-end with no gaps, correctly from week 0 to week 26B1
- (a) activity A plotted from week 0 to 4, with dashed float shown from week 4 to week 8B1
- (a) 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)B1
- (a) activities F, H plotted from their correct earliest start times (7, 11), with dashed float extending to their latest finish times (21, 24)B1
- (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) activity I can start at week 19 (earliest) caoB1
- (b) activity F must finish by week 21 (latest) caoB1
- (b) Answer: I: week 19; F: week 21.
Question 23
- (a) yes caoB1
- (a) because the total float of C is 10 weeks (Question 19(e)), and 8 ≤ 10, so a delay of 8 weeks remains within its float (oe)B1
- (a) Answer: Yes; C's total float is 10 weeks, and 8 ≤ 10.
- (b) 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)M1
- (b) new project completion time = 27 weeks caoA1
- (b) new critical path: A - D - G - I - J caoA1
- (b) 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 19(e)) by exactly 1 week (oe)B1
- (b) Answer: New completion time = 27 weeks; new critical path A - D - G - I - J; the project is delayed by 1 week overall.
Question 24
- (a) correct forward-pass method at each merge activity (S takes max of EFT(P), EFT(Q); T takes max of EFT(R), EFT(S))M1
- (a) EST/EFT all correct: P(0,5), Q(0,3), R(5,11), S(5,9), T(11,13)A1
- (a) correct backward-pass method at the branch activity (P takes min of LST(R), LST(S))M1
- (a) LST/LFT all correct: T(11,13), R(5,11), S(7,11), Q(4,7), P(0,5)A1
- (a) project duration = 13 days stated or impliedB1
- (a) fully correct, internally consistent table for all five activities (allow follow-through from one earlier slip)B1
- (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) 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)M1
- (b) state that the true project duration is 13 days (from part (a)), not 11, so the manager's claim is incorrectA1
- (b) 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)B1
- (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.
Mark your answers
Check answers without an account. Some answers can be checked automatically; use the mark scheme to mark the rest.