6. 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.
\begin{table}[h]
\captionsetup{labelformat=empty}
\caption{Table 1}
| Week | 1 | 2 | 3 |
| Shows | A, B, C | D, E | F, G, H |
\end{table}
Table 2
\begin{table}[h]
\captionsetup{labelformat=empty}
\caption{Table 1}
| Show | A | \(B\) | \(C\) | \(D\) | \(E\) | \(F\) | \(G\) | \(H\) |
| Expected Profit \(( \pounds )\) | 900 | 800 | 1000 | 1500 | 1300 | 500 | 700 | 600 |
\end{table}
\begin{table}[h]
\captionsetup{labelformat=empty}
\caption{Table 3}
| Travel costs (£) | A | B | C | D | E | F | G | H |
| Home | 70 | 80 | 150 | | | 80 | 90 | 70 |
| A | | | | 180 | 150 | | | |
| B | | | | 140 | 120 | | | |
| C | | | | 200 | 210 | | | |
| D | | | | | | 200 | 160 | 120 |
| E | | | | | | 170 | 100 | 110 |
\end{table}
It is decided to use dynamic programming to find a schedule that maximises the total expected profit, taking into account the travel costs.
- Define suitable stage, state and action variables.
- Determine the schedule that maximises the total profit. Show your working in a table.
- Advise Joan on the shows that she should visit and state her total expected profit.
(3) (Total 18 marks)