Edexcel D2 (Decision Mathematics 2)

1. \section*{Figure 1} Figure 1 shows a network of roads connecting six villages \(A , B , C , D , E\) and \(F\). The lengths of the roads are given in km.

1. Complete the table in the answer booklet, in which the entries are the shortest distances between pairs of villages. You should do this by inspection.
   (2) The table can now be taken to represent a complete network.
2. Use the nearest-neighbour algorithm, starting at \(A\), on your completed table in part (a). Obtain an upper bound to the length of a tour in this complete network, which starts and finishes at \(A\) and visits every village exactly once.
3. Interpret your answer in part (b) in terms of the original network of roads connecting the six villages.
4. By choosing a different vertex as your starting point, use the nearest-neighbour algorithm to obtain a shorter tour than that found in part (b). State the tour and its length.

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

1. Determine the play-safe strategy for each player.
2. Verify that there is a stable solution and determine the saddle points.
3. State the value of the game to \(B\). Figure 2 \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{3.} \includegraphics[alt={},max width=\textwidth]{4f494f19-5690-4d9f-8c18-db03d41da203-02_502_990_319_148}
   \end{figure} The network in Fig. 2 shows possible routes that an aircraft can take from \(S\) to \(T\). The numbers on the directed arcs give the amount of fuel used on that part of the route, in appropriate units. The airline wishes to choose the route for which the maximum amount of fuel used on any part of the route is as small as possible. This is the rninimax route.
4. Complete the table in the answer booklet.
5. Hence obtain the minimax route from \(S\) to \(T\) and state the maximum amount of fuel used on any part of this route.
   (2)
   4. Andrew ( \(A\) ) and Barbara ( \(B\) ) play a zero-sum game. This game is represented by the following payoff matrix for Andrew. $$A \left( \begin{array} { c c c } & B &
   3 & 5 & 4
   1 & 4 & 2
   6 & 3 & 7 \end{array} \right)$$
6. Explain why this matrix may be reduced to $$\left( \begin{array} { l l } 3 & 5
   6 & 3 \end{array} \right) .$$
7. Hence find the best strategy for each player and the value of the game.
   5. An engineering company has 4 machines available and 4 jobs to be completed. Each machine is to be assigned to one job. The time, in hours, required by each machine to complete each job is shown in the table below.

   \cline { 2 - 5 } \multicolumn{1}{c|}{}	Job 1	Job 2	Job 3	Job 4
   Machine 1	14	5	8	7
   Machine 2	2	12	6	5
   Machine 3	7	8	3	9
   Machine 4	2	4	6	10

   Use the Hungarian algorithm, reducing rows first, to obtain the allocation of machines to jobs which minimises the total time required. State this minimum time.
   6. The table below shows the distances, in km , between six towns \(A , B , C , D , E\) and \(F\).

   \cline { 2 - 7 } \multicolumn{1}{c|}{}	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)
   \(A\)	-	85	110	175	108	100
   \(B\)	85	-	38	175	160	93
   \(C\)	110	38	-	148	156	73
   \(D\)	175	175	148	-	110	84
   \(E\)	108	160	156	110	-	92
   \(F\)	100	93	73	84	92	-

8. Starting from \(A\), use Prim's algorithm to find a minimum connector and draw the minimum spanning tree. You must make your method clear by stating the order in which the arcs are selected.
9. 1. Using your answer to part (a) obtain an initial upper hound for the solution of the travelling salesman problem.
   2. Use a short cut to reduce the upper bound to a value less than 680 .
10. Starting by deleting \(F\), find a lower bound for the solution of the travelling salesman problem.
    7. A steel manufacturer has 3 factories \(F _ { 1 } , F _ { 2 }\) and \(F _ { 3 }\) which can produce 35,25 and 15 kilotonnes of steel per year, respectively. Three businesses \(B _ { 1 } , B _ { 2 }\) and \(B _ { 3 }\) have annual requirements of 20,25 and 30 kilotonnes respectively. The table below shows the cost \(C _ { i j }\) in appropriate units, of transporting one kilotonne of steel from factory \(F _ { i }\) to business \(B _ { j }\).

    \cline { 3 - 5 } \multicolumn{2}{c|}{}	Business
    \cline { 3 - 5 } \multicolumn{2}{c|}{}	\(B _ { 1 }\)	\(B _ { 2 }\)	\(B _ { 3 }\)
    \multirow{3}{*}{Factory}	\(F _ { 1 }\)	10	4	11
    \cline { 2 - 5 }	\(F _ { 2 }\)	12	5	8
    \cline { 2 - 5 }	\(F _ { 3 }\)	9	6	7

    The manufacturer wishes to transport the steel to the businesses at minimum total cost.
