On Some Theorems of Stochastic Linear Programming with Applications

Abstract

A linear programming problem is said to be stochastic if one or more of the coefficients in the objective function or the system of constraints or resource availabilities is known only by its probability distribution. Various approaches are available in this case, which may be classified into three broad types: ‘chance constrained programming’, ‘two-stage programming under uncertainty’ and ‘stochastic linear programming’. For problems of ‘stochastic linear programming’ a distinction is usually made between two related approaches to stochastic programming, the passive and the active approach respectively. In the passive approach to stochastic linear programming the statistical distribution of the optimum value of the objective function is estimated either exactly or approximately by numerical methods and optimum decision rules are based on the different characteristics of the estimated distribution. In the active approach, a new set of decision variables are introduced which indicate the proportions of different resources to be allocated to the various activities. One effect of introducing this set of new decision variables in the active approach is the truncation of the statistical distribution of optimal value of the objective function of the passive approach. In this aspect the active approach is useful in suggesting criteria for changing from one optimum decision rule to another, as the probability distribution of the objective function is specified less and less incompletely for different choices of the set of new decision variables. This paper investigates some mathematical relations between the active and passive approach and derives some inequalities for the case when the elements of the coefficient matrix of the inequalities are random variables. Since an ’approximate solution’ of a stochastic linear programming problem is defined usually by replacing each random element by its expected value and then solving the resulting non-stochastic program, some conditions have been derived under which the expected value of the objective function for the optimal solution will exceed the optimal value of the objective function for ’the approximate solution’. Based on the properties of the distribution of extreme values and other order statistics, some approximate bounds have also been specified for the passive approach, which can easily be extended to the active approach.