Edexcel D2 (Decision Mathematics 2) 2014 June

1. Four bakeries, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , supply bread to four supermarkets, \(\mathrm { P } , \mathrm { Q } , \mathrm { R }\) and S . The table gives the cost, in pounds, of transporting one lorry load of bread from each bakery to each supermarket. It also shows the number of lorry loads of bread at each bakery and the number of lorry loads of bread required at each supermarket. The total cost of transportation is to be minimised.

1. Use the north-west corner method to obtain a possible solution. A partly completed table of improvement indices is given in Table 1 in the answer book.
2. Complete Table 1.
3. Taking the most negative improvement index to indicate the entering cell, use the steppingstone method once to obtain an improved solution. You must make your route clear and state your entering cell and exiting cell.
4. State the cost of your improved solution.

2. (a) Explain the difference between the classical and the practical travelling salesperson problem. The table above shows the least distances, in km, between six towns, A, B, C, D, E and F. Keith needs to visit each town, starting and finishing at A , and wishes to minimise the total distance he will travel.
(b) Starting at A, use the nearest neighbour algorithm to obtain an upper bound. You must state your route and its length.
(c) Starting by deleting A, and all of its arcs, find a lower bound for the route length.
(d) Use your results to write down the smallest interval which you are confident contains the optimal length of the route.

3. A two-person zero-sum game is represented by the following pay-off matrix for player A.

1. Starting by reducing player B's options, find the best strategy for player B.
2. State the value of the game to player B.

4. The tableau below is the initial tableau for a three-variable linear programming problem in \(x , y\) and \(z\). The objective is to maximise the profit, \(P\).

1. Taking the most negative number in the profit row to indicate the pivot column at each stage, perform two complete iterations of the simplex algorithm to obtain tableau T. Make your method clear by stating the row operations you use.
2. Write down the profit equation given by T .
3. Use your answer to (b) to determine whether T is optimal, justifying your answer.

5. \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. 1. Add a supersource, S , and a supersink, T , and corresponding arcs to Diagrams 1 and 2, in the answer book.
   2. Enter the flow value and appropriate capacity on each of the arcs you have added to Diagram 1.
2. Complete the initialisation of the labelling procedure on Diagram 2 by entering values along the new arcs from \(S\) and \(T\), and along \(A B , A D\) and \(D _ { 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. Draw a maximal flow pattern on Diagram 3 in the answer book.
5. Prove that your flow is maximal.

6. Four workers, A, B, C and D, are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to just one task and each task must be done by just one worker. Worker C cannot do task 4 and worker D cannot do task 1. The cost of assigning each worker to each task is shown 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.

7. Susie has hired a team of four workers who can make three types of toy. The total number of toys the team can produce will depend on which toys they make, and on how many workers are assigned to make each type of toy. The table shows how many of each toy would be made if different numbers of workers were assigned to make them. Each worker is to be assigned to make just one type of toy and all four workers are to be assigned. Susie wishes to maximise the total number of toys produced.

1. Use dynamic programming to determine the allocation of workers which maximises the total number of toys made. You should show your working in the table provided in the answer book.
   (12)
2. State the maximum total number of toys produced by this team.
   (1)
   (Total 13 marks)