11. Write down the transportation pattern obtained by using the North-West corner rule.
12. Calculate all of the improvement indices \(I _ { i j }\), and hence show that this pattern is not optimal.
13. Use the stepping-stone method to obtain an improved solution.
14. Show that the transportation pattern obtained in part (c) is optimal and find its cost. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{4f494f19-5690-4d9f-8c18-db03d41da203-04_346_922_319_278}
    \end{figure} The network in Fig. 4 models a drainage system. The number on each arc indicates the capacity of that arc, in litres per second.
15. Write down the source vertices. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{4f494f19-5690-4d9f-8c18-db03d41da203-04_341_920_900_278}
    \end{figure} Figure 5 shows a feasible flow through the same network.
16. State the value of the feasible flow shown in Fig. 5. Taking the flow in Fig. 5 as your initial flow pattern,
17. use the labelling procedure on Diagram 1 to find a maximum flow through this network. You should list each flow-augmenting route you use, together with its flow.
18. Show the maximal flow on Diagram 2 and state its value.
19. Prove that your flow is maximal.
    9. T42 Co. Ltd produces three different blends of tea, Morning, Afternoon and Evening. The teas must be processed, blended and then packed for distribution. The table below shows the time taken, in hours, for each stage of the production of a tonne of tea. It also shows the profit, in hundreds of pounds, on each tonne.

    \cline { 2 - 5 } \multicolumn{1}{c|}{}	Processing	Blending	Packing	Profit (£100)
    Morning blend	3	1	2	4
    Afternoon blend	2	3	4	5
    Evening blend	4	2	3	3

    The total times available each week for processing, blending and packing are 35, 20 and 24 hours respectively. T42 Co. Ltd wishes to maximise the weekly profit. Let \(x , y\) and \(z\) be the number of tonnes of Morning, Afternoon and Evening blend produced each week.
20. Formulate the above situation as a linear programming problem, listing clearly the objective function, and the constraints as inequalities. An initial Simplex tableau for the above situation is

    Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
    \(r\)	3	2	4	1	0	0	35
    \(s\)	1	3	2	0	1	0	20
    \(t\)	2	4	3	0	0	1	24
    \(P\)	- 4	- 5	- 3	0	0	0	0

21. Solve this linear programming problem using the Simplex algorithm. Take the most negative number in the profit row to indicate the pivot column at each stage.
    (11) T42 Co. Ltd wishes to increase its profit further and is prepared to increase the time available for processing or blending or packing or any two of these three.
22. Use your answer to part (b) to advise the company as to which stage(s) it should increase the time available.
    (2)
    10. While solving a maximizing linear programming problem, the following tableau was obtained.

    Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
    \(r\)	0	0	\(1 \frac { 2 } { 3 }\)	1	0	\(- \frac { 1 } { 6 }\)	\(\frac { 2 } { 3 }\)
    \(y\)	0	1	\(3 \frac { 1 } { 3 }\)	0	1	\(- \frac { 1 } { 3 }\)	\(\frac { 1 } { 3 }\)
    \(x\)	1	0	- 3	0	- 1	\(\frac { 1 } { 2 }\)	1
    \(P\)	0	0	1	0	1	1	11

23. Explain why this is an optimal tableau.
24. Write down the optimal solution of this problem, stating the value of every variable.
25. Write down the profit equation from the tableau. Use it to explain why changing the value of any of the non-basic variables will decrease the value of \(P\).
    11. A company wishes to transport its products from 3 factories \(F _ { 1 } , F _ { 2 }\) and \(F _ { 3 }\) to a single retail outlet \(R\). The capacities of the possible routes, in van loads per day, are shown in Fig. 5. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{4f494f19-5690-4d9f-8c18-db03d41da203-05_470_766_447_1695}
    \end{figure}
