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

Fig. 1 shows a network. The weights on the arcs are distances.

Apply Dijkstra’s algorithm to the copy of the network in the Printed Answer Booklet to find the shortest path from A to H.

State each of the following.

• the shortest path

• its length

A problem requires a spanning tree that must include the arcs AD and GH.

The arcs AD and GH are chosen first. Apply Kruskal’s algorithm to the ordered list of arcs in the

Printed Answer Booklet to complete the tree. You should draw your tree and give its total length.

How could you modify the network in Fig. 1 so that Prim’s algorithm would find a spanning tree that

includes arcs AD and GH?

Fig. 2 represents a system of one-way roads through which traffic flows from a source, S, to a sink, T. The weights on the arcs show the capacities of the roads in cars per minute.

Explain why the maximum possible flow along FG must be less than 23 cars per minute.

(A) The cut partitions the vertices into the sets {S, C}, {A, B, D, E, F, G, T}. Calculate the capacity

(B) The cut partitions the vertices into the sets {S, A, C, F, G}, {B, D, E, T}. Calculate the capacity

Given that one of or is a minimum cut, write down the maximum possible flow from S to T.

On a particular morning

• road GE is closed for repairs,

• roads FB, AD and DE are full to capacity.

Use the diagram in the Printed Answer Booklet to show that the maximum possible flow from part (iii)

is still achievable when GE is not used and FB, AD and DE are full to capacity.

Sort the following list of six numbers using the above algorithm

12 34 15 23 10 25

You should only show the result at the end of each pass.

The algorithm is now applied to a list of n numbers.

Find, when n = 6,

• the minimum possible number of comparisons needed,

• the maximum possible number of comparisons needed.

The number of comparisons is used as a measure of the complexity of the above algorithm.

Determine, in the worst case, the complexity of the algorithm in terms of n.

Explain the purpose of each of the following lines from the LP formulation.

(A) Minimise 18AW + 11AX + … + 18CZ

(B) AW + AX + AY + AZ = 20

The LP is run in an Online LP Solver and the following output is obtained.

OBJECTIVE FUNCTION VALUE

1) 726.0000

VARIABLE VALUE REDUCED COST

The REDUCED COST value indicates by how much more the unit cost needs to be reduced for that particular transportation link to become part of the optimal solution. For example, the unit cost of transporting from B to Z would need to be reduced by at least £900 if BZ was to become part of the solution.

(A) Interpret the output to give a solution to the transportation problem.

(B) State the minimum total cost of delivering all the required stock.

It is later found that the unit cost of transporting goods from supplier B to depot X is only £1500

State the effect this change has on

(A) the objective function in the original LP formulation

(B) the constraints in the original LP formulation.

The modified LP problem (where the unit cost of transporting goods from B to X was reduced to £1500) is run in the same Online LP Solver and the following output is obtained.

OBJECTIVE FUNCTION VALUE

1) 726.0000

VARIABLE VALUE REDUCED COST

In an attempt to cut the minimum total cost of delivering the required stock, supplier C decides to reduce the unit cost of supplying one of the four depots by £150. You can assume that the unit cost of transporting goods from B to X is still only £1500 and that no other supplier is going to cut their unit costs.

(A) Determine which of the four depots should have its transportation costs cut by supplier C to

reduce the minimum total cost of delivery. Give a reason for your answer.

(B) What is the new minimum total cost of delivering all the stock when supplier C makes this

change?

Fig. 5 shows an activity network for a project. Each activity is represented by an arc. The early event times and late event times are shown at each vertex.

State the minimum completion time for the project.

It is given that

• the project contains two critical paths that both include activity C,

• the total float for activity I is 3.

(A) Complete, as far as possible, the table in the Printed Answer Booklet showing the duration of

each activity. Note that you will not be able to determine the duration for one of the activities.

(B) Explain why one of the activity durations could not be determined in part (ii) (A).

• 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 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 one iteration of the two-stage simplex method the tableau in Fig. 6.1 is produced.

Explain how the tableau in Fig. 6.1 shows that the first stage has been completed.

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

• reduce the tableau so that the second stage can be started,

• carry out the first iteration of the second stage of the two-stage simplex method, using an entry in

the s₂ column as the pivot element.

State which variables are now basic after this first iteration of the second stage of the two-stage simplex

method.

The final tableau is shown in Fig. 6.2.

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