Dynamic programming

The staged, directed network in Figure 2 represents a series of roads connecting 11 towns, S, A, B, C, D, E, F, G, H, J and T. The number on each arc shows the weight limit, in tonnes, for the corresponding road. Janet needs to drive a truck from S to T, passing through exactly three other towns. She needs to find the maximum weight of the truck that she can use.

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

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

Hence find the maximum weight of the truck Janet can use.

Write down the route that Janet should take.

Janet intends to ask for the weight limit to be increased on one of the three roads leading directly into T. Janet wishes to maximise the weight of her truck.

Determine which of the three roads she should choose and its new minimum weight limit.

Write down the maximum weight of the truck she would be able to use and the new route she would take.

A company assembles microlight aircraft. They can assemble up to four aircraft in any one month, but if they assemble more than three they will have to hire additional space at a cost of £1000 per month. They can store up to two aircraft at a cost of £500 each per month. The overhead costs are £2000 in any month in which work is done. Aircraft are delivered at the end of each month. There are no aircraft in stock at the beginning of March and there should be none in stock at the end of July. The order book for aircraft is

Use dynamic programming to determine the production schedule which minimises the costs. Show your working in the table provided in the answer book and state the minimum production cost.

_{Pearson Education Ltd copyright policy.}

_________________________________

_________________________________

_________________________________

_________________________________ 1 2 3 4

_________________________________

_________________________________

_________________________________

1 2 3 4 _________________________________

C _________________________________

D _________________________________

1 2 3 4 _________________________________

D _________________________________

_________________________________

_________________________________

_________________________________

_________________________________ 1 2 3 4

_________________________________

_________________________________

_________________________________

_________________________________ 1 2 3 4

_________________________________

_________________________________

_________________________________

_________________________________ 1 2 3 4

C _________________________________

D _________________________________

_________________________________

1 2 3 4 _________________________________

C _________________________________

D _________________________________

_________________________________

2.

3.

You may not need to use all of these tableaux

4.

5. (a) Initial flow value: ______________________________

6.

7.

You may not need to use all of these rows

Production schedule

Minimum production cost £

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 £1000s.

Nigel has a new fleet of bicycles now and wishes to maximise his total profit over the next four

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.

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.

_{Pearson Education Ltd copyright policy.}

1. (a)

2.

Demand 27 18 20 ________________________________

Demand 27 18 20

4.

5. (a)

(b) You may not need to use all of these tableaux

6.

7. You may not need to use all the rows in this table

Total profit

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.

Table 2 shows the value of the orders, in £100s, he expects to take in each country.

Table 3 shows the cost, in £100s, of travelling between the various countries.

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.

You may not need to use all these tables _____________________________________ A B C D _____________________________________

A B C D _____________________________________

You may not need to use all of these tableaux

4.

Optimal expected income: ________________________________

Explain the difference between a maximin route and a minimax route in dynamic programming.

A Maximin route from L to R is to be found through the staged network shown in Figure 1.

Use dynamic programming to complete the table in the answer book and hence find a maximin route.