Edexcel D2 (Decision Mathematics 2) Specimen

1. \begin{figure}[h] \end{figure} Figure 1 shows a directed, capacitated network where the number on each arc is its capacity. A possible flow is shown from \(S\) to \(T\) and the value in brackets on each arc is the flow in that arc.

1. Find the values of \(x , y\), and \(z\).
   (3)
2. Find, by inspection, the maximal flow from \(S\) to \(T\) and verify that it is maximal.
   (2)

2. 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 initial tableau was obtained.

1. Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the simplex algorithm, to obtain tableau \(T\). State the row operations that you use.
2. Write down the profit equation shown in tableau \(T\).
3. State whether tableau \(T\) is optimal. Give a reason for your answer.

3. Freezy Co. has three factories \(A , B\) and \(C\). It supplies freezers to three shops \(D , E\) and \(F\). The table shows the transportation cost in pounds of moving one freezer from each factory to each outlet. It also shows the number of freezers available for delivery at each factory and the number of freezers required at each shop. The total number of freezers required is equal to the total number of freezers available.

1. Use the north-west corner rule to find an initial solution.
2. Obtain improvement indices for each unused route.
3. Use the stepping-stone method once to obtain a better solution and state its cost.

4. \begin{figure}[h] \end{figure} The network in Figure 2 shows the distances, in km , of the cables between seven electricity relay stations \(A , B , C , D , E , F\) and \(G\). An inspector needs to visit each relay station. He wishes to travel a minimum distance, and his route must start and finish at the same station. By deleting C, a lower bound for the length of the route is found to be 129 km .

1. Find another lower bound for the length of the route by deleting \(F\). State which is the best lower bound of the two.
2. By inspection, complete the table of least distances. The table can now be taken to represent a complete network.
3. Using the nearest-neighbour algorithm, starting at \(F\), obtain an upper bound to the length of the route. State your route.

5. Three warehouses \(W , X\) and \(Y\) supply televisions to three supermarkets \(J , K\) and \(L\). The table gives the cost, in pounds, of transporting a television from each warehouse to each supermarket. The warehouses have stocks of 34,57 and 25 televisions respectively, and the supermarkets require 20, 56 and 40 televisions respectively. The total cost of transporting the televisions is to be minimised. Formulate this transportation problem as a linear programming problem. Make clear your decision variables, objective function and constraints.

6. \begin{figure}[h] \end{figure} A maximin route is to be found through the network shown in Figure 3.
Complete the table in the answer book, and hence find a maximin route.

7. Four salespersons \(A , B , C\) and \(D\) are to be sent to visit four companies 1,2,3 and 4. Each salesperson will visit exactly one company, and all companies will be visited.
Previous sales figures show that each salesperson will make sales of different values, depending on the company that they visit. These values (in \(\pounds 10000\) s) are shown in the table below.

1. Use the Hungarian algorithm to obtain an allocation that maximises the sales. You must make your method clear and show the table after each stage.
2. State the value of the maximum sales.
3. Show that there is a second allocation that maximises the sales.

8. 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. Find the best strategy for player \(A\) and the value of the game to her.
   (Total 11 marks)