Dynamic Programming

4 Monica and Vladimir play a zero-sum game. The game is represented by the following pay-off matrix for Monica.

5. (a) In game theory, explain the circumstances under which column \(( x )\) dominates column \(( y )\) in a two-person zero-sum game. Liz and Mark play a zero-sum game. This game is represented by the following pay-off matrix for Liz. (b) Verify that there is no stable solution to this game.
(c) Find the best strategy for Liz and the value of the game to her. The game now changes so that when Liz plays 1 and Mark plays 3 the pay-off to Liz changes from 2 to
4. All other pay-offs for this zero-sum game remain the same.
(d) Explain why a graphical approach is no longer possible and briefly describe the method Liz should use to determine her best strategy.
(2) (Total 16 marks)

8 John and Danielle play a zero-sum game which does not have a stable solution. The game is represented by the following pay-off matrix for John. Find the optimal mixed strategy for John.

3

1. Set up a dynamic programming tabulation to find the minimum weight route from ( \(0 ; 0\) ) to ( \(4 ; 0\) ) on the following directed network. \includegraphics[max width=\textwidth, alt={}, center]{406831f5-74a3-415e-8849-2c381bfe47f4-03_707_1342_1594_443} Give the route and its total weight.
2. Explain carefully how the route is obtained directly from the values in the table, without referring to the network.

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)

3. \begin{figure}[h] \end{figure} In Figure 1 the weight of \(\operatorname { arc } \mathrm { SB }\) is denoted by \(x\) where \(x \geqslant 0\)

1. Explain why Dijkstra's algorithm cannot be used on the directed network in Figure 1.
   (1) It is given that the minimum weight route from S to T passes through B .
2. Use dynamic programming to find
   1. the range of possible values of \(x\)
   2. the minimum weight route from S to T .
      (12)

In game theory explain what is meant by

1. zero-sum game, [2]
2. saddle point. [2]

(Total 4 marks)

In game theory explain what is meant by

1. zero-sum game, [2]
2. saddle point. [2]

(Total 4 marks)

Bilal and Mayon play a zero-sum game. The game is represented by the following pay-off matrix for Bilal, where \(x\) is an integer.

	Mayon
	\(\mathbf{M_1}\)	\(\mathbf{M_2}\)	\(\mathbf{M_3}\)
\(\mathbf{B_1}\)	\(-2\)	\(-1\)	\(1\)
Bilal \quad \(\mathbf{B_2}\)	\(4\)	\(-3\)	\(1\)
\(\mathbf{B_3}\)	\(-1\)	\(x\)	\(0\)

The game has a stable solution.

1. Show that there is only one possible value for \(x\) Fully justify your answer. [6 marks]
2. State the value of the game for Bilal. [1 mark]

4. The table below gives the pay-off matrix for a zero-sum game between two players, Aljaz and Brendan. The values in the table show the pay-offs for Aljaz. You may not need to use all of these tables
You may not need to use all the rows and columns \includegraphics[max width=\textwidth, alt={}, center]{bbdfa492-6578-484a-a0b5-fcdb78020b83-06_437_832_1201_139}

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.

6. A two person zero-sum game is represented by the pay-off matrix for player A, shown above.

