Edexcel D2 (Decision Mathematics 2) 2016 June

1. (a) Explain the difference between the classical travelling salesperson problem and the practical travelling salesperson problem.

The table above shows the least direct distances, in miles, between seven towns, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) and G. Yiyi needs to visit each town, starting and finishing at A, and wishes to minimise the total distance she will travel.
(b) Show that there are two nearest neighbour routes that start from A. State these routes and their lengths.
(c) Starting by deleting A, and all of its arcs, find a lower bound for the length of Yiyi's route.
(d) Use your results to write down the smallest interval which you can be confident contains the optimal length of Yiyi's route.

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

1. List the saturated arcs.
2. State the value of the initial flow.
3. State the capacities of the cuts \(C _ { 1 }\) and \(C _ { 2 }\)
4. By inspection, find a flow-augmenting route to increase the flow by three units. You must state your route.
5. Prove that the new flow is maximal.

3. Four pupils, Alexa, Ewan, Faith and Zak, are to be allocated to four rounds, 1, 2, 3 and 4, in a mathematics competition. Each pupil is to be allocated to exactly one round and each round must be allocated to exactly one pupil. Each pupil has been given a score, based on previous performance, to show how suitable they are for each round. The higher the score the more suitable the pupil is for that round. The scores for each pupil are shown in the table below.

1. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total score. You must make your method clear and show the table after each stage.
   (8)
2. State the maximum total score.

4. A three-variable linear programming problem in \(x , y\) and \(z\) is to be solved. The objective is to maximise the profit, \(P\). The following tableau is obtained after the first iteration.

1. State which variable was increased first, giving a reason for your answer.
2. Perform one complete iteration of the simplex algorithm, to obtain a new tableau, T. Make your method clear by stating the row operations you use.
3. Write down the profit equation given by T .
4. State whether T is optimal. You must use your answer to (c) to justify your answer.

5. The table below shows the cost of transporting one unit of stock from each of four supply points, 1 , 2,3 and 4, to each of three demand points, A, B and C. It also shows the stock held at each supply point and the stock required at each demand point. A minimal cost solution is required.

1. Explain why it is necessary to add a dummy demand point.
2. Add a dummy demand point and appropriate values to Table 1 in the answer book.
3. Use the north-west corner method to obtain a possible solution. After one iteration of the stepping-stone method the table becomes

   	A	B	C	D
   1	15
   2	19	17
   3		3	25
   4	6			14

4. Taking D3 as the entering cell, 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.
5. Determine whether your solution from (d) is optimal. Justify your answer.

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

1. Verify that there is no stable solution to this game.
2. Formulate the game as a linear programming problem for player A. Define your variables clearly. Write the constraints as equations.
3. Write down an initial simplex tableau, making your variables clear.

7. Remy builds canoes. He can build up to five canoes each month, but if he wishes to build more than three canoes in any one month he has to hire an additional worker at a cost of \(\pounds 400\) for that month. In any month when canoes are built, the overhead costs are \(\pounds 150\) A maximum of three canoes can be held in stock in any one month, at a cost of \(\pounds 25\) per canoe per month. Canoes must be delivered at the end of the month. The order book for canoes is There is no stock at the beginning of January and Remy plans to have no stock after the May delivery.

1. Use dynamic programming to determine the production schedule that minimises the costs given above. Show your working in the table provided in the answer book and state the minimum cost.
   (13) The cost of materials is \(\pounds 200\) per canoe and the cost of Remy’s time is \(\pounds 450\) per month. Remy sells the canoes for \(\pounds 700\) each.
2. Determine Remy's total profit for the five-month period.
   (2)
   (Total 15 marks)