OCR GCE AS Level Further Maths B (MEI) Modelling with Algorithms (optional - choose any two of Y411/Y412/Y413/Y414) June 2025 question paper Y413

A network has ten vertices, A to J. The table shows the distances between each pair of vertices for which there is a connecting arc.

Apply the tabular form of Prim’s algorithm to the network, starting at A, to find a minimum spanning tree for the network.

Your solution should contain the following.

• The order in which the arcs are selected

• The total length of the arcs in the minimum spanning tree

The list below shows the sizes of eleven items.

28 25 19 32 18 22 3 12 20 7 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 50.

Show the result of applying the first fit decreasing algorithm to pack items with the sizes

listed above into bins that have a capacity of 50.

A computer takes 4.7 × 10^-8 seconds to pack 50 items with sizes 100, 99, 98, …, 53, 52, 51 into bins that have a capacity of 100 using the first fit decreasing algorithm.

Calculate approximately how long it will take the same computer to pack 1 000 000 items with sizes 2 000 000, 1 999 999, 1 999 998, …, 1 000 003, 1 000 002, 1 000 001 into bins that

have a capacity of 2 000 000 using the first fit decreasing algorithm.

Explain why vertex A should be chosen as the starting vertex for the algorithm.

On the copy of the network in the Printed Answer Booklet, apply Dijkstra’s algorithm

once to find the length of the shortest route from F to C via A.

State the corresponding shortest route from F to C via A.

Determine the number of nodes in the complete graph with 1431 arcs.

In this question you must show detailed reasoning.

A simply connected graph G has eight nodes of orders 1, 1, 2, 3, 3, 4, 4 and x.

• Determine the three possible values of x.

• Use the nodes in the Printed Answer Booklet to draw an example of G for each of these

three values of x.

Explain why the maximum possible flow along DE must be less than 43 litres per minute.

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

Calculate the capacity of cut α.

Explain why partitioning the vertices into sets {S, A, D, E, T}, {B, C, F} does not give a cut.

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

Write down the required constraint in the LP formulation regarding the flow through

vertex D.

Write down the required constraint in the LP formulation regarding the flow along arc

AD.

The LP formulation for the system was run in a solver and some of the output is shown in the table.

Complete the diagram in the Printed Answer Booklet to show the maximum flow

through the system.

State the maximum value of the flow through the system.

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

The capacity of pipe SD is increased to x litres per minute. In doing so, the maximum flow through the system is increased as much as possible. The capacities of the other pipes in the system remain unchanged.

Find the least possible value of x.

State the corresponding maximum possible flow through the system.

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

The LP problem is reformulated into standard form. The reformulated problem consists of a linear objective function P (that is to be maximised) and constraints in terms of x and y.

The tableau after the first iteration of the simplex method, is given in Table 6.1.

Table 6.1

State the column that contains the pivot value for the first iteration. You must give a reason

for your answer.

Perform the second iteration of the simplex method. Give each entry as an exact value.

The tableau after a third iteration of the simplex method, is given in Table 6.2.

Table 6.2

The diagram shows the constraints of the reformulated LP problem. The feasible region, R, is the unshaded region together with its boundaries. Three vertices, A, B, and C, of R are also shown.

Write down the coordinates of A, B and C.

You are given that the reformulation of the original LP into standard form was done using the substitutions X = - 2 - x, Y = y and Q = P + 16.

Determine the maximum value of Q, and the corresponding values of X and Y.

The diagram shows an activity network for a project. Each activity is represented by an arc. The expressions in brackets show the duration of these activities in hours. The early event times and late event times are shown at each vertex.

Complete the tables in the Printed Answer Booklet to show the immediate predecessors for

each activity.

State the minimum completion time for the project.

State the critical activities of the project.

A student is tasked with finding the durations of activities E, H and I. The student knows the following information regarding the activities in the project.

• The sum of the durations of all the activities in the project is at least 79 hours.

• The durations of activities E, H and I must satisfy the early event times and late event times shown in the activity network.

• The combined duration, in hours, of activities E and H must be as small as possible.

Formulate the student’s task as an LP problem in x and y.

By representing the feasible region for x and y graphically, find the durations of activities E,

H and I.