Edexcel D2 (Decision Mathematics 2) 2018 June

1. Table 1 shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , to each of four demand points, \(1,2,3\) and 4 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution to this transportation problem is required.

\begin{table}[h] \end{table} Table 2 shows an initial solution given by the north-west corner method. \begin{table}[h] \end{table}

1. Explain why a zero has been placed in cell C 2 in Table 2. State the other cell in Table 2 in which the zero could have been placed.
2. State the shadow costs clearly and enter the improvement indices into Table 3 in your answer book. Taking the most negative improvement index to indicate the entering cell,
   [0pt]
3. list the stepping-stone route that should be used to obtain the next solution. You should make clear the cells that are included in your route and state your entering and exiting cells. [You do not need to state the next solution. You do not need to solve this problem.]

2. A two-person zero-sum game is represented by the following pay-off matrix for player A.

1. Identify the play safe strategies for each player.
2. State, giving a reason, whether there is a stable solution to this game.
3. Explain why the game above can be reduced to the following \(3 \times 3\) game.

   - 3	2	5
   - 2	5	4
   2	- 3	- 1

4. Formulate the \(3 \times 3\) game as a linear programming problem for player A, defining your variables clearly and writing the constraints as inequalities.

3. Five workers, A, B, C, D and E, are to be assigned to five tasks, 1, 2, 3, 4 and 5 . Each worker must be assigned to only one task and each task must be done by only one worker. The cost, in pounds, of assigning each worker to each task is shown in the table below. The cost of assigning worker D to task 4 is \(\pounds x\), where \(x > 38\) The total cost is to be minimised.

1. Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the cost. You must make your method clear and show the table after each stage.
   (8)
2. Find the minimum total cost.
   (1) Workers A and D decide that they do not like the task they have been allocated and are allowed to swap tasks with each other. The other three allocations are unchanged. The cost now of allocating the five workers to the five tasks is now \(\pounds 5\) more than the minimum cost found in (b).
3. Calculate the value of \(x\). You must show your working.
   (2)

4. \begin{figure}[h] \end{figure} Figure 1 represents a system of pipes through which fluid can flow from the source node, S , to the sink node, T. The labelling procedure has been applied to Figure 1, and the numbers on the arrows, either side of each arc, show the excess capacities and potential backflows. Currently, no fluid is flowing through the system.

1. Calculate the capacity of the cut that passes through arcs \(\mathrm { GT } , \mathrm { EG } , \mathrm { DE } , \mathrm { BE } , \mathrm { FE }\) and FH .
2. Explain why arc GT can never be full to capacity when fluid is flowing through the system.
3. Apply the labelling procedure to Diagram 1 in the answer book to show the maximum flow along SBET. State the amount that can flow along this route.
4. Use the labelling procedure to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
5. State the maximum flow through the system and find a cut to show that this flow is maximal.
6. Show the maximum flow on Diagram 2 in the answer book.

5. The initial tableau for a linear programming problem in \(x , y\) and \(z\) is shown below. The objective function to be maximised is \(P = 4 x + 2 y + k z\), where \(k\) is a positive constant.

1. Using the information in the tableau, write down the three constraints as inequalities.
2. By increasing \(x\), perform one complete iteration of the simplex algorithm to obtain tableau \(T _ { 1 }\) and state the row operations you use.
3. Given that \(T _ { 1 }\) is not optimal, find an inequality for the value of \(k\).
4. Perform a second complete iteration of the simplex algorithm to obtain tableau \(T _ { 2 }\) and state the row operations you use.
5. Given that \(T _ { 2 }\) is optimal, find a second inequality for the value of \(k\).
6. State the final value of each variable and give an expression for the final value of \(P\) in terms of \(k\).
7. Hence find the range of possible values of \(P\).

6. Jonathan is an author who is planning his next book tour. He will visit four countries over a period of four weeks. He will visit just one country each week. He will leave from his home, S , 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 each week. \begin{table}[h] 2. 3.

1. You may not need to use all of these tables

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   	1	2	3	4	5
   A
   B
   C
   D
   E

   4. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{4abb2325-b9df-4849-b08c-7db465fe85e0-18_1056_1572_1450_185} \captionsetup{labelformat=empty} \caption{Diagram 1}
   \end{figure} Maximum flow along SBET: \(\_\_\_\_\) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{4abb2325-b9df-4849-b08c-7db465fe85e0-19_1043_1572_1505_187} \captionsetup{labelformat=empty} \caption{Diagram 2}
   \end{figure} 5.

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	- 2	- 6	1	1	0	0	40
   \(s\)	2	3	2	0	1	0	80
   \(t\)	1	2	2	0	0	1	50
   \(P\)	- 4	- 2	\(- k\)	0	0	0	0

   You may not need to use all of these tableaux

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value	Row Ops
   \(P\)

   6.

   Stage	State	Action	Destination	Value
   0	I	IS	S	\(30 - 5 = 25 ^ { * }\)

   Stage	State	Action	Destination	Value

   END