A Level Further Maths Decision Essentials includes Decision Maths: Algorithms, Sorting and Bin Packing (Decision Maths); Decision Maths: Graphs, Trees and Minimum Spanning Trees (Decision Maths); Decision Maths: Shortest Paths and Route Inspection (Decision Maths); Decision Maths: Critical Path Analysis and Linear Programming (Decision Maths); Decision: Algorithms and Graph Theory Depth (Decision Maths); Decision: Linear Programming and Critical Path Depth (Decision Maths).
Method recap - Decision: Algorithms and Graph Theory Depth
- Represent a bipartite graph as two sets of vertices (for example workers and jobs) with edges showing which pairings are allowed, and find an initial matching by inspection, pairing as many vertices directly as possible.
- To improve a matching, search from an unmatched vertex in the first set for an alternating path: a path that alternates between edges not in the current matching and edges in the current matching, ending at an unmatched vertex in the second set.
- If an alternating path reaching an unmatched vertex is found, it is 'augmenting': swap the status of every edge along it (matched edges become unmatched and unmatched edges become matched), which increases the size of the matching by exactly one pair.
- Repeat the search from each remaining unmatched vertex until no augmenting path can be found; the matching is then maximum. A matching that matches every vertex in the smaller set is automatically maximum, giving a useful stopping check.
Worked example - Decision: Algorithms and Graph Theory Depth
Four workers P, Q, R, S can each be assigned to certain jobs from 1, 2, 3, 4, according to the allowed pairings: P can do jobs 1 and 2; Q can do jobs 1 and 3; R can do jobs 2, 3 and 4; S can do jobs 3 and 4. An initial matching P-1, Q-3, R-4 has been found, leaving S and job 2 unmatched. Use the alternating path algorithm to find a matching of size 4, if one exists.
- S is unmatched. Its allowed jobs are 3 and 4, both currently matched (3 to Q, 4 to R); try the edge S-3 first, which is an unmatched edge.
- From job 3, follow its matched edge back to Q (since 3-Q is in the current matching). From Q, look for another unmatched edge: Q-1 is unmatched, since the matching uses P-1, not Q-1.
- From job 1, follow its matched edge back to P (since 1-P is in the current matching). From P, look for another unmatched edge: P-2 is unmatched, and job 2 is currently unmatched.
- The path S - 3 - Q - 1 - P - 2 alternates unmatched, matched, unmatched, matched, unmatched edges and starts and ends at unmatched vertices, so it is a valid augmenting path.
- Swap the status of every edge on the path: S-3 becomes matched, 3-Q becomes unmatched, Q-1 becomes matched, 1-P becomes unmatched, P-2 becomes matched.
- The new matching is P-2, Q-1, R-4, S-3 (R-4 is unchanged, as it was not on the path). All four workers are now matched.
- Final answer: a complete matching of size 4 exists: P-2, Q-1, R-4, S-3.
Question 10 - Decision: Algorithms and Graph Theory Depth
4 marks
A bipartite graph has 6 vertices in set X and 4 vertices in set Y. Explain, with reference to the maximum possible matching size, why at least 2 vertices of X can never be matched, whatever the edges are.
Answer and mark scheme
Mark scheme for Question 10 [4 marks]| Question 10[4 marks] |
|---|
| Answer or working | Marks |
|---|
| a matching cannot match more vertices than the size of the smaller vertex set. | 1 |
| set Y has only 4 vertices, so at most 4 edges can ever be in a matching (each using one distinct Y-vertex). | 1 |
| at most 4 of the 6 vertices in X can therefore be matched. | 1 |
| Final answer: at least 6 - 4 = 2 vertices in X can never be matched, whatever the edges are, because Y does not have enough vertices to pair with all of X. | 1 |
Question 8 - Decision: Algorithms and Graph Theory Depth
7 marks
Five applicants A, B, C, D, E are considered for jobs 1, 2, 3, 4. A is qualified for jobs 1, 2. B is qualified for jobs 1, 3. C is qualified for jobs 2, 3. D is qualified for jobs 3, 4. E is qualified for job 4 only. An initial matching A-1, B-3, C-2, D-4 has been found by inspection, leaving E unmatched. (a) Attempt to find an augmenting path starting from E, showing your working. (b) State the size of the maximum matching. (c) Explain why no matching can match all five applicants, however the matching is chosen.
Answer and mark scheme
Mark scheme for Question 8 [7 marks]| Question 8[7 marks] |
|---|
| Answer or working | Marks |
|---|
| from E, the only edge is E-4 (unmatched); job 4 is matched to D, so follows the matched edge 4-D. | 1 |
| from D, the only other edge is D-3 (unmatched); job 3 is matched to B, so follows the matched edge 3-B. | 1 |
| from B, the only other edge is B-1 (unmatched); job 1 is matched to A, so follows the matched edge 1-A. | 1 |
| from A, the only other edge is A-2 (unmatched); job 2 is matched to C, so follows the matched edge 2-C. From C, the only other edge is C-3, but job 3 has already been visited, so the search ends with no unmatched job reached: no augmenting path exists from E. | 1 |
| the maximum matching therefore has size 4 (the initial matching A-1, B-3, C-2, D-4 is already maximum). | 1 |
| between them, A, B, C, D and E are qualified only for jobs 1, 2, 3, 4 (four distinct jobs across all five applicants), so at most 4 of the 5 applicants can ever be matched, whichever matching is chosen. | 1 |
| Final answer: no augmenting path exists from E; maximum matching size = 4; no matching can match all five applicants, because their qualifications cover only four distinct jobs between them (E itself is matched in some maximum matchings, for example A-1, B-3, C-2, E-4, which leaves D unmatched). | 1 |
Method recap - Decision: Linear Programming and Critical Path Depth
- For a linear programming problem written as 'maximise P = ...' subject to '<=' constraints, introduce one slack variable for each constraint to convert every inequality into an equation, and write the objective as an equation P - (coefficients) = 0.
- Set up the initial Simplex tableau, with one row per constraint (labelled by its slack variable, which starts as the basic variable) plus a final row for the objective equation.
- Choose the pivot column: the column (other than the RHS) with the most negative entry in the objective row. If every entry in the objective row is zero or positive, the tableau is already optimal, so stop.
- Choose the pivot row using the ratio test: divide the RHS of each constraint row by its entry in the pivot column (ignoring rows with a zero or negative entry in that column), and pick the row with the smallest non-negative ratio.
Question 9 - Decision: Linear Programming and Critical Path Depth
8 marks
Maximise P = 5x + 4y subject to 6x + 4y <= 24, x + 2y <= 6, x >= 0, y >= 0. Use the Simplex algorithm to find the optimal values of x, y and P, showing each tableau.
Answer and mark scheme
Mark scheme for Question 9 [8 marks]| Question 9[8 marks] |
|---|
| Answer or working | Marks |
|---|
| sets up the problem in standard form with slack variables: 6x+4y+s1=24, x+2y+s2=6, and objective row P-5x-4y=0 | 1 |
| identifies x as the first entering variable, since -5 is the most negative entry in the objective row | 1 |
| correct ratio test (24/6=4, 6/1=6) identifies s1 as the leaving variable, with pivot element 6 | 1 |
| forms the correct tableau after this pivot, with x row: x=1, y=2/3, s1=1/6, s2=0, RHS=4 | 1 |
| identifies y as the next entering variable, since -2/3 is the only remaining negative objective-row entry | 1 |
| correct ratio test (4 divided by 2/3 = 6, 2 divided by 4/3 = 1.5) identifies s2 as the leaving variable, with pivot element 4/3 | 1 |
| correct final tableau with x row: x=1, y=0, s1=1/4, s2=-1/2, RHS=3, and y row: x=0, y=1, s1=-1/8, s2=3/4, RHS=3/2, and every objective-row entry (3/4 and 1/2) zero or positive, confirming optimality | 1 |
| P=21 at x=3, y=3/2; Final answer: x=3, y=3/2 (=1.5), maximum P=21 | 1 |
Question 10 - Decision: Linear Programming and Critical Path Depth
9 marks
The table shows the activities needed for a small project, their duration in days, their immediate predecessor activities, and the number of workers each activity needs while it is running. Activity | Duration (days) | Predecessor(s) | Workers needed A | 4 | none | 2 B | 3 | none | 1 C | 2 | A | 3 D | 5 | A | 2 E | 3 | B, C | 2 F | 4 | D, E | 1 (a) Find the earliest and latest start time of every activity, and hence find the length of the critical path and the total float of activity B. (b) Given that every activity is scheduled to start at its earliest start time, find the maximum number of workers required at any one time, stating the days on which this maximum occurs. (c) Explain why delaying the start of activity B cannot reduce this maximum.
Answer and mark scheme
Mark scheme for Question 10 [9 marks]| Question 10[9 marks] |
|---|
| Answer or working | Marks |
|---|
| attempts a forward pass to find the earliest start (ES) and earliest finish (EF) of every activity, respecting all listed predecessors (e.g. ES(D)=EF(A)=4, ES(E)=max(EF(B),EF(C))=max(3,6)=6) | 1 |
| correct EF values throughout, in particular EF(D)=9, EF(E)=9 and EF(F)=13, so the project duration is 13 days | 1 |
| attempts a backward pass from a project duration of 13 to find the latest finish (LF) and latest start (LS) of every activity | 1 |
| correct LS values throughout, in particular LS(A)=0, LS(C)=4, LS(D)=4 and LS(E)=6 | 1 |
| total float of B = LS(B)-ES(B) = 3-0 = 3 days; critical path length = 13 days (with A, C, D, E and F all having zero float) | 1 |
| lists which activities are running in each time interval between day 0 and day 13 under the earliest-start schedule | 1 |
| identifies days 4 to 6 as the peak interval, where C (3 workers) and D (2 workers) are both running, since A has just finished and E has not yet started | 1 |
| maximum = 5 workers, occurring on days 4 to 6 | 1 |
| C and D, the two activities running during the days 4 to 6 peak, both have zero total float so neither can be delayed, and B is not running during that interval at its earliest start, so shifting B can only add its worker to days 4 to 6 (a delay of 2 or 3 days raises the maximum to 6) and cannot lower the maximum of 5 workers; Final answer: critical path length 13 days, float of B = 3 days, maximum workers = 5 (days 4 to 6), and delaying B cannot reduce this maximum | 1 |