26. On Diagram 1 in the answer booklet add a supersource \(S\) to obtain a capacitated network with a single source and a single sink. State the minimum capacity of each arc you have added.
27. 1. State the maximum flow along \(S F _ { 1 } A B R\) and \(S F _ { 3 } C R\).
    2. Show these maximum flows on Diagram 2 in the answer booklet, using numbers in circles. Taking your answer to part (b)(ii) as the initial flow pattern,
28. 1. use the labelling procedure to find a maximum flow from \(S\) to \(R\). Your working should be shown on Diagram 3. List each flow-augmenting route you find together with its flow.
    2. Prove that your final flow is maximal.
       12. \begin{figure}[h]
       \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{4f494f19-5690-4d9f-8c18-db03d41da203-06_405_791_301_221}
       \end{figure} A company has 3 warehouses \(W _ { 1 } , W _ { 2 }\), and \(W _ { 3 }\). It needs to transport the goods stored there to 2 retail outlets \(R _ { 1 }\) and \(R _ { 2 }\). The capacities of the possible routes, in van loads per day, are shown in Fig 2. Warehouses \(W _ { 1 } , W _ { 2 }\) and \(W _ { 3 }\) have 14, 12 and 14 van loads respectively available per day and retail outlets \(R _ { 1 }\) and \(R _ { 2 }\) can accept 6 and 25 van loads respectively per day.
29. On Diagram 1 on the answer sheet add a supersource \(W\), a supersink \(R\) and the appropriate directed arcs to obtain a single-source, single-sink capacitated network. State the minimum capacity of each arc you have added.
30. State the maximum flow along
    1. \(W \quad W _ { 1 } \quad A \quad R _ { 1 } \quad R\),
    2. \(W W _ { 3 } \quad C \quad R _ { 2 } \quad R\).
31. Taking your answers to part (b) as the initial flow pattern, use the labelling procedure to obtain a maximum flow through the network from \(W\) to \(R\). Show your working on Diagram 2. List each flowaugmenting route you use, together with its flow.
32. From your final flow pattern, determine the number of van loads passing through \(B\) each day. \section*{D2 2003 (adapted for new spec)}
    1. A two person zero-sum game is represented by the following pay-off matrix for player \(A\).

    \cline { 2 - 4 } \multicolumn{1}{c|}{}	B plays I	\(B\) plays II	\(B\) plays III
    \(A\) plays I	- 3	2	5
    \(A\) plays II	4	- 1	- 4

33. Write down the pay off matrix for player \(B\).
34. Formulate the game as a linear programming problem for player \(B\), writing the constraints as equalities and stating your variables clearly.
    2. (a) Explain the difference between the classical and practical travelling salesman problems.
    \includegraphics[max width=\textwidth, alt={}, center]{4f494f19-5690-4d9f-8c18-db03d41da203-06_454_857_737_1736} The network in the diagram above shows the distances, in kilometres, between eight McBurger restaurants. An inspector from head office wishes to visit each restaurant. His route should start and finish at \(A\), visit each restaurant at least once and cover a minimum distance.
35. Obtain a minimum spanning tree for the network using Kruskal's algorithm. You should draw your tree and state the order in which the arcs were added.
36. Use your answer to part (b) to determine an initial upper bound for the length of the route.
37. Starting from your initial upper bound and using an appropriate method, find an upper bound which is less than 135 km . State your tour.

4. Andrew ( \(A\) ) and Barbara ( \(B\) ) play a zero-sum game. This game is represented by the following payoff matrix for Andrew. $$A \left( \begin{array} { c c c } & B &
3 & 5 & 4
1 & 4 & 2
6 & 3 & 7 \end{array} \right)$$

1. Explain why this matrix may be reduced to $$\left( \begin{array} { l l } 3 & 5
   6 & 3 \end{array} \right) .$$
2. Hence find the best strategy for each player and the value of the game.

6. The table below shows the distances, in km , between six towns \(A , B , C , D , E\) and \(F\).

1. Starting from \(A\), use Prim's algorithm to find a minimum connector and draw the minimum spanning tree. You must make your method clear by stating the order in which the arcs are selected.
2. 1. Using your answer to part (a) obtain an initial upper hound for the solution of the travelling salesman problem.
   2. Use a short cut to reduce the upper bound to a value less than 680 .
3. Starting by deleting \(F\), find a lower bound for the solution of the travelling salesman problem.

