Linear Programming and Sequential Decision Models

This paper is designed to show how a typical sequential probabilistic model may be formulated in linear programming terms. In contrast with Dantzig and Radner, the time horizon here is an infinite one. For another very closely related study, the reader is referred to a paper by R. Howard.

The essential idea underlying this linear programming formulation is that the “state” variable i and the “decision” variable j are introduced as subscripts to the unknowns xij. These unknowns xij represent the joint probabilities with which the state variable takes on the value of i and the decision variable the value of j. Although the particular application described is a rather specialized one, there seem to be quite a number of other cases where the technique should be an efficient alternative to the functional equation approach of Bellman.