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

State the number of arcs in the complete graph with 6 nodes.

State the minimum number of arcs in a simply connected graph with 6 nodes.

Using the nodes in the Printed Answer Booklet, draw the graph described by the

incidence matrix below.

A B C D E

State the order of node C.

A process for finding a square root of the positive real number N is described by the flow chart

Explain why the process described by the flow chart is an example of an algorithm.

Work through the algorithm using the inputs N = 73 and A = 8. Record the values of A and B, to at least 9 decimal places where necessary, every time they change.

Give the final output correct to 7 decimal places.

The inputs remain as N = 73 and A = 8. The box in the algorithm where B is defined needs adapting to ensure that the negative square root of 73 is the output.

Explain how to adapt the box.

A student claims that if the statement A > 0 is removed from the algorithm, so that there is no longer a restriction on the value of A, the algorithm can still be used to find a square root of N.

Explain whether the student’s claim is correct.

In Fig. 3 the weights of the arcs represent distances.

Dijkstra’s algorithm is to be used once to find both the shortest path from A to C and the shortest path from C to G.

State which vertex should be chosen as the start vertex.

On the copy of the network in the Printed Answer Booklet, apply Dijkstra’s algorithm (with the starting vertex stated in part (a)) to find both the shortest path from A to C and

the shortest path from C to G.

State the weight of the shortest route from A to F via C.

Apply Prim’s algorithm, starting at A, to find the minimum spanning tree for the network in Fig. 3.

• State the order in which the arcs were included in the tree.

• Draw the minimum spanning tree.

Fig. 4.1 shows an activity network for a project. The arc weights show activity duration in hours.

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

each activity.

It is given that the duration of activity B is x hours, and the duration of activity J is y hours where x and y are integers and

0 < x < 5 and 0 < y < 7.

Carry out a forward pass and a backward pass through the entire network to find the following.

• The minimum completion time for the project

• The critical activities

It is given that the total float for activity J is 4 hours.

Determine the value of y.

Each activity requires one worker.

Fig. 4.2 shows a partly completed resource histogram containing the eight activities A to H in which each of the eight activities begins at their earliest possible start time.

State the value of x.

Complete the resource histogram for the project by adding the remaining four activities I, J, K and L to the copy of Fig. 4.2 in the Printed Answer Booklet.

Each of the four activities should begin at their earliest possible start time.

Draw a schedule to show how three workers can complete the project in the minimum completion time. Each box in the Printed Answer Booklet represents 1 hour. For each worker, write the letter of the activity they are doing in each box, or leave the box

blank if the worker is not required for that 1 hour.

Fig. 5.1 represents a system of pipes through which a fluid flows continuously from a source S to a sink T. The weight on the arcs show the capacities of the pipes in litres per minute.

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

Calculate the capacity of cut α.

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

Calculate the capacity of cut β.

Using only the capacities of cuts α and β, explain what can be deduced about the maximum

possible flow through the system.

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

Explain why a possible objective function for the LP formulation is to maximise

SA + SB + CE + CF.

Write down the required constraint in the LP formulation regarding the flow through vertex F.

The LP formulation for the network was run in a solver and some of the output is shown in Fig. 5.2.

Explain how the output in Fig. 5.2 gives a flow of 106 litres per minute through the system of

pipes.

Use the diagram in the Printed Answer Booklet to show how a flow of 106 litres per minute

can be achieved.

Use a suitable cut to show that a flow of 106 litres per minute is the maximum possible flow

through the system of pipes.

Each Monday morning a company has its weekly delivery of milk. The milk comes in three types, whole, semi-skimmed and skimmed.

The company manager knows that each week she should order the following.

• At most 32 litres in total of semi-skimmed and skimmed milk.

• At least three times as much semi-skimmed milk as skimmed milk.

Furthermore, at least 10% of the milk should be skimmed milk.

The cost of one litre of whole milk is 55p, the cost of one litre of semi-skimmed milk is 50p, and the cost of one litre of skimmed milk is 40p.

In total the company has a budget of £50 to spend each week on milk.

Let x represent the number of litres of whole milk. Let y represent the number of litres of semi-skimmed milk. Let z represent the number of litres of skimmed milk.

The company manager wants to maximise the total amount of milk ordered each week.

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

• Show how the constraints for the problem have been made into equations using slack

variables.

After two iterations of the simplex method a computer produces the tableau below.

Perform a third iteration of the simplex method.

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

iteration is optimal.

State the number of litres of each type of milk the company manager should order each

week.

Calculate how much of the weekly milk budget will not be spent.

Due to an increase in the amount of milk consumed, the manager believes that it may be possible, with a weekly budget of at least £50, to order exactly 40 litres in total of semi-skimmed and skimmed milk each week.

She still plans on ordering at least three times as much semi-skimmed milk as skimmed milk, and that at least 10% of the milk ordered should still be skimmed.

Furthermore, she still wishes to maximise the total amount of milk ordered each week.

The two-stage simplex method is to be used to solve this modified problem.

• Formulate the modified constraints as equations.

• Define the new objective function.

In both cases, you are required to define the variables you use. Note that you do not need to

re-state the original objective function or any constraints that are unchanged.