Computerized closed form solutions to nonserial dynamic programming problems

Abstract

Dynamic programming models are typically solved by considering discrete values of the decision and state variables. Solutions are tabular inform, showing the best decision for discrete values of the state variable. For certain problems, analytic results can be computed as opposed to tabular solutions. This research develops a computerized procedure that yields closed form solutions for dynamic programming models with additive quadratic returns, linear state transition relationships, and a single state and decision variable per stage. The objective is to optimize the sum of returns from the stages. The return functions may be convex, nonconvex, or a mixture of these forms. Global parametric solutions are generated as functions of the system input state. Serial and some nonserial problems can be solved analytically on the computer. Computational concepts are borrowed from the study of networks, and dynamic programming procedures are in turn applied to a class of network problems. A FORTRAN program is presented to perform the analytical method, and solutions or large-scale problems are studied. Closed form solution methods are compared to approximate methods with respect to computational complexity and accuracy.