How to Make a Hula Hoop:

Discovering the Fundamental Theorem of Linear Programming

by Philip J. Owens
Austin Community College
Austin, Texas
e-mail: powens@austincc.edu

is a Registered Trademark of the  Corp.

Click for more about Wham-o

The Prologue , in which we are introduced to Joe and Josephine Hula

An algorithm for solving linear programming problems:

Experimental interlude : The Fundamental Theorem of Linear Programming
 

Prologue

• the standard model (called The Standard Model, or SM), and
• the professional model (called The Professional Model, or PM)

The profit on an SM is $50, and the profit on a PM is $60.

TYBO President Joe Hula meets with his top management team, consisting of Mrs. Josephine Hula (they make these things in their garage).

"How many of each kind should we make to maximize profit?", he asks.

"Make 20 SM's and the rest PM's, since the PM's have the highest profit margin," suggests Josephine.

Joe makes a quick calculation. "But that will cost $11200, and we have only $9000 for this production run. There seem to be some complicated trade-offs among the variables here."

"Oh-boy, we need some high-powered mathematics to solve this," offers Josephine.

Joe and Josephine, you may relax. There is an algorithm (computer scientists refer to well-defined methods for solving problems as "algorithms") for solving your problem.  As with all algorithms, it is described as a series of steps to be taken to arrive at a solution. Here are the steps:

We need to identify what it is we are looking for, and give them algebraic names, which we will then use in the mathematical expressions we will subsequently write. We call this step "writing the Let statement", and it looks like this:

Let

This may be the hardest part of the solution, because it requires that we read and correctly understand the statement of the problem, and that we recognize constraints for what they are when we read them. What we are looking for are all the statements in the problem description that assert that certain quantities must be greater-than-or-equal-to or less-than-or-equal-to certain other quantities. As we read the problem, we see that the constraints (4 of them) are all found in the abo ve paragraph, repeated here, with the constraints high-lighted in red:

They already have firm orders for 30 Standard Models and 20 Professional Models, and they know, based on market research, that they will be able to sell all of either model that they make.  The bank has told them that they can spend no more than $9000 dollars on the production run.  It costs $60 to manufacture an SM, and $100 to manufacture a PM. Production capacity is limited to a total of 120 hoops.

Restating the constraints using more-than and less-than language, we have:

(1)  they must make 30 or more SM's
(2)  they must make 20 or more PM's
(3)  the cost of production must be $9000 or less
(4)  they must make 120 or fewer hoops

Looking at the constraints more closely:

(1) they must make 30 or more SM's

Since the number of SM's is given by x (according to step 1), we may restate this constraint mathematically as:

(2) they must make 20 or more PM's

Since the number of PM's is given by y (according to step 1), we may restate this constraint mathematically as:

(3) the cost of production must be $9000 or less. Proceeding in small steps:

(4) they must make 120 or fewer hoops

The complete set of four constraints, mathematically stated, is

Every problem of this type has some quantity that we are to maximize or minimize. This quantity is called the objective function , and it must be stated algebraically.  It is not an equation or an inequality;  it is simply an expression.

By reading our problem carefully we can identify the objective function:

"How many of each kind should we make to maximize profit?", he asks.

Notice that the key word in identifying the objective function here was "maximize".  If you can find that word (or the word "minimize"),  or some variation thereof, in your problem,  you know you are hot on the trail of the objective function.  Unfortunately, the notion of "maximize" and "minimize" can be expressed using other terminology, and fiendish textbook writers will try to disguise the objective function to see how clever you can be at finding it (such authors created "where's Waldo?" games in a previous life).

What is to be maximized here?  Profit.  So profit is the objective function.  We need to turn profit into an expression involving the variables (x and y ) of the problem. Here goes:

profit = (profit from the SM's to be made) + (profit from the PM's to be made)

= (profit from x SM's) + (profit from y PM's)

and since (as stated in the problem)

we have the profit from x PM's and y SM's given by:

and the complete statement of the objective function is:

