Edexcel D2 (Decision Mathematics 2) 2004 June

1. In game theory explain what is meant by
   1. zero-sum game,
   2. saddle point.
      (Total 4 marks)
   3. In a quiz there are four individual rounds, Art, Literature, Music and Science. A team consists of four people, Donna, Hannah, Kerwin and Thomas. Each of four rounds must be answered by a different team member. The table shows the number of points that each team member is likely to get on each individual round.

   \cline { 2 - 5 } \multicolumn{1}{c|}{}	Art	Literature	Music	Science
   Donna	31	24	32	35
   Hannah	16	10	19	22
   Kerwin	19	14	20	21
   Thomas	18	15	21	23

   Use the Hungarian algorithm, reducing rows first, to obtain an allocation which maximises the total points likely to be scored in the four rounds. You must make your method clear and show the table after each stage.
   (Total 9 marks)

3. The table shows the least distances, in km, between five towns, \(A , B , C , D\) and \(E\). Nassim wishes to find an interval which contains the solution to the travelling salesman problem for this network.

1. Making your method clear, find an initial upper bound starting at \(A\) and using
   1. the minimum spanning tree method,
   2. the nearest neighbour algorithm.

      	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)
      \(A\)	-	153	98	124	115
      \(B\)	153	-	74	131	149
      \(C\)	98	74	-	82	103
      \(D\)	124	131	82	-	134
      \(E\)	115	149	103	134	-

2. By deleting \(E\), find a lower bound.
3. Using your answers to parts (a) and (b), state the smallest interval that Nassim could correctly write down.
   (Total 12 marks)

4. Emma and Freddie play a zero-sum game. This game is represented by the following pay-off matrix for Emma. \(\left( \begin{array} { r r r } - 4 & - 1 & 3
2 & 1 & - 2 \end{array} \right)\)

1. Show that there is no stable solution.
2. Find the best strategy for Emma and the value of the game to her.
3. Write down the value of the game to Freddie and his pay-off matrix.

5. (a) Describe a practical problem that could be solved using the transportation algorithm. A problem is to be solved using the transportation problem. The costs are shown in the table. The supply is from \(A , B\) and \(C\) and the demand is at \(d\) and \(e\). (b) Explain why it is necessary to add a third demand \(f\).
(c) Use the north-west corner rule to obtain a possible pattern of distribution and find its cost. (d) Calculate shadow costs and improvement indices for this pattern.
(e) Use the stepping-stone method once to obtain an improved solution and its cost.
(Total 16 marks)

6. Joan sells ice cream. She needs to decide which three shows to visit over a three-week period in the summer. She starts the three-week period at home and finishes at home. She will spend one week at each of the three shows she chooses travelling directly from one show to the next. Table 1 gives the week in which each show is held. Table 2 gives the expected profits from visiting each show. Table 3 gives the cost of travel between shows. \begin{table}[h] \end{table} Table 2 \begin{table}[h] \end{table} \begin{table}[h] \end{table} It is decided to use dynamic programming to find a schedule that maximises the total expected profit, taking into account the travel costs.

1. Define suitable stage, state and action variables.
2. Determine the schedule that maximises the total profit. Show your working in a table.
3. Advise Joan on the shows that she should visit and state her total expected profit.
   (3) (Total 18 marks)

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

1. Write down the values of the flow \(x\) and the flow \(y\).
2. Obtain the value of the initial flow through the network, and explain how you know it is not maximal.
3. Use this initial flow and the labelling procedure on Diagram 1 below to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow. \section*{Diagram 1} \includegraphics[max width=\textwidth, alt={}, center]{343fdcef-660e-4e8c-bd9c-a7f929dc668e-4_1920_1175_742_450}
   d) Show your maximal flow pattern on Diagram 2. \section*{Diagram 2} \includegraphics[max width=\textwidth, alt={}, center]{343fdcef-660e-4e8c-bd9c-a7f929dc668e-5_679_1102_315_479}
   (2)
4. Prove that your flow is maximal.
   (2)
   (Total 13 marks)

8. 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 was obtained.

1. State, giving your reason, whether this tableau represents the optimal solution.
2. State the values of every variable.
3. Calculate the profit made on each unit of \(y\).

9.
\includegraphics[max width=\textwidth, alt={}, center]{343fdcef-660e-4e8c-bd9c-a7f929dc668e-6_1088_1509_219_285} The diagram above shows a network of roads represented by arcs. The capacity of the road represented by that arc is shown on each arc. The numbers in circles represent a possible flow of 26 from \(B\) to \(L\). Three cuts \(\mathrm { C } _ { 1 } , \mathrm { C } _ { 2 }\) and \(\mathrm { C } _ { 3 }\) are shown on The diagram above.

1. Find the capacity of each of the three cuts.
2. Verify that the flow of 26 is maximal. The government aims to maximise the possible flow from \(B\) to \(L\) by using one of two options.
   Option 1: Build a new road from \(E\) to \(J\) with capacity 5.
   or
   Option 2: Build a new road from \(F\) to \(H\) with capacity 3.
3. By considering both options, explain which one meets the government's aim

10. Flatland UK Ltd makes three types of carpet, the Lincoln, the Norfolk and the Suffolk. The carpets all require units of black, green and red wool. For each roll of carpet, the Lincoln requires 1 unit of black, 1 of green and 3 of red, the Norfolk requires 1 unit of black, 2 of green and 2 of red, and the Suffolk requires 2 units of black, 1 of green and 1 of red. There are up to 30 units of black, 40 units of green and 50 units of red available each day.
Profits of \(\pounds 50 , \pounds 80\) and \(\pounds 60\) are made on each roll of Lincoln, Norfolk and Suffolk respectively. Flatland UK Ltd wishes to maximise its profit. Let the number of rolls of the Lincoln, Norfolk and Suffolk made daily be \(x , y\) and \(z\) respectively.

1. Formulate the above situation as a linear programming problem, listing clearly the constraints as inequalities in their simplest form, and stating the objective function. This problem is to be solved using the Simplex algorithm. The most negative number in the profit row is taken to indicate the pivot column at each stage.
2. Stating your row operations, show that after one complete iteration the tableau becomes

   Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	\(\frac { 1 } { 2 }\)	0	\(1 \frac { 1 } { 2 }\)	1	\(- \frac { 1 } { 2 }\)	0	10
   \(y\)	\(\frac { 1 } { 2 }\)	1	\(\frac { 1 } { 2 }\)	0	\(\frac { 1 } { 2 }\)	0	20
   \(t\)	2	0	0	0	-1	1	10
   \(P\)	-10	0	-20	0	40	0	1600

   You may not need to use all of the tableaux.

   Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row operations
   \(r\)
   \(S\)
   \(t\)
   \(P\)

   Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row operations

3. Explain the practical meaning of the value 10 in the top row.
4. 1. Perform one further complete iteration of the Simplex algorithm.

      Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row operations

      Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row operations

   2. State whether your current answer to part (d)(i) is optimal. Give a reason for your answer.
   3. Interpret your current tableau, giving the value of each variable.
      (8)