For stochastic
programming, some variables are to be set by a decision
maker, these are the decision variables, while some
model parameters are determined by chance, and these are the
random variables. There are a variety of situations one might
consider in this context. One differentiation is based on when
the decision maker
must make decisions relative to the time when the random variables
are realized. There are several possibilities. Links on the
titles go to pages in this section. Some of these descriptions
are simplified from more general situations described in more
advanced sources.
*Wait and See*: The decision maker makes no decisions until
all random variables are realized.
*No Recourse*: The decision maker must choose values for the
decision variables before any of the random variables are
realized. There is a risk of violating the constraints.
*Chance Constraints*: This is the
no-recourse situation when only the RHS vector is random.
Solutions are found with specified
risks of constraint infeasibility.
*Simple Recourse*: This
topic considers the problem with a random RHS vector. The
decision maker must
choose values
for the
decision variables before
the
RHS values
are
known, but variables adjusting to the RHS variation are set
after the realization. Penalties for constraint violation
are specified. A section on *Approximations* indicates
how continuous probability distributions can be approximated
for this analysis. An *Aircraft
Allocation *example describes one of the first problems
addressed by stochastic programming.
*Recourse*: Some of the
decision variables must be set before the random variables
are realized, while others may wait
until
after they are realized. Models explicitly represent
the initial decisions and all recourse decisions. Although
the models can be very large, optimum solutions solve for
all possible circumstances. A *Capacity
Expansion *example shows
that small problems sometimes result in very large models.
*Multistage Recourse*: Decisions and random variables
are determined in stages. The first set of decision variables
must be fixed
before all realizations. Then the first set of random variables
are realized and the second set of decision variables are
fixed. The process continues through a series of decisions
and realizations. Typically the stages represent intervals
of time. We do not consider this situation.
This section addresses some of the relatively simple problems
of stochastic programming, those that we might be able to
approach
with our Excel add-ins. Along the way we provide examples of
situations involving uncertainty. There is a great deal
of high-level research in this field attempting to extend the
bounds on the variety of problems that can be practically
solved.
Most solutions require high-power computation. The research
and the computation are beyond the capabilities of this author
and also of Excel. The reader interested in pursuing this
subject further should visit the *Stochastic
Programming Community Home Page*.
Uncertainty, or risk, is modeled using random variables and
probability distributions. In this section, we often use the
features of the *Random
Variables* add-in, particularly the *Functions* feature.
A page is provided
in the random variables section summarizing some of the results
of this section. We assume in the following some familiarity
with probability theory and the Random Variables add-in. Many
of the models constructed in this section use the *Side
Model* feature
of the Math Programming add-in.
The materials here are partially based on the unpublished
manuscript *An Optimization Primer, An Introduction to Linear,
Nonlinear, Large-Scale, Stochastic Programming and Variational
Analysis*, by Roger J-B Wets, January 11, 2005. Suggestions
and notes from University of Texas colleagues David Morton
and Lisa Korf were very helpful. |