DYNAMIC

PROGRAMMING
Decision Analysis Making
Henry Yuliando; Agung Putra Pamungkas
Session 11
 Dynamic programming is a quantitative analysis approach
that is applicable to decision-making situtations in which a
series of interrelated decision have to be made.
 It is based on the idea of dividing problem into stages. The
outcome of the decision at one stage affects the decision
and outcome at the next stage of the problem. (somewhat
similar to decision tree)
 As an approach technique, this means that there is no
standard solution procedure, but it may even utilize other
techniques within its overall solution strategy.
 Widely used in business and managerial problems,
particularly in a variety of production scheduling and
inventory control decision making situations.

Introduction
1. The overall problem is decomposed into sub-
problems called stages.

2. The final stages of the problem is analyzed and

solved for all the possible conditions or states.

3. Each preceeding stage is solved, working

backward from the final stage of the problem,
establish a recursion relationship.

4. The initial stage of the problem is solved, and

when this has been accomplished the optimal
solution has been obtained.

Major steps in DP
 2 700

200
150
400 5 500

Denver 500 Pittsburgh

(origin) 1 3 100 7 (destination)
350

100 700
400 400 6

Stage 1 Subproblem. Where should we go from Node 5 and 6 in

order to reach Node 7 along the shortest route?
Stage 2 Subproblem. Using the result of stage 1, where should we
go from Node 2,3, and 4 in order to reach Node 7 along the shortest
route?
Stage 3 Subproblem. Using the result of stage 2, where should we
go from Node 1 in order to reach Node 7 along the shortest route?

DP approach on The Shortest Route Problem

 Policy decision, xn Policy decision, x2 Policy decision, x1

State, sn State, sn-1 State, s2 State, s1 State, s0

Stage n Stage 2 Stage 1

Return function Return function Return function

fn(sn, xn) = rn(sn, xn) + f*n-1(sn-1, xn-1) f2(s2, x2) = r2(s2, x2) + f*1(s2, x2) f1(s1, x1) = r1(s1, x1) + f*0(s1, x1)

Return Optimal
Return Optimal
from return
from return
current from
stage 2 from
stage previous
stage 1
stage

...
 An optimal policy must have the property that, regardless
of the decision made to enter a particular state, the
remaining decisions must constitute an optimal policy for
leaving that state.
 At each stage in the decision process, given the current
state, an optimal policy for the remaining stages of the
process is independent of the policy adopted in previous
stages of the decision process.
 The solution procedure for DP problems generally begins
by finding the optimal policy for each state of the last stage
of the process.
 The solution procedures proceeds in a fashion that
identifies the optimal policy for each state with n stages
remaining, given the optimal policy for each state with n-1
stages remaining, using a recursion relationship.

Principle of optimality of DP
 General form of recursion relationship :
fn*(sn) = max/min {fn(sn, xn)}

 For the shortest route problem above, it can be

written that :
f n * ( sn )  min { f n ( sn , xn )}
xn

f n * ( sn )  min {d sn , xn  f n 1 * ( xn )}
xn

where d s , x is the distance associated withthe

n n

state variable, sn , and the decision variable, xn ,

for the current stage of the problem.
xn fn(sn, xn) fn*(sn) xn*
sn xn

...
 Three-stage problem

All nodes are arc from Node 7

Two-stage problem
All nodes are arc from Node 7

One-stage problem

All nodes are arc from Node 7

Decision, x3 Decision, x2 Decision, x1

s3 Stage s2 Stage s1 Stage s0

3 2 1

f 2 (s2 , x2 )  d s2 , x2  f1 * ( x2 ) f1 ( s1 , x1 )  d s1 , x1

2 700
200
150
400
5 500
500
Denver
(origin)
1 3 350 100 7 Pittsburgh
(destination)

400
100
400
6 700

4
Stage 2
d25 + f1*(5) = 700 + 500 = 1200
f2(2, 5) =
d235 + f1*(5) = 550 + 500 = 1050
d236 + f1*(6) = 500 + 600 = 1100
f2(2, 6) =
d2346 + f1*(6) = 650 + 600 = 1250
d35 + f1*(5) = 400 + 500 = 900
f2(3, 5) =
d325 + f1*(5) = 850 + 500 = 1350
d36 + f1*(6) = 350 + 600 = 950
f2(3, 6) =
d346 + f1*(6) = 500 + 600 = 1100
d435 + f1*(5) = 500 + 500 = 1000
f2(4, 5) =
d 4325 + f1*(5) = 950+ 500 = 1450
d46 + f1*(6) = 400 + 600 = 1000
f2(4, 6) =
d436 + f1*(6) = 450 + 600 = 1050