1. Explain, with justification, why this matrix may be reduced to a \(3 \times 3\) matrix by removing option S from player A's choices.
2. Verify that there is no stable solution to the reduced game. Player A intends to make a random choice between options \(\mathrm { Q } , \mathrm { R }\) and T , choosing option Q with probability \(p _ { 1 }\), option R with probability \(p _ { 2 }\) and option T with probability \(p _ { 3 }\) Player A wants to find the optimal values of \(p _ { 1 } , p _ { 2 }\) and \(p _ { 3 }\) using the Simplex algorithm. Player A formulates the following linear programme, writing the constraints as inequalities. Maximise \(P = V\), where \(V =\) the value of original game + 3 $$\begin{aligned} \text { subject to } & V \leqslant 4 p _ { 1 } + 7 p _ { 2 } + 6 p _ { 3 } \\ & V \leqslant 8 p _ { 1 } + p _ { 3 } \\ & V \leqslant 6 p _ { 1 } + 4 p _ { 2 } + 3 p _ { 3 } \\ & p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1 \\ & p _ { 1 } \geqslant 0 , p _ { 2 } \geqslant 0 , p _ { 3 } \geqslant 0 , V \geqslant 0 \end{aligned}$$
3. Explain why \(V\) cannot exceed any of the following expressions $$4 p _ { 1 } + 7 p _ { 2 } + 6 p _ { 3 } \quad 8 p _ { 1 } + p _ { 3 } \quad 6 p _ { 1 } + 4 p _ { 2 } + 3 p _ { 3 }$$
4. Explain why it is necessary to use the constraint \(p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1\) The Simplex algorithm is used to solve the linear programming problem.
   Given that the optimal value of \(p _ { 1 } = \frac { 7 } { 11 }\) and the optimal value of \(p _ { 3 } = 0\)
5. calculate the value of the game to player A .
   (3) Player B intends to make a random choice between options \(\mathrm { X } , \mathrm { Y }\) and Z , choosing option X with probability \(q _ { 1 }\), option Y with probability \(q _ { 2 }\) and option Z with probability \(q _ { 3 }\)
6. Determine the optimal strategy for player B, making your working clear.

6 Set up a dynamic programming tabulation to find the maximin route from ( \(0 ; 0\) ) to ( \(3 ; 0\) ) on the following directed network. \includegraphics[max width=\textwidth, alt={}, center]{76486ad4-c00e-4e0b-9527-6f13f9222dbb-7_883_1323_390_411}

1 Answer this question on the insert provided. The table shows a partially completed dynamic programming tabulation for solving a maximin problem.

1. Complete the last two columns of the table in the insert.
2. State the maximin value and write down the maximin route.

This question should be answered on the sheet provided. A rally consisting of four stages is being planned. The first stage will begin at A and the last stage will end at L. Various routes are being considered, with the end of one stage being the start of the next. The organisers want the shortest stage to be as long as possible. The table below shows the length, in miles, of each of the possible stages.

			Finishing point
		C	D	E	F	G	H	I
\multirow{3}{*}{Starting point}	A	1	4.5	13	10	8	11	4
	B					5	10.5
	C					9	6
	D					12	7	15
	E
	F							5
	G							8
	H							10
	I
	J
	K

Finishing point
J	K	L
		2
9	2	3
2	9
		5
		6
		10

Use dynamic programming to find the route which satisfies the wish of the organisers. State the length of the shortest stage on this route. [10 marks]

1. State Bellman's principle of optimality. [1]
2. Explain what is meant by a minimax route. [1]
3. Describe a practical problem that would require a minimax route as its solution. [2]

(Total 4 marks)

1. State Bellman's principle of optimality. [1]
2. Explain what is meant by a minimax route. [1]
3. Describe a practical problem that would require a minimax route as its solution. [2]

(Total 4 marks)

6. \begin{figure}[h] \end{figure} The staged, directed network in Figure 3 represents a series of roads connecting 12 towns, \(S , A , B , C , D , E , F , G , H , I , J\) and \(T\). The number on each arc shows the distance between these towns, in miles. Bradley is planning a four-day cycle ride from \(S\) to \(T\).
He plans to leave his home at \(S\). On the first night he will stay at \(A , B\) or \(C\), on the second night he will stay at \(D , E , F\) or \(G\), on the third night he will stay at \(H , I\) or \(J\), and he will arrive at his friend's house at \(T\) on the fourth day. Bradley decides that the maximum distance he will cycle on any one day should be as small as possible.

1. Write down the type of dynamic programming problem that Bradley needs to solve.
2. Use dynamic programming to complete the table in the answer book.
3. Hence write down the possible routes that Bradley could take.