7. A steel manufacturer has 3 factories \(F _ { 1 } , F _ { 2 }\) and \(F _ { 3 }\) which can produce 35,25 and 15 kilotonnes of steel per year, respectively. Three businesses \(B _ { 1 } , B _ { 2 }\) and \(B _ { 3 }\) have annual requirements of 20,25 and 30 kilotonnes respectively. The table below shows the cost \(C _ { i j }\) in appropriate units, of transporting one kilotonne of steel from factory \(F _ { i }\) to business \(B _ { j }\). The manufacturer wishes to transport the steel to the businesses at minimum total cost.

1. Write down the transportation pattern obtained by using the North-West corner rule.
2. Calculate all of the improvement indices \(I _ { i j }\), and hence show that this pattern is not optimal.
3. Use the stepping-stone method to obtain an improved solution.
4. Show that the transportation pattern obtained in part (c) is optimal and find its cost. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{4f494f19-5690-4d9f-8c18-db03d41da203-04_346_922_319_278}
   \end{figure} The network in Fig. 4 models a drainage system. The number on each arc indicates the capacity of that arc, in litres per second.
5. Write down the source vertices. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{4f494f19-5690-4d9f-8c18-db03d41da203-04_341_920_900_278}
   \end{figure} Figure 5 shows a feasible flow through the same network.
6. State the value of the feasible flow shown in Fig. 5. Taking the flow in Fig. 5 as your initial flow pattern,
7. use the labelling procedure on Diagram 1 to find a maximum flow through this network. You should list each flow-augmenting route you use, together with its flow.
8. Show the maximal flow on Diagram 2 and state its value.
9. Prove that your flow is maximal.
   9. T42 Co. Ltd produces three different blends of tea, Morning, Afternoon and Evening. The teas must be processed, blended and then packed for distribution. The table below shows the time taken, in hours, for each stage of the production of a tonne of tea. It also shows the profit, in hundreds of pounds, on each tonne.

   \cline { 2 - 5 } \multicolumn{1}{c|}{}	Processing	Blending	Packing	Profit (£100)
   Morning blend	3	1	2	4
   Afternoon blend	2	3	4	5
   Evening blend	4	2	3	3

   The total times available each week for processing, blending and packing are 35, 20 and 24 hours respectively. T42 Co. Ltd wishes to maximise the weekly profit. Let \(x , y\) and \(z\) be the number of tonnes of Morning, Afternoon and Evening blend produced each week.
10. Formulate the above situation as a linear programming problem, listing clearly the objective function, and the constraints as inequalities. An initial Simplex tableau for the above situation is

    Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
    \(r\)	3	2	4	1	0	0	35
    \(s\)	1	3	2	0	1	0	20
    \(t\)	2	4	3	0	0	1	24
    \(P\)	- 4	- 5	- 3	0	0	0	0

11. Solve this linear programming problem using the Simplex algorithm. Take the most negative number in the profit row to indicate the pivot column at each stage.
    (11) T42 Co. Ltd wishes to increase its profit further and is prepared to increase the time available for processing or blending or packing or any two of these three.
12. Use your answer to part (b) to advise the company as to which stage(s) it should increase the time available.
    (2)
    10. While solving a maximizing linear programming problem, the following tableau was obtained.

    Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
    \(r\)	0	0	\(1 \frac { 2 } { 3 }\)	1	0	\(- \frac { 1 } { 6 }\)	\(\frac { 2 } { 3 }\)
    \(y\)	0	1	\(3 \frac { 1 } { 3 }\)	0	1	\(- \frac { 1 } { 3 }\)	\(\frac { 1 } { 3 }\)
    \(x\)	1	0	- 3	0	- 1	\(\frac { 1 } { 2 }\)	1
    \(P\)	0	0	1	0	1	1	11

13. Explain why this is an optimal tableau.
14. Write down the optimal solution of this problem, stating the value of every variable.
15. Write down the profit equation from the tableau. Use it to explain why changing the value of any of the non-basic variables will decrease the value of \(P\).
    11. A company wishes to transport its products from 3 factories \(F _ { 1 } , F _ { 2 }\) and \(F _ { 3 }\) to a single retail outlet \(R\). The capacities of the possible routes, in van loads per day, are shown in Fig. 5. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{4f494f19-5690-4d9f-8c18-db03d41da203-05_470_766_447_1695}
    \end{figure}
