Dynamic Programming works for optimization. Optimization finds the best solution meeting up the desired criterion among several available solutions. Problems in Dynamic Programming may exist in abstract or symbolic form and to represent them mathematical models are used.
Dynamic Programming uses mathematical models. Mathematical models are used for decision making process having following characteristics:
Table 1. Characteristics of Dynamic Programming
The Variables D = (d1, d2, . . . , dn):
These are independent or decision variables.
The parameters Y = (y1, y2, . . . , yn):
These factors influence objective but are uncontrollable.
The measure of effectiveness (R):
It defines the value associated with decision variables and parameters.
The criterion function based decision variables and parameters is represented as:
R = R(D,Y)
The criterion function must be chosen that is able to reflect differences among different values of the decision variables.
The region of feasibility (S)
Decision variables take values within the constraint set (S). the constraint set S is represented as:
gi(D) <= 0 or gi(D) = 0 or gi(D) >= 0
Where, i =1,…m
Any D satisfying the constraints is a feasible solution to the model.
Optimal solution (D*) is defined as:
R(Y) = R(D*,Y) ≥ R(D,Y), D ∊S
= max R(D,Y), D ∊ S
D
For every problem there exists unique R(Y), and there may be more than one optimal solution to the problem
Mathematical models of decision making are not mutually exclusive and exhaustive but few distinctions may be made based on the values of the variable they take. Deterministic models and Probabilistic models are two models of Dynamic Programming.
In the Deterministic model of Dynamic Programming values of decision variables are defined unambiguously. In the Probabilistic model values of decision variables are given by probability distribution.
In Dynamic Programming, there exists another model known as competitive or game-theoretic models. In game-theoretic models, the number of variables are more and they take different decision values.
First step of Dynamic Programming is to build a mathematical model and then choose an optimized technique to find a solution to the model. Optimized solution to the given mathematical model depends on objective function and constraints, the type variables and number of variables.
Dynamic programming converts a multistage decision making process having a number of independent variables into a single-stage decision making process having few variables. Outcome of the first decision in Dynamic Programming decides the optimality of the remaining decisions.
A dynamic programming problem is subdivided based on a number of decision variables. Thus, more is the number of decision variables, more is the computation required. The critical factor of Dynamic Programming is sequential calculation.
Dynamic Programming is related to recursive relationships. Recursive relationships are associated with divide-and-conquer strategies. Mergesort and Quicksort follow divide-and-conquer strategies and exhibit optimal substructure properties.
Dynamic Programming can be implemented using Top-down and Bottom-up approaches. In the top-down approach the problem is solved recursively and using previous computation later on. In the bottom-up approach a table of subproblem results is built until the solution is reached.
In recursion we follow a top-down approach. Recursion begins with the initial problem which is broken down into subproblems. Subproblems are not solved for multiple times instead their solved results are saved which will be used later.