Stage 3
x3 f3(s3, x3) = d s3 , x3  f 2 * ( x3 )
s3 2 3 4 f3*(s3) x3*
1 1250 1400 1400 1250 2
 2 700

200
150
400 5 500

Denver 500 Pittsburgh

(origin) 1 3 100 7 (destination)
350

100 700
400 400 6

Optimal Solution
NODES
Sequence 12357
Distances 200 + 150 + 400 + 500 = 1250
 General formulation of a resource allocation problem :
Maximize Z = R1(A1) + R2(A2) + ... + Rn(An)
subject to
A1 + A2 + ... + AN ≤ T
with
A1, A2, ..., AN ≥ 0
where
R1, R2,...,Rn = the return from the various projects;
A1, A2, ..., AN = the resources allocated to the various projects;
T = the total amount of resources available.

 An example, available time allocation for study time (50 hours).

Grade Points (GP) Expected as a function of hours studied

Course
5 HOURS 10 HOURS 15 HOURS 20 HOURS
Accounting D(1) C(3) B(4) A(5)
Finance C(3) B(4) A(5) A(5)
Mangement Science D(1) C(3) B(4) A(5)
Business Policy B(4) B(4) A(5) A(5)

The Allocation Problem using DP

 x1 f1(s1, x1) = GPx1
s1 5 10 15 20 f1*(s1) x1*
5 1 1 5 Note : n = 1,
10 1 3 3 10
Accounting

15 1 3 4 4 15

20 1 3 4 5 5 20

X2 f2(s2, x2) = GPx  f1 * ( s2  x2 )

2

s2 5 10 15 20 f2*(s2) x2*
10 4 4 5
Note : n = 2,
15 6 5 6 5
Accounting
20 7 7 6 7 5 or 10 and Finance
25 8 8 8 6 8 5, 10, or 15

30 9 9 8 9 10 or 15

35 10 9 10 15

40 10 10 20
 Stage 2, n=2 (accounting and finance), a maximum of 50
hours of study time is available for both Accounting and
Finance. The maximum amount of time that can be
devoted to either subject is 20 hours, or total 40 hours.
Given that s2 = 40 hours, the return (GP expectation) :
f 2 ( s2 , x2 )  GPx2  f1 * ( s2  x2 )
 GPx2 20  f1 * (40  20)  5  5  10

 Another case, if s2 = 25 hours, then

f 2 ( s2 , x2 )  GPx2  f1 * ( s2  x2 )
 GPx2 15  f1 * (25  15)  5  3  8

The decision policies on stage 2

 x3 f3(s3, x3) = GPx  f 2 * ( s3  x3 )
3

s3 5 10 15 20 f3*(s3) x3*
15 5 5 5

20 7 7 7 5 or 10 Note : n = 3,
Accounting;
25 8 9 8 9 10
Finance; and
30 9 10 10 9 10 10 or 15 Management
35 10 11 11 11 11 10, 15, or 20 Science
40 11 12 12 12 12 10, 15, or 20

45 11 13 13 13 13 10, 15, or 20

50 13 14 14 14 15 or 20

if s3 = 30 hours, and you choose to study Management Science for 15

hours, then GP expectation :
f 3 ( s3 , x3 )  GPx3  f 2 * ( s3  x3 )
 GPx3 15  f1 * (30  15)  4  6  10
 x4 f4(s4, x4) = GPx  f 3 * ( s4  x4 )
4

s4 5 10 15 20 f4*(s4) x4*
50 17 16 16 15 17 5

Note : n = 4, Accounting; Finance; Management Science; and Business Policy

Alternative final decisions :

COURSE STUDY HOURS GRADE GRADE POINTS
Business Policy x4 = 5 B 4
Mangement Science x3 = 10 C 3
Finance x2 = 15 A 5
Accounting x1 = 20 A 5
Total 17

COURSE STUDY HOURS GRADE GRADE POINTS

Business Policy x4 = 5 B 4
Mangement Science x3 = 15 B 4
Finance x2 = 10 B 4
Accounting x1 = 20 A 5
Total 17