Dynamic programming order sequencing

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.

6 Bob is planning to build four garden sheds, \(A , B , C\) and \(D\), at the rate of one per day. The order in which they are built is a matter of choice, but the costs will vary because some of the materials left over from making one shed can be used for the next one. The expected profits, in pounds, are given in the table below. By completing the table of values opposite, or otherwise, use dynamic programming, working backwards from Thursday, to find the building schedule that maximises the total expected profit. \section*{Schedule}

7. Patrick is to take orders for his company's products. He will visit four countries over the next four weeks.
He will visit just one country each week.
He will leave from his office in London 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 in each week. \begin{table}[h] \end{table} Table 2 shows the value of the orders, in \(\pounds 100\) s, he expects to take in each country. \begin{table}[h] \end{table} Table 3 shows the cost, in \(\pounds 100\) s, of travelling between the various countries. \begin{table}[h] \end{table} The expected income is the value of the expected orders minus the cost of travel. It is decided to use dynamic programming to find a schedule that maximises the total expected income for these four weeks.

1. Complete the table in the answer book to determine the optimal expected income.
2. State Patrick's two optimal schedules.

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)

5 A card game between two players consists of several rounds. In each round the players both choose a card from those in their hand; they then show these cards to each other and exchange tokens. The number of tokens that the second player gives to the first player depends on the colour of the first player's card and the design on the second player's card. The table shows the number of tokens that the first player receives for each combination of colour and design. A negative entry means that the first player gives tokens to the second, zero means that no tokens are exchanged. Let the stages be \(0,1,2,3,4,5\). Stage 0 represents arriving at the sanctuary entrance. Stage 1 represents visiting the first bird, stage 2 the second bird, and so on, with stage 5 representing leaving the sanctuary. Let the states be \(0,1,2,3,4\) representing the entrance/exit, kite, lark, moorhen and nightjar respectively.

1. Calculate how many minutes it takes to travel the route $$( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 4 ) - ( 5 ; 0 ) .$$ The friends then realise that if they try to find the quickest route using dynamic programming with this (stage; state) formulation, they will get the route \(( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )\), or this in reverse, taking 27 minutes.
2. Explain why the route \(( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )\) is not a solution to the friends' problem. Instead, the friends set up a dynamic programming tabulation with stages and states as described above, except that now the states also show, in brackets, any birds that have already been visited. So, for example, state \(1 ( 234 )\) means that they are currently visiting the kite and have already visited the other three birds in some order. The partially completed dynamic programming tabulation is shown opposite.
3. For the last completed row, i.e. stage 2, state 1(3), action 4(13), explain where the value 18 and the value 6 in the working column come from.
4. Complete the table in the insert and hence find the order in which the birds should be visited to give a quickest route and find the corresponding minimum journey time.

   Stage	State	Action	Working	Suboptimal minimum
   \multirow{4}{*}{4}	1(234)	0	10	10
   	2(134)	0	14	14
   	3(124)	0	12	12
   	4(123)	0	17	17
   \multirow{12}{*}{3}	1(23)	4(123)	\(17 + 6 = 23\)	23
   	1(24)	3(124)	\(12 + 2 = 14\)	14
   	1(34)	2(134)	\(14 + 3 = 17\)	17
   	2(13)	4(123)	\(17 + 4 = 21\)	21
   	2(14)	3(124)	\(12 + 2 = 14\)	14
   	2(34)	1(234)	\(10 + 3 = 13\)	13
   	3(12)	4(123)	\(17 + 3 = 20\)	20
   	3(14)	2(134)	\(14 + 2 = 16\)	16
   	3(24)	1(234)	\(10 + 2 = 12\)	12
   	4(12)	3(124)	\(12 + 3 = 15\)	15
   	4(13)	2(134)	\(14 + 4 = 18\)	18
   	4(23)	1(234)	\(10 + 6 = 16\)	16
   \multirow{12}{*}{2}	1(2)	3(12) 4(12)	\(20 + 2 = 22\)	21
   	1(3)	2(13) 4(13)	\(21 + 3 = 24 18 + 6 = 24\)	24
   	1(4)
   	2(1)
   	2(3)
   	2(4)
   	3(1)
   	3(2)
   	3(4)
   	4(1)
   	4(2)
   	4(3)
   \multirow{4}{*}{1}	1
   	2
   	3
   	4
   0	0	1 2 3 4

2. This question should be answered on the sheet provided. A pool player is to play in four tournaments. Some of the tournaments take place simultaneously and the player has to choose one of each of the following: $$\begin{array} { l l } 1 ^ { \text {st } } \text { tournament: } & A , B \text { or } C , \\ 2 ^ { \text {nd } } \text { tournament: } & D , E \text { or } F , \\ 3 ^ { \text {rd } } \text { tournament: } & G , H \text { or } I , \\ 4 ^ { \text {th } } \text { tournament: } & J , K \text { or } L \end{array}$$ Each tournament has six rounds and the player estimates how well he will do in each tournament based on which tournament he plays before it. The table below shows his expectations with each number indicating the round he expects to reach and a "7" indicating he expects to win the tournament. He wishes to choose the tournaments such that his worst performance is as good as possible. Use dynamic programming to find which tournaments he should play.
(10 marks)

