To explain the simple recourse
approach, we consider the linear programming model
below. We
show a tilde over the RHS vector to indicate that its components
are random variables with known probability distributions.
We use a minimization objective function for the convenience
of
the
discussion. The methods work equally well for ">=", "<="
and "=" constraints.
The problem, as stated, is not well defined
because it does not indicate
the
time order
of
decisions
and
random
variable realizations. Also, it does not specify the response
of the decision maker when the resources requested by a solution
exceed or fall below the amounts available. These issues
are addressed on this page.
The decision maker must choose the values of the variables, **x**,
before the random RHS values are known, so this is similar
to the no-recourse situation discussed on the previous pages.
The situation
is, however, a special case of the decision making with recourse problem
to be considered later, so we use the term *simple
recourse* to
describe this case.
The model below introduces new variables expressed by the
vector **z**,
where is
the amount of resource *i* used by the solution. The
constraints assure the equality between the amount of resource
used, and
. After the decisions have been made and after the random RHS
values are realized it may be that the amount of resource
used for
some constraint *i*, ,
may be different than the amount available, .
In that case we will assess a penalty based on the
difference between of the amount used over the amount available.
We cannot be sure of the value of the penalty when the decisions
are made, but we can compute the expected value. A reasonable
goal for
the
decision
maker
is to minimize the *expected value* associated with
the decision. This is reflected in the model.
The new term in the objective is the expected
cost of the resource used. We call it the *expected recourse
cost*.
We will derive a closed form expression for the expected
recourse cost,
so that the
model
can
be
solved as a
deterministic
equivalent
math programming model. When the probability distributions
for the
RHS values are discrete, the representation of the expected
value is piecewise linear, and it can be solved as
a linear program. When the distributions are continuous,
the model is
a separable nonlinear math programming model. The expected
recourse cost is a convex function of . On
this page we concentrate on the discrete distribution
case. On the next page we show how to approximate
a continuous distribution with a discrete distribution. In
the following we assume that the random variables are independent,
but the results can be extended
to dependent random
variables. |