Chapter 11

Linear Programming11.1 Simple Geometric Considerations

One of the most important uses of row operations is in solving linear program problemswhich involve maximizing a linear function subject to inequality constraints determinedfrom linear equations. Here is an example. A certain hamburger store has 9000 hamburgerpatties to use in one week and a limitless supply of special sauce, lettuce, tomatoes, onions,and buns. They sell two types of hamburgers, the big stack and the basic burger. It has alsobeen determined that the employees cannot prepare more than 9000 of either type in oneweek. The big stack, popular with the teenagers from the local high school, involves twopatties, lots of delicious sauce, condiments galore, and a divider between the two patties.The basic burger, very popular with children, involves only one patty and some picklesand ketchup. Demand for the basic burger is twice what it is for the big stack. What isthe maximum number of hamburgers which could be sold in one week given the abovelimitations?

Let x be the number of basic burgers and y the number of big stacks which could be soldin a week. Thus it is desired to maximize z = x+ y subject to the above constraints. Thetotal number of patties is 9000 and so the number of patty used is x+2y. This number mustsatisfy x+2y≤ 9000 because there are only 9000 patty available. Because of the limitationon the number the employees can prepare and the demand, it follows 2x+ y ≤ 9000. Younever sell a negative number of hamburgers and so x,y ≥ 0. In simpler terms the problemreduces to maximizing z = x+y subject to the two constraints, x+2y≤ 9000 and 2x+y≤9000. This problem is pretty easy to solve geometrically. Consider the following picturein which R labels the region described by the above inequalities and the line z = x+ y isshown for a particular value of z.

x+2y = 4

2x+ y = 4

R

x+ y = z

As you make z larger this line moves away from the origin, always having the sameslope and the desired solution would consist of a point in the region, R which makes z aslarge as possible or equivalently one for which the line is as far as possible from the origin.Clearly this point is the point of intersection of the two lines, (3000,3000) and so themaximum value of the given function is 6000. Of course this type of procedure is fine fora situation in which there are only two variables but what about a similar problem in whichthere are very many variables. In reality, this hamburger store makes many more types of

221