Edexcel A Level Further Maths Paper 4D: Decision Mathematics 2 June 2022 question paper 9FM0/4D

Four workers, A, B, C and D, are to be assigned to four tasks, 1, 2, 3 and 4. Each task must be assigned to just one worker and each worker must do only one task.

The cost of assigning each worker to each task is shown in the table below.

The total cost is to be minimised.

Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the total cost. You must make your method clear and show the table after each stage.

State the minimum total cost.

The general solution of the second order recurrence relation

is given by

where A and B are arbitrary non‑zero constants.

Find the value of k₁ and the value of k₂

Given that u₀ = u₁ = 1

find the value of A and the value of B.

The table below shows the transport options, usual travel times, possible delay times and corresponding probabilities of delay for a journey. All times are in minutes.

Draw a decision tree to model the transport options and the possible outcomes.

State the minimum expected travel time and the corresponding transport option indicated by the decision tree.

Figure 1 shows a capacitated, directed network of pipes. The uncircled number on each arc represents the capacity of the corresponding pipe. The numbers in circles represent an initial flow.

List the saturated arcs.

State the value of the initial flow.

Explain why arc FT cannot be full to capacity.

State the capacity of cut C₁ and the capacity of cut C₂

By inspection find one flow‑augmenting route to increase the flow by three units. You must state your route.

Prove that, once the flow‑augmenting route found in part (e) has been applied, the flow is maximal.

A standard transportation problem is described in the linear programming formulation below.

Let x_ij be the number of units transported from i to j

where i i {A, B, C, D}

Minimise P x_AR + 17x_AS + 24x_AT + 15x_BR + 29x_BS + 32x_BT

subject to

Given that the problem is balanced,

state the value of k.

transportation problem.

Use the north‑west corner method to obtain the cost of an initial solution to this transportation problem.

Perform one iteration of the stepping‑stone method to obtain an improved solution. You must make your method clear by showing the route and the

• shadow costs

• improvement indices

• entering cell and exiting cell.

Bernie makes garden sheds. He can build up to four sheds each month.

If he builds more than two sheds in any one month, he must hire an additional worker at a cost of £250 for that month.

In any month in which sheds are made, the overhead costs are £35 for each shed made that month.

A maximum of three sheds can be held in storage at the end of any one month, at a cost of £80 per shed per month.

Sheds must be delivered at the end of the month.

The order schedule for sheds is

There are no sheds in storage at the beginning of January and Bernie plans to have no sheds left in storage after the May delivery.

Use dynamic programming to determine the production schedule that minimises the costs given above. Complete the working in the table provided in the answer book and state the minimum cost.

A two person zero‑sum game is represented by the pay‑off matrix for player A shown above. It is given that k is an integer.

Show that Q is the play‑safe option for player A regardless of the value of k.

Given that Z is the play‑safe option for player B,

determine the range of possible values of k. You must make your working clear.

Explain why player B should never play option X. You must make your reasoning clear.

Player A intends to make a random choice between options Q, R and S, choosing option Q with probability p₁, option R with probability p₂ and option S with probability p₃

Player A wants to find the optimal values of p₁, p₂ and p₃ using the Simplex algorithm.

Given that k –4, player A formulates the following objective function for the corresponding linear program.

Maximise P = V, where V = the value of the original game + 4

Formulate the constraints of the linear programming problem for player A. You should write the constraints as equations.

Write down an initial Simplex tableau, making your variables clear.

The Simplex algorithm is used to solve the linear programming problem. It is given that in the final Simplex tableau the optimal value of p = , the optimal value of p = and all the slack variables are zero.

Determine the value of k, making your method clear.

The owner of a new company models the number of customers that the company will have at the end of each month. The owner assumes that

• a constant proportion, p (where 0 p 1), of the previous month’s customers will be retained for the next month

• a constant number of new customers, k, will be added each month.

Let u_n (where n 1) represent the number of customers that the company will have at the end of n months.

The company has 5000 customers at the end of the first month.

By setting up a first order recurrence relation for u_{n+ 1} in terms of u_n, determine an expression for u_n in terms of n, p and k.

The owner believes that 95% of the previous month’s customers will be retained each month and that there will be 10 000 new customers each month.

According to the model, the company will first have at least 135 000 customers by the end of the m th month.

Using logarithms, determine the value of m.