Linear Programming, by hand

Return to Chapter 4 notes

This page will walk through solving a linear programming problem, using a calculator but only to help in the tedious process of solving the probem by hand. Our task is to is to use the constraints
-1x + y ≥ -7 3x + 1y ≤ 41 x + 2y ≤ 27
-7x + 3y ≤ -19 x + 2y ≥ 10
and then the positions in the critical region that produces a minimum and a maximum for the onjective function 5x – 7y and give the minimum and the maximum value achieved.

We start by graphing the inequalities (the constraints). To do this we want to find points on the lines represented by the "equality" part of the constraints. That is, we wnat to graph the equalities
-1x + y = -7 3x + 1y = 41 x + 2y = 27
-7x + 3y = -19 x + 2y = 10
We could do this in any number of ways. For example, we could put each equation into slope-intercept form (i.e., y = mx + b) and then use each intercept and slope to find a starting point and successive oints on the graph. We could even put those equations into the calcyulator, in the slope-intercept form, and have th calculator plot the graphs. If we did that then we could use the TRACE key to diplay points along the graph. lternatively, we could use the TABLE feature of the calculator to get sets of points that are on each line.

The approach we will take here is to use a special program,FINDPNTS, on the calculator. It turns out that any linear equation of the form Ax + By = C where A, B, and C are integers, must have points on it that are of the form (p,q) where p and q are integers. THe FINDPNTS program finds such points. The nice thing about those points is that they are easy to graph.

We start with the steps needed to load and run the program, and put in the coefficients of the first equation -1x + y = -7.
[Note: the images on this page tend to be small. On the computer screen you can point to an image, right click on it, and ask to view the image. Doing so should give you a larger version of the image.]
Once that is done the program continues by first printing out the formatted equation, so tht we can verify that we have put in the values correctly, and then it gives groups of lattice point (points with integer valeus) that are on the line.
The points that we are intrested in are in the first quadrant. Therefore, the first three of the screens shown above are of no particuar interest. However the fourth screen does give us the points (7,0), (8,1), and (9,2). That is all that we need to draw our line, but I went ahead and got yet another screen, shown below, that added the points (10,3), (11.4), (12,5), and (13,6). Then, on a piece of paper, we can graph those points, and finally connect them to get our line.
We should note on this that the inequality, the original constraint, -1x + y ≥ -7 has, as its solution the red line and all the points above it.

Then we move to the second equation, 3x + 1y = 41. The New option in the FINDPNTS program allows us to enter new coefficients. The screens below show that and the first two screens of lattice point solutions. The final screen above has points in the first quadrant, but I happen to know that the solution will fit on our graph paper and those points are way off of that diagram.
We continue with two more screens from the FINDPNTS program, giving us points (9,14), (10,11), (11,8), (12,5), (13,2) and (14,-1), which we then graph, and then connect, in this case with a blue line.
The original constraint, 3x + 1y ≤ 41 would have that blue line and all of the points to its left in the solution.

Still using the FINDPNTS program, we move to the third equation x + 2y = 27. We enter those coefficients and get some points on the line.
From that we have the points (-1,14), (1,13), (3,12), (5,11), (7,10), (9,9), (11,8), and (13,7). Again, we plot those points on our paper, and then we connect them to get our line, shown in green below.
We move to the fourth equation -7x + 3y = -19. We enter those coefficients and get some points on the line.
This gives us just three points of interest, namely, (1,-4), (4,3), and (7,10). Again, we plot those points on our paper, and then we connect them to get our line, shown in orange below.
We move to the fifth equation x + 2y = 10. We enter those coefficients and get some points on the line.
This gives us just three points of interest, namely, (-2,6), (0,5), (2,4), (4,3), (6,2), and (8,1). Again, we plot those points on our paper, and then we connect them to get our line, shown in purple below.
The final image above shows the critical region, the points that make all of the constraints true, shaded in gray. From that we can pick out the corner points of the critical region, namely, (8,1), (12,5), (11,8), (7,10) and (4,3).

Our task is now to ealuate the Objective function, namely 5x – 7y , for each of those points. We are done using FINDPNTS so we terminate that program using the END option. Then we use the STAT key to open that menu and there we select the Edit option. In the editor we put the x-values of the corner points into L1 and the corresponding y-values of the corner points into L2. This is shown in the following two screens.
Now we move the cursor to the L3 column and then use the up-arrow to move the cursor to the top of the column (the first figure below).
Once there, we enter the objective function as 5L1-7L2, as shown in the middle screen above. Once that has been entered, we press the ENTER key and the objctive function is evaluated for each pair in the first two columns with that new valu given in the third column.

All that remains now is to look down that third column, find the minimum and maximum values, and then report both those values and the points that generated them. In our example, the maximum value is 33 and it was generated at the point (8,1), while the minimum value is -35 and it was generated by the point (7,10). That is our solution.

Return to Chapter 4 notes

©Roger M. Palay     Saline, MI 48176     October, 2016