p.77

The Stability of Truncated Solutions of Stochastic Linear Programming

J. K. Sengupta

Abstract

In an ordinary linear programming problem it is assumed that all the parameters (i.e., the coefficients of the objective function), the inequalities, and the resource availabilities are exactly known without errors. This assumption is relaxed in stochastic linear programming where some or all of the parameters are known only by their probability distributions. A distinction is generally drawn between the two approaches to stochastic linear programming: the passive (also termed "wait and see" approach) and the active (also termed "here and now" approach). In the passive approach the probability distribution of the objective function is derived explicitly or by numerical approximations, and decision rules are based on some features of this distribution. In the active approach additional decision variables are introduced indicating the amounts of various resources to be allocated to different activities. This paper analyzes a method of characterizing the distribution of the objective function values corresponding to the set of extreme points in the solution space for both these approaches of stochastic linear programming. Truncation refers to the selection of extreme points that are neighbors, so to say, to the optimal extreme point. The sensitivity of objective function values corresponding to truncated solutions is analyzed here in terms of stability properties, stability being measured in terms of variance. An application to an empirical economic problem where there are parametric variations in the coefficient matrix only is presented to illustrate the numerical problems and approximations involved in estimating the statistical distribution of the objective function. From an economic point of view the approach outlined here offers a theory of the second best, since it specifies the set of conditions under which a value of the objective function that corresponds to the optimum solution on the average may have higher instability than another value of the objective function that corresponds to a truncated solution, under the assumed conditions of stochastic linear programming.