Scribd
Upload
4 views11 pages

Understanding Dynamic Programming Basics

Dynamic programming, introduced by Bellman and Dantzig in 1952, is a method for optimizing multi-stage decision problems using recursive equations. It relies on the principle of optimality, where decisions made at one stage influence subsequent stages, and involves defining problem variables, stages, and state variables. The procedure includes developing recursive relationships, tabulating values, and determining optimal policies for decision-making.

Uploaded by

zafran
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
4 views11 pages

Understanding Dynamic Programming Basics

Dynamic programming, introduced by Bellman and Dantzig in 1952, is a method for optimizing multi-stage decision problems using recursive equations. It relies on the principle of optimality, where decisions made at one stage influence subsequent stages, and involves defining problem variables, stages, and state variables. The procedure includes developing recursive relationships, tabulating values, and determining optimal policies for decision-making.

Uploaded by

zafran
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Presented by:

ZAFRAN KHATTAK
[Link]
IHSAN ULLAH
INTRODUCTION
• Originated in 1952 by BELLMAN and G.B Dantzig.
• Initialy was called as stochastic linear programming.
• A bottom-up approach.
• Situation in which decisions may vary with time.
• It also include multistage problems.
• Dynamic programming uses recursive equations.
• optimization of multi-stage decision problem
CHARACTERISTICS OF D.P
• Involve multi-stage process of decision
• Stage variables(linking variables)
• Outcome of stage depends on small number of variables.
• The stage variables only alter numerical values of variables i.e
production smoothening, production capacity,cost,time.
• No variable is added or dropped.
• The effect to decision of one stage will alter the decision till last.
CHARACTERISTICS OF D.P
Bellman’s principle
• D.p uses principle of optimality “ an optimal
policy (decision sequence) has property that
whatever the initial stage and decision one,
the remaining decision must constitute an
optimal policy with regard to the state
resulting from the first decision’’.
CHARACTERISTICS OF D.P
• Using this principle , recursive equations take
optimal decisions at each stage.

• D.P provides a systematic procedure wherein


starting with last stage and working in
backwards. But it can also be solved by
working in forward .
APPROACHES OF D.P
• First concept is stage.
• Second concept is state.

“The variable which specify the conditions of decision


process and summarize the current status of system are
called state variable”
PROCEDURE
1. Define the problem variables, determine the objective
function, and specify constraints.
2. Define the stages of problem, state variables. Specify
the relationship by which state at one stage can be
expressed as a function of state at other stage.
3. Develop the recursive relationship and define whether
to follow forward or backwards method.
PROCEDURE
4. Make a tabular representation to show the required
values and calculations for each stage.
5. Find optimal decision at each stage and then the
overall optimal policy. Therefore, may be more than
one such policy.
EXAMPLES

You might also like