When we recognize
the possibility of uncertainty or risk within the context of
mathematical programming, the decision problem might be written
as below. The
model is shown in the typical matrix format for an LP except
tildes appear over all the parameter matrices. This implies
that all
may be affected by a
vector of random variables. In practical instances the model
could be complicated by nonlinear terms and
integrality restrictions.
In any event, the
model as stated, is not well defined because: (1)
the
timing
of the
decisions
and observations of the randomness are ambiguous and (2)
what is meant by an optimal solution and a feasible solution
is unclear.
Stochastic programming addresses the first issue by explicitly
defining the sequence of decisions in relation to the realization
of the random variables. Given the sequence, an objective function
is defined that reflects a rational criterion for
evaluating the decisions at the time they must be made. Feasibility
conditions must be adapted to the fact that decisions made
before
the realization of randomness may have feasibility consequences
after the realization. How the issues are resolved leads to
the several different problems considered in this section.
No single problem formulation is sufficient.
For this section we assume that the
probability distribution of is
known. More properly we should say that stochastic programming
is *decision making under risk*, reserving the phrase *decision
making under uncertainty* for
those situations for which probability
distributions are unavailable. We will, however, use the
more popular term, uncertainty, to refer to situations
in which
distributions are known.
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. |