Dynamic programming Worked Solutions — Further Maths Maths

Fully worked, step-by-step solutions to Further Maths Dynamic programming questions. See exactly how to solve problems on dynamic-programming, bellman, stage-state-action, minimisation.

dynamic-programmingbellmanstage-state-actionminimisationmaximisationmaximin-minimax

Further Maths70 questionsStep-by-step solutions

Question 1

2 markseasy

A route must be chosen through a staged network so as to keep the total cost as low as possible. The states are arranged in stages as follows: stage

0

contains

A

; stage

1

contains

B

C

D

; stage

2

contains

E

F

; stage

3

contains

G

. Each arc joins a state to a state in the next stage, and the arc values are

AB=7

AC=33

AD=3

BE=46

BF=27

CE=37

CF=24

DE=41

DF=26

EG=18

FG=16

. Using Bellman's principle of optimality and working backwards through the stages, find the minimum total cost of a route from

A

G

Worked solution

Identify the stages, states and arcs of the network
$\text{stages }0\text{ to }3,\;\text{source }A,\;\text{sink }G$
Dynamic programming labels each state by the stage it belongs to; a route uses exactly one arc per stage from the source to the sink.
Work backwards from the final stage, giving each state its optimal value
$g(A)=45,\;g(B)=43,\;g(C)=40,\;g(D)=42,\;g(E)=18,\;g(F)=16$
Starting at the stage just before the sink and moving back one stage at a time, each state is given its best value using the values already found at the next stage.
Trace the optimal route forwards from the source
$A\to D\to F\to G\quad\left(3+26+16=45\right)$
Following the optimal choice recorded at each state gives the route, whose arc values add up to the optimal total.
State the minimum total cost
$\text{minimum total cost}=45$
The least possible total cost of a route from $A$ to $G$ is $45$ .

Answer

45

Question 2

2 markseasy

A piece of equipment is to be kept in service over several stages. In this staged network each arc value is the net cost, in suitable units, of a keep-or-replace decision. The states are arranged in stages as follows: stage

0

contains

A

; stage

1

contains

B

C

D

; stage

2

contains

E

F

; stage

3

contains

G

. Each arc joins a state to a state in the next stage, and the arc values are

AB=19

AC=12

AD=32

BE=43

BF=14

CE=29

CF=31

DE=24

DF=38

EG=11

FG=37

. Using Bellman's principle of optimality and working backwards through the stages, find the minimum total cost of a route from

A

G

Worked solution

Identify the stages, states and arcs of the network
$\text{stages }0\text{ to }3,\;\text{source }A,\;\text{sink }G$
Dynamic programming labels each state by the stage it belongs to; a route uses exactly one arc per stage from the source to the sink.
Work backwards from the final stage, giving each state its optimal value
$g(A)=52,\;g(B)=51,\;g(C)=40,\;g(D)=35,\;g(E)=11,\;g(F)=37$
Starting at the stage just before the sink and moving back one stage at a time, each state is given its best value using the values already found at the next stage.
Trace the optimal route forwards from the source
$A\to C\to E\to G\quad\left(12+29+11=52\right)$
Following the optimal choice recorded at each state gives the route, whose arc values add up to the optimal total.
State the minimum total cost
$\text{minimum total cost}=52$
The least possible total cost of a route from $A$ to $G$ is $52$ .

Answer

52

Question 3

2 markseasy

A factory schedules its production over several stages. Each arc value is the cost, in suitable units, of meeting demand by the corresponding production decision. The states are arranged in stages as follows: stage

0

contains

A

; stage

1

contains

B

C

D

; stage

2

contains

E

F

; stage

3

contains

G

. Each arc joins a state to a state in the next stage, and the arc values are

AB=29

AC=21

AD=7

BE=46

BF=16

CE=48

CF=12

DE=18

DF=40

EG=11

FG=5

. Using Bellman's principle of optimality and working backwards through the stages, find the minimum total cost of a route from

A

G

Worked solution

