| Review of Inequalities | Linear Programming Terms and Hints |
| Bounded and Unbounded Regions | Linear Programming Applications |
| Inequality Applications |
Linear Programming sounds really difficult, but it’s just a neat way to use math to find out the best way to do things – for example, how many things to make or buy. It usually involves a system of linear inequalities, called constraints, but in the end, we want to either maximize something (like profit) or minimize something (like cost). Whatever we’re maximizing or minimizing is called the objective function. Linear programming techniques were developed during the second World War for solving military logistic problems. It is used extensively today in business to minimize costs and maximize profits.
Before we start Linear Programming, here is a review of Linear Inequalities, which we saw here in the Coordinate System and Graphing Lines section.
Review of Inequalities
To solve inequalities on the coordinate system, graph the line using the “$ \displaystyle y=mx+b$” formula (or another method, like intercepts), and look which way the inequality sign is, with respect to the positive coefficient of $ \boldsymbol{y}$. The shaded areas will be where the equation “works”; in other words, where the solutions are.
For “$ y<$”, shade in under the line (or to the left, for a vertical line, when $ x=\text{a constant}$). Think of “less than” as “raining down” from the graph. Note the $ y$-coefficient must be positive for this to work.
For “$ y>$”, shade above the line (or to the right, for a vertical line). Think of “greater than” as “raining up” from the graph. (I know – it doesn’t really “rain up”, but I still like to explain the graphs that way.) Note the $ y$-coefficient must be positive for this to work.
This also works for horizontal lines ($ y=\text{a constant}$).
You can always plug in an $ (x,y)$ ordered pair to see if it shows up in the shaded areas (which means it’s a solution), or the unshaded areas (which means it’s not a solution.) For an example of this, see the first inequality below.
With “$ <$” and “$ >$” inequalities, draw a dashed (or dotted) line to indicate that we’re not including that line (exclusive), whereas with “$ \le$” and “$ \ge$”, draw a regular line, to indicate that we are including it in the solution (inclusive). To remember this, I think about the fact that “$ <$” and “$ >$” have less pencil marks than “$ \le$” and “$ \ge$”, so there is less pencil used when you draw the lines on the graph. You can also remember this by thinking the line under the “$ \le$” and “$ \ge$” means you draw a solid line on the graph.
Note that the last example is a “Compound Inequality” since it involves more than one inequality. The solution set is the ordered pairs that satisfy both inequalities; it is indicated by the darker shading. Here are some examples:
| Inequality/Explanation | Graph |
| $ y<2x+4$
First, graph the line $ y=2x+4$. For a “$ y<$” inequality, shade under the graph, since it “rains down”. Use a dashed line since there is a “$ <$ ”.
Plug in $ \left( {5,0} \right)$ to see if it shows up as a solution. $ \left( {5,0} \right)$ is in the shaded area, so that it satisfies the inequality: $ \displaystyle 0<2\left( 5 \right)+4\,\,\,\,\,\surd $. |  |
| $ 3x-4y\le 12$
The easiest way to graph this is with the “cover up” or intercepts method, since there are variables on one side and a constant on the other.
To graph using the intercepts method, cover up the $ 4y$ (making $ y=0$) and the $ x$-intercept is 4, since $ 3\times 4=12$. Then cover up the $ 3x$ (making $ x=0$) and the $ y$-intercept is –3, since $ -4\times -3=12$.
Be careful though since the $ -4y$ is before the $ \le $ sign. We need a positive $ y$, so the $ -4y$ would end up on the side of the “greater than”. Thus, shade above the line (“rains up”). Note that there is a solid line because of the “$ \ge $”. |  |
| $ x>3$
For a vertical line, with “greater than”, shade to the right. (With “less than”, $ <$, shade to the left.)
Note: For a horizontal line (like $ y>3$), shade above the line, and with $ y<3$, shade below the line. |  |
| Compound Inequality
$ y<2x+4$ and $ y\le 5$
Draw both lines and fill in the inequalities separately.
The solution set is the ordered pairs that satisfy both inequalities; it is indicated by the darker shading. Note that part of this solution would be inclusive (the solid lines) and part would be exclusive (the dotted line). |
|
Bounded and Unbounded Regions
Linear Programming problems typically have a set of compound bounded inequalities, meaning the regions of the inequalities have both maximum and minimum values. We’ll show examples below, but think of bounded meaning that you could draw a “circle” around the feasible region, which is the solution set to the inequalities.
By contrast, unbounded regions are not enclosed on all sides, and, again, we typically don’t see these in linear programming problems.
Here are examples of bounded and unbounded inequalities:
| Inequality/Explanation | Graph |
| $ \begin{array}{c}x+y\le 6\\x+2y\le 8\\x\ge 0\\y\ge 0\end{array}$
Graph the equations as equalities, and shade “up” or shade “down”. The easiest way to graph the first two inequalities is with the intercepts or “cover up” method. For example, for the second inequality, cover up the $ x$ to get $ 2y=8$, or $ y=4$, so the $ y$-intercept is $ (0,4)$; cover up the $ 2y$ to get $ x=8$, so the $ x$-intercept is $ (8,0)$.
This area is bounded, since you can draw a “circle” around the double-shaded region.
To test shading, check a point in the double-shaded area, and see if it works. For example, the point $ (2,2)$. It works in all the inequalities. |  |
| $ \begin{array}{c}2x+y\ge 8\\x+y\ge 5\\x\ge 0\\y\ge 0\end{array}$
This region is unbounded, since you can’t draw a “circle” around the double-shaded region (it goes on and on forever).
To test that you shaded correctly, check a point in the double-shaded area, and see if it works. For example, try the point $ (6,4)$. It works in all the inequalities. |  |
Inequality Applications
Linear Programming problems are typically word problems – not cool. But most will fit in the same mold for these beginning problems: they will have two types of unknowns or variables, like earrings and necklaces, and they will involve inequalities. The first variable can be put on the $ x$-axis and the second on the $ y$-axis. Typically, we’ll solve for the number of each type that either gives the maximum profit, or minimum cost.
First, here are some examples of graphing an inequality in real-life situations. Remember these common expressions with inequalities: “less than” ($ <$), “more than” ($ >$),“no more than” ($ \le$), “at least” ($ \ge$), and “at most” ($ \le$).
Problem:
Lisa has an online jewelry shop where she sells earrings and necklaces. She sells earrings for $30 and necklaces for $40. To make a profit, she must sell at least $1200 of jewelry per month. Define the variables, write an inequality for this situation, and graph the solutions to the inequality.
Solution:
It’s best to make the first item (pairs of earrings) the $ x$, and the second item (necklaces) $ y$. (Usually, we can look at what the problem is asking to get these variables).
Plug in some real numbers to try to get our equations. If she sells 1 pair of earrings and 1 necklace, she’ll only make $70, which is way below her goal for a profit. How about 20 pairs of earrings and 15 necklaces? Do you see what we’re doing here? The number of pairs of earrings she sells times $30 plus the number of necklaces she sells times $40 has to be greater than $1200. Also, she can’t sell less than 0 pairs of earrings or necklaces, so we need to include those inequalities, too.
Here are the inequalities, and a graph:
| Inequalities/Explanation | Graph |
| $ \begin{array}{c}30x+40y\ge 1200\\\,x\ge 0\\\,y\ge 0\end{array}$ Graph the equations as equalities, and shade “up” or shade “down”.
In the double-shaded region, we can see all the different combinations of number of pairs of earrings and number of necklaces to sell in order to make a profit. This area is unbounded, since you can’t draw a circle around the double-shaded region.
To test the shading, check a point in the double-shaded area, and see if it works. Try the point $ (40,15)$ (40 pairs of earrings and 15 necklaces). It works in all the inequalities. $ \displaystyle \surd $ |  |
Here is one more that that has a bounded region.
Problem:
Mark is buying two types of notebooks for school: spiral notebooks costs $2 and three-ring notebooks costs $4. Mark needs a total of at least six notebooks, but the total cost can be no more than $28. Find three combinations of notebooks that Mark can buy in order to meet these conditions.
Solution:
Here are the inequalities and a graph:
| Inequalities/Explanation | Graph |
| $ \begin{array}{c}2x+4y\le 28\\x+y\ge 6\\\,x\ge 0\\\,y\ge 0\end{array}$
Graph the equations as equalities, and shade “up” or shade “down”.
In the darker region, we can see all the different combinations of number of spiral notebooks and number of three-ring notebooks Mark can buy. This area is bounded, since you can draw a circle around this region.
Three random points that work are $ (7,1)$ (7 spirals and 1 three-ring), $ (4,4$) (4 spirals and 4 three-ring), and $ (1,6)$ (1 spiral and 6 three-ring). Try these combinations; they work! $ \displaystyle \surd $ |  |
Linear Programming Terms and Hints
Here are some hints for attacking Linear Programming problems, including important terms:
- Typically, you can look at what the problem is asking to determine what the variables are. You can put the first variable on the $ x$-axis and the second on the $ y$-axis.
- In most cases, you will be solving for the number of each type that either gives the maximum profit, or minimum cost. The maximum profit or minimum cost expression is called the objective function. As an example, to maximize profit, the objective function will be “Maximize $ 30x+40y$”.
- The inequalities of the problem are called the constraints, since we are limiting what we have, such as time or resources. If needed, we need to include non-negative constraints, where the $ x$- and $ y$-values have to be greater than or equal to 0. Some constraints will involve greater than inequalities, for example, if a certain number of things need to be sold.
- Usually there will be a sentence or phrase in the word problem for each constraint. Match units when coming up with inequality constraints; for example, one may have to do with money, and another with hours.
- We have to make sure our inequality is bounded, in order to find a maximum profit (for minimizing cost, it doesn’t have to be bounded, but it usually is). Again, the bounded region (solutions to the system of inequalities) is called the feasible region, which will be the double-shaded region.
- After we graph the inequalities, we’ll want to find the corner points. The corner points are the vertices of the feasible region, which are the intersections of the lines of the feasible region. The solution to the linear programming will occur at one of the corner points. (There is something called a Corner Point Theorem that proves this, but we won’t have to worry about it).
- Then, we’ll substitute our corner points into the objective function to see which point yields the largest (for maximizing profit) or smallest (for minimizing cost) value; this will be the optimal solution. We can do this with a table, as we’ll see later.
Linear Programming Applications
Now let’s put it all together and solve “real-life” linear programming problems!
Problem:
Lisa has an online jewelry shop where she sells earrings and necklaces. She sells earrings for $30 and necklaces for $40. It takes 30 minutes to make a pair of earrings and 1 hour to make a necklace, and, since Lisa is a math tutor, she only has 10 hours a week to make jewelry. In addition, she only has enough materials to make 15 total jewelry items per week. She makes a profit of $15 on each pair of earrings and $20 on each necklace. How many pairs of earrings and necklaces should Lisa make each week in order to maximize her profit, assuming she sells all her jewelry? Define the variables, write an inequality for this situation, and graph the solutions to the inequality.
Solution:
Variables: Look at what the problem is asking: how many pairs of earrings and how many necklaces should Lisa make to make a profit? Let $ x=$ the number of pairs of earrings, and $ y=$ the number of necklaces.
Objective Function: Since we are maximizing profit, this will be a maximum, and it will be total dollars. The objective function is “Maximize $ 15x+20y$”. Hint: Usually the objective function is a money function.
Constraints: Lisa’s constraints are based on her time, and also her materials. Always make sure all the units match; change 30 minutes into .5 hours. Note that we didn’t need to know what the jewelry sells for; sometimes they will give you extra information! Hint: To figure out the constraint inequalities, match units. For example, one inequality has to do with hours, the other with number of items. Set up a separate constraint for each sentence, and first put it in a table:
| $ x$ (Earrings) | $ y$ (Necklaces) | ||
| Hours | .5 | 1 | $ \le \text{ }10$ (hours in a week) |
| Materials | 1 | 1 | $ \le \text{ }15$ (total items in a week) |
Turn these into inequalities, and add the non-negative constraints:
| Inequalities/Explanation | Graph |
| $ \begin{array}{c}.5x+y\le 10\\x+y\le 15\\x\ge 0\\y\ge 0\end{array}$
Graph the equations as equalities, and shade “up” or shade “down”. This area is bounded, since you can draw a circle around the double-shaded region.
To test the shading, check a point in the double-shaded area, and see if it works. Try the point $ (5,5)$ (5 pairs of earrings and 5 necklaces). It works in all the inequalities. $ \displaystyle \surd $ |  |
Corner Points: Think of the corner points as on the outside of the shaded area, but where there is a turn in the graph (the vertices). In this case, we can easily see what they are from the graph; if we can’t, we’ll have to solve a system of equations (see next example). Take these points and plug in the $ x$- and $ y$-values into the objective function:
| Corner Point | $ x$ (Earrings) | $ y$ (Necklaces) | $ 15x+20y$ | Maximum |
| $ (0,0)$ | 0 | 0 | 0 | |
| $ (15,0)$ | 15 | 0 | 225 | |
| $ (0,10)$ | 0 | 10 | 200 | |
| $ (10,5)$ | 10 | 5 | 250 | $ \displaystyle \surd $ |
Thus, in order to maximize her profits, Lisa should make 10 pair of earrings and 5 necklaces per week, and her weekly profit is $250.
Problem:
Bountiful Boats has to produce at least 5000 cabin cruisers and 12,000 pontoons each year; they can produce at most 30,000 jet skis in a year. The company has two factories: one in Michigan, and one in Wisconsin; each factory is open for a maximum of 240 days per year. The Michigan factory makes 20 cabin cruisers, 40 pontoons, and 60 jet skis per day. The Wisconsin factory makes 10 cruisers, 30 pontoons, and 50 jet skis per day. The cost to run the Michigan factory per day is $960,000; the cost to run the Wisconsin factory per day is $750,000. How many days of the year should each factory run in order to meet the boat production, yet do so at a minimum cost? Define the variables, write an inequality for this situation, and graph the solutions to the inequality.
Solution:
Variables: Look at what the problem is asking: how many days of the year should each factory run? Let $ x=$ the number days per year that the Michigan factory should run, and $ y=$ the number days per year that the Wisconsin factory should run.
Objective Function: Since we are minimizing the cost per day, this will be a minimum, and it will be total dollars. The objective function then is “Minimize $ 960000x+750000y$”.
Constraints: Bountiful Boats’ constraints are based on how much they need to produce (both less than and greater than inequalities), how many days the factories are open (less than inequality), along with the non-negative constraints.
If you can’t find the constraints from sentences in the problem, look for another set of items (like cabin cruisers, pontoons, and jet skis), and these will usually each represent an inequality. Set up a separate constraint for each of the boats, and put them in a table. Note that the first two inequalities are greater than (“at least”), and the last one is less than (“at most”).
|
Numbers of boats made per day $ \to $ | $ x$ (days/year boats made in Michigan) | $ y$ (days/year boats made in Wisconsin) | Numbers of boats made per year $ \downarrow $ | ||
| Cruisers | 20 | 10 | $ \ge \text{ }5000$ | ||
| Pontoons | 40 | 30 | $ \ge \text{ }12000$ | ||
| Jet Skis | 60 | 50 | $ \le \text{ }30000$ | ||
Turn these into inequalities, and also add the factory days open and non-negative constraints. Notice how we use compound inequalities for the number of days open.
| Inequalities/Explanation | Graph |
| $ \displaystyle \begin{array}{c}20x+10y\ge 5000\\40x+30y\ge 12000\\60x+50y\le 30000\\0\le x\le 240\\0\le y\le 240\end{array}$
Graph the equations as equalities, and shade “up” or shade “down”. This area is bounded, since you can draw a “circle” around the double-shaded region. Notice that we didn’t really even need the equation $ \displaystyle 60x+50y\le 30000$; this constraint was taken care of by other constraints (this happens sometimes).
To test the shading, check a point in the double-shaded area, and see if it works. Try the point $ (200,200)$. It works in all the inequalities. $ \displaystyle \surd $ |  |
Corner Points: Think of the corner points as on the outside of the shaded area, but where there is a turn in the graph (the vertices).
Note that to get the exact points of intersection for the corner points, many times we need to set up a system of equations and solve. For example, for the exact intersection of $ \displaystyle 20x+10y=5000$ and $ \displaystyle 40x+30y=12000$ from the graph, we could turn the equations into equalities, and use Linear Combination of Systems to solve:
$ \displaystyle \begin{align}20x+10y&=5000\,\,\,\,\,\,\,\,\,\text{multiply by }-3\\40x+30y&=12000\\\\-60x+-30y&=-15000\\40x+\,\,\,\,\,30y&=12000\\-20x\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,&=-3000\,\\x&=150\end{align}$ $ \displaystyle \begin{align}40\left( {150} \right)+30y&=12000\\6000+30y&=12000\\30y&=6000\\y&=200\end{align}$
Take the corner points and plug in the $ x$- and $ y$-values into the objective function:
| Corner Point | $ x$ (Michigan) | $ y$ (Wisconsin) | $ 960000x+750000y$ | Minimum |
| $ (130,240)$ | 130 | 240 | 304,800,000 | |
| $ (150,200)$ | 150 | 200 | 294,000,000 | |
| $ (240,80)$ | 240 | 80 | 290,400,000 | $ \displaystyle \surd $ |
| $ (240,240)$ | 240 | 240 | 410,400,000 |
Note that you can see that the point $ (240,240)$ won’t provide a minimum since the point $ (240,80)$ will provide a smaller amount. So, technically, you wouldn’t even have to plug this point into the objective function.
In order to minimize their costs, Bountiful Boats should make boats 240 days a year at their Michigan plant, and 80 days a year at their Wisconsin plant. This will yield a cost of $290,400,000. You can see that your answer may be surprising!
Problem:
The office manager for a firm needs to purchase new solid-wood bookcases from two stores. Akea bookcases cost $100 each, require 6 square feet of floor space, and hold 8 cubic feet of books. Ekea bookcases cost $200 each, requires 8 square feet of floor space, and hold 12 cubic feet of books. The office manager’s budget allows her to spend no more than $1400 on the new bookcases, and the office has no more than 72 square feet of space for them. What is the greatest book storage capacity within the limits imposed by funds and space? How many bookcases from each store should be purchased? Define the variables, write an inequality for this situation, and graph the solutions to the inequality.
Solution:
Variables: Look at what the problem is asking: how many bookcases from each store should be purchased? Let $ x=$ the number of Akea bookcases, and $ y=$ the number of Ekea bookcases.
Objective Function: Since we are maximizing storage, this will be a maximum, and it will be cubic feet. The objective function is “Maximize $ 8x+12y$”.
Constraints: The constraints are based on the budget and square feet of floor space. Set up a separate constraint for each unit, and first put in a table:
| $ x$ (Akea Bookcases) | $ y$ (Ekea Bookcases) | ||
| Cost ($) | 100 | 200 | $ \displaystyle \le \text{ }1400$ |
| Floor Space (ft2) | 6 | 8 | $ \displaystyle \le \text{ }72$ |
Turn these into inequalities, and add the non-negative constraints:
| Inequalities/Explanation | Graph |
| $ \begin{array}{c}100x+200y\le 1400\\6x+8y\le 72\\x\ge 0\\y\ge 0\end{array}$
Graph the equations as equalities, and shade “up” or shade “down”. This area is bounded, since you can draw a circle around the double-shaded region.
To test the shading, check a point in the double-shaded area, and see if it works. Try the point $ (5,3)$ (5 Akea bookcases and 3 Ekea bookcases). It works in all the inequalities. $ \displaystyle \surd $ |  |
Corner Points: Think of the corner points as on the outside of the shaded area, but where there is a turn in the graph (the vertices). In this case, we can see what they are from the graph. Take these points and plug in the $ x$- and $ y$-values into the objective function:
| Corner Point | $ x$ (Akea Bookcases) | $ y$ (Ekea Bookcases) | $ 8x+12y$ | Maximum |
| $ (0,0)$ | 0 | 0 | 0 | |
| $ (12,0)$ | 12 | 0 | 96 | |
| $ (0,7)$ | 0 | 7 | 84 | |
| $ (10,5)$ | 8 | 3 | 100 | $ \displaystyle \surd $ |
Thus, in order to maximize the book storage capacity, the office manager should buy 8 Akea bookcases and 3 Ekea bookcases, for a total storage capacity of 100 cubic feet.
Learn these rules, and practice, practice, practice!
On to Rational Functions, Equations, and Inequalities – you are ready!