Edexcel D2 (Decision Mathematics 2)

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

Find the optimal strategy for each player and the value of the game.

2. A supplier has three warehouses, \(A , B\) and \(C\), at which there are 42,26 and 32 crates of a particular cereal respectively. Three supermarkets, \(D , E\) and \(F\), require 29, 47 and 24 crates of the cereal respectively. The supplier wishes to minimise the cost in meeting the requirements of the supermarkets. The cost, in pounds, of supplying one crate of the cereal from each warehouse to each supermarket is given in the table below. 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. This question should be answered on the sheet provided. A couple are making the arrangements for their wedding. They are deciding whether to have the ceremony at their church, a local castle or a nearby registry office. The reception will then be held in a marquee, at the castle or at a local hotel. Both the castle and hotel offer catering services but the couple are also considering using Deluxe Catering or Cuisine, who can both provide the food at any venue. \begin{figure}[h] \end{figure} The network in Figure 1 shows the costs incurred (including transport), in hundreds of pounds, according to the choice the couple make for each stage of the day. Use dynamic programming to find how the couple can minimise the total cost of their wedding and state the total cost of this arrangement.
(9 marks)

4. This question should be answered on the sheet provided. A travelling salesman problem relates to the network represented by the following table of distances in kilometres. You may assume that the network satisfies the triangle inequality. Showing your method clearly, use

1. the nearest neighbour algorithm, beginning with \(A\),
2. Prim's algorithm with \(H\) deleted,
   to show that the minimum distance travelled, \(d \mathrm {~km}\), satisfies the inequality \(357 \leq d \leq 371\).
   (11 marks)

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

1. Using a graphical method, find the optimal strategy for player \(X\).
2. Find the optimal strategy for player \(Y\).
3. Find the value of the game.

6. Four sales representatives ( \(R _ { 1 } , R _ { 2 } , R _ { 3 }\) and \(R _ { 4 }\) ) are to be sent to four areas ( \(A _ { 1 } , A _ { 2 } , A _ { 3 }\) and \(A _ { 4 }\) ) such that each representative visits one area. The estimated profit, in tens of pounds, that each representative will make in each area is shown in the table below. Use the Hungarian method to obtain an allocation which will maximise the total profit made from the visits. Show the state of the table after each stage in the algorithm.
(13 marks)

7. A distributor has six warehouses. At one point the distributor needs to move 25 lorries from warehouses \(W _ { 1 } , W _ { 2 }\) and \(W _ { 3 }\) to warehouses \(W _ { \mathrm { A } } , W _ { \mathrm { B } }\) and \(W _ { \mathrm { C } }\) for the minimum possible cost. The transportation tableau below shows the unit cost, in tens of pounds, of moving a lorry between two warehouses, and the relevant figures regarding the number of lorries available or required at each warehouse.

1. Write down the initial solution given by the north-west corner rule.
2. Obtain improvement indices for the unused routes.
3. Use the stepping-stone method to find an improved solution and state why it is degenerate.
4. Placing a zero in cell \(( 2,2 )\), show that the improved solution is optimal and state the transportation pattern.
5. Find the total cost of the optimal solution. \section*{Please hand this sheet in for marking}

   Stage	State	Destination	Cost	Total cost
   \multirow[t]{3}{*}{1}	Marquee	Deluxe Cuisine
   	Castle	Deluxe Castle Cuisine
   	Hotel	Deluxe Cuisine Hotel
   \multirow[t]{3}{*}{2}	Church	Marquee Castle Hotel
   	Castle	Marquee Castle
   	Registry Office	Marquee Castle Hotel
   3	Home	Castle Church Registry

   \section*{Please hand this sheet in for marking}

   1. 	A	B	\(C\)	D	\(E\)	\(F\)	\(G\)	\(H\)
      A	-	85	59	31	47	52	74	41
      B	85	-	104	73	51	68	43	55
      C	59	104	-	54	62	88	61	45
      D	31	73	54	-	40	59	65	78
      E	47	51	62	40	-	56	71	68
      \(F\)	52	68	88	59	56	-	53	49
      \(G\)	74	43	61	65	71	53	-	63
      \(H\)	41	55	45	78	68	49	63	-

   2. 	A	\(B\)	\(C\)	D	\(E\)	\(F\)	\(G\)	\(H\)
      A	-	85	59	31	47	52	74	41
      B	85	-	104	73	51	68	43	55
      C	59	104	-	54	62	88	61	45
      D	31	73	54	-	40	59	65	78
      E	47	51	62	40	-	56	71	68
      \(F\)	52	68	88	59	56	-	53	49
      G	74	43	61	65	71	53	-	63
      \(H\)	41	55	45	78	68	49	63	-