Edexcel D2 (Decision Mathematics 2)

1. A company has five machines \(A , B , C , D\) and \(E\), which it can assign to four tasks \(1,2,3\) and 4 . Each task must be assigned to just one machine and each machine may only be assigned to just one task.

The profit, in \(\pounds 100\) s, of using each machine to do each task is given in the table below.

1. Explain why it is necessary to add a dummy column to the table.
   (2)
2. Use the Hungarian algorithm to allocate machines to tasks in order to maximise the total profit. You must make your method clear and show the state of the table after each iteration.
   (7)
   (Total 9 marks)

2. The following transportation problem is to be solved. A possible north-west corner solution is:

1. Use the stepping-stone method once to obtain an improved solution. You must make your shadow costs, improvement indices, entering cell, exiting cell and stepping-stone route clear.
2. Demonstrate that your solution is optimal.
   (3)

3. A two-person zero-sum game is represented by the following pay-off matrix for player A. Find the best strategy for player A and the value of the game.
(Total 7 marks)

4. The table shows the least distances, in km, between six towns \(A , B , C , D , E\) and \(F\).

1. Starting at \(A\), and making your method clear, find an upper bound for the travelling salesman problem using the nearest neighbour algorithm.
2. By deleting \(A\), and all of its arcs, find a lower bound for the travelling salesman problem.
3. Write down an inequality about the length of the optimal route.

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

1. Find the capacity of each of the two cuts and the value of the initial flow.
   (3)
2. Complete the initialisation of the labelling procedure on Figure 1 in the answer book, by entering values along \(\mathrm { SB } , \mathrm { AB } , \mathrm { BE }\) and BG .
   (2)
3. Hence use the labelling procedure to find a maximum flow of 85 through the network. You must list each flow-augmenting path you use, together with its flow.
   (5)
4. Show your flow pattern on Figure 2.
   (2)
5. Prove that your flow is maximal.
   (2)

6. The tableau below is the initial tableau for a maximising linear programming problem.

1. Write down the four equations represented in the initial tableau.
2. Taking the most negative number in the profit row to indicate the pivot column at each stage, perform two complete iterations of the Simplex algorithm. State the row operations that you use.
3. State whether or not your last tableau is optimal. Give a reason for your answer.

7. D2 make industrial robots. They can make up to four in any one month, but if they make more than three they need to hire additional labour at a cost of \(\pounds 300\) per month. They can store up to three robots at a cost of \(\pounds 100\) per robot per month. The overhead costs are \(\pounds 500\) in any month in which work is done. The robots are delivered to buyers at the end of each month. There are no robots in stock at the beginning of January and there should be none in stock at the end of May. The order book for January to May is: Use dynamic programming to determine the production schedule that minimises the costs, showing your working in the table provided in the answer book. State the minimum cost.
(Total 14 marks)