Don't forget to note which it is, maximize or minimize! Other problems (unlike TYBO's problem) will be minimization problems ;  for example, nuclear scientists may want to minimize the amount of radioactive waste being released by a nuclear reactor.

When speaking of these problems in general, the term "maximize or minimize" may be replaced by the single term optimize.  Optimize can stand for either maximize or minimize; which one it will stand for will depend on the specifics of the problem.

We have turned the problem as stated in words into a mathematical model, now stated completely in mathematical notation, as follows:

Variables:	Let:  x = the number of SM's to make  y = the number of PM's to make
Constraints:	x >= 30  y >= 20  x + y <= 120  60x + 100y <= 9000
Objective function:	(profit) = 50x + 60y (maximize)

Notice that the inequalities and the objective function are all linear :  there are no powers of x or y higher than 1, nor does the product xy appear anywhere.  Whenever this property holds for a problem situation of this type, we have what mathematicians refer to as a linear programming problem.

We will be graphing all four inequalities, but as an example, we will concentrate for now on the third one, "x + y <= 120".

You will remember from second-year algebra the algorithm for graphing a linear inequality:

Step 1: graph the corresponding equality; that is, the inequality with the inequality sign replaced by "=". This will graph as a line. For our inequality x + y <= 120, we will be graphing the line

Here is what it looks like when we graph it:

Step 2: shade one side of the line. You have been taught how to find the "correct" side to shade. That shaded portion will be the set of all points (x,y) that satisfy the inequality.

Note: In the shaded graphs to follow, I will indicate the "shading" by drawing a grayish border on the side of the line to be shaded (a complete shading for all inequalities would result in too messy a picture).  We will defer a complete shading to when we have all the inequalities drawn, and will then shade only those points that satisfy all the inequalities.

Here is the graph of "x + y <= 120", including shading:

Question: Can you tell (by the way I have depicted shading) which side of it includes those points (x, y) that satisfy the inequality x + y <= 120 ?
Answer: All points below the line.  The line itself is also included in the set, because our inequality is "<=", not just "<".

We now have a picture of all (x, y) pairs that satisfy the inequality x + y <= 120. In terms of the original problems, we can visualize all possible combinations of (number of SM, number of PM) that satisfy the constraint that we can produce no more that 120 hula hoops during one production run.

But that is only one of the constraints we must satisfy!  We need to graph all four inequalities, and examine the graph to find those points that satisfy not just any one of the constraints, but all of them simultaneously .

Here is what the graph of all four inequalities looks like.

Question: What region of the graph consists of exactly those points that satisfy all four inequalities?
Answer: The large quadrilateral (four-sided) region in the middle.

The set of points in the region you have identified is called the set of feasible solutions. Note that it is a geometrical shape, whose boundary is made up of straight lines. Each "corner" (where two lines intersect, and the boundary changes direction) is called a vertex (plural: vertices ).

Question: How many vertices are present in this system?
Answer: Four.

Make sure you understand what vertices are, as they play an important role in the experiment that follows, and in the solution of TYBO's problem.

