OCR A Level Further Maths B (MEI) Modelling with Algorithms (minor option - choose one with a major, or three alone) June 2022 question paper Y433

The diagram in Fig. 1.1 represents a system of pipes through which a fluid can flow from three sources to three sinks. The weights on the arcs show the capacities of the pipes in litres per minute.

Add a supersource S and a supersink T to the network in the Printed Answer Booklet. Give

appropriate weightings and directions to the connecting arcs.

The cut α partitions the vertices into sets {S, A, B, C, D},{E, F, G, H, I, J, K, T}.

Calculate the capacity of cut α.

Explain why a flow of 34 litres per minute along AE cannot be achieved.

An LP formulation is set up to find the maximum flow through the network.

Write down a suitable objective function for the LP formulation.

The diagram in Fig. 1.2 shows a feasible flow through the network.

Show that this is a maximum flow.

The flow chart shows an algorithm that gives a numerical approximation for the real root of the cubic equation x³ - 11x - 21 = 0.

Work through the algorithm using the input A = 5. Record the values of A and B correct to

7 decimal places every time they change. Give the final output correct to 3 decimal places.

Show that the algorithm does give the real root of x³ - 11x - 21 = 0 correct to 3 decimal

places.

Explain how to adapt the algorithm so that a numerical approximation for the real root of the

cubic equation x³ - 12x - 23 = 0 can be found.

Fig. 3.1 shows an activity network for a project. Each activity is represented by an arc. The duration of each activity is measured in hours. The early event times and the late event times are shown at each vertex.

Fig. 3.2 shows the independent float for each activity.

State which activities are critical.

Complete the table in the Printed Answer Booklet showing the duration of each activity.

Each activity requires one worker. Once a worker has started an activity they continue with that activity until it is complete.

Draw a schedule to show how three workers can complete the project in the minimum completion time. Each box in the Printed Answer Booklet represents 1 hour. For each worker, write the letter of the activity they are doing in each box, or leave the box blank if the worker

is not required for that 1 hour.

A list of n numbers is to be sorted into descending order using the quick sort algorithm.

The number of comparisons made in each pass of the algorithm is used as a measure of the complexity of the quick sort algorithm.

Show that, in the worst case, the quick sort algorithm has complexity O(n²).

A computer takes 2.3 × 10^-7 seconds to sort the list of 100 ascending integers 1, 2, 3…, 99, 100 into descending order using the quick sort algorithm.

Calculate approximately how long it will take the computer to sort the list of 500 000 ascending integers 1, 2, 3,…, 499 999, 500 000 into descending order using the quick sort algorithm. You should assume that the computer uses the first value as the pivot for each

sublist.

A student attempts to use the quick sort algorithm to sort a list of seven random integers into descending order. After two passes through the list the student produces the following list.

6 8 10 5 7 11 4

Explain how you know that the student has made at least one error in these two passes.

Explain why the simplex algorithm cannot be used to solve this LP problem.

Use the substitutions x = X + 4, y = Y + 2, z =- Z - 2 and P = Q + 16 to reformulate this LP

problem into standard form.

Represent the reformulated problem as an initial simplex tableau.

After a first iteration of the simplex algorithm the tableau below is produced.

Perform a second iteration of the simplex algorithm.

Find the maximum value of P, and the corresponding values of x, y and z.

Fig. 6.1 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 G.

AB + AC + AD + AE = 1

CF + DF - FC - FD - FE - FG = 0

CE + EC ⩽ 1

The LP is run in a solver and the following output is shown in the table in Fig. 6.2.

Find the length of the longest route from A to G given by the output in Fig. 6.2.

State all possible corresponding longest routes from A to G.

Kai makes three sizes of model car, small, medium and large, to sell each year at a fair.

Kai has enough material to make either 250 small cars or 175 medium cars or 150 large cars. Alternatively, he could make a combination of the three sizes.

Each small car requires 40 minutes to make, each medium car requires 70 minutes to make, and each large car requires 140 minutes to make.

The total time that Kai spends making all the cars must not exceed 220 hours.

From experience, small cars sell particularly well so Kai decides to make at least three small cars for every one large car.

Furthermore, Kai decides to make exactly 210 cars.

Kai plans on selling each small car for £5, each medium car for £8 and each large car for £12. Kai wants to maximise the total income from the sale of the cars at the fair (that is, money made from selling cars, ignoring the cost of materials).

Let x, y and z represent the number of small, medium and large cars respectively that Kai makes.

Explain why the maximum total income is achieved when 7 x + 4 y is minimised.

Determine the constraints of this ILP problem by listing them as simplified inequalities with

integer coefficients in x and y only.

By representing the feasible region for x and y graphically, determine how many of each size of car Kai should make to maximise the total income from the fair. You must show all your

working.

Using the solution found in part (c), find the maximum possible total income from the sales.