Show description

In this connection it should be noted that a discrete dynamic programming problem is considered to be discrete with respect to the structure of the stage process, not with respect to the structure of the state variables. There are situations in which the stage variable is considered to be continuous. This is the case when the stage variable is time and a decision can be made at any arbitrary time. Certain Markov decision processes [7] have this characteristic and these will be discussed in Chapter 8.

Bellman [3] approaches this matter by exhibiting a large number of specific kinds of problems and problem structures. , to have the principle of optimality apply. In addition, Denardo and Mitten [9, 13], Karp and Held [10], and Elmaghraby [11] give similar conditions on the monotonicity of the return (objective) functions in order that a sequential decision process be amenable to treat­ ment by dynamic programming. 4. The general framework we shall use to develop the basic theory will hopefully clarify some of these matters.

Let us consider that in the final stage we have a boundary or terminal state which we shall designate λ„ = b. , b = max(x„ | x^ ζ S„). Since a final value b is being given, this implies that we shall use a backwards solution from the final state, to find the values of x„_i, x„-2y "^yXv Hence we shall need to vary the values of λ^, Ag, . . , A„_i over all possible values, when we apply the principle of optimality. , the vec­ tors λ^, x^ each have only one component. 5). Si Since we do not know what the value of Ai should be as we work backwards, we must allow Ai to vary over its full allowable range.