IN THE CLASSROOM

RICK HESSE, Feature Editor, Mercer University

More Graphs for Postoptimal LP

by Rick Hesse, Feature Editor

In the last issue of this column, we discussed a way to graph those simple 2-dimensional LP problems that can show all the vital elements of LP. Remember Bob's Sweet Shop, which makes two types of hot fudge sundaes? The spreadsheet layout in Figure 1 shows the data elements and optimal solution of the problem. The unshaded boxed cells contain data, the other unshaded cells contain labels, and the shaded cells are the objective function (D3), variables (B5..C5), and constraints (D7..D9). The formula for D3 is +B3*$B$5+C3*$C$5 and copied to D7..D9. An XY-graph was developed to illustrate the constraints and feasible region, but of course is limited to 2-variable LP problems.

Using any software, either a spreadsheet solver or a stand-alone program such as LINDO, the solution and postoptimal results can be summarized in a generic postoptimal report, such as the one shown in Figure 2. The generic term marginal value is used instead of the several other terms: shadow cost, reduced cost, gradient, Lagrange multiplier, or partial derivative. While the information in Figure 2 is in nice readable form, many people are not good or comfortable with just a table of numbers. Therefore a graphical representation along with the numbers may be another way to present the data.

The results in the table can be illustrated graphically without the requirement that there be just two decision variables, but I will continue to use this simple 2-variable example and illustrate range graphs using the High-Low-Close (HLC) graph. The coefficient ranges can be graphed using the HLC type graph found on spreadsheets (in Excel it is under the category of line graph). The data and graph are shown in Figure 3, which illustrates the bounds or limits of how much each objective function coefficient can be increased or decreased while the others are held constant and the LP problem would have the same solution values for the decision variables.

The small bar in between the ends of each range in the graph is the current value. The data (A13..D14) is arranged by columns with each row representing a coefficient. The four columns are the label, the low value, the high value (or these last two reversed) and the original (or close) value. This type of graph is normally used for stock market activity, but yields a useful picture of the relative sizes of the ranges. The lower limit is set to 0.0 but could be any appropriate value (like $0.500). Care must be taken if the upper or lower increase for a coefficient is infiniteþyou must set an appropriate bound. I usually set limits either on the graph scaling or on the spreadsheet using the MAX or MIN function. For this case, there are finite limits to the ranges.

The second data ranges that can be graphed are the resources. Resource constraints are usually supplies, materials that might be added or taken away. Including constraints that are ratio or material balance usually does not yield any insight. For this example, the data and HLC graph are shown in Figure 4.

Bananas have the widest allowable upper range not being a binding constraint (also indicated by the marginal value of $0.00). The narrowest range is the Hot Fudge resource, but of course each resource is measured in different units.

A way to be able to compare these "apples & oranges" is to measure the increase and decrease in terms of percentage. The data can be expressed in terms of percentage, with a low of 0% and an arbitrary high of 300% as shown in Figure 5.

Using percentages helps to compare the range increases and decreases in common terms, both visually and numerically.

I have presented three ways of graphing some of the postoptimal information found in standard LP problems that is not limited to just two-variable problems using the High-Low-Close type graph. Next time we will look at single resource graphs and the opportunity to solve Bob's problem as an integer programming problem using a two-way data table.

FOR COPIES OF THE FIGURES USED IN THIS ARTICLE,
CONTACT THE MANAGING EDITOR
tel. 404-286-0170
dsihhj@gsusgi2.gsu.edu