Edexcel D2 (Decision Mathematics 2)

1. \begin{figure}[h] \end{figure} The network in Figure 1 shows the shortest distance by road, in kilometres, between five villages. Find the best achievable upper bound for a tour of the network, of minimum length, using the nearest neighbour algorithm.

2. A school entrance examination consists of three papers - Mathematics, English and Verbal Reasoning. Three teams of markers are to mark one style of paper each. The table below shows the average time, in minutes, taken by each team to mark one script for each style of paper. It is desired that the scripts are marked as quickly as possible.
Formulate this information as a linear programming problem.

1. State your decision variables.
2. Write down the objective function in terms of your decision variables.
3. Write down the constraints, explaining what each one represents.

3. A two-person zero-sum game is represented by the payoff matrix for player \(A\) shown below.

1. Represent the expected payoffs to \(A\) against \(B\) 's strategies graphically and hence determine which strategy is not worth considering for player \(B\).
2. Find the best strategy for player \(A\) and the value of the game.

4. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} A salesman is planning a four-day trip beginning at home and ending at town \(I\). He will spend the first night in town \(A , B\) or \(C\), the second night in town \(D , E\) or \(F\) and the third night in town \(G\) or \(H\). The network in Figure 2 shows the expected net profit, in tens of pounds, that he will gain on each day according to the route he chooses. Use dynamic programming to find the route which should maximise the salesman’s net profit. State the expected profit from using this route.
(10 marks)

5. A construction company has three teams of workers available, each of which is to be assigned to one of four jobs at a site. The following table shows the estimated cost, in tens of pounds, of each team doing each job: Use the Hungarian algorithm to find an allocation of jobs which will minimise the total cost. Show the state of the table after each stage in the algorithm and state the cost of the final assignment.
(13 marks)

6. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} The network in Figure 3 shows the distances, in miles, between a newspaper distributor based at area \(A\), and five areas, \(B , C , D , E\), and \(F\), to which the distributor must deliver newspapers. Each morning a delivery van has to set out from \(A\) and visit each of these areas before again returning to \(A\), and the driver wishes to keep the total mileage to a minimum.

1. Draw a complete network showing the shortest distances between the six areas.
   (3 marks)
2. Obtain a minimum spanning tree for the complete network and hence find an upper bound for the length of the driver's route.
   (5 marks)
3. Improve this upper bound to find an upper bound of less than 55 miles.
4. By deleting \(A\), find a lower bound for the total length of the route.

7. Mrs. Hartley organises the tennis fixtures for her school. On one day she has to send a team of 10 players to a match against school \(A\) and a team of 6 players to a match against school \(B\). She has to select the two teams from a squad that includes 7 players who live in village \(C\), 5 players who live in village \(D\) and 8 players who live in village \(E\). Having a small budget, Mrs. Hartley wishes to minimise the total amount spent on travel. The table below shows the cost, in pounds, for one player to travel from each village to each of the schools they are competing against.

1. Use the north-west corner rule to find an initial solution to this problem.
2. Obtain improvement indices for this initial solution.
3. Use the stepping-stone method to obtain an optimal solution and state the pattern of transportation that this represents. \section*{Please hand this sheet in for marking}

   Stage	State	Action
   \multirow[t]{2}{*}{1}	G	GI
   	H	HI
   \multirow[t]{3}{*}{2}	D	DG DH
   	E	EG \(E H\)
   	F	FG FH
   \multirow[t]{3}{*}{3}	A	AD \(A E\) \(A F\)
   	B	BD BE \(B F\)
   	C	CD CE CF
   4	Home	Home-A Home-B Home-C

   \section*{Please hand this sheet in for marking}
4. 
   \includegraphics[max width=\textwidth, alt={}, center]{4e50371b-0c1c-4b4e-b21d-60858ae160df-8_662_1025_529_440}
5. Sheet for answering question 6 (cont.)