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

The values below represent the weights of eleven suitcases, in kg.

23 15 17 10 35 18 12 21 22 11 8

Show the result of applying the first fit algorithm to pack the weights into containers that can

hold a maximum of 50 kg.

Show the result of applying the first fit decreasing algorithm to pack the weights into

containers that can hold a maximum of 50 kg.

Give a reason why the number of containers used for the packing of the suitcases in part (b)

is optimal.

The table shows the distance, in kilometres, along the direct roads between eight towns, A to H. A dash (-) indicates that there is no direct road linking the towns.

Use Dijkstra’s algorithm to find the shortest path from A to E for the network shown in the

table.

Apply the tabular form of Prim’s algorithm on the diagram in the Printed Answer Booklet, starting at vertex A, to find the total length of the arcs in the minimum

spanning tree for the network shown in the table.

On the vertices provided in the Printed Answer Booklet draw the minimum spanning

tree for this network.

Write down the length of the shortest path from A to F which passes through all the towns

except D.

A computer takes 0.016 secs to solve the minimum connector problem on the network shown in the table using Prim’s algorithm.

Approximately how long will it take the computer to solve the minimum connector problem

on a network with 1000 edges using Prim’s algorithm?

A directed network consists of eight nodes, S, A, B, C, D, E, F and T, and seventeen arcs. The arcs represent a system of pipes through which a fluid flows continuously from the source S to a sink T. The weight of each arc is the corresponding capacity of that pipe in litres per minute.

The following LP formulation can be used to find the maximum flow from S to T in this network.

Maximise SA + SB + SC + SD

subject to SA + BA - AE - AT = 0 SB + CB - BA - BE - BF - BT = 0 SC + DC - CB - CF = 0 SD - DC - DF = 0 AE + BE - EF - ET = 0 BF + CF + DF + EF - FT = 0 SA ⩽ 25, SB ⩽ 61, SC ⩽ 37, SD ⩽ 35, AE ⩽ 25, AT ⩽ 38, BA ⩽ 39, BE ⩽ 40, BF ⩽ 17, BT ⩽ 49, CB ⩽ 12, CF ⩽ 26, DC ⩽ 28, DF ⩽ 19, EF ⩽ 25, ET ⩽ 27, FT ⩽ 32

Complete the diagram in the Printed Answer Booklet to show the directed network

represented in the above LP formulation.

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

Calculate the capacity of cut α.

By considering the objective function of the LP and the answer to part (b), explain why the

maximum flow through the network cannot be equal to the capacity of cut α.

The LP formulation was run in an online solver and some of the output is shown below.

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.

It is decided to reverse the flow in pipe CB so that fluid can flow directly from B to C, instead of C to B. The capacity of the pipe is unchanged. No other pipes are changed.

Explain what changes would be required to the LP formulation due to this modified

constraint on the flow in pipe BC.

A student is trying to draw a triangle XYZ subject to the following constraints.

• Angle X must be at most 10° smaller than angle Z.

• Angle Y must be at least twice the size of angle Z.

Furthermore, the student wishes to maximise the size of angle Z.

Let x, y, and z represent the size (in degrees) of angle X, Y and Z respectively.

Complete the initial tableau in the Printed Answer Booklet so that the two-stage simplex method may be used to solve this problem in x, y, and z.

Your tableau should only contain one surplus variable and one artificial variable.

You must show all your working and you are not required to solve the problem.

The table in Fig. 5.1 lists the immediate predecessors for each of the eleven activities in a project.

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

contain exactly 3 dummy activities.

Each of the eleven activities in the table requires exactly one worker.

The diagram in Fig. 5.2 shows how three people can complete the project in the minimum time. Each column in the diagram represent 1 hour. If a box is blank the person is resting for that 1 hour.

State the critical activities of the project.

State the minimum project completion time.

For the remainder of this question, it may be assumed that there is no restriction on the number of workers available to complete the project.

Complete the table in the Printed Answer Booklet to show the total float for each activity.

A twelfth activity L is added to the project. Activity L can only begin once activity G is completed, and no activity depends on its completion.

It is given that the duration of activity L is 9 hours.

State the new minimum project completion time.

State the new critical activities.

A maximisation LP problem in x, y and z is to be solved.

The tableau after the 1^st iteration of the simplex method is shown below.

State the value of the objective function after this 1^st iteration.

Explain how the tableau shows that the pivot value for the 1^st iteration came from a value

from the y column.

By considering the equations in the tableau, formulate the original LP problem. You should state the objective and list the constraints as simplified inequalities with integer coefficients.

Perform the 2^nd iteration of the simplex method, using the tableau in the Printed Answer

Booklet, choosing the pivot from the x column and giving each entry as an exact value.

After three iterations of the simplex method an optimal solution to the LP problem is obtained and the following three equations are found.

State the optimal values of x, y and z.

Determine the corresponding value of the objective function.