CHAPTER 07
DYNAMIC PROGRAMMING
CHARACTERISTICS OF DYNAMIC
PROGRAMMING
• Multi-Stage process of decision making
• It provides a systematic procedure
• DP is based on Bellman’s principle of optimality
APPLICATIONS OF DYNAMIC
PROGRAMMING
• Production Planning
• Inventory Control
• Production Scheduling Problem
• Luggage Planning Problem
• Selection of an advertising media
• Transportation Route Plan
• Capital Budgeting Problem
• Resources Allocation Problem
• Research failure problem
DYNAMIC PROGRAMMING APPROACH
• Identify the followings
Problem variables
Objective function
Constrains
Stages of the problem
State variables
• Develop the recursive relationship for the optimal return function
• Make a tabular presentation to show the calculation
• Find the optimal decision at each stage
• Find the overall optimal policy
DYNAMIC PROGRAMMING
Dynamic programming is Operations research technique dealing with the
optimization of multistage decision problems. The technique was originated in
1952 by Richard Bellman and G.B. Dantzig.
By this technique decisions regarding a certain problem are typically optimized in
stages rather than simultaneously. The original problem is broken into sub-
problems (stages) and solve each sub problems separately and make the final
decision at the end.
Dynamic Programming is not a one-shot decision process like LP in which all the
variables consider simultaneously in making decision.
BASIC CONCEPTS OF DYNAMIC
PROGRAMMING
Decomposition- The division of the problem into several sub problems.
Stage- when the problem divide into sub problems, each sub problem is considered
as its stage.
System Status- The concepts is status or system indicates or represent by arrows
from one stage to other indicates the information flow about the status of that
system.
Decision Variable – This represent various decisions that are can made at each
stages.
Transition Function- This is the combination of system status and the
decision variable at particular stage.
Stage Return- This represent possible income or cost or expected profit or
loss or cost for each decisions at each stage.
Stage Optimization- This means the optimization of income or minimization
of cost at each stage in order to optimize the total income or minimize the
total cost.
Backward Recursion- This means the backward solution process of the
dynamic programming. In other wards The Dynamic Programme are solved
from right to left by taking accumulated results from stage one to stage n.
EXAMPLE :1
A student has to take the exam in three courses OR, OB and OM. Three
days are available to study. According to the following estimates, how
should he plan to study to maximize the No. of grades.
Days / Course
Subject 0 1 2 3
OR 1 2 2 4
OB 2 2 4 5
OM 1 2 4 4
Using Dynamic Programming identify optimal solution
Example 2:
Suppose a person needs to travel from territory A to territory J. The journey would
require travelling by trains through unsettled territories, where there is serious danger of
attacks by robbers. The traveler has a choice as to which territories to travel through en
route. Possible shown in the figure, where each territory is represented by a circled letter
and the direction of travel is from left to right. He is quite concerned about his safety and
wishes to determine the safest route. Life insurance policies are offered to travelers.
Cost (in thousand rupees) for the standard policy on train‐run from territory i to j are
provided in the figure along the edges. Safest route is the one with the cheapest total
life insurance policy. Using Dynamic Programming identify optimal route from territory
A to territory J.
Routes
Stage Cost (Rs 000)
From To
A B 2
1 A C 4
A D 3
B E 7
2 B F 4
B G 6
C E 3
C F 2
C G 4
D E 4
D F 1
D G 5
E H 1
3 E I 4
F H 6
F I 3
G H 3
G I 3
4 H J 3
I J 4
EXAMPLE: 3
An individual has Rs. 4000 to invest and three opportunities are available to
him. Each opportunity requires deposits in Rs. 1000 amounts; the investor may
allocate all the money to just one opportunity or split the money between them.
The expected returns are tabulated as follows. Identify optimal investment
plan.
Rupees Invested
0 1000 2000 3000 4000
OPP 1 0 2000 5000 6000 7000
OPP 2 0 1000 3000 6000 7000
OPP 3 0 1000 4000 5000 8000
EXAMPLE :4
A cosmetics manufacturing company is interested in selecting the advertising media for its product and the frequency
of advertising in the in each media. The data collected over the past two years regarding the frequency of advertising
in three medias of television, radio and newspaper the related sales of the product give the following results:
Expected Sales in Thousands of Rupees
Frequency/Week Television Radio Newspaper
1 220 150 100
2 275 250 175
3 325 300 225
4 350 320 250
The cost of advertising in newspaper is Rs. 500 per appearance, while in radio and television, it is Rs.
1000 and Rs. 2000 respectively. The budget provides Rs.4500 per week for advertisements. The problem
is to determining the optimal combination of advertising media and advertising frequency.
EXAMPLE :5
An organization is planning to diversify its business with a maximum outlay of Rs. 5
Million. It has identified three different locations to install plants. Find the optimal
allocation of the capital, which maximize the return. Given table matrix value are
represent return values (Rs. 000).
Cost
0 1 2 3 4 5
Plant 1 0 15 18 28
Plant 2 0 14 18 21
Plant 3 0 3 7
Using Dynamic Programming identify optimal plan.
EXAMPLE :6
A company has three sections producing automobile parts, bicycle parts and sewing
machine parts respectively. The management has allocated Rs. 20,000 for expanding the
production facilities. In the auto parts and bicycle parts sections, the production can be
increased either by adding new machines or by replacing some old inefficient machines by
automatic machine.
The sewing machine parts section was started only a few years back and thus the
additional amount can be invested only by adding new machines to the section. The cost
of adding and replacing the machines, along with the associated expected returns in the
different sections is given in the table. Select a set of expansion plans which may yield the
maximum return.
EXAMPLE 7…
EXAMPLE:8
A company makes three types of products A,B and C. The new raw material required and the
cash return for each product are shown bellow. 12 kg of raw material are available. What
product mix will maximize the cash return. Factional units of the product are meaningless;
the product must be measured in integer values.
Product Raw material Profit per unit
(Kg) (000s)
A 4 5
B 3 3
C 2 4
Using Dynamic Programming identify optimal Solution
EXAMPLE:9
Shahen produces large industrial equipment. The firm has received the following orders for its
equipment:
Month Jan Feb Mar Ap
Units 2 3 4 3
The cost of production involves a set-up cost of Rs. 50 and an average variable cost of Rs. 30 per
unit. Inventory holding cost is Rs. 10 per unit per month. Due to restrictions of storage space not
more than three units can be held in inventory. Assume that the firm has no inventory at the
beginning of Jan and does not wish to have any inventory at the end of April. What production
schedule should be followed to minimize costs?
THANK YOU
!!!
05/03/2026 18