16. On Diagram 1 in the answer booklet add a supersource \(S\) to obtain a capacitated network with a single source and a single sink. State the minimum capacity of each arc you have added.
17. 1. State the maximum flow along \(S F _ { 1 } A B R\) and \(S F _ { 3 } C R\).
    2. Show these maximum flows on Diagram 2 in the answer booklet, using numbers in circles. Taking your answer to part (b)(ii) as the initial flow pattern,
18. 1. use the labelling procedure to find a maximum flow from \(S\) to \(R\). Your working should be shown on Diagram 3. List each flow-augmenting route you find together with its flow.
    2. Prove that your final flow is maximal.
       12. \begin{figure}[h]
       \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{4f494f19-5690-4d9f-8c18-db03d41da203-06_405_791_301_221}
       \end{figure} A company has 3 warehouses \(W _ { 1 } , W _ { 2 }\), and \(W _ { 3 }\). It needs to transport the goods stored there to 2 retail outlets \(R _ { 1 }\) and \(R _ { 2 }\). The capacities of the possible routes, in van loads per day, are shown in Fig 2. Warehouses \(W _ { 1 } , W _ { 2 }\) and \(W _ { 3 }\) have 14, 12 and 14 van loads respectively available per day and retail outlets \(R _ { 1 }\) and \(R _ { 2 }\) can accept 6 and 25 van loads respectively per day.
19. On Diagram 1 on the answer sheet add a supersource \(W\), a supersink \(R\) and the appropriate directed arcs to obtain a single-source, single-sink capacitated network. State the minimum capacity of each arc you have added.
20. State the maximum flow along
    1. \(W \quad W _ { 1 } \quad A \quad R _ { 1 } \quad R\),
    2. \(W W _ { 3 } \quad C \quad R _ { 2 } \quad R\).
21. Taking your answers to part (b) as the initial flow pattern, use the labelling procedure to obtain a maximum flow through the network from \(W\) to \(R\). Show your working on Diagram 2. List each flowaugmenting route you use, together with its flow.
22. From your final flow pattern, determine the number of van loads passing through \(B\) each day. \section*{D2 2003 (adapted for new spec)}
    1. A two person zero-sum game is represented by the following pay-off matrix for player \(A\).

    \cline { 2 - 4 } \multicolumn{1}{c|}{}	B plays I	\(B\) plays II	\(B\) plays III
    \(A\) plays I	- 3	2	5
    \(A\) plays II	4	- 1	- 4

23. Write down the pay off matrix for player \(B\).
24. Formulate the game as a linear programming problem for player \(B\), writing the constraints as equalities and stating your variables clearly.
    2. (a) Explain the difference between the classical and practical travelling salesman problems.
    \includegraphics[max width=\textwidth, alt={}, center]{4f494f19-5690-4d9f-8c18-db03d41da203-06_454_857_737_1736} The network in the diagram above shows the distances, in kilometres, between eight McBurger restaurants. An inspector from head office wishes to visit each restaurant. His route should start and finish at \(A\), visit each restaurant at least once and cover a minimum distance.
25. Obtain a minimum spanning tree for the network using Kruskal's algorithm. You should draw your tree and state the order in which the arcs were added.
26. Use your answer to part (b) to determine an initial upper bound for the length of the route.
27. Starting from your initial upper bound and using an appropriate method, find an upper bound which is less than 135 km . State your tour.
    3. Talkalot College holds an induction meeting for new students. The meeting consists of four talks: I (Welcome), II (Options and Facilities), III (Study Tips) and IV (Planning for Success). The four department heads, Clive, Julie, Nicky and Steve, deliver one of these talks each. The talks are delivered consecutively and there are no breaks between talks. The meeting starts at 10 a.m. and ends when all four talks have been delivered. The time, in minutes, each department head takes to deliver each talk is given in the table below.

    \cline { 2 - 5 } \multicolumn{1}{c|}{}	Talk I	Talk II	Talk III	Talk IV
    Clive	12	34	28	16
    Julie	13	32	36	12
    Nicky	15	32	32	14
    Steve	11	33	36	10

