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]
| Week | Week 1 | Week 2 | Week 3 | Week 4 |
| Possible countries | A or B | C, D or E | F or G | H or I |
\captionsetup{labelformat=empty}
\caption{Table 1}
\end{table}
Table 2 shows the value of the orders, in \(\pounds 100\) s, he expects to take in each country.
\begin{table}[h]
| Country | A | B | C | D | E | F | G | H | I |
| Value of expected orders in \(\pounds 100\) s | 22 | 17 | 42 | 41 | 39 | 29 | 27 | 36 | 38 |
\captionsetup{labelformat=empty}
\caption{Table 2}
\end{table}
Table 3 shows the cost, in \(\pounds 100\) s, of travelling between the various countries.
\begin{table}[h]
| Travel costs in £100s | A | B | C | D | E | F | G | H | I |
| London | 5 | 3 | | | | | | 5 | 4 |
| A | | | 5 | 4 | 2 | | | | |
| B | | | 4 | 4 | 3 | | | | |
| C | | | | | | 6 | 5 | | |
| D | | | | | | 6 | 3 | | |
| E | | | | | | 4 | 4 | | |
| F | | | | | | | | 6 | 7 |
| G | | | | | | | | 5 | 6 |
\captionsetup{labelformat=empty}
\caption{Table 3}
\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.
- Complete the table in the answer book to determine the optimal expected income.
- State Patrick's two optimal schedules.