Edexcel D2 (Decision Mathematics 2) 2019 June

1. The table above shows the least distances, in km, between six towns, A, B, C, D, E and F. Jas needs to visit each town, starting and finishing at D , and wishes to minimise the total distance she travels.

1. Starting at D , use the nearest neighbour algorithm to obtain an upper bound for the length of the route. You must state your route and its length.
2. Starting by deleting D , and all of its arcs, find a lower bound for the route length.

2. Table 1 shows the cost, in pounds, of transporting one unit of stock from each of three supply points, \(\mathrm { A } , \mathrm { B }\) and C , to each of four demand points, 1, 2, 3 and 4 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required. \begin{table}[h] \end{table} Table 2 shows an initial solution given by the north-west corner method. \begin{table}[h] \end{table}

1. Taking A4 as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear.
2. Taking the most negative improvement index to indicate the entering cell, use the stepping-stone method once to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, route, entering cell and exiting cell.
3. Determine whether your current solution is optimal, giving a reason for your answer.
4. State the cost of your current solution.

3. Five friends have rented a house that has five bedrooms. They each require their own bedroom. The table below shows how each friend rated the five bedrooms, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E , where 0 is low and 10 is high. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total of all the ratings. You must make your method clear and show the table after each stage.
(Total 8 marks)

4. Eugene and Stephen play a zero-sum game. The pay-off matrix shows the number of points that Eugene scores for each combination of strategies.

1. Find the play-safe strategies for each of Eugene and Stephen, and hence show that this zero-sum game does not have a stable solution.
2. Suppose that Eugene knows that Stephen will use his play-safe strategy. Explain why Eugene should change from his play-safe strategy. You should state as part of your answer which strategy Eugene should now play.
3. Formulate the game as a linear programming problem for Stephen. Define your variables clearly. Write the constraints as equations.

5. A linear programming problem in \(x , y\) and \(z\) is described as follows. Maximise \(P = 2 x + 3 y + z\)
subject to \(\quad 2 y - 3 z \leqslant 30\) $$\begin{array} { r } - 3 x + y + z \leqslant 60
x + 4 y - z \leqslant 80 \end{array}$$

1. Complete the initial tableau in the answer book for this linear programming problem.
   (3)
2. Taking the most negative number in the profit row to indicate the pivot column, 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.
   (5)
3. Write down the profit equation given by T and state the values of the slack variables given by T . The following tableau is obtained after further iterations.

   Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	0	2	-3	1	0	0	30
   \(s\)	0	13	-2	0	1	3	300
   \(x\)	1	4	-1	0	0	1	80
   \(P\)	0	5	-3	0	0	2	160

4. Explain why no optimal solution can be found by applying the simplex algorithm to the above tableau.

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.
2. 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.
3. Complete the initialisation of the labelling procedure on Diagram 2 in the answer book by entering values along the new arcs from S to T , and along \(\operatorname { arcs } \mathrm { S } _ { 1 } \mathrm {~B}\) and \(\mathrm { AT } _ { 1 }\)
4. 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.
5. Draw a maximal flow pattern on Diagram 3 in the answer book.
6. Prove that your flow is maximal.

7. A company has purchased a plot of land and has decided to build four holiday homes, A, B, C and D, on the land at the rate of one home per year. The company expects that the construction costs each year will vary, depending on which houses have already been constructed and which house is currently under construction. The expected construction costs, in thousands of pounds, are shown in the table below. \begin{table}[h] \end{table} 2. You may not need to use all of these tables \begin{table}[h] \end{table} 3. You may not need to use all of these tables 4. 5. (a) You may not need to use all of these tableaux 6. (a) Value of initial flow
(b) and (c)
\includegraphics[max width=\textwidth, alt={}, center]{e0c66144-9e34-42fc-9f40-a87a49331483-20_725_1251_404_349} \section*{Diagram 1} \section*{Diagram 2} (d)
(e)
\includegraphics[max width=\textwidth, alt={}, center]{e0c66144-9e34-42fc-9f40-a87a49331483-21_714_1385_1306_283} \section*{Diagram 3} (f)
7. (a)