Edexcel D2 (Decision Mathematics 2)

1. A team of gardeners is called in to attend to the grounds of a stately home. The three gardeners will each be assigned to one of three areas, the lawns, the hedgerows and the flower beds. The table below shows the estimated time, in hours, it will take each gardener to do each job.

The team wishes to complete the tasks in the least total time.
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 and explain what each one represents.

2. This question should be answered on the sheet provided. A pool player is to play in four tournaments. Some of the tournaments take place simultaneously and the player has to choose one of each of the following: $$\begin{array} { l l } 1 ^ { \text {st } } \text { tournament: } & A , B \text { or } C ,
2 ^ { \text {nd } } \text { tournament: } & D , E \text { or } F ,
3 ^ { \text {rd } } \text { tournament: } & G , H \text { or } I ,
4 ^ { \text {th } } \text { tournament: } & J , K \text { or } L \end{array}$$ Each tournament has six rounds and the player estimates how well he will do in each tournament based on which tournament he plays before it. The table below shows his expectations with each number indicating the round he expects to reach and a "7" indicating he expects to win the tournament. He wishes to choose the tournaments such that his worst performance is as good as possible. Use dynamic programming to find which tournaments he should play.
(10 marks) Turn over

3. Four people are contributing to the entertainment section of an email magazine. For one issue reviews are required for a film, a musical, a ballet and a concert such that each person reviews one show. The people in charge of the magazine will pay each person's expenses and the cost, in pounds, for each reviewer to attend each show are given below. Use the Hungarian algorithm to find an optimal assignment which minimises the total cost. State the total cost of this allocation.
(10 marks)

4. The payoff matrix for player \(A\) in a two-person zero-sum game is shown below.

1. Explain why the game does not have a saddle point.
2. Using a graphical method, find the optimal strategy for player \(B\).
3. Find the optimal strategy for player \(A\).
4. Find the value of the game.

5. A carpet manufacturer has two warehouses, \(W _ { 1 }\) and \(W _ { 2 }\), which supply carpets for three sales outlets, \(S _ { 1 } , S _ { 2 }\) and \(S _ { 3 }\). At one point \(S _ { 1 }\) requires 40 rolls of carpet, \(S _ { 2 }\) requires 23 rolls of carpet and \(S _ { 3 }\) requires 37 rolls of carpet. At this point \(W _ { 1 }\) has 45 rolls in stock and \(W _ { 2 }\) has 40 rolls in stock. The following table shows the cost, in pounds, of transporting one roll from each warehouse to each sales outlet: The company's manager wishes to supply the 85 rolls that are in stock such that transportation costs are kept to a minimum.

1. Use the north-west corner rule to obtain an initial solution to the problem.
2. Calculate improvement indices for the unused routes.
3. Use the stepping-stone method to obtain an optimal solution. Turn over

6. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} A band is going on tour to play gigs in six towns, including their home town, \(A\). The network in Figure 1 shows the distances, in miles, between the various towns. The band must begin and end their tour at \(A\) and visit each of the other towns once, and they wish to keep the total distance travelled as small as possible.

1. By inspection, draw a complete network showing the shortest distances between the towns.
2. Use your complete network and the nearest neighbour algorithm, starting at \(A\), to find an upper bound for the total distance travelled.
3. 1. Use your complete network to obtain and draw a minimum spanning tree and hence obtain another upper bound for the total distance travelled.
   2. Improve this upper bound using two shortcuts to find an upper bound below 225 miles.
4. By deleting \(A\), find a lower bound for the total distance travelled.
5. State an interval of as small a width as possible within which \(d\), the minimum distance travelled, in miles, must lie. \section*{Please hand this sheet in for marking}

   Stage	Previous tournament	Current tournament
   \multirow[t]{3}{*}{1}	G	J K L
   	\(H\)	J K L
   	I	J K L
   \multirow[t]{3}{*}{2}	D	G H I
   	\(E\)	G H I
   	\(F\)	G H I
   \multirow[t]{3}{*}{3}	A	D E F
   	\(B\)	D E F
   	C	D E F
   4	None	A B C

   \section*{Please hand this sheet in for marking}
6. 
   \includegraphics[max width=\textwidth, alt={}, center]{073926c5-03cc-41d4-82bf-315740ead663-8_684_992_461_427}
7. \section*{Sheet for answering question 6 (cont.)}
8. 2. \(\_\_\_\_\)
10. \(\_\_\_\_\)