Multi-period stochastic programming.

摘要

This dissertation presents various aspects of the solution of linear multi-period stochastic programming problems. Under relatively mild assumptions on the stochastic structure of the problem, the value function at every time stage is shown to be convex in the history of the process, namely the random variables observed so far as well as the decisions taken up to that point.; Convexity enables the construction of both upper and lower bounds on the value of the entire problem by suitable discretization of the random variables. These bounds can be made arbitrarily sharp if the discretizations are chosen sufficiently fine.; The practise commonly followed to obtain a discretization of a random variable is to partition its support, usually into rectangular subsets, which requires the computation of the probability mass and weighted centroid for each element of the partition. This is a hard problem in itself, since in the continuous case it amounts to a multi-dimensional integration. Some Monte-Carlo techniques are described which can be used for normal distributions. These methods require random sampling, and the two main issues addressed are efficiency and accuracy.; Having obtained a suitable discretization, one can then solve the resulting large scale linear program which approximates the original problem. Its constraint matrix is highly structured, and an algorithm is presented which utilizes this structure. The algorithm uses the Dantzig-Wolfe decomposition principle, nesting deomposition levels one inside the other. Many of the subproblems generated in the course of this decomposition share the same constraint matrices and can thus be solved simultaneously. Numerical results show that the algorithm may out-perform a linear programming package on some simple problems.; Finally, all these ideas are combined and applied to a problem in forest management. Here it is required to find logging levels in each of several time periods to maximize the expected volume of lumber cut. Uncertainty enters into the model through the risk of forest fires and other environmental hazards, which may destroy a fraction of the existing forest. Several discretizations are used to formulate both upper and lower bound approximations to the original problem.