Decomposition of systems governed by Markov chains

This paper applies the Dantzig-Wolfe decomposition technique to control systems governed by Markov chains, and the three usual types of costs: 1) the average cost attained until a target state is reached, 2) discounted cost, 3) average cost per unit time. Additional systems constraints are allowed. A technique for subdividing or "essentially" decomposing the problem is developed, and a Markov interpretation is given to each subsystem. The special significance, for this problem, of the extreme points and rays of the subproblem, is discussed.