Dynamic Programming
Dynamic Programming is a method for solving complex problems by breaking them down into simpler subproblems and solving each subproblem only once, storing the solution to avoid redundant calculations. It is often used in optimization problems and is based on the principle of overlapping subproblems and optimal substructure. This approach can significantly improve the efficiency of solving problems with recursive structures.
5 Key excerpts on "Dynamic Programming"
eBook - ePubManagement Science, Operations Research and Project Management
Modelling, Evaluation, Scheduling, Monitoring
- José Ramón San Cristóbal Mateo(Author)
- 2016(Publication Date)
- Routledge(Publisher)
...Chapter 5 Dynamic Programming Of all mathematics techniques employed in Operations Research, Dynamic Programming is perhaps the simplest in concept and one of the most difficult to apply. One of the difficulties in applying Dynamic Programming is the lack of a clear-cut formulation and solution algorithm (Shamblin and Steven, 1974). As a result, each problem requires basic decisions for formulation. Dynamic Programming is a technique that can be used to solve many optimization problems that require interrelated solutions, i.e., decisions which must be made in a sequence and which influence future decisions in that sequence. In most applications, Dynamic Programming obtains solutions by working backwards from the beginning, thus breaking a large, unwieldy problem into a series of smaller, more tractable problems. In this chapter, we begin by introducing the Dynamic Programming recursion and apply it to a multi-project investment problem. Next, the time-cost trade-off problem will be revisited using Dynamic Programming. Dynamic Programming The following characteristics are common to most applications of Dynamic Programming (Shamblin and Steven, 1974; Winston, 2003): 1. The problem can be divided into stages with a decision required at each stage. The stage is the amount of time that has elapsed since the beginning of the problem. 2. Each stage has a number of states associated with it. By a state we mean the information that is needed at any stage to make an optimal decision. 3. The decision chosen at any stage describes how the state at the current stage is transformed into the state at the next stage. In many problems, a decision does not determine the next stage’s state with certainty; instead, the current decision only determines the probability distribution of the state at the next stage. 4. Given the current state, the optimal decision for each of the remaining stages must not depend on previously reached states or previously chosen decisions...
- James A. Momoh(Author)
- 2017(Publication Date)
- CRC Press(Publisher)
...8 Dynamic Programming 8.1 Introduction Dynamic Programming (DP) is an optimization approach that transforms a complex problem into a sequence of simpler problems [ 3 – 6, 9, 12 – 14 ]; its essential characteristic is the multistage nature of the optimization procedure. More so than the optimization techniques described previously, DP 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. Usually creativity is required before we can recognize that a particular problem can be cast effectively as a dynamic program, and often subtle insights are necessary to restructure the formulation so that it can be solved effectively. The DP method was developed in the 1950s through the work of Richard Bellman [ 1, 2 ] who is still the doyen of research workers in this field. The essential feature of the method is that a multivariable optimization problem is decomposed into a series of stages, optimization being done at each stage with respect to one variable only. Bellman [1] gave it the rather undescriptive name of DP. A more significant name would be recursive optimization. Both discrete and continuous problems can be amenable to this method and deterministic as well as stochastic models can be handled by it. The complexities increase tremendously with the number of constraints. A single-constraint problem is relatively simple, but even more than two constraints can be formidable. The DP technique, when applicable, represents or decomposes a multistage decision problem as a sequence of single-stage decision problems. Thus an N -variable problem is represented as a sequence of N single-variable problems that are solved successively. In most of the cases, these N subproblems are easier to solve than the original problem...
eBook - ePubOperations Research
Operations Research: Theory and Practice
- N.V.S Raju(Author)
- 2019(Publication Date)
- CRC Press(Publisher)
...12 Chapter Dynamic Programming Chapter Outline 12.0 Introduction 12.1 The Approach & Algorithm 12.2 Salient Features & Their Definitions of DPP 12.3 Characteristics of DPP Practice Problems Review Questions Objective Type Questions Fill in the Blanks Answers 12.0 Introduction Dynamic Programming is an optimization technique of multistage decision process. The word “dynamic” means to the situations of change in several stages, such as every week, every day or every month etc., and ‘programming’ is the term used in the mathematical sense of selecting an optimum allocation of resource. Rechard Bellman propounded this technique of finding optimal solution by developing recursive relation. In Dynamic Programming, a large problem is split into smaller sub problems each of which involve in a few variables. These sub problems are sequentially optimized so as to make the total problem optimal. An important point to note here is that – the problem of successive stages is treated separately even though by the very nature of the problem, these stages are dependent. The answer to this question is based on “Bellman’s principle of optimality”, which is stated as “An optimal policy (set of decisions) has the property that what ever the initial state and decisions are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision”. Discrete and continuous, deterministic as well as probablistic models can be solved by this method. Thus Dynamic Programming method is very useful in obtaining optimal solutions of various problems such as inventory, replacement, allocation, linear programming, reliability calculations etc...
eBook - ePubEngineering Optimization
Theory and Practice
- Singiresu S. Rao(Author)
- 2019(Publication Date)
- Wiley(Publisher)
...9 Dynamic Programming 9.1 Introduction In most practical problems, decisions have to be made sequentially at different points in time, at different points in space, and at different levels, say, for a component, for a subsystem, and/or for a system. The problems in which the decisions are to be made sequentially are called sequential decision problems. Since these decisions are to be made at a number of stages, they are also referred to as multistage decision problems. Dynamic Programming is a mathematical technique well suited for the optimization of multistage decision problems. This technique was developed by Richard Bellman in the early 1950s [ 2, 6 ]. The Dynamic Programming technique, when applicable, represents or decomposes a multistage decision problem as a sequence of single‐stage decision problems. Thus, an N ‐variable problem is represented as a sequence of N single‐variable problems that are solved successively. In most cases, these N subproblems are easier to solve than the original problem. The decomposition to N subproblems is done in such a manner that the optimal solution of the original N ‐variable problem can be obtained from the optimal solutions of the N one‐dimensional problems. It is important to note that the particular optimization technique used for the optimization of the N single‐variable problems is irrelevant. It may range from a simple enumeration process to a differential calculus or a nonlinear programming technique. Multistage decision problems can also be solved by direct application of the classical optimization techniques. However, this requires the number of variables to be small, the functions involved to be continuous and continuously differentiable, and the optimum points not to lie at the boundary points. Further, the problem has to be relatively simple so that the set of resultant equations can be solved either analytically or numerically...
eBook - ePubMicroeconomics
A Global Text
- Judy Whitehead(Author)
- 2014(Publication Date)
- Routledge(Publisher)
...In particular, it eliminates the difficulty with calculus of finding a solution to the differential equations. Its special advantage lies in its computational efficiency. The efficiency the Dynamic Programming optimization technique for handling discrete (staged) processes derives from the application of Bellman’s (1957) ‘principle of optimality’ by which the determination of one variable leaves the problem with one less variable to solve at the next stage in the process. The technique systematizes the search for the optimum in a complex process, by decomposing the overall optimization problem with several variables into a series of simpler individual problems (sub-processes or stages) each possessing a few (or, in the extreme, one) of the total number of variables in the larger problem. The technique works in such a way that by optimizing the simple component sub-problems in a particular manner, it leads to the optimal solution of the larger, more complex problem. In applying the Dynamic Programming technique to the problem of finding the lowest cost combination of sub-process alternatives for a disaggregated multi-stage manufacturing process, a specially customized version of the technique is required. This is permitted by the high degree of flexibility of the technique. A special interpretation is required both at the conceptual level and at the procedural level. In applying the Dynamic Programming technique to a production process certain customizations must be done: The ‘stages’ in Dynamic Programming nomenclature are considered here to be the points in the manufacturing process at which technological decisions are made. The Dynamic Programming ‘states’ at any stage may be defined in terms of the characteristics which describe the nature of the processed or semi-processed product at that particular stage in the production process...