Identify the stages, states and arcs of the network
$\text{stages }0\text{ to }3,\;\text{source }A,\;\text{sink }G$
Dynamic programming labels each state by the stage it belongs to; a route uses exactly one arc per stage from the source to the sink.
Work backwards from the final stage, giving each state its optimal value
$g(A)=36,\;g(B)=21,\;g(C)=17,\;g(D)=29,\;g(E)=11,\;g(F)=5$
Starting at the stage just before the sink and moving back one stage at a time, each state is given its best value using the values already found at the next stage.
Trace the optimal route forwards from the source
$A\to D\to E\to G\quad\left(7+18+11=36\right)$
Following the optimal choice recorded at each state gives the route, whose arc values add up to the optimal total.
State the minimum total cost
$\text{minimum total cost}=36$
The least possible total cost of a route from $A$ to $G$ is $36$ .

Answer

36

Question 4

2 markseasy

Stock is to be managed over several stages. Each arc value is the combined ordering and holding cost of the corresponding decision. The states are arranged in stages as follows: stage

0

contains

A

; stage

1

contains

B

C

D

; stage

2

contains

E

F

; stage

3

contains

G

. Each arc joins a state to a state in the next stage, and the arc values are

AB=25

AC=43

AD=41

BE=13

BF=3

CE=5

CF=45

DE=34

DF=12

EG=4

FG=46

. Using Bellman's principle of optimality and working backwards through the stages, find the minimum total cost of a route from

A

G

Worked solution

Identify the stages, states and arcs of the network
$\text{stages }0\text{ to }3,\;\text{source }A,\;\text{sink }G$
Dynamic programming labels each state by the stage it belongs to; a route uses exactly one arc per stage from the source to the sink.
Work backwards from the final stage, giving each state its optimal value
$g(A)=42,\;g(B)=17,\;g(C)=9,\;g(D)=38,\;g(E)=4,\;g(F)=46$
Starting at the stage just before the sink and moving back one stage at a time, each state is given its best value using the values already found at the next stage.
Trace the optimal route forwards from the source
$A\to B\to E\to G\quad\left(25+13+4=42\right)$
Following the optimal choice recorded at each state gives the route, whose arc values add up to the optimal total.
State the minimum total cost
$\text{minimum total cost}=42$
The least possible total cost of a route from $A$ to $G$ is $42$ .

Answer

42

Question 5

2 markseasy

A project is to be staffed over several stages. Each arc value is the cost, in suitable units, of the corresponding hiring-and-firing decision. The states are arranged in stages as follows: stage

0

contains

A

; stage

1

contains

B

C

D

; stage

2

contains

E

F

; stage

3

contains

G

. Each arc joins a state to a state in the next stage, and the arc values are

AB=4

AC=23

AD=2

BE=21

BF=38

CE=13

CF=15

DE=41

DF=9

EG=35

FG=46

. Using Bellman's principle of optimality and working backwards through the stages, find the minimum total cost of a route from

A

G

Worked solution

Identify the stages, states and arcs of the network
$\text{stages }0\text{ to }3,\;\text{source }A,\;\text{sink }G$
Dynamic programming labels each state by the stage it belongs to; a route uses exactly one arc per stage from the source to the sink.
Work backwards from the final stage, giving each state its optimal value
$g(A)=57,\;g(B)=56,\;g(C)=48,\;g(D)=55,\;g(E)=35,\;g(F)=46$
Starting at the stage just before the sink and moving back one stage at a time, each state is given its best value using the values already found at the next stage.
Trace the optimal route forwards from the source
$A\to D\to F\to G\quad\left(2+9+46=57\right)$
Following the optimal choice recorded at each state gives the route, whose arc values add up to the optimal total.
State the minimum total cost
$\text{minimum total cost}=57$
The least possible total cost of a route from $A$ to $G$ is $57$ .

Answer

57

Unlock 65 more Dynamic programming questions

Create a free account to work through every Further Maths Dynamic programming question with instant step-by-step worked solutions, progress tracking and interactive lessons.

Full worked solutions for every question
Interactive lessons and instant feedback
Track your mastery across every topic

Create a Free Account

No card required · Free forever

More Dynamic programming practice

Hard Questions Practice Questions

Dynamic programming Worked Solutions — Further Maths Maths

Worked solution

Worked solution

Worked solution

Worked solution

Worked solution

Unlock 65 more Dynamic programming questions

More Dynamic programming practice

Related Decision Maths topics