5 Robert is planning to renovate four houses, \(A , B , C\) and \(D\), at the rate of one per month. The houses can be renovated in any order but the costs will vary because some of the materials left over from renovating one house can be used for the next one. The expected profits, in hundreds of pounds, are given in the table below.

2. This question should be answered on the sheet provided. A builder is going to put up houses on a plot of land of area \(12000 \mathrm {~m} ^ { 2 }\).
There are 5 designs to choose from and no more than one of each design can be built. The builder needs to work out which houses he should build in order to maximise the total value of the site. He does this using a tree diagram and each "branch" on the tree is terminated when the total area of land on that branch exceeds \(12000 \mathrm {~m} ^ { 2 }\).

1. 1. Complete the tree diagram so that each branch is terminated or all choices have been considered.
   2. Hence, determine which designs the builder should use and the total value that the site will have when completed.
2. Explain how this method could be altered if more than one of each design is allowed.

7. Nigel has a business renting out his fleet of bicycles to tourists. At the start of each year Nigel must decide on one of two actions:

• Keep his fleet of bicycles, incurring maintenance costs.
• Replace his fleet of bicycles.

The cost of keeping the fleet of bicycles, the cost of replacing the fleet of bicycles and the annual income are dependent on the age of the fleet of bicycles.
Table 1 shows these amounts, in \(\pounds 1000\) s. \begin{table}[h] \end{table} Nigel has a new fleet of bicycles now and wishes to maximise his total profit over the next four years. He is planning to sell his business at the end of the fourth year.
The amount Nigel will receive will depend on the age of his fleet of bicycles.
These amounts, in £1000s, are shown in Table 2. \begin{table}[h] \end{table} Complete the table in the answer book to determine Nigel's best strategy to maximise his total profit over the next four years. You must state the action he should take each year (keep or replace) and his total profit.
(Total 13 marks)

8. A company makes industrial robots. They can make up to four robots in any one month, but if they make more than three they will have to hire additional labour at a cost of \(\pounds 400\) per month.
They can store up to two robots at a cost of \(\pounds 150\) per robot per month.
The overhead costs are \(\pounds 300\) in any month in which work is done.
Robots are delivered to buyers at the end of each month. There are no robots in stock at the beginning of January and there should be none in stock after the April delivery. The order book for robots is Use dynamic programming to determine the production schedule which minimises the costs, showing your working in the table provided in the answer book.
(Total 12 marks)

5 [Figure 3, printed on the insert, is provided for use in this question.]
A landscape gardener has three projects, \(A , B\) and \(C\), to be completed over a period of 4 months: May, June, July and August. The gardener must allocate one of these months to each project and the other month is to be taken as a holiday. Various factors, such as availability of materials and transport, mean that the costs for completing the projects in different months will vary. The costs, in thousands of pounds, are given in the table. By completing the table of values on Figure 3, or otherwise, use dynamic programming, working backwards from August, to find the project schedule that minimises total costs. State clearly which month should be taken as a holiday and which project should be undertaken in which month.

7. D2 make industrial robots. They can make up to four in any one month, but if they make more than three they need to hire additional labour at a cost of \(\pounds 300\) per month. They can store up to three robots at a cost of \(\pounds 100\) per robot per month. The overhead costs are \(\pounds 500\) in any month in which work is done. The robots are delivered to buyers at the end of each month. There are no robots in stock at the beginning of January and there should be none in stock at the end of May. The order book for January to May is: Use dynamic programming to determine the production schedule that minimises the costs, showing your working in the table provided in the answer book. State the minimum cost.
(Total 14 marks)

2. (a) Find the general solution of the recurrence relation $$u _ { n + 1 } = 3 u _ { n } + 2 ^ { n } \quad n \geqslant 1$$ (b) Find the particular solution of this recurrence relation for which \(u _ { 1 } = u _ { 2 }\)

