Edexcel D2 (Decision Mathematics 2) 2012 June

1. Five workers, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E , are to be assigned to five tasks, \(1,2,3,4\) and 5 . Each worker is to be assigned to one task and each task must be assigned to one worker.

The cost, in pounds, of assigning each person to each task is shown in the table below. The cost is to be minimised.

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

2. The table shows the least distances, in km, between six towns, A, B, C, D, E and F. Toby must visit each town at least once. He will start and finish at A and wishes to minimise the total distance.

1. Use the nearest neighbour algorithm, starting at A , to find an upper bound for the length of Toby's route.
2. Starting by deleting A, and all of its arcs, find a lower bound for the route length.

3. The table below shows the cost, in pounds, of transporting one tonne of concrete from each of three supply depots, \(\mathrm { A } , \mathrm { B }\) and C , to each of four building sites, \(\mathrm { D } , \mathrm { E } , \mathrm { F }\) and G . It also shows the number of tonnes that can be supplied from each depot and the number of tonnes required at each building site. A minimum cost solution is required. The north-west corner method gives the following possible solution. Taking AG as the first entering cell,

1. use the stepping stone method twice to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, routes, entering cells and exiting cells.
2. Determine whether your current solution is optimal. Justify your answer.

4. The tableau below is the initial tableau for a maximising linear programming problem in \(x , y\) and \(z\) which is to be solved.

1. Starting by increasing \(y\), perform one complete iteration of the simplex algorithm, to obtain tableau T. State the row operations you use.
2. Write down the profit equation given by tableau T .
3. Use the profit equation from part (b) to explain why tableau T is optimal.

5. Agent Goodie is planning to break into Evil Doctor Fiendish's secret base. He uses game theory to determine whether to approach the base from air, sea or land.
Evil Doctor Fiendish decides each day which of three possible plans he should use to protect his base. Agent Goodie evaluates the situation. He assigns numbers, negative indicating he fails in his mission, positive indicating success, to create a pay-off matrix. The numbers range from - 3 (he fails in his mission and is captured) to 5 (he successfully achieves his mission and escapes uninjured) and the pay-off matrix is shown below.

1. Reduce the game so that Agent Goodie has only two choices, explaining your reasoning.
2. Use game theory to determine Agent Goodie's best strategy.
3. Find the value of the game to Agent Goodie.

6. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.

1. State the value of the initial flow.
   (1)
2. Complete the initialisation of the labelling procedure on Diagram 1 in the answer book by entering values along \(\mathrm { SB } , \mathrm { BD } , \mathrm { CF }\) and FT .
   (2)
3. Hence use the labelling procedure to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
   (4)
4. Draw a maximal flow pattern on Diagram 2 in your answer book.
   (2)
5. Prove that your flow is maximal.
   (2)

7. Four workers, A, B, C and D, are to be assigned to four tasks, P, Q, R and S. Each worker is to be assigned to exactly one task and each task must be assigned to just one worker. The cost, in pounds, of using each worker for each task is given in the table below. The total cost is to be minimised. Formulate the above situation as a linear programming problem. You must define your decision variables and make the objective function and constraints clear.
(Total 7 marks)

8. A company makes industrial robots. They can make up to four robots in any one month, but if they make more than three they will have to hire additional labour at a cost of \(\pounds 400\) per month.
They can store up to two robots at a cost of \(\pounds 150\) per robot per month.
The overhead costs are \(\pounds 300\) in any month in which work is done.
Robots are delivered to buyers at the end of each month. There are no robots in stock at the beginning of January and there should be none in stock after the April delivery. The order book for robots is Use dynamic programming to determine the production schedule which minimises the costs, showing your working in the table provided in the answer book.
(Total 12 marks)