Scribd
Upload
9 views3 pages

Dynamic Programming Explained

Dynamic Programming is a mathematical technique for optimizing a sequence of inter-related decisions over time, developed by Richard Bellman. It involves breaking complex problems into sub-problems, with decisions made at each stage that affect the state of the system. This methodology is applicable in various fields such as inventory control, network analysis, and job-shop scheduling.

Uploaded by

a c s Kumar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
9 views3 pages

Dynamic Programming Explained

Dynamic Programming is a mathematical technique for optimizing a sequence of inter-related decisions over time, developed by Richard Bellman. It involves breaking complex problems into sub-problems, with decisions made at each stage that affect the state of the system. This methodology is applicable in various fields such as inventory control, network analysis, and job-shop scheduling.

Uploaded by

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

DYNAMIC PROGRAMMING

Usually, in situations, where a series of consecutive decisions are


involved, the OVERALL OPTIMAL POLICY is arrived at by considering
the effects of each decision SEPERATELY.
e.g., In Inventory Models A Policy of determining the Optimal
Inventory for each month which minimizes the Inventory
Cost for that month, may be optimal for the whole year
also, i.e., That Policy might minimize the Inventory Cost for
the whole year also.
However, in many situations, it is not necessary that:
The Overall Return for the total period (e.g., the whole year) will be
optimal If we optimize the return over each individual period (e.g., a
month)
i.e. It may be that a bit of sacrifice in one period, ( say, January’s )
might increase the return in February to a larger extent.
For such situations Optimization -- by -- Dynamic Programming
developed by RICHARD BELLMAN & Associates at the Rand Corporation,
USA might be quite useful.
Definition : A mathematical technique of optimizing a sequence of
inter-related decisions over a period of time.
The word Dynamic indicates that TIME is explicitly being considered
in this methodology.
Dynamic Programming uses The Principle of Recursion.
Here To solve a Complex problem The problem is broken into
a series of SUB- PROBLEMS.
Dynamic Programming can be applied in various situations pertaining to:
Inventory Control, Network Analysis, Job-shop
Scheduling (Sequencing), Production Control, and
Capital Budgeting, etc.,
*Some Important Terms:
1. STAGE:
Dynamic Programming problem can be divided into a Sequence of
(which are called Stages of the Original problem) Sub Problems

At each stage a Decision is made.


Usually the Stages represent Different time periods in the
Overall Period of the problem
Or
Different places (Zones) in the Overall Territory considered in the original
problem.
e.g., In Replacement problems each year may be considered a
Stage.
In Salesman problems each zone may be treated as a Stage.
2. STATE:
Each Stage has certain Number of States associated with it.
The States represent various conditions prevailing at a point in time,
( i.e., in a Stage ) of the problem.
e.g., A specific city is referred to as a State Variable in the
Shortest Route problem.
The number of States may be Finite or Infinite.
3. DECISION:
At each stage a Decision is made which affects the State of the
System at the next Stage.
Always, a Decision is made at the current stage to arrive at the
Optimal Solution at the current stage.
Every Decision has its own MERIT in terms of the Worth or Benefit

associated with it
which may be described in Algebraic form by an Equation.
called the Return Function
which depends upon the State Variable -- and -- the Decision made at
a particular Stage.
*Basic Features (Characteristics) of Dynamic Programming Problems:
1. The problem can be divided into Stages with a policy decision
required at each stage.
2. Each stage has a number of States associated with it -- and --
Various possible conditions of existence of the system at that stage of
the problem are possible.
Further, The number of States may be Finite / Infinite.

Common questions

Powered by AI

Dynamic Programming facilitates decision-making in complex optimization problems by breaking them down into stages, each requiring a decision that influences future stages. Key features distinguishing it from other optimization techniques include its recursive structure, the explicit consideration of time, and its capacity to handle problems that involve a sequence of inter-dependent decisions. This contrasts with techniques that optimize independently without the sequential dependency consideration.

In Dynamic Programming, a 'Stage' refers to a distinct phase or period within the problem timeline where a decision occurs. A 'State' is a specific condition or set of conditions associated with a stage that characterizes the problem at that point. 'Decision' involves choosing from various alternatives at each stage, affecting the system's state in the next stage. These components interrelate such that the decision made at one stage directly influences the subsequent state and stages, cumulatively leading to an optimal solution when decisions are made sequentially across all stages.

Dynamic Programming is applied in Inventory Control, Network Analysis, Job-shop Scheduling, Production Control, and Capital Budgeting. It is suitable for these scenarios because each involves making a series of inter-dependent decisions over time, which requires optimizing the entire sequence rather than optimizing each decision in isolation. The method's ability to handle complex interdependencies and time-sequenced decisions fits well with the needs of these applications.

In Dynamic Programming, a 'Stage' signifies a specific point in time or a step in the sequence of decision-making where a particular choice must be made. It helps in structuring the problem by breaking it into manageable parts, each requiring a decision, thus facilitating a step-by-step approach to solving the overall problem. Each stage is an integral division of the entire problem timeline.

In Dynamic Programming, the 'Return Function' quantitatively describes the benefit associated with each decision at a particular stage. It depends on the state variables and the decision made, and it aids in determining the merit of one decision over another. Effectively, it guides the selection of optimal decisions by evaluating the potential benefits against each state, ensuring that decisions taken align with achieving the overall optimal solution.

The Principle of Recursion in Dynamic Programming involves solving a complex problem by breaking it down into simpler sub-problems, which are solved recursively. This method is critical because it allows the system to build up solutions to larger problems using the solutions of smaller, previously solved sub-problems. This hierarchical structure ensures that each decision contributes optimally to the final outcome.

Time is essential in Dynamic Programming, as it directly influences the sequence and inter-dependence of decisions. In its definition, the term 'dynamic' signals that time periods are explicitly considered, stressing the need to evaluate how decisions made at one point affect future outcomes. This time-based component ensures that the solution process accounts for all temporal relationships, making it apt for problems where the sequence of events over time critically impacts optimal outcomes.

Dynamic Programming is advantageous in optimizing problems involving a series of inter-related decisions because it considers the effects of decisions across multiple stages rather than just each decision in isolation. Unlike optimizing each stage separately (such as finding the optimal inventory for each month), Dynamic Programming evaluates the entire sequence of decisions to find an overall optimal solution. This approach is beneficial when sacrifices in one period can lead to greater benefits in subsequent periods.

Dynamic Programming is beneficial over individual period optimization, for instance, in inventory management. Optimizing monthly inventory costs separately may not yield the lowest annual costs, as saving costs in one month might require spending more in another. Dynamic Programming considers such trade-offs and the cumulative impact of decisions, possibly sacrificing some cost savings in one period for greater savings in another, leading to a more optimal overall yearly policy.

The implication of finite versus infinite 'States' in Dynamic Programming is significant in terms of computational complexity. Finite states imply a limited number of possible conditions to consider at each stage, leading to a manageable computational load. In contrast, infinite states pose much higher computational challenges, requiring more complex algorithms to efficiently explore and evaluate the vast state space within reasonable time and resource constraints. Managing these complexities is crucial for practical feasibility in real-world applications.

You might also like