Edexcel D2 (Decision Mathematics 2) 2009 June

1. A company, Kleenitquick, has developed a new stain remover. To promote sales, three salespersons, Jess, Matt and Rachel, will be assigned to three of four department stores \(1,2,3\) and 4 , to demonstrate the stain remover. Each salesperson can only be assigned to one department store.

The table below shows the cost, in pounds, of assigning each salesperson to each department store.

1. Explain why a dummy row needs to be added to the table.
2. Complete Table 1 in the answer book.
3. Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the cost of assigning salespersons to department stores. You must make your method clear and show the table after each iteration.
4. Find the minimum cost.

2. (a) Explain the difference between the classical and the practical travelling salesperson problems. The table below shows the distances, in km, between six data collection points, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\), and F . Rachel must visit each collection point. She will start and finish at A and wishes to minimise the total distance travelled.
(b) Starting at A, use the nearest neighbour algorithm to obtain an upper bound. Make your method clear. Starting at B, a second upper bound of 293 km was found.
(c) State the better upper bound of these two, giving a reason for your answer. By deleting A, a lower bound was found to be 245 km .
(d) By deleting B, find a second lower bound. Make your method clear.
(e) State the better lower bound of these two, giving a reason for your answer.
(f) Taking your answers to (c) and (e), use inequalities to write down an interval that must contain the length of Rachel's optimal route.

3. 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. Reduce the game so that player B has a choice of only two actions.
3. Write down the reduced pay-off matrix for player B.
4. Find the best strategy for player B and the value of the game to player B.

4. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated network. The capacity of each arc is shown on the arc. The numbers in circles represent an initial flow from S to T . Two cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\) are shown in Figure 1.

1. Find the capacity of each of the two cuts.
   (2)
2. Find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow.
   (3)

5. While solving a maximising linear programming problem, the following tableau was obtained.

1. Write down the values of \(\mathrm { x } , \mathrm { y }\) and z as indicated by this tableau.
2. Write down the profit equation from the tableau.

6. The table below shows the cost, in pounds, of transporting one unit of stock from each of three supply points, \(\mathrm { X } , \mathrm { Y }\) and Z to three demand points, \(\mathrm { A } , \mathrm { B }\) and C . It also shows the stock held at each supply point and the stock required at each demand point.

1. This is a balanced problem. Explain what this means.
2. Use the north west corner method to obtain a possible solution.
3. Taking ZA as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear and state your exiting cell.
4. Perform one more iteration of the stepping-stone method to find a further improved solution. You must make your shadow costs, improvement indices, entering cell, exiting cell and route clear.
5. State the cost of the solution you found in part (d).

7. Minty has \(\pounds 250000\) to allocate to three investment schemes. She will allocate the money to these schemes in units of \(\pounds 50000\). The net income generated by each scheme, in \(\pounds 1000\) s, is given in the table below. Minty wishes to maximise the net income. She decides to use dynamic programming to determine the optimal allocation, and starts the table shown in your answer book.

1. Complete the table in the answer book to determine the amount Minty should allocate to each scheme in order to maximise the income. State the maximum income and the amount that should be allocated to each scheme.
2. For this problem give the meaning of the table headings
   1. Stage,
   2. State,
   3. Action.

8. Laura (L) and Sam (S) play a two-person zero-sum game which is represented by the following pay-off matrix for Laura. Formulate the game as a linear programming problem for Laura, writing the constraints as inequalities. Define your variables clearly.