Functions - Feasibility

For some problems it useful and sometimes necessary to identify specific combinations of the random variables that satisfy logical conditions. For example, say we are uncertain about the right-hand-side constants for the constraints of a linear programming model, so we assume that each constant is a random variable. Using the expected values of the random variables, we solve the LP model to obtain "optimum" values of the decision variables. We enclose the word optimum in quotes because the solution is only optimum for the expected values. It is probably not optimum for other realizations of the random variables. In fact, the solution is probably not feasible for some realizations. We want to use probability analysis to find the probability that the solution is feasible and also the expected value for the objective function over the solutions that are feasible. Feasibility is a logical state taking the values TRUE and FALSE. A solution is feasible (TRUE) if all the constraints are simultaneously satisfied. Otherwise the solution is not feasible (FALSE).

The add-in provides for logical conditions by including a cell for logical expressions along with each cell for function evaluations. On this page we illustrate this feature using the built-in function examples. We will return to the LP situation described above on another page.

To add logical expressions, we click the Include Feasibility box on the dialog. We use the term feasibility here to represent any logical expression because the concept of feasibility is so common for Operations Research.

The form shown below is the same as that considered earlier, but two new rows are added called Fun. Feas. (Function Feasible) and Prob. Feas. (Probability Feasible). The problem has already been solved on this form.

The function feasible row (row 16 for the example) holds logical expressions that can refer to the random variable values or other cells on the worksheet. Each logical expression returns either TRUE or FALSE. The examples shown above all relate to the values of the random variables. These are the built-in examples obtained when the Example Function button is clicked. Logical expressions for Excel may have a variety of forms as illustrated by the example. The three expressions used here have the mathematical descriptions shown below.

Note that the second and third conditions include the previous conditions, so the number of solutions that are feasible (the logical expression evaluates to TRUE) decreases with the function index.

Enumeration

When we choose the Moments command from the menu, the entire sample space of the random variables is enumerated. For every combination, the feasibility and function value for each function is evaluated. These values are combined to obtain the results in the green fields at the bottom of the form. Row 17 shows the probabilities that the logical expressions are satisfied. Row 19 shows the mean values of the functions for those solutions that satisfy the logical expressions. Row 20 shows the variances of the function values for those solutions that satisfy the logical expressions.

The formulas for calculating these values are below.

When we enumerate all possible values of the random variables, as for the example, these results are exact.

Simulation

The same problem can be addressed with Monte Carlo simulation. The figure below shows the form constructed for simulation with the results determined by a sample of 1000 observations.

The simulation results are reported in rows 12 through 18. The probability of feasibility is estimated as the proportion of the simulation observations that satisfy the feasibility conditions. Since the logical conditions for each function are different, these probabilities are all different. The moment values in rows 14 and 15 are computed only for feasible combinations. Since not all the combinations are feasible, the sample sizes used for the moment estimates are less than the number of iterations (1000). The reduced sample sizes generally increase the confidence intervals.

The results are obtained with the following formulas. Only feasible observations are used when computing moments.

The provision for logical functions described on this page will be useful in many contexts. Examples are given on later pages of this section.

Operations Research Models and Methods
Internet
by Paul A. Jensen