A student is testing a numerical method for finding an approximation for \(\pi\). The algorithm that the student is using is as follows. Line 10 \quad Input \(A\), \(B\), \(C\), \(D\), \(E\) Line 20 \quad Let \(A = A + 2\) Line 30 \quad Let \(B = -B\) Line 40 \quad Let \(C = \frac{B}{A}\) Line 50 \quad Let \(D = D + C\) Line 60 \quad Let \(E = (D - 3.14)^2\) Line 70 \quad If \(E < 0.05\) then go to Line 90 Line 80 \quad Go to Line 20 Line 90 \quad Print '\(\pi\) is approximately', \(D\) Line 100 \quad End Trace the algorithm in the case where the input values are $$A = 1, \quad B = 4, \quad C = 0, \quad D = 4, \quad E = 0$$ [6 marks]

2. (a) Find the general solution of the recurrence relation $$u _ { n + 1 } = 3 u _ { n } + 2 ^ { n } \quad n \geqslant 1$$ (b) Find the particular solution of this recurrence relation for which \(u _ { 1 } = u _ { 2 }\)

8. A factory can process up to five units of carrots each month. Each unit can be sold fresh or frozen or canned.
The profits, in \(\pounds 100\) s, for the number of units sold, are shown in the table.
The total monthly profit is to be maximised. Use dynamic programming to determine how many of the five units should be sold fresh, frozen and canned in order to maximise the monthly profit. State the maximum monthly profit.
(Total 12 marks)

1. Alka is considering paying \(\pounds 5\) to play a game. The game involves rolling two fair six-sided dice. If the sum of the numbers on the two dice is at least 8 , she receives \(\pounds 10\), otherwise she loses and receives nothing.

If Alka loses, she can pay a further \(\pounds 5\) to roll the dice again. If both dice show the same number then she receives \(\pounds 35\), otherwise she loses and receives nothing.

1. Draw a decision tree to model Alka's possible decisions and the possible outcomes.
2. Determine Alka's optimal EMV and state the optimal strategy indicated by the decision tree.

The payoff matrix for player \(A\) in a two-person zero-sum game is shown below. \begin{array}{c|c|c|c|c} & & \multicolumn{3}{c}{B}
& & \text{I} & \text{II} & \text{III}
\hline \multirow{3}{*}{A} & \text{I} & -3 & 4 & 0
& \text{II} & 2 & 2 & 1
& \text{III} & 3 & -2 & -1
\end{array} Find the optimal strategy for each player and the value of the game. [4 marks]

4. A sequence \(\left\{ u _ { n } \right\}\), where \(n \geqslant 0\), satisfies the recurrence relation $$u _ { n + 1 } = \frac { 3 } { 2 } u _ { n } - 2 n ^ { 2 } - 4 \quad u _ { 0 } = k$$ where \(k\) is an integer.

1. Determine an expression for \(u _ { n }\) in terms of \(n\) and \(k\).
   (6) Given that \(u _ { 10 } > 5000\)
2. determine the minimum possible value of \(k\).
   (2)

2. Jenny can choose one of three options, A, B or C, when playing a game. The profit, in pounds, associated with each outcome and their corresponding probabilities are shown on the decision tree in Figure 1. \begin{figure}[h] \end{figure}

1. Calculate the optimal EMV to determine Jenny's best course of action. You must make your working clear. For a profit of \(\pounds x\), Jenny's utility is given by \(1 - \mathrm { e } ^ { - \frac { x } { 400 } }\)
2. Using expected utility as the criterion for the best course of action, determine what Jenny should do now to maximise her profit. You must make your working clear.

4

1. When investigating three network flow problems, a student finds:
   1. a flow of 50 and a cut with capacity 50 ;
   2. a flow of 35 and a cut with capacity 50 ;
   3. a flow of 50 and a cut with capacity 35 . In each case, write down what the student can deduce about the maximum flow.
2. The diagram below shows a network. The numbers on the arcs represent the minimum and maximum flow along each arc respectively. By considering the flow at an appropriate vertex, explain why a flow is not possible through this network. \includegraphics[max width=\textwidth, alt={}, center]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-10_1189_1559_1105_246}
   (2 marks)