To Index To Models
Operations Research Models and Methods /Methods / Dynamic Programming

Teach Dynamic Programming Add-in



 

Contents

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.

To Index To Models TOC

Operations Research Models and Methods
by Paul A. Jensen and Jon Bard, University of Texas, Copyright by the Authors