Introduction to Linear Programming

This section covers:

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 was 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, let’s review Graphing Linear Inequalities with Two Variables.

Review of Inequalities

Let’s go back and revisit graphing linear inequalities on the coordinate system.

To graph inequalities on the coordinate system, we need to 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.

When we have “$$y<$$”, we always shade in under the line that we draw (or to the left, if we have a vertical line). Think of “less than” as “raining down” from the graph. Note that we need a positive coefficient of $$y$$ for this to work.

When we have “$$y>$$”, we always shade above the line that we draw (or to the right, if we have 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 that we need a positive coefficient of $$y$$ for this to work.

Note that 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, we draw a dashed (or dotted) line to indicate that we’re not  including that line (but everything up to it), whereas with “$$\le$$” and “$$\ge$$”, we draw a regular line, to indicate that we are including it in the solution. 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$$. Since we have “$$y<$$” inequality, we shade under the graph, since it “rains down”. Note that we use a dashed line since we have a “$$<$$ ”.   Let’s 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$$. $$3x-4y\le 12$$   The easiest way to graph this is with the “cover up” or intercepts method, since we have variables on one side and the constant on the other.   To graph using the intercepts method, cover up the $$4y$$ (making $$y=0$$) and we see the $$x$$ intercept is 4, since $$3\times 4=12$$. Then cover up the $$3x$$ (making $$x=0$$) and we see that the $$y$$ intercept is –3, since $$-4\times -3=12$$.   We have to be careful though since we have a $$-3y$$ before the $$\le$$ sign. We need a positive $$y$$, so the $$-3y$$ would end up on the side of the “greater than”. Thus, we want to graph above the line (“rains up”). Note that we used a solid line since we have a “$$\ge$$”. $$x>3$$   Since we’re graphing a vertical line, when we’re dealing with “greater than”, when we need to shade to the right. With “less than” ($$<$$), we’d shade to the left.   If we’re graphing a horizontal line (like $$y>3$$), we’d shade above the line, or with $$y<3$$, shade below the line. Compound Inequality     $$y<2x+4$$  and  $$y\le 5$$   We draw both lines and fill in the inequalities separately.   Whatever is shaded in twice (shaded in from both graphs) contains the solutions. Again, 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.

Bounded and Unbounded Regions

With our Linear Programming examples, we’ll have a set of compound inequalities, and they will be bounded inequalities, meaning the regions of the inequalities will 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 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}$$   We’ll 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 that you shaded correctly, check a point in the double-shaded area, and see if it works. Let’s try 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. Let’s try the point $$(6,4)$$. It works in all the inequalities. Inequality Word Problem:

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.

You’ll just put the first variable on the $$x$$-axis and the second on the $$y$$-axis. We will be solving for the number of each type that either gives the maximum profit, or minimum cost. Let’s first see an example of just graphing an inequality in a real-life situation. 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 we’ll also draw a graph:  Inequalities/Explanation Graph $$\begin{array}{c}30x+40y\ge 1200\\\,x\ge 0\\\,y\ge 0\end{array}$$ We’ll 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 that you shaded correctly, check a point in the double-shaded area, and see if it works. Let’s try the point $$(40,15)$$ (40 pairs of earrings and 15 necklaces). It works in all the inequalities. 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 at least six notebooks, but the cost can be no more than$28. Find three combinations of notebooks that Mark that buy in order to meet these conditions.
Solution:
Here are the inequalities and graph:

 Inequalities/Explanation Graph $$\begin{array}{c}2x+4y\le 28\\x+y\ge 6\\\,x\ge 0\\\,y\ge 0\end{array}$$   We’ll 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

Again, the linear programming problems we’ll be working with have the first variable on the $$x$$-axis and the second on the $$y$$-axis. In our example, $$x$$ is the number of pairs of earrings and $$y$$ is the number of necklaces. Typically, you can look at what the problem is asking to determine what the variables are.

Typically, we 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. We’ll do an example where we want to maximize profit, so our 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. We’ll do an example where we are limiting our time to make jewelry. We also will always have our 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 Word Problems

Now let’s put it all together and solve “real” 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:  Let’s look at what the problem is asking: how many pairs of earrings and how many necklaces should Lisa make to make a profit? Let’s 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; we had to change 30 minutes into .5 hours. Also 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.

Let’s 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)

Let’s turn these into inequalities, and also 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}$$   We’ll 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 that you shaded correctly, check a point in the double-shaded area, and see if it works. Let’s try the point $$(5,5)$$ (5 pairs of earrings and 5 necklaces). It works in all the inequalities. 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).

Then take these points and plug in the $$x$$ and $$y$$ values into the objective function. Here is what we get:

 Corner Point $$x$$  (Earrings) $$y$$  (Necklaces) $$15x+20$$ Maximum $$(0,0)$$ 0 0 0 $$(15,0)$$ 15 0 225 $$(0,10)$$ 0 10 200 $$(10,5)$$ 10 5 250 $$\displaystyle \surd$$

So, 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,000How many days of the year should each factory run in order to meet the boat production, yet do so at a minimum cost? Solution: Variables: Let’s look at what the problem is asking: how many days of the year should each factory run? Let’s 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 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, we can look for another set of items (like cabin cruisers, pontoons, and jet skis), and these will usually each represent an inequality. Let’s set up a separate constraint for each of the boats, and put them in a table. Note that the first two inequalities are less than (“at least”), and the last one is greater 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$$ Let’s 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}$$ We’ll 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 that you shaded correctly, check a point in the double-shaded area, and see if it works. Let’s try the point $$(200,200)$$. It works in all the inequalities. 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. Let’s say we couldn’t see the exact intersection of $$\displaystyle 20x+10y=5000$$ and $$\displaystyle 40x+30y=12000$$ from the graphWe could turn the equations into equalities, and use Linear Combination of Systems to solve: $$\displaystyle \begin{array}{l}\,\,\,\,20x+10y=5000\,\,\,\,\,\,\,\,\,\,\,\,\,\,\text{multiply by }-3\\\,\,\,\,40x+30y=12000\\\\-60x+-30y=-15000\\\,\,\,\,\underline{{40x+\,\,\,\,30y=\,\,\,12000}}\\-20x\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,=-3000\,\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,x=150\\\\40(150)+30y=12000\\\,\,\,\,\,\,\,6000+30y=12000\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,30y=6000\\\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,y=200\end{array}$$ Then take these points and plug in the $$x$$ and $$y$$ values into the objective function. Here is what we get:  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. So you can see that your answer may be surprising!

Learn these rules, and practice, practice, practice!