The model has two stages as described below. We use notation that is compatible with the side-model notation introduced earlier. For this discussion we restrict attention to the linear case. The first-stage decisions are the vectors x and z. The decisions x appear only in the first-stage model, while z links the first and second stage. These decisions are constrained by linear constraints and simple upper bounds. The first-stage decisions contribute directly to the objective value through the first-stage costs.

The random variables affecting the second stage are described by the vector . In the most general case the vector may affect all aspects of the second-stage problem as indicated by the tildes over the parameters of the second stage. The cost of the second stage, , depends on z and on the realization of . This cost is a random variable. The problem for the decision maker is that x and z must be set before the realization, so the most reasonable first-stage decision should minimize the first-stage cost plus the expected value of the second-stage cost.

Recourse Model

It has been shown that there is a linear programming equivalent to the two-stage model when there is a finite number of possible realizations of the random features of the second stage. We call a particular realization a scenario and index the second-stage components to identify the scenarios. Each scenario has a specified probability.

The solution of the linear programming model simultaneously determines the first-stage decisions and the second-stage decisions for all scenarios. The last term in the objective function computes the expected recourse cost.

The fact that we can solve the stochastic programming problem with recourse is good news, since packages are available to solve large models efficiently. The difficulty is that for even small stochastic problems, the models become very large. The free Solver that comes with Excel can handle no more than 200 variables. Only very trivial problems are this small. We illustrate the method with a very small problem below and for a larger problem on the next page.

In the remainder of this section we consider only problems that can be modeled with the side model feature of the Math Programming add-in. We can build much larger models than can be solved with the free Solver. Solver versions with much larger capacities can be purchased from Front-Line Systems. With the side model, the matrix W must be the same for all realizations.

Although the general model includes a matrix Tk that depends on the scenario index k, we restrict attention to those allowed by the side model feature. Here a square diagonal matrix Dk is defined for each scenario. In the constraint set the diagonal matrix post multiplies a constant matrix T. Since only the diagonal elements are relevant they are stored on our side-model form in a single row for each scenario. Although not every situation can be handled using these matrices, we will find that they are very useful for some applications. For applications where Tk does not vary by scenario, Dk is an identity matrix for all k. The feature is illustrated for a two variable example below.

With these limitations, the problems to be considered are below.

More general models are easily constructed with the Math Programming add-in that allows inequality constraints, simple lower bounds, integer variables and various kinds of nonlinearities.

To illustrate the method we use the example used for simple recourse. A product mix problem has four products and two resources. The details of the problem are described at another page. The production amounts for the products are x1 through x4 in the master problem below. The unit profits for the products are in the objective coefficient row. The problem has two resources, carpentry and finishing. The hours used for the products on the resources are shown in the constraint matrix. The variables z1 and z2 are the amounts of the resources used for production. The equality constraints in the master problem assure the equality of z1 and z2 to the resources required.

The available hours for the resources are uncertain. The possible values of the hours available are shown in the table. The values are equally likely, so each has a 0.25 probability.

When the number of hours available for the resources happens to be less than the amount used by the production plan, there is a shortage of hours and extra hours must be purchased to make up the shortage. The cost of extra carpentry hours is $5 per hour and the cost of extra hours for finishing is $10 per hour. There is no penalty for when the available hours exceeds the amount used (overage).

The scenarios for the recourse model are determined by the possible values of carpentry and finish hours. Since each factor has four possibilities, there are 16 scenarios. Each is equally likely with probability (0.25)(0.25) = 0.0625. The decisions for the scenarios are the extra hours to purchase for each scenario. The scenario models are as below. Only the RHS values of the constraints and the decision variables differ by scenario.

The scenario problems are represented by rows in the side model starting at row 31. The T and W matrices are at the top of the side model. The scenario probabilities are in column I and the scenario RHS values are in columns T and U.