Stochastic Programming

Linear programming has proven to be a suitable framework for the quantitative analysis of many decision problems. The reasons for its popularity are obvious: many practical problems can be modeled, at least approximately, as linear programs, and powerful software is available. Nevertheless, even if the problem has the necessary linear structure it is not sure that the linear programming approach works. One of the reasons is that the model builder must be able to provide numerical values for each of the coefficients. But in practical situations one often is not sure about the ‘true’ values of all coefficients. Usually the uncertainty is exorcised by taking reasonable guesses or maybe by making careful estimates. In combination with sensitivity analysis with respect to the most inaccurate coefficients this approach is satisfactory in many cases. However, if it appears that the optimal solution depends heavily on the value of some inaccurate data, it might be sensible to take the uncertainty of the coefficients into consideration in a more fundamental way. Since an evident framework for the quantitative analysis of uncertainty is provided by probability theory it seems only natural to interpret the uncertain coefficient values as realizations of random variables. This approach characterizes stochastic linear programming. In this chapter we discuss three small examples of linear programming problems in which some coefficients are random variables.