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

12 15 11 9 20 16 8 23 10 7

Apply the quick sort algorithm to sort the list of numbers into descending order. You should

use the first value as the pivot for each sublist.

The values represent masses, measured in kg.

Show the result of applying the first fit decreasing algorithm to pack these masses into bags

that can each hold a maximum of 40 kg.

Show the result of applying a full bin strategy to pack these masses into bags that can each

hold a maximum of 40 kg.

The table in Fig. 2 shows the distances, in miles, along the direct roads between ten villages, A to J. A dash (–) indicates that there is no direct road linking the villages.

Apply the tabular form of Prim’s algorithm to the network, starting at vertex D, to find a

minimum spanning tree for the network.

State the total length of the arcs in the minimum spanning tree.

Use Dijkstra’s algorithm to determine the length of the shortest path from G to J via D.

A computer takes 0.25 secs to solve a shortest path problem on a network with 15 vertices using Dijkstra’s algorithm. Approximately how long will it take the computer to solve a

shortest path problem on a network with 300 vertices using Dijkstra’s algorithm?

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

appropriate weightings and directions to the connecting arcs.

Calculate the capacity of the cut α.

Explain why the arcs DG and DI cannot simultaneously be full to capacity.

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

Write down a suitable objective function for the LP formulation.

Write down the constraint required for the LP formulation that ensures that the flow into

vertex I is equal to the flow out of vertex I.

The complete LP was run in an LP solver and it was found that arcs AC, BE, BF, ED, CH, DG, HK, LI and JM (and possibly others) were all saturated and that the flow through DI was 5 gallons per hour.

By completing the diagram in the Printed Answer Booklet, determine the maximum value of

the flow through the network.

Use a suitable cut to prove that this is the maximum flow.

Complete the table in the Printed Answer Booklet giving the duration and immediate

predecessors for each activity in the project.

Draw an activity network, using activity on arc, to represent the project.

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.

It is given that activity C has a non-zero independent float.

State the other activity that has a non-zero independent float.

Calculate the corresponding value of this independent float.

Explain, with regards to any delays for this project, the significance of this activity having

a non-zero independent float.

Fig. 5.1 shows the constraints of a linear programming problem, in which the objective is to maximise a function of the variables x and y.

The feasible region, R, is the unshaded region together with its boundaries. An objective line is also shown and labelled on Fig. 5.1.

• Complete the initial tableau in the Printed Answer Booklet so that the two-stage simplex method may be used to solve this problem.

• Show how the constraints for the problem have been made into equations using slack variables, surplus variables and artificial variables.

• Show how the rows for the two objective functions are formed.

After two iterations of the two-stage simplex method a computer produces the tableau in Fig. 5.2.

It is given that the tableau in Fig. 5.2 does not give an optimal solution to the LP problem.

Using the tableau in Fig. 5.2 as the starting point for the second stage,

• reduce the tableau, in the Printed Answer Booklet, so that the second stage can be started,

• carry out one iteration of the second stage of the two-stage simplex method, using an

entry in the s₂ column as the pivot element.

It is given that an optimal solution to the LP problem is not found after one iteration of the second stage of the two-stage simplex method.

Determine the range of values of k.