To recapitulate, we have (graphically) described a set of feasible solutions. What we are really after is just one answer, not a whole region of a graph. What we have identified so far are all combinations of (#SM,#PM) (and there are many of them!) that satisfy the constraints.  That's not good enough.  We want the (usually) one combination that maximizes profit!

Going back to our graph, let's experiment a little with feasible solutions. If you place the cursor on a point in the feasible region and click on a point (x, y), you will cause the objective function (50x + 60y) to be evaluated for that (x, y) pair, and the value of the objective function will appear at that point. On the screen at the top of the screen you will see the coordinates of the (x, y) point you have clicked on. Remember, x = #SM's, and y=#PM's. Move the mouse around to various points and evaluate the objective function for those sample points

Note: if the graph gets too messy with lots of values, clean it up by clicking just to the right of where the x-axis ends.

Question 1: Do you see any pattern with regard to objective function values?
Question 2: In what part of the feasible region do the highest objective function values appear?
Question 3: Based on what you have seen, can you guess (approximately) what combination of values of x (number of SM's) and y (number of PM's) maximize profit?

Now, look again at the graph you have been reviewing and click just below the y-axis. This will cause the feasible region to be shaded in color. Those points whose objective function values are high will be shaded in bright red, those points whose objective function values are low will be shaded in bright green. Intermediate values will appear in various intermediate shades.

Question 4: Based on your observations, do you see a clear pattern of objective function values? Considering that pattern, can you guess what (x, y) pair would maximize the objective function (profit)?

Now, let's try another experiment.  You are about to see another system of inequalities.  Note that the system you are examining appears upper right in the window of the graph.  Do the same experiment with this linear programming problem.

Note: Some systems have only a maximum, some have only a minimum, and some have both. The system you are about to see has only a minimum. Why?

Question 5: Based on what you have observed so far, what would you tentatively conclude about where, in general, minimum and/or maximum objective function values occur?

To test your theory, try another one:

Question 5 (again): Based on what you have observed so far, what would you tentatively conclude about where, in general, minimum and/or maximum objective function values occur?

If your answer was at the vertices, you are absolutely correct! This leads us to the following remarkable theorem:
 

This is a truly remarkable theorem!  Most problems have infinitely many feasible solutions.  To find the one and onlyoptimum solution the "brute force" way, we would have to evaluate the objective function for infinitely many feasible points in order to find the one that provides the optimum value for the objective function.  This is clearly impossible, even for a computer!

The Fundamental Theorem of Linear Programming says that we need to consider only finitely many points (the vertices), and of those, pick just one that optimizes the objective function. This is possible, even for humans (if given enough time), and even more so for computers, which can solve problems of this type involving hundreds of variables (not just x and y!) and thousands of constraints.  Such problems actually appear in real-life business and industry situations, and their solution is key to optimizing the operations of that business or industry.  They will then pass the savings along to us, the consumer, of course!

This completes our experimental interlude.  Armed with the Fundamental Theorem of Linear Programming, we are ready to complete our program of describing how to solve Joe Hula's problem. We have proceeded through four steps:

Step 1: identify the variables
Step 2: identify and formulate the constraints
Step 3: identify and formulate the objective function
Step 4: graph the constraints

We proceed with the wrap-up steps, steps 5 and 6.

How do we find the vertices? We can see them on the graph, but how do we get them analytically (that is, by using algebra)?

It's not too hard, but it can be a little tedious.  You will observe that the vertices are where the lines intersect.  Your graph shows you where the vertices are, and which two lines intersect to form each vertex.  You have learned in algebra that the intersection of two lines is found by solving the equations of those lines simultaneously (by substitution , elimination, or by using Cramer's Rule).  The lines for TYBO are:

(1) x = 30
(2) y = 20
(3) x + y = 120
(4) 60x + 100y = 9000

Since there are four lines, there may be as many as four vertices, but no more than four (there may be fewer). I won't go through the algebra here, but (as was shown when you shaded the feasible region) the vertices are:

Intersection of lines x = 30, y = 20: the point (30, 20)
Intersection of lines x = 30, x + y = 120: the point (30, 72)
Intersection of lines x + y = 120, 60x + 100y = 900: the point (75, 45)
Intersection of the lines x + y = 120, y = 20: the point (100, 20)

If we now evaluate the objective function 50x + 60y for each of those points, we get:

vertex (x, y)	objective: 50x + 60y (maximize)
(30, 20)	2700
(30, 72)	5820
(75, 45)	6450
(100, 20)	6200

We want a maximum for all feasible solutions, and the Fundamental Theorem tells us that the maximum will occur at one of these four vertices. The maximum objective function value for the four vertices (and hence for the whole problem) is 6450, and occurs for the point (75, 45).

If we tell Joe and Josephine that we have solved their problem, and that "x = 75 and y = 45", they will conclude that we are a bit cracked, and gently but firmly escort us off the premises.  They will be much more receptive to the following statement:

What follows is a laboratory in which you can enter your own constraints and objective function. The computer will graph your constraints, and you will then be able to see what the optimal solution should be by shading the feasible region.