Models - Operations Research Models and Methods

Models

Dynamic Programming

Terminology

The language of dynamic programming is quite different from that used in other areas of mathematical programming. Although it is common to have an objective to be optimized and a set of constraints that limits the decisions, a DP model represents a sequential decision process rather than an algebraic statement of a problem. The two principal components of the dynamic programming model are the states and decisions. A state is like a snapshot of the situation at some point in time. It describes the developments in sufficient detail so that alternative courses of action starting from the current state can be evaluated. A decision is an action that causes the state to change in some predefined way. Thus a decision causes a movement from one state to another. The state transition equations govern the movement. A sequential decision process starts in some initial state and advances forward, continuing until some final state is reached. The alternating sequence of states and decisions describes a path through the state space.

State	where is the value of state variable i and m is the number of state variables.
Initial state set	I = {s : states where the decision process begins}
Final state set	F = {s : states where the decision process ends}
State space	S = {s : s is feasible}
Decision	where is the value of the jthdecision variable and p is the number of decision variables.
Feasible decision	D(s) = {d : d leads to a feasible state from state s}
Transition function	s' = T(s, d), a function that determines the next state, s', reached when decision d is taken from state s
Decision objective	z(s, d), the measure of effectiveness associated with decision d taken in state s
Path objective	z(P), the measure of effectiveness defined for path P. This function describes how the objective terms for each state on the path and the final value function are combined to obtain a measure for the entire path.
Final value function	f(s) value that is specified for all final states