Further Maths B (MEI) · OCR H645 · Modelling with Algorithms (minor option - choose one with a major, or three alone) · November 2021
The list below shows the sizes of 13 items.
5 16 12 15 21 10 17 5 3 6 13 24 5
Show the result of applying the first fit algorithm to pack items with the sizes listed above into
bins that have a capacity of 45.
[2]
Show the result of applying a full bin strategy to pack items with the sizes listed above into
bins that have a capacity of 45.
[2]
The table below shows the activities involved in a project, together with their immediate predecessors. The table also gives the duration (in hours) of each activity, apart from G and H.
| Activity | Immediate predecessors | Duration (hours) |
| A | – | 6 |
| B | – | 4 |
| C | – | 8 |
| D | C | 3 |
| E | A, B, D | 6 |
| F | B, D | 10 |
| G | C | |
| H | C | |
| I | E, F, G | 10 |
| J | F, G | 7 |
| K | F, G, H | 9 |
Draw an activity network, using activity on arc, to represent the project.
[3]
It is given that the only critical activities of the project are C, D, F, and I.
Carry out a forward pass and a backward pass through the activity network, showing the early
event time and late event time at each vertex of your network.
[3]
State the minimum completion time for the project.
[1]
Calculate the interfering float at H, given that the independent float is not 0.
[1]
It is given that the total float of activity G is at most double the total float of activity E. Let x be the duration, in hours, of activity G.
Determine the range of possible values of x.
[3]
A vertex of a graph for which the order is an odd number is called an odd vertex.
By considering the number of arc endings for a general graph, explain why, for every
graph, the sum of the vertex orders must be an even number.
[1]
Hence explain why no graph can have an odd number of odd vertices.
[1]
Fig. 3 shows a weighted graph. The weights represent arc lengths.
Apply Dijkstra’s algorithm to the copy of the network in the Printed Answer Booklet to find
the shortest path from A to F.
[5]
The following algorithm can be used to find the length of the shortest route in a network that uses every arc at least once, and ends at the vertex where it started.
START with a list of the odd vertices. STEP 1 For each pair of odd vertices find the shortest path that connects them and the length of this path. STEP 2 Find the set of paths connecting odd vertices that includes every odd vertex and has the shortest total length. STEP 3 Add this shortest total to the total weight of the network. STOP
Complete STEP 1 of the algorithm by completing the table in the Printed Answer Booklet.
[4]
You are given that the total weight of the network in Fig. 3 is 353.
Complete STEP 2 and STEP 3 of the algorithm to determine the length of the shortest route
that uses every arc of Fig. 3 at least once, starting and ending at vertex A.
[2]
Fig. 4.1 represents a system of pipes through which fluid can flow from a source, S, to a sink, T. It also shows two cuts, α and β. The arc weights show capacities in litres per minute.
Calculate the capacity of the cut α.
[1]
Calculate the capacity of the cut β.
[1]
Using only the answers to part (a), state what can be deduced about the maximum possible
flow through the system.
[1]
An LP formulation is set up to find the maximum flow through the network.
Some of the constraints of the LP formulation are shown below.
SA - AB - AD = 0 SC - CB - CF = 0 AD + BD - DE - DT = 0 BF + CF - FG = 0 BG + EG + FG - GT = 0
SA ⩽ 62, SB ⩽ 71, SC ⩽ 47, AB ⩽ 43, AD ⩽ 22, BD ⩽ 39, BE ⩽ 32, BF ⩽ 43, BG ⩽ 47, CB ⩽ 25, CF ⩽ 39, DE ⩽ 33, EG ⩽ 43, FG ⩽ 42
Explain the purpose of the line SC - CB - CF = 0 in the LP formulation.
[1]
Complete the LP formulation that includes the sink node in the objective function.
[3]
The complete LP was run in an LP solver and some of the output is shown in Fig. 4.2.
Use the diagram in the Printed Answer Booklet to show how a flow of 152 litres per minute
can be achieved.
[2]
Prove that this is the maximum possible flow through the system.
[2]
The capacity of pipe AD is increased to x litres per minute.
Determine the maximum possible flow through the system, stating the corresponding value
of x.
[2]
A mathematics competition consists of a written paper that involves questions on the topics of algebra, trigonometry, and calculus only.
From experience of the paper, Leo knows that in the three and a half hours available to complete the paper
• he will answer exactly 50 questions,
• at most half of these will be on the topic of algebra,
• he will answer at least three times as many trigonometry questions as calculus questions.
The table below shows further information about the paper and defines the variables x, y and z.
| Type of question | Average time (minutes) to solve each question | Points for each correct answer | Number of questions answered by Leo |
| Algebra | 1 | 2 | x |
| Trigonometry | 4 | 5 | y |
| Calculus | 12 | 20 | z |
Leo wants to maximise the number of points that he scores.
The two-stage simplex method could be used to solve Leo’s problem.
• Show how the constraints for the problem can be made into equations using slack variables, exactly one surplus variable and exactly one artificial variable.
• Show how the rows for the two objective functions can be formed.
• Complete the initial tableau in the Printed Answer Booklet.
You do not need to carry out any iterations of the simplex method.
[9]
Represent the feasible region for x and y graphically.
[5]
Explain why the optimal values of x and y can be found by minimising the function 6 x + 5.
[2]
Hence find the number of each type of question Leo should answer.
[1]
State the corresponding number of points Leo will score.
[1]
Give a reason why Leo may not score the number of points stated in part (d)(ii).
[1]
The paper as printed
Spotted a mistake on this page?Report a problem