Edexcel A Level Further Maths Paper 3D: Decision Mathematics 1 June 2019 question paper 9FM0/3D

2.1 1.7 3.0 1.9 3.2 1.2 3.3 1.4 1.5 0.2

Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 5

The list of numbers is now to be sorted into descending order.

Perform a quick sort on the original list to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.

For a list of n numbers, the quick sort algorithm has, on average, order n log n.

Given that it takes 2.32 seconds to run the algorithm when n = 450

calculate approximately how long it will take, to the nearest tenth of a second, to run the algorithm when n = 11 250. You should make your method and working clear.

[ The total weight of the network is 370]

Figure 1 represents a network of corridors in a building. The number on each arc represents the length, in metres, of the corresponding corridor.

Use Dijkstra’s algorithm to find the shortest path from A to D, stating the path and its length.

On a particular day, Naasir needs to check the paintwork along each corridor. Naasir must find a route of minimum length. It must traverse each corridor at least once, starting at B and finishing at G.

Use an appropriate algorithm to find the arcs that will need to be traversed twice. You must make your method and working clear.

Find the length of Naasir’s route.

On a different day, all the corridors that start or finish at B are closed for redecorating. Naasir needs to check all the remaining corridors and may now start at any vertex and finish at any vertex. A route is required that excludes all those corridors that start or finish at B.

Determine the possible starting and finishing points so that the length of Naasir’s route is minimised. You must give reasons for your answer.

Find the length of Naasir’s new route.

The network in Figure 2 shows the direct roads linking five villages, A, B, C, D and E. The number on each arc represents the length, in miles, of the corresponding road. The roads from A to E and from C to B are one-way, as indicated by the arrows.

Complete the initial distance and route tables for the network provided in the answer book.

Perform the first three iterations of Floyd’s algorithm. You should show the distance table and the route table after each of the three iterations.

Explain how the partially completed final route table can be used to find the shortest route from E to A.

State this route.

Mabintou decides to use the distance table to try to find the shortest cycle that passes through each vertex. Starting at D, she applies the nearest neighbour algorithm to the final distance table.

State the cycle obtained using the nearest neighbour algorithm.

State the length of this cycle.

Interpret the cycle in terms of the actual villages visited.

Prove that Mabintou’s cycle is not optimal.

The total float of activity H is 7 days.

Explain, with detailed reasoning, why x = 11

Determine the missing early event times and late event times, and hence complete Diagram 1 in your answer book.

Each activity requires one worker and the project must be completed in the shortest possible time using as few workers as possible.

Calculate a lower bound for the number of workers needed to complete the project in the shortest possible time.

Schedule the activities using Grid 1 in the answer book.

Draw the activity network described in the precedence table above, using activity on arc. Your activity network must contain only the minimum number of dummies.

Given that all the activities shown in the precedence table have the same duration,

state the critical path for the network.

A linear programming problem in x, y and z is described as follows.

Maximise P = 2x + 2yz

subject to 3x + y + 2z 30

Explain why the Simplex algorithm cannot be used to solve this linear programming problem.

Set up the initial tableau for solving this linear programming problem using the big-M method.

After a first iteration of the big-M method, the tableau is

b.v.	x	y	z	s1	s2	s3	a1	a2	Value
s1	3	0	1.5	1	0	0.25	0		26.25
a1	1	0	1.5	0			1	0.25	11.75
y	0	1	0.5	0	0		0	0.25	3.75
P	M)	0	M	0	M	M	0	0.5 + 0.75M	M

State the value of each variable after the first iteration.

Explain why the solution given by the first iteration is not feasible.

Taking the most negative entry in the profit row to indicate the pivot column,

obtain the most efficient pivot for a second iteration. You must give reasons for your answer.

A shop sells two types of watch, analogue watches and digital watches.

The shop manager knows that, each month, she should order at least 60 watches in total. In addition, at most 80% of the watches she orders must be digital.

Let x be the number of analogue watches ordered and let y be the number of digital watches ordered.

Write down inequalities, in terms of x and y, to model these constraints.

Two further constraints are

Represent all these constraints on Diagram 1 in the answer book. Hence determine, and label, the feasible region, R.

The cost to the shop of ordering an analogue watch is five times the cost of ordering a digital watch. The shop manager wishes to minimise the total cost.

Determine the number of each type of watch the shop manager should order. You must make your method clear.

Given that the minimum total cost of ordering the watches is £4455

determine the cost of ordering one analogue watch and the cost of ordering one digital watch. You must make your method clear.