To explain the simple recourse
approach, we consider the linear programming model
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
discussion. The methods work equally well for ">=", "<="
and "=" constraints.
The problem, as stated, is not well defined
because it does not indicate
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.
is, however, a special case of the decision making with recourse problem
to be considered later, so we use the term simple
describe this case.
The model below introduces new variables expressed by the
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
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
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
We will derive a closed form expression for the expected
so that the
solved as a
math programming model. When the probability distributions
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