6 Answer this question on the insert provided. Four friends have decided to sponsor four birds at a bird sanctuary. They want to construct a route through the bird sanctuary, starting and ending at the entrance/exit, that enables them to visit the four birds in the shortest possible time. The table below shows the times, in minutes, that it takes to get between the different birds and the entrance/exit. The friends will spend the same amount of time with each bird, so this does not need to be included in the calculation. Let the stages be \(0,1,2,3,4,5\). Stage 0 represents arriving at the sanctuary entrance. Stage 1 represents visiting the first bird, stage 2 the second bird, and so on, with stage 5 representing leaving the sanctuary. Let the states be \(0,1,2,3,4\) representing the entrance/exit, kite, lark, moorhen and nightjar respectively.

1. Calculate how many minutes it takes to travel the route $$( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 4 ) - ( 5 ; 0 ) .$$ The friends then realise that if they try to find the quickest route using dynamic programming with this (stage; state) formulation, they will get the route \(( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )\), or this in reverse, taking 27 minutes.
2. Explain why the route \(( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )\) is not a solution to the friends' problem. Instead, the friends set up a dynamic programming tabulation with stages and states as described above, except that now the states also show, in brackets, any birds that have already been visited. So, for example, state \(1 ( 234 )\) means that they are currently visiting the kite and have already visited the other three birds in some order. The partially completed dynamic programming tabulation is shown opposite.
3. For the last completed row, i.e. stage 2, state 1(3), action 4(13), explain where the value 18 and the value 6 in the working column come from.
4. Complete the table in the insert and hence find the order in which the birds should be visited to give a quickest route and find the corresponding minimum journey time.

   Stage	State	Action	Working	Suboptimal minimum
   \multirow{4}{*}{4}	1(234)	0	10	10
   	2(134)	0	14	14
   	3(124)	0	12	12
   	4(123)	0	17	17
   \multirow{12}{*}{3}	1(23)	4(123)	\(17 + 6 = 23\)	23
   	1(24)	3(124)	\(12 + 2 = 14\)	14
   	1(34)	2(134)	\(14 + 3 = 17\)	17
   	2(13)	4(123)	\(17 + 4 = 21\)	21
   	2(14)	3(124)	\(12 + 2 = 14\)	14
   	2(34)	1(234)	\(10 + 3 = 13\)	13
   	3(12)	4(123)	\(17 + 3 = 20\)	20
   	3(14)	2(134)	\(14 + 2 = 16\)	16
   	3(24)	1(234)	\(10 + 2 = 12\)	12
   	4(12)	3(124)	\(12 + 3 = 15\)	15
   	4(13)	2(134)	\(14 + 4 = 18\)	18
   	4(23)	1(234)	\(10 + 6 = 16\)	16
   \multirow{12}{*}{2}	1(2)	3(12) 4(12)	\(20 + 2 = 22\)	21
   	1(3)	2(13) 4(13)	\(21 + 3 = 24 18 + 6 = 24\)	24
   	1(4)
   	2(1)
   	2(3)
   	2(4)
   	3(1)
   	3(2)
   	3(4)
   	4(1)
   	4(2)
   	4(3)
   \multirow{4}{*}{1}	1
   	2
   	3
   	4
   0	0	1 2 3 4

2 A manufacturing company is planning to build three new machines, \(A , B\) and \(C\), at the rate of one per month. The order in which they are built is a matter of choice, but the profits will vary according to the number of workers available and the suppliers' costs. The expected profits in thousands of pounds are given in the table.

1. Draw a labelled network such that the most profitable order of manufacture corresponds to the longest path within that network.
2. Use dynamic programming to determine the order of manufacture that maximises the total profit, and state this maximum profit.

5 [Figure 3, printed on the insert, is provided for use in this question.]
A maker of exclusive furniture is planning to build three cabinets \(A , B\) and \(C\) at the rate of one per month. The order in which they are built is a matter of choice, but the costs will vary because of the materials available and suppliers' costs. The expected costs, in pounds, are given in the table.

1. Use dynamic programming, working backwards from month 3, to determine the order of manufacture that minimises the total cost. You may wish to use Figure 3 for your working.
2. It is discovered that the figures given were actually the profits, not the costs, for each item. Modify your solution to find the order of manufacture that maximises the total profit. You may wish to use the final column of Figure 3 for your working.

5 Dave plans to renovate three houses, \(A , B\) and \(C\), at the rate of one per year. The order in which they are renovated is a matter of choice, but some costs vary over the three years. The expected costs, in thousands of pounds, are given in the table below. (b) Optimum order \(\_\_\_\_\)

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.

7. A company has purchased a plot of land and has decided to build four holiday homes, A, B, C and D, on the land at the rate of one home per year. The company expects that the construction costs each year will vary, depending on which houses have already been constructed and which house is currently under construction. The expected construction costs, in thousands of pounds, are shown in the table below. \begin{table}[h] \end{table} 2. You may not need to use all of these tables \begin{table}[h] \end{table} 3. You may not need to use all of these tables 4. 5. (a) You may not need to use all of these tableaux 6. (a) Value of initial flow
(b) and (c) \includegraphics[max width=\textwidth, alt={}, center]{e0c66144-9e34-42fc-9f40-a87a49331483-20_725_1251_404_349} \section*{Diagram 1} \section*{Diagram 2} (d)
(e) \includegraphics[max width=\textwidth, alt={}, center]{e0c66144-9e34-42fc-9f40-a87a49331483-21_714_1385_1306_283} \section*{Diagram 3} (f)
7. (a)

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. Table 1 Table 2 Table 3 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. [3]
2. Determine the schedule that maximises the total profit. Show your working in a table. [12]
3. Advise Joan on the shows that she should visit and state her total expected profit. [3]

(Total 18 marks)