IN THE CLASSROOM

RICK HESSE, Feature Editor, Mercer University

Simple Graphs for Simple LP Problems

by Rick Hesse, Mercer University

Regardless of which management science text and software you use to teach linear programming, spreadsheets have a visual way of showing those simple two-dimensional LP problems that can show all the vital elements of LP. If you have the ability to show your spreadsheet in the classroom, this quick example can be modified to suit your needs and whichever textbook example you use to illustrate the graphical approach to LP. I have found over the years that listening to students is one of the best ways to continue to grow in knowledge. In fact, asking students if they have a better way of doing something can lead to interesting insights and better teaching. Such was the case when in the spring of 1992, I told my class that one of the drawbacks of using spreadsheets is that you couldn't graph a two-dimensional LP problem. After class, Ananat Bushnan, a student, came up and told me that you certainly could graph it in Lotus, and from that shared discovery has come some useful visual aids to teaching LP.

LP Model of Bob's Sweet Shop

Let us start with a simple problem of Bob's Sweet Shop, which makes two types of hot fudge sundaes. Now let us assume that Bob has a limited amount of materials and a shop full of customers, all wanting Deluxe or Super Sundaes. Bob wants to make the most money he can, and since his demand is far greater than he can produce, he has the luxury of being able to determine the optimal product mix. The spreadsheet layout in Figure 1 shows the data elements 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. The template then can accept values in cells B5..C5 and computes the objective function and then the constraints can be checked for feasibility.

Graphing the Model

An XY-graph can be developed as in Figure 2 to illustrate the constraints and feasible region. (If you have WYSIWYG in Lotus or use Excel or Quattro Pro, you can label the constraints.) The data points for this graph (called XY or Scatter in different spreadsheets) are given in Figure 3.

Each set of constraint end points is separated by a blank row and are in column order, so that the data is boxed (cells B13..C20) and you must specify these as a group in column order. To make the graph even more usable, the non-zero data points are formulas from the LP model data. Thus, cell B13 is +F7/B7 and cell C14 is +F7/C7, and so on. This will allow you later to change the right-hand-side(s) and watch the feasible area change and the feasible extreme points move. Again, if you have drawing tools on your spreadsheet, you can shade in the feasible area, if desired, and label the feasible extreme points, as shown in Figure 4.

Solving for Feasible Extreme Points

Depending upon the brand and version of the spreadsheet you use, there are several ways that you can determine the feasible extreme points C and D. I have shown the original matrix, right-hand-side, inverse, and solution in Figure 5. This can be done from either menu commands (Data Matrix in Lotus, Tools Statistics in Quattro Pro 5.0) or Excel has functions (MINVERSE, MPRODUCT) for this. You can also use a spreadsheet solver directly on the model to find the intersection of each pair of constraints and copy the results to a summary area.

From the data for the first graph and the solution of points C and D, a summary table of the feasible points A-E can be developed, as shown in Figure 6. The profit for CELL D22 is the formula $B$3*B22+$C$3*C22 copied to D23..D26. These points (B22..C26) make up a second XY-graph which outlines the feasible area and is also shown in Figure 6.

Embellishments

There are many other embellishments that can be made to these graphs, including adding iso-profit lines to show that the optimal LP solution must always occur at one or more of the feasible extreme points. Quattro Pro 5.0 has a nice slide show feature that allows you to set up layering each constraint one by one to show the reduced feasible area. I have left off labeling the axis and other niceties to keep the figures simple and less cluttered. Adding bounds constraints or ratio constraints (Delux/Super >= 2) requires choosing a set of two end points on each constraint that is only slightly more difficult than having all coefficients <=/> 0. Another embellishment is to "zoom" the graph, which can be done in WYSIWYG or by changing the scale for the X and Y axis with a manual lower and upper bound.

This template is now ready for doing postoptimal analysis, including sensitivity and range analysis, that will be covered in the next issue. We have also left the matter of partial sundaes being produced and sold for later discussion, but there is a quick way to handle integer linear programming on a spreadsheet with Two-Way Data Tables and logic statements.