IN THE CLASSROOM

RICK HESSE, Feature Editor, Mercer University

Further Spreadsheet Graphs for Linear and Integer Programming

by Rick Hesse, Mercer University

In the previous column article we discussed a way to do some postoptimal graphs for Bob's Sweet Shop, who makes two types of hot fudge sundaes. (Imagine my delight when in May I got a call from one of our members who does management science analysis for a nationally known ice cream manufacturer and franchisee. Thanks for the free ice cream and the encouraging wordsþmaybe next time I'll write an article about luxury automobiles!) The spreadsheet layout in Figure 1 recaps the data elements and optimal solution for the Bob's Sweet Shop 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 two issues ago to illustrate the constraints and feasible region, but of course is limited to 2-variable LP problems. Last issue we showed how to illustrate post- optimal ranges for the objective function coefficients and constraint ranges. The generic postoptimal table can be developed from any program that gives the results of the solution of linear programming models. The term ``marginal value'' is a generic term to indicate shadow prices, reduced gradients, Lagrange multipliers, partial derivatives, reduced costs, and a plethora of associated terms. The ranges for the objective functions coefficients and resources are put in a more logical order for easier reading than the manner in which most programs present the results.

Looking at the ice cream resource, we see that ice cream is a binding resource between 40 and 54 ounces, with an associated marginal value of $0.443 per ounce. It is of interest to show what happens to this resource if we have more than the upper limit or less than the lower limit. If we set the amount of available ice cream at a little above the upper limit or below the lower limit and rerun the model and save the results, we will get a different marginal value and new range. Above 54 ounces ice cream is no longer a binding constraint, and thus has a marginal value of $0.00. The range below 40 ounces is from 26.667 ounces to 40, with a marginal value of $0.46 per ounce. By doing this successively (much easier to do on a spreadsheet than LINDO, OSB, etc.), we arrive at the lowest range, from 0-26.667 ounces with a marginal value of $0.55 per ounce.

Once we have determined the ranges and associated marginal values, we can determine the values of the decision variables at each of the break points. All of this information is shown in tabular fashion as well as graphically (the first two columns of the table) in Figure 3. From 54 ounces on, there is no value to added amounts of ice cream, and 60 is an arbitrary value chosen to get a nice looking graph. This graph gives a good visual picture that ice cream has about the same relative importance from none to 54 ounces. As with most sensitivity analysis, all other constraints stay the same while the amount of available ice cream changes.

A look at the hot fudge resource (Figure 4) gives only two break points at 32 ounces and 37.6 ounces, with a considerable reduction in the marginal value, as the graph dramatically shows. We could also develop a single resource table and graph for the banana constraint, but leave that as ``an exercise for the reader!''

Quick & Dirty Integer Solution

When we first solved the Bob's Sweet Shop as an LP problem, we found that we were making partial sundaes, and deferred until now how to find an integer solution. The add-in solvers have branch & bound capabilities which will find the optimal solution. (If you are using Excel or Quattro Pro, make sure that you set ``Best Integer'' option to 0.00 rather than the default of 0.05 (5% from the LP optimal).

But to illustrate a quick & dirty way to get the best integer solution, consider the two-way data table shown in Figures 5 and 6. The formula in I3 uses logic statements to check if all constraints are satisfied. Students can do this even if they don't have a solver with their spreadsheet.

We are able to illustrate the possible feasible integers solutions found in the table by adding them to the set of XY points in the graph range. Remember that you must have a blank row between each point. The data points and the resulting XY (Scatter) graph are shown in Figure 7.

Conclusion

This series of three column articles has taken Bob's Sweet Shop and illustrated many things that spreadsheets can do with both two-variable LP problems and those that have many more variables. Not only can the solver find workable solutions, but the postoptimal results can be graphed to give a visual presentation of the results. We have also seen how to use two-way data tables to illustrate finding good or optimal solutions to two-variable integer programming problems.

FOR COPIES OF FIGURES, contact the Managing Editor at dsihhj@gsusgi2.gsu.edu