Edexcel D2 (Decision Mathematics 2)

1. This question should be answered on the sheet provided.

The table below shows the distances in miles between five villages. Jane lives in village \(A\) and is about to take her daughter's friends home to villages \(B , C , D\) and \(E\). She will begin and end her journey at \(A\) and wishes to travel the minimum distance possible.

1. Obtain a minimum spanning tree for the network and hence find an upper bound for the length of Jane's journey.
2. Using a shortcut, improve this upper bound to find an upper bound of less than 15 miles.
   (2 marks)

2. The payoff matrix for player \(A\) in a two-person zero-sum game with value \(V\) is shown below. Formulate this information as a linear programming problem, the solution to which will give the optimal strategy for player \(B\).

1. Rewrite the matrix as necessary and state the new value of the game, \(v\), in terms of \(V\).
2. Define your decision variables.
3. Write down the objective function in terms of your decision variables.
4. Write down the constraints.

3. This question should be answered on the sheet provided. The table below gives distances, in miles, for a network relating to a travelling salesman problem. Use dynamic programming to find the route which satisfies the wish of the organisers. State the length of the shortest stage on this route.

5. Four athletes are put forward for selection for a mixed stage relay race at a local competition. They may each be selected for a maximum of one stage and only one athlete can be entered for each stage. The average time, in seconds, for each athlete to complete each stage is given below, based on past performances. Use the Hungarian algorithm to find an optimal allocation which will minimise the team's total time. Your answer should show clearly how you have applied the algorithm.

6. The payoff matrix for player \(X\) in a two-person zero-sum game is shown below.

1. Explain why the game does not have a saddle point.
2. Find the optimal strategy for
   1. player \(X\),
   2. player \(Y\).
3. Find the value of the game.

7. A transportation problem has costs, in pounds, and supply and demand, in appropriate units, as given in the transportation tableau below. (c) \section*{Please hand this sheet in for marking}