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

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

each activity.

Carry out a forward pass and a backward pass through the activity network, showing the

early event time and the late event time at each vertex of the network.

State the critical activities of the project.

Calculate the total float for activity E.

The list below shows the sizes of eleven items.

15 4 23 16 2 12 14 11 20 13 22

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

into bins that have a capacity of 40.

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

You should use the first value as the pivot for each sublist.

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 40.

By considering the answers to parts (a) and (c) explain why first fit is an example of a

heuristic algorithm.

The quick sort algorithm is to be used to sort a different list of eight numbers into descending order. After one pass through the list the quick sort algorithm produces the following list

18 22 17 19 14 11 4 13

State, with a reason, which number was used as a pivot for the first pass.

Explain why the simplex algorithm cannot be applied to the initial tableau in Fig. 3.1 to solve

the LP problem.

The tableau in Fig. 3.1 is reformulated so the simplex method can be used to solve the LP problem.

The simplex method is applied to the reformulated problem. After two iterations a computer produces the tableau in Fig. 3.2.

Perform a third iteration of the simplex method.

Explain how the answer to part (b) shows that the solution obtained after the third iteration is

optimal.

State the optimal values of x, y and z.

State the corresponding minimum value of P for the original LP problem.

The flow chart shows an algorithm that produces a numerical approximation for the integral

Work through the algorithm using the inputs a = 1, b = 3 and n = 4. Record the exact values

of c and d every time they change.

By considering the percentage difference between the exact value of the integral given in part (b) and the approximation found in part (a), comment on the accuracy of the algorithm in this

case.

Explain how to adapt the algorithm to produce a numerical approximation for the integral

Explain why

• two of the constraint equations are equal to 1,

• five of the constraint equations are equal to 0.

Using the vertices given in the Printed Answer Booklet draw a directed network with 13 arcs to represent the information given in the formulation above. Two of the arcs are directed and the rest are undirected. The arcs from A and the arcs to G may be regarded as being

undirected.

Apply Dijkstra’s algorithm to the network drawn in part (b), to find the length of the

shortest path from A to G.

Write down the shortest path from A to G.

An eighth vertex, X, is added to the network. The table in Fig. 5.1 shows the corresponding weights between each pair of vertices for which there is a connecting arc.

It is given that x is a positive integer and all arcs from vertex X are undirected.

State what changes need to be made to the original LP formulation when X is included as an

eighth vertex in the network.

For a certain value of x, the complete LP for the network with eight vertices was run in an LP solver and the output is shown in the table in Fig. 5.2.

State the maximum value of x that is consistent with this solution.

A computer takes 0.018 seconds to solve a shortest path problem on a network with eight vertices using Dijkstra’s algorithm.

Approximately how long will it take the computer to solve a shortest path problem on a

network with eight hundred vertices using Dijkstra’s algorithm?

An incomplete initial tableau for a two-stage simplex solution for a maximisation integer linear programming (ILP) problem, in x, y and z where x, y, z ⩾ 0, is shown below.

Formulate the information given in the tableau as an ILP problem by

• stating the objective function for the original ILP problem,

• listing the constraints in terms of x, y and z only.

In the Printed Answer Booklet, complete the top row of the initial tableau for the ILP

problem.

Use a 2-D graphical method, with axes representing x and y, to determine

• the maximum value of P,

• the corresponding integer values of x, y and z.