One strategy is to replace the random variables by their expected values and solve the resultant deterministic model. We might ask how well this expected value solution serves as the solution to the stochastic problem. The expected value solution to our example problem is shown below. Since the expected values of the random variables are 0, the RHS values are just the constants originally proposed.

To evaluate this solution in a stochastic setting, we create a function model below the LP model. We create the model by calling the Function command of the Random Variables add-in. Five random variables are defined, each with a Normal distribution. Note that the algorithm field is blank. We use the Include Address option.

The LP model is the same as before, but now we allow the RHS values to vary randomly but do not solve the LP for each sample. For each sample, the solution variables are fixed at the values obtained with the expected RHS. The objective value does not change because the decision vector is fixed. The only question is: What is the probability that this solution will be feasible?

We place logical expressions in G15:G19 to indicate when the constraints are feasible. Cell G31 holds the address of the function value (the objective function of the LP), and cell G33 holds the address of the logical expression that returns TRUE if the solution is feasible and False if it is not. The LP solution on the worksheet is optimal when the RHS values are the expected values, so this solution is feasible. With the Include Address option, cells G32 and G34 are initially blank. They are filled with the appropriate transfer expression when the simulation begins.

These results should not be surprising. With the expected RHS values, four of the five constraints are tight in the deterministic optimal solution. Since the RHS values are Normally distributed, there is a 50% that a tight constraint will be violated when the random RHS is realized. Even if the single loose constraint is never violated, the probability that all the tight constraints are satisfied is 0.5 raised to the fourth power or 0.0625. The simulation shows that only 5% if the simulated RHS vectors result in feasible solutions.

One might ask, how should the problem with no recourse be solved? The answer to this question is the provence of stochastic programming.

Combining wait-and-see Solutions

One suggestion often made for this kind of problem is to solve the problem as if we could wait and see the random realizations and then combine the wait-and-see decisions in some way. We do this for the example by creating a new math programming model identical to the wait-and-see model considered earlier, but create a simulation form that records the values of the decision variables as well as the objective. The form is below. We now have 11 functions defined. The first is the objective function and the remaining ten are the values of the decision variables. All eleven functions have the same feasibility equation. A solution is recorded only when the LP has a feasible solution.

We simulate the random variables, solve the LP for each sample point and record the observed function values. The results from 100 observations is below. None of the solutions were infeasible as indicted by cell G37. This is not surprising since the wait-and-see solutions observe the RHS vector before finding the solution.

Row 39 shows the mean values for the 100 observations. The first entry shows the mean objective value of 125.97. The remainder of the entries on row 39 show the average values of the decision variables. Variables X1, X2, X4, X5, X8, and X10 are nonzero for at least some of the observations.

The Average Solution

To continue, we impose the average of the wait-and-see solution on the LP model.

We have investigated two solutions to the no-recourse problem, the expected value solution and the mean wait-and-see solution. The two solutions are shown in the table. The combined wait-and-see solution has a slightly higher objective value because it is not feasible for the expected RHS vector. Neither fixed solution has a very high chance of being feasible when there is randomness in the RHS vector.

When uncertainty affects the RHS values of the constraint coefficients, there is always a chance that some constraints will be violated by a fixed solution. Choosing a solution involves a tradeoff between the risk of infeasibility and the expected value of the objective function. Chance Constraints, described on the next page, gain some control of the feasibility probability, but again we will be left with a variety of alternative solutions.