Edexcel D2 (Decision Mathematics 2) 2005 June

1. 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.

2.
\includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-1_613_1269_1318_392} The network in the diagram 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 better 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.
   (4) (Total 11 marks)

3. 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.
(Total 7 marks)

4. (a) Explain what is meant by a maximin route in dynamic programming, and give an example of a situation that would require a maximin solution.
(3)
\includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-2_700_1392_1069_338} A maximin route is to be found through the network shown in the diagram.
(b) Complete the table in the answer book, and hence find a maximin route.
(9)
(c) List all other maximin routes through the network.
(Total 14 marks)

5. Four salesperson \(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.
   (Total 15 marks)

6.
\includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-3_696_1319_1292_374} This figure shows a capacitated directed network. The number on each arc is its capacity. The numbers in circles show a feasible flow through the network. Take this as the initial flow.

1. On Diagram 1 and Diagram 2 in the answer book, add a supersource \(S\) and a supersink \(T\). On Diagram 1 show the minimum capacities of the arcs you have added. Diagram 2 in the answer book shows the first stage of the labelling procedure for the given initial flow.
2. Complete the initial labelling procedure in Diagram 2.
3. Find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow, and state the maximal flow.
4. Show a maximal flow pattern on Diagram 3.
5. Prove that your flow is maximal.
6. Describe briefly a situation for which this network could be a suitable model.
   (Total 16 marks)
   \includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-4_1486_1963_568_50}

7. (a) Explain briefly what is meant by a zero-sum game. A two person zero-sum game is represented by the following pay-off matrix for player \(A\). (b) Verify that there is no stable solution to this game.
(c) Find the best strategy for player \(A\) and the value of the game to her.
(d) Formulate the game as a linear programming problem for player \(B\). Write the constraints as inequalities and define your variables clearly.
(Total 17 marks)

8. Polly has a bird food stall at the local market. Each week she makes and sells three types of packs \(A , B\) and C. Pack \(A\) contains 4 kg of bird seed, 2 suet blocks and 1 kg of peanuts.
Pack \(B\) contains 5 kg of bird seed, 1 suet block and 2 kg of peanuts.
Pack \(C\) contains 10 kg of bird seed, 4 suet blocks and 3 kg of peanuts.
Each week Polly has 140 kg of bird seed, 60 suet blocks and 60 kg of peanuts available for the packs.
The profit made on each pack of \(A , B\) and \(C\) sold is \(\pounds 3.50 , \pounds 3.50\) and \(\pounds 6.50\) respectively. Polly sells every pack on her stall and wishes to maximise her profit, \(P\) pence. Let \(x , y\) and \(z\) be the numbers of packs \(A , B\) and \(C\) sold each week.
An initial Simplex tableau for the above situation is

1. Explain the meaning of the variables \(r , s\) and \(t\) in the context of this question.
2. Perform one complete iteration of the Simplex algorithm to form a new tableau \(T\). Take the most negative number in the profit row to indicate the pivotal column.
3. State the value of every variable as given by tableau \(T\).
4. Write down the profit equation given by tableau \(T\).
5. Use your profit equation to explain why tableau \(T\) is not optimal. Taking the most negative number in the profit row to indicate the pivotal column,
6. identify clearly the location of the next pivotal element.

9.
\includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-6_540_1291_203_411} This diagram shows a capacitated directed network. The number on each arc is its capacity.

1. State the maximum flow along
   1. SADT,
   2. SCET,
   3. \(S B F T\).
2. Show these maximum flows on Diagram 1 below. \section*{Diagram 1}
   \includegraphics[max width=\textwidth, alt={}]{be329a47-a709-4719-abe6-41d388a6c631-6_561_1187_1283_721}
   Take your answer to part (b) as the initial flow pattern.
3. 1. Use the labelling procedure to find a maximum flow from \(S\) to \(T\). Your working should be shown on Diagram 2 below. List each flow-augmenting route you use, together with its flow. \section*{Diagram 2} \includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-7_718_1525_205_269}
   2. Draw your final flow pattern on Diagram 3 below.
      \includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-7_611_1196_1082_717}
   3. Prove that your flow is maximal.
4. Give an example of a practical situation that could have been modelled by the original network.