Dynamic programming

Anvi makes boats during the winter months. She can make up to five boats each month.

If she builds more than three boats in any one month, she must hire an assistant at a cost of £400 for that month.

In any month in which boats are made, the overhead costs are £60 for each boat made that month.

A maximum of three boats can be held in storage at the end of each month, at a cost of £70 per boat per month.

Boats must be delivered at the end of each month.

The order schedule for boats is

There are no boats in storage at the beginning of November. Anvi plans to have no boats left in storage after the end of the March delivery.

Use dynamic programming to determine the production schedule that minimises the costs given above. Complete the working in the table provided in the answer book and state the minimum cost.

The assistant asks to work in November, and Anvi agrees.

Given that more than three boats are now made in November, state the minimum additional cost of producing all the required boats to the schedule shown above.

Bernie makes garden sheds. He can build up to four sheds each month.

If he builds more than two sheds in any one month, he must hire an additional worker at a cost of £250 for that month.

In any month in which sheds are made, the overhead costs are £35 for each shed made that month.

A maximum of three sheds can be held in storage at the end of any one month, at a cost of £80 per shed per month.

Sheds must be delivered at the end of the month.

The order schedule for sheds is

There are no sheds in storage at the beginning of January and Bernie plans to have no sheds left in storage after the May delivery.

Use dynamic programming to determine the production schedule that minimises the costs given above. Complete the working in the table provided in the answer book and state the minimum cost.

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.

Write down the type of dynamic programming problem that Bradley needs to solve.

Use dynamic programming to complete the table in the answer book.

Hence write down the possible routes that Bradley could take.

A manufacturer can export five batches of footwear each year. Each exported batch contains just one type of footwear. The types of footwear are trainers, sandals or high heels.

The table below shows the profit, in £1000s, for the number of batches of each type of footwear.

The total annual profit is to be maximised.

Use dynamic programming to determine the two possible values of the maximum total annual profit, giving one of these values in terms of x.

Given that the maximum total annual profit is £320 000

advise the manufacturer on the possible ways in which the five batches should be allocated.

In Figure 1 the weight of arc SB is denoted by x where x 0

Explain why Dijkstra’s algorithm cannot be used on the directed network in Figure 1.

It is given that the minimum weight route from S to T passes through B.

Use dynamic programming to find

the range of possible values of x

the minimum weight route from S to T.