Edexcel D2 (Decision Mathematics 2) 2011 June

1. \begin{figure}[h] \end{figure} The network in Figure 1 shows the distances, in km, between six towns, A, B, C, D, E and F. Mabintou needs to visit each town. She will start and finish at A and wishes to minimise the total distance travelled.

1. By inspection, complete the two copies of the table of least distances in your answer book.
2. Starting at A, use the nearest neighbour algorithm to find an upper bound for the length of Mabintou's route. Write down the route which gives this upper bound.
3. Starting by deleting A, and all of its arcs, find a lower bound for the route length.

2. The table below shows the cost of transporting one unit of stock from each of four supply points, 1 , 2, 3 and 4, to each of 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. A minimal cost solution is required.

1. Add a dummy demand point and appropriate values to Table 1 in the answer book. Table 2 shows an initial solution given by the north-west corner method.
   Table 3 shows some of the improvement indices for this solution. \begin{table}[h]

   	A	B	C	D
   1	20
   2	15	7
   3		18	2
   4			28	10

   \captionsetup{labelformat=empty} \caption{Table 2}
   \end{table} \begin{table}[h]

   	A	B	C	D
   1		- 13		- 9
   2			- 11
   3
   4	1	- 7

   \captionsetup{labelformat=empty} \caption{Table 3}
   \end{table}
2. Calculate the shadow costs and the missing improvement indices and enter them into Table 3 in the answer book.
3. Taking the most negative improvement index to indicate the entering square, use the steppingstone method once to obtain an improved solution. You must make your route clear and state your entering cell and exiting cell.

3. 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 tableau is obtained.

1. Write down the profit equation represented in the tableau.
2. Taking the most negative number in the profit row to indicate the pivot column at each stage, solve this linear programming problem. Make your method clear by stating the row operations you use.
3. State the value of the objective function and of each variable.

4. Laura and Sam play a zero-sum game. This game is represented by the following pay-off matrix for Laura. Find the best strategy for Laura and the value of the game to her.

5. \begin{figure}[h] \end{figure} Figure 2 shows a capacitated directed network. The number on each arc is its capacity. \begin{figure}[h] \end{figure} Figure 3 shows an initial flow through the same network.

1. State the values of flows \(a , b\) and \(c\), and the value of the initial flow.
2. By entering values along HG, HT and FG, complete the labelling procedure on Diagram 1 in the answer book.
3. Find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
4. State the value of the maximum flow through the network.
5. Show your maximum flow on Diagram 2 in the answer book.
6. Prove that your flow is maximal.

6. Three workers, \(\mathrm { P } , \mathrm { Q }\) and R , are to be assigned to three tasks, A, B and C. Each worker must be assigned to just one task and each task must be assigned to just one worker.
Table 1 shows the cost of using each worker for each task. The total cost is to be minimised. \begin{table}[h] \end{table}

1. Formulate the above situation as a linear programming problem. You must define your decision variables and make the objective and constraints clear.
   You are not required to solve the problem. Table 2 shows the profit gained by using each worker for each task. The total profit is to be maximised. \begin{table}[h]

   	Task A	Task B	Task C
   Worker P	33	37	31
   Worker Q	32	36	40
   Worker R	41	35	38

   \captionsetup{labelformat=empty} \caption{Table 2}
   \end{table}
2. Modify Table 2 in the answer book so that the Hungarian Algorithm could be used to find the maximum total profit. You are not required to solve the problem.
   (2)
   (Total 9 marks)

7. Patrick is to take orders for his company's products. He will visit four countries over the next four weeks.
He will visit just one country each week.
He will leave from his office in London and will only return there after visiting the four countries.
He will travel directly from one country to the next.
He wishes to determine a schedule of four countries to visit. Table 1 shows the countries he could visit in each week. \begin{table}[h] \end{table} Table 2 shows the value of the orders, in \(\pounds 100\) s, he expects to take in each country. \begin{table}[h] \end{table} Table 3 shows the cost, in \(\pounds 100\) s, of travelling between the various countries. \begin{table}[h] \end{table} The expected income is the value of the expected orders minus the cost of travel. It is decided to use dynamic programming to find a schedule that maximises the total expected income for these four weeks.

1. Complete the table in the answer book to determine the optimal expected income.
2. State Patrick's two optimal schedules.