DYNAMIC PROGRAMMING
Dr Maaz Akhtar
Associate Professor
MED, NED UET
Outline
• Dynamic Programming is mainly an
optimization over plain recursion.
• Wherever we see a recursive solution that
has repeated calls for same inputs, we can
optimize it using Dynamic Programming.
• The idea is to simply store the results of
subproblems, so that we do not have to re-
compute them when needed later.
Learning Objectives
• Dynamic programming is an optimization
approach that transforms a complex problem into
a sequence of simpler problems; its essential
characteristic is the multistage nature of the
optimization procedure.
• More so than the optimization techniques
described previously, dynamic programming
provides a general framework for analyzing many
problem types.
• Within this framework a variety of optimization
techniques can be employed to solve particular
aspects of a more general formulation
DYNAMIC PROGRAMMING
In Dynamic programing we will be discussing two
types of studies:
1. Equipment Replacement Policy
2. Work Force Size Model
EQUIPMENT REPLACEMENT POLICY
The longer a machine stays in service, the higher
is its maintenance cost, and the lower its
productivity.
When a machine reaches a certain age, it may be
more economical to replace it.
The problem thus reduces to determining the
most economical age of a machine.
It can be used to help resolve distribution and
location decisions
EQUIPMENT REPLACEMENT POLICY
Suppose that we are studying the machine
replacement problem over a span of n years.
At the start of each year, we decide whether to
keep the machine in service an extra year or to
replace it with a new one.
Let r(t), c(t), and s(t) represent the yearly revenue,
operating cost, and salvage value of a t-year-old
machine.
The cost of acquiring a new machine in any year
is 1.
EQUIPMENT REPLACEMENT POLICY
Above logic will be used to develop optimum
equipment replacement policy that give us
maximum revenue.
Example-1: Equipment Replacement Policy
A company needs to determine the optimal
replacement policy for a current 3-year-old machine
over the next 4 years (n = 4). The company requires
that a 5-year-old machine be replaced. Determine
all possible outcomes.
Solution: Example-1
5
K
4 4
K K S
3 R 3 3 S
R K K
R S EN
2 2 D
KR
2 R
K K S
1 1 1 1
R R R
Example-2:
A company needs to determine the optimal
replacement policy for a current 3-year-old
machine over the next 4 years (n = 4). The
company requires that a 6-year-old machine be
replaced. The cost of a new machine is
$100,000. The following table gives the data of
the problem.
Optimum
Keep Replace
time Solution
R(t)+s(t+1)-c(t) R(0)+s(t)+s(1)-c(0)-I F(t) Decision
19000-600+60000= 20000-200+80000+ 80000-
1 79800 R
78400 100000 =79800
18500-1200+50000= 20000-200+60000+ 80000-
2 67300 K
67300 100000 =59800
17200-1500+30000= 20000-200+50000+ 80000-
3 49800 R
45700 100000 =49800
20000-200+5000+ 80000-
6 - 100000 =4800
4800 R
The alternative optimal policies starting in year 1 are (R,
K, K, R) and (R, R, K, K). The total cost is $55,300.
Unsolved Problem for Equipment Replacement Policy
A company needs to determine the optimal replacement policy
for a current 1-year-old machine over the next 4 years (n = 4).
The company requires that a 6-year-old machine be replaced.
The cost of a new machine is $100,000. The following table
gives the data of the problem.