28. Use the Hungarian algorithm to find the earliest time that the meeting could end. You must make your method clear and show
    1. the state of the table after each stage in the algorithm,
    2. the final allocation.
29. Modify the table so it could be used to find the latest time that the meeting could end.
    4. A two person zero-sum game is represented by the following pay-off matrix for player \(A\).

    \cline { 2 - 4 } \multicolumn{1}{c|}{}	\(B\) plays I	\(B\) plays II	\(B\) plays III
    \(A\) plays I	2	- 1	3
    \(A\) plays II	1	3	0
    \(A\) plays III	0	1	- 3

30. Identify the play safe strategies for each player.
31. Verify that there is no stable solution to this game.
32. Explain why the pay-off matrix above may be reduced to

    \cline { 2 - 4 } \multicolumn{1}{c|}{}	\(B\) plays I	\(B\) plays II	\(B\) plays III
    \(A\) plays I	2	- 1	3
    \(A\) plays II	1	3	0

33. Find the best strategy for player \(A\), and the value of the game.
    5. The manager of a car hire firm has to arrange to move cars from three garages \(A , B\) and \(C\) to three airports \(D , E\) and \(F\) so that customers can collect them. The table below shows the transportation cost of moving one car from each garage to each airport. It also shows the number of cars available in each garage and the number of cars required at each airport. The total number of cars available is equal to the total number required.

    	Airport \(D\)	Airport E	Airport \(F\)	Cars available
    Garage \(A\)	£20	£40	£10	6
    Garage \(B\)	£20	£30	£40	5
    Garage \(C\)	£10	£20	£30	8
    Cars required	6	9	4

34. Use the North-West corner rule to obtain a possible pattern of distribution and find its cost.
35. Calculate shadow costs for this pattern and hence obtain improvement indices for each route.
36. Use the stepping-stone method to obtain an optimal solution and state its cost.
    6. Kris produces custom made racing cycles. She can produce up to four cycles each month, but if she wishes to produce more than three in any one month she has to hire additional help at a cost of \(\pounds 350\) for that month. In any month when cycles are produced, the overhead costs are \(\pounds 200\). A maximum of 3 cycles can be held in stock in any one month, at a cost of \(\pounds 40\) per cycle per month. Cycles must be delivered at the end of the month. The order book for cycles is

    Month	August	September	October	November
    Number of cycles required	3	3	5	2

    Disregarding the cost of parts and Kris' time,
37. determine the total cost of storing 2 cycles and producing 4 cycles in a given month, making your calculations clear. There is no stock at the beginning of August and Kris plans to have no stock after the November delivery.
38. Use dynamic programming to determine the production schedule which minimises the costs, showing your working in the table below.

    Stage	Demand	State	Action	Destination	Value
    \multirow[t]{3}{*}{1 (Nov)}	\multirow[t]{3}{*}{2}	0 (in stock)	(make) 2	0	200
    		1 (in stock)	(make) 1	0	240
    		2 (in stock)	(make) 0	0	80
    \multirow[t]{2}{*}{2 (Oct)}	\multirow[t]{2}{*}{5}	1	4	0	\(590 + 200 = 790\)
    		2	3	0

    The fixed cost of parts is \(\pounds 600\) per cycle and of Kris' time is \(\pounds 500\) per month. She sells the cycles for \(\pounds 2000\) each.
39. Determine her total profit for the four month period.
    (Total 18 marks)
40. Find the value of cuts \(C _ { 1 }\) and \(C _ { 2 }\). Starting with the given feasible flow of 68,
41. use the labelling procedure on Diagram 2 to find a maximal flow through this network. List each flow-augmenting route you use, together with its flow.
    7. \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{4f494f19-5690-4d9f-8c18-db03d41da203-08_499_1011_536_246}
    \end{figure} Figure 1 shows a capacitated, directed network. The unbracketed number on each arc indicates the capacity of that arc, and the numbers in brackets show a feasible flow of value 68 through the network.
42. Add a supersource and a supersink, and arcs of appropriate capacity, to Diagram 1 below. \section*{Diagram 1} \begin{figure}[h]
    \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{4f494f19-5690-4d9f-8c18-db03d41da203-08_451_1013_1274_246}
    \end{figure}
43. Find the values of \(x\) and \(y\), explaining your method briefly. \section*{Diagram 2} \includegraphics[max width=\textwidth, alt={}, center]{4f494f19-5690-4d9f-8c18-db03d41da203-08_438_1010_463_1663}
44. Show your maximal flow on Diagram 3 and state its value. \section*{Diagram 3} \includegraphics[max width=\textwidth, alt={}, center]{4f494f19-5690-4d9f-8c18-db03d41da203-08_437_1006_1105_1665}
45. Prove that your flow is maximal.

9. T42 Co. Ltd produces three different blends of tea, Morning, Afternoon and Evening. The teas must be processed, blended and then packed for distribution. The table below shows the time taken, in hours, for each stage of the production of a tonne of tea. It also shows the profit, in hundreds of pounds, on each tonne. The total times available each week for processing, blending and packing are 35, 20 and 24 hours respectively. T42 Co. Ltd wishes to maximise the weekly profit. Let \(x , y\) and \(z\) be the number of tonnes of Morning, Afternoon and Evening blend produced each week.

1. Formulate the above situation as a linear programming problem, listing clearly the objective function, and the constraints as inequalities. An initial Simplex tableau for the above situation is

   Basic variable	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
   \(r\)	3	2	4	1	0	0	35
   \(s\)	1	3	2	0	1	0	20
   \(t\)	2	4	3	0	0	1	24
   \(P\)	- 4	- 5	- 3	0	0	0	0

2. Solve this linear programming problem using the Simplex algorithm. Take the most negative number in the profit row to indicate the pivot column at each stage.
   (11) T42 Co. Ltd wishes to increase its profit further and is prepared to increase the time available for processing or blending or packing or any two of these three.
3. Use your answer to part (b) to advise the company as to which stage(s) it should increase the time available.
   (2)

10. While solving a maximizing linear programming problem, the following tableau was obtained.

1. Explain why this is an optimal tableau.
2. Write down the optimal solution of this problem, stating the value of every variable.
3. Write down the profit equation from the tableau. Use it to explain why changing the value of any of the non-basic variables will decrease the value of \(P\).

11. A company wishes to transport its products from 3 factories \(F _ { 1 } , F _ { 2 }\) and \(F _ { 3 }\) to a single retail outlet \(R\). The capacities of the possible routes, in van loads per day, are shown in Fig. 5. \begin{figure}[h] \end{figure}

1. On Diagram 1 in the answer booklet add a supersource \(S\) to obtain a capacitated network with a single source and a single sink. State the minimum capacity of each arc you have added.
2. 1. State the maximum flow along \(S F _ { 1 } A B R\) and \(S F _ { 3 } C R\).
   2. Show these maximum flows on Diagram 2 in the answer booklet, using numbers in circles. Taking your answer to part (b)(ii) as the initial flow pattern,
3. 1. use the labelling procedure to find a maximum flow from \(S\) to \(R\). Your working should be shown on Diagram 3. List each flow-augmenting route you find together with its flow.
   2. Prove that your final flow is maximal.

12. \begin{figure}[h] \end{figure} A company has 3 warehouses \(W _ { 1 } , W _ { 2 }\), and \(W _ { 3 }\). It needs to transport the goods stored there to 2 retail outlets \(R _ { 1 }\) and \(R _ { 2 }\). The capacities of the possible routes, in van loads per day, are shown in Fig 2. Warehouses \(W _ { 1 } , W _ { 2 }\) and \(W _ { 3 }\) have 14, 12 and 14 van loads respectively available per day and retail outlets \(R _ { 1 }\) and \(R _ { 2 }\) can accept 6 and 25 van loads respectively per day.

1. On Diagram 1 on the answer sheet add a supersource \(W\), a supersink \(R\) and the appropriate directed arcs to obtain a single-source, single-sink capacitated network. State the minimum capacity of each arc you have added.
2. State the maximum flow along
   1. \(W \quad W _ { 1 } \quad A \quad R _ { 1 } \quad R\),
   2. \(W W _ { 3 } \quad C \quad R _ { 2 } \quad R\).
3. Taking your answers to part (b) as the initial flow pattern, use the labelling procedure to obtain a maximum flow through the network from \(W\) to \(R\). Show your working on Diagram 2. List each flowaugmenting route you use, together with its flow.
4. From your final flow pattern, determine the number of van loads passing through \(B\) each day. \section*{D2 2003 (adapted for new spec)}
   1. A two person zero-sum game is represented by the following pay-off matrix for player \(A\).
5. Explain why a dummy row needs to be added to the table.
6. Complete Table 1 in the answer book.
7. Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the cost of assigning salespersons to department stores. You must make your method clear and show the table after each iteration.
8. Find the minimum cost.
   2. (a) Explain the difference between the classical and the practical travelling salesperson problems. The table below shows the distances, in km, between six data collection points, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\), and F . Vicky must visit each city at least once. She will start and finish at A and wishes to minimise the total cost.
9. Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network.
10. Use your answer to part (a) to help you calculate an initial upper bound for the length of Vicky's route.
11. Show that there are two nearest neighbour routes that start from A . You must make your routes and their lengths clear.
12. State the best upper bound from your answers to (b) and (c).
13. Starting by deleting A , and all of its arcs, find a lower bound for the route length.
    2. A team of four workers, Harry, Jess, Louis and Saul, are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to one task and each task must be done by just one worker. Jess cannot be assigned to task 4.
    The amount, in pounds, that each person would earn while assigned to each task is shown in the table below.
14. Add a dummy demand point and appropriate values to Table 1 in the answer book. Table 2 shows an initial solution given by the north-west corner method.
    Table 3 shows some of the improvement indices for this solution.
15. Calculate the shadow costs and the missing improvement indices and enter them into Table 3 in the answer book.
16. Taking the most negative improvement index to indicate the entering square, use the steppingstone method once to obtain an improved solution. You must make your route clear and state your entering cell and exiting cell.
    3. 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 is obtained. Toby must visit each town at least once. He will start and finish at A and wishes to minimise the total distance.
17. Use the nearest neighbour algorithm, starting at A , to find an upper bound for the length of Toby's route.
18. Starting by deleting A, and all of its arcs, find a lower bound for the route length.
    3. The table below shows the cost, in pounds, of transporting one tonne of concrete from each of three supply depots, \(\mathrm { A } , \mathrm { B }\) and C , to each of four building sites, \(\mathrm { D } , \mathrm { E } , \mathrm { F }\) and G . It also shows the number of tonnes that can be supplied from each depot and the number of tonnes required at each building site. A minimum cost solution is required.
19. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total profit. You must make your method clear and show the table after each stage.
20. State which worker should be allocated to each task and the resulting total profit made.
    2. The table shows the least distances, in km, between six towns, A, B, C, D, E and F. The table shows the least distances, in km, between five hiding places, A, B, C, D and E.
    Agent Goodie has to leave a secret message in each of the hiding places. He will start and finish at A , and wishes to minimise the total distance travelled.
21. Use Prim's algorithm to find a minimum spanning tree for this network. Make your order of arc selection clear.
22. Use your answer to part (a) to determine an initial upper bound for the length of Agent Goodie's route.
23. Show that there are two nearest neighbour routes which start from A . State these routes and their lengths.
24. State the better upper bound from your answers to (b) and (c).
25. Starting by deleting B, and all of its arcs, find a lower bound for the length of Agent Goodie's route.
26. Consider your answers to (d) and (e) and hence state an optimal route. You must ensure that your answers to parts of questions are clearly labelled.
    You should show sufficient working to make your methods clear to the Examiner.
    Answers without working may not gain full credit.
    2. The table 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 three demand points, 1, 2 and 3 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required.
27. Use the north-west corner method to obtain a possible solution. A partly completed table of improvement indices is given in Table 1 in the answer book.
28. Complete Table 1.
29. Taking the most negative improvement index to indicate the entering cell, use the steppingstone method once to obtain an improved solution. You must make your route clear and state your entering cell and exiting cell.
30. State the cost of your improved solution.
    2. (a) Explain the difference between the classical and the practical travelling salesperson problem. Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total earnings. You must make your method clear and show the table after each stage.
    2. The table shows the least times, in seconds, that it takes a robot to travel between six points in an automated warehouse. These six points are an entrance, A, and five storage bins, B, C, D, E and F. The robot will start at A , visit each bin, and return to A . The total time taken for the robot's route is to be minimised.
31. Perform one iteration of the Simplex algorithm to obtain a new tableau, \(T\). State the row operations you use.
32. Write down the profit equation given by \(T\) and state the current values of the slack variables.