Dynamic programming (DP) has quite a different model form
than the other types of mathematical programming. Instead of
an objective function and constraints, dynamic programming
models consist of a collection of equations that describe a
sequential decision process.
The process begins in some initial state, the first decision
moves it to a second state, and then continues through alternating
decisions and states until a final state is reached. For a
given problem, the model must provide:
-
mathematical vectors that describe states
and decisions
- initial and final state definitions
-
transition functions that map the current
state and decision to the next state in the sequence
-
the objective function that evaluates the
sequence of decisions
Many problems are naturally described as a sequential decision
process and are ready candidates for a DP solution. Others
that seem more naturally stated as Integer Programming models
can be adapted to the DP format. DP has an advantage over other
formulations in that it does not require linearity.
One difficulty with DP is the curse of dimensionality. DP
solves for the optimal solution from every feasible state.
If the number of feasible states is too large, a very long
time might be required to solve a problem.
This DP add-in provides a general structure with which most
problems appropriate for DP can be modeled and solved.
Use the links at the left to reach other relevant links on
this site. The DP Models PDF describes the general
model structure as well as several additional problem classes
with their dynamic programming models. The DP Methods PDF describes
the methods used for solution. The Models section
has a more mathematical treatment of the investment problem
used as an example in this section. The Download links download
the Excel add-in and the Excel demo file for this section.
Be sure you know how to install and use add-ins before attempting
to use these files. |
