Linear Programming – Explanation and Examples

Linear programming is a way of using systems of linear inequalities to find a maximum or minimum value. In geometry, linear programming analyzes the vertices of a polygon in the Cartesian plane.Linear programming is one specific type of mathematical optimization, which has applications in many scientific fields. Though there are ways to solve these problems using matrices, this section will focus on geometric solutions.Linear programming relies heavily on a solid understanding of systems of linear inequalities. Make sure you review that section before moving forward with this one.In particular, this topic will explain:

• What is Linear Programming?
• How to Solve Linear Programming Problems
• Identifying Variables
• Identify the Objective Function
• Graphing
• The Solution

What is Linear Programming?

Linear programming is a way of solving problems involving two variables with certain constraints. Usually, linear programming problems will ask us to find the minimum or maximum of a certain output dependent on the two variables.Linear programming problems are almost always word problems. This method of solving problems has applications in business, supply-chain management, hospitality, cooking, farming, and crafting among others.Typically, solving linear programming problems requires us to use a word problem to derive several linear inequalities. We can then use these linear inequalities to find an extreme value (either a minimum or a maximum) by graphing them on the coordinate plane and analyzing the vertices of the resulting polygonal figure.

How to Solve Linear Programming Problems

Solving linear programming problems is not difficult as long as you have a solid foundational knowledge of how to solve problems involving systems of linear inequalities. Depending on the number of constraints, however, the process can be a bit time-consuming.The main steps are:

1. Identify the variables and the constraints.
2. Find the objective function.
3. Graph the constraints and identify the vertices of the polygon.
4. Test the values of the vertices in the objective function.

These problems are essentially complex word problems relating to linear inequalities. The most classic example of a linear programming problem is related to a company that must allocate its time and money to creating two different products. The products require different amounts of time and money, which are typically restricted resources, and they sell for different prices. In this case, the ultimate question is “how can this company maximize its profit?”

Identifying Variables

As stated above, the first step to solving linear programming problems is finding the variables in the word problem and identifying the constraints. In any type of word problem, the easiest way to do this is to start listing things that are known.To find the variables, look at the last sentence of the problem. Typically, it will ask how many __ and __… use whatever is in these two blanks as the x and y values. It usually does not matter which is which, but it is important to keep the two values straight and not mix them up.Then, list everything known about these variables. Usually, there will be a lower bound on each variable. If one is not given, it is probably 0. For example, factories cannot make -1 product.Usually there is some relationship between the products and limited resources like time and money. There may also be a relationship between the two products, such as the number of one product being greater than another or the total number of products being greater than or less than a certain number. Constraints are almost always inequalities.This will become clearer in context with the example problems.

Identify the Objective Function

The objective function is the function we want to maximize or minimize. It will depend on the two variables and, unlike the constraints, is a function, not an inequality.We will come back to the objective function, but, for now, it is important to just identify it.

Graphing

At this point, we need to graph the inequalities. Since it is easiest to graph functions in slope-intercept form, we may need to convert the inequalities to this before graphing.Remember that the constraints are connected by a mathematical “and,” meaning we need to shade the region where all of the inequalities are true. This usually creates a closed polygon, which we call “the feasible region.”That is, the area inside the polygon contains all possible solutions to the problem.Our goal, however, is not to find just any solution. We want to find the maximum or minimum value. That is, we want the best solution.Fortunately, the best solution will actually be one of the vertices of the polygon! We can use the graph and/or the equations of the bounds of the polygon to find these vertices.

The Solution

We can find the best solution plugging each of the x and y-values from the vertices into the objective function and analyzing the result. We then can pick the maximum or minimum output, depending on what we are looking for.We must also double check that the answer makes sense. For example, it does not make sense to create 0.5 products. If we get an answer that is a decimal or fraction and this does not make sense in context, we can analyze a nearby whole number point. We have to make sure that this point is still greater than/less than the other vertices before declaring it to be the maximum/minimum.This all may seem a bit confusing. Since linear programming problems are nearly always word problems, they make more sense when context is added.

Examples

In this section, we will add context and practice problems relating to linear programming. This section also includes step-by-step solutions.

Example 1

Consider the geometric region shown in the graph.

• What are the inequalities that define this function?
• If the objective function is 3x+2y=P, what is the maximum value of P?
• If the objective function is 3x+2y=P, what is the minimum value of P

Example 1 Solution

Part A

This figure is bounded by three different lines. The easiest one to identify is the vertical line on the right side. This is the line x=5. Since the shaded region is to the left of this line, the inequality is x≤5.Next, let’s find the equation of the lower bound. This line crosses the y-axis at (0, 4). It also has a point at (2, 3). Therefore, its slope is (4-3/0-2)=^-1/₂. Therefore, the equation of the line is y=-¹/₂x+4. Since the shading is above this line, the inequality is y≥-¹/₂x+4.Now, let’s consider the upper bound. This line also crosses the y-axis at (0, 4). It has another point at (4, 3). Therefore, its slope is (3-4)/(4-0)=^-1/₄. Thus, its equation is y=-¹/₄x+4. Since the shaded region is below this line, the inequality is y≤–¹/₄x+4.In summary, our system of linear inequalities is x≤5 and y≥–¹/₂x+4 and y≤–¹/₄x+4.

Part B

Now, we are given an objective function P=3x+2y to maximize. That is, we want to find values x and y in the shaded region so that we can maximize P. The key thing to note is that an extrema of the function P will be at the vertices of the shaded figure.The easiest way to find this is to test the vertices. There are ways to find this using matrices, but they will be covered in greater depth in later modules. They also work better for problems with significantly many more vertices. Since there are only three in this problem, this is not too complicated.We already know one of the vertices, the y-intercept, which is (0, 4). The other two are intersections of the two lines with x=5. Therefore, we just need to plug x=5 into both equations.We then get y=-¹/₂(5)+4=-⁵/₂+4=1.5 and y=-¹/₄(5)+4=2.75. Thus, our other two vertices are (5, 1.5) and (5, 2.75).Now, we plug all three pairs of x and y-values into the objective function to get the following outputs.(0, 4): P=0+2(4)=8.(5, 1.5): P=3(5)+2(1.5)=18(5, 2.75): P=3(5)+2(2.75)=20.5.Therefore, the function P has a maximum at the point (5, 2.75).

Part C

We actually did most of the work for part C in part B. Finding the minimum of a function is not very different than finding the maximum. We still find all of the vertices and then test all of them in the objective function. Now, however, we just select the output with the smallest value.Looking at part B, we see that this happens at the point (0, 4), with an output of 8.

Example 2

A company creates square boxes and triangular boxes. Square boxes take 2 minutes to make and sell for a profit of $4. Triangular boxes take 3 minutes to make and sell for a profit of $5. Their client wants at least 25 boxes and at least 5 of each type ready in one hour. What is the best combination of square and triangular boxes to make so that the company makes the most profit from this client?

Example 2 Solution

The first step in any word problem is defining what we know and what we want to find out. In this case, we know about the production of two different products which are dependent upon time. Each of these products also makes a profit. Our goal is to find the best combination of square and triangular boxes so that the company makes the most profit.

Constraints

First, let’s write down all of the inequalities we know. We can do this by considering the problem line by line.The first line tells us that we have two kinds of boxes, square ones and triangular ones. The second tells us some information about the square boxes, namely that they take two minutes to make and net $4 profit.At this point, we should define some variables. Let’s let x be the number of square boxes and y be the number of triangular boxes. These variables are both dependent upon each other because time spent making one is time that could be spent making the other. Make a note of this so that you do not mix them up.Now, we know that the amount of time spent making a square box is 2x.Now, we can do the same with the number of triangular boxes, y. We know that each triangular box requires 3 minutes and nets $5. Therefore, we can say that the amount of time spent making a triangular box is 3y.We also know that there is a limit on the total time, namely 60 minutes. Thus, we know that the time spent making both types of boxes must be less than 60, so we can define the inequality 2x+3y≤60.We also know that both x and y must be greater than or equal to 5 because the client has specified wanting at least 5 of each.Finally, we know that the client wants at least 25 boxes. This gives us another relationship between the number of square and triangular boxes, namely x+y≥25.Thus, overall, we have the following constraints:2x+3y≤60x≥5y≥5x+y≥25.These constraints function line the boundaries in the graphical region from example 1.

The Objective Function

Our objective, or goal, is to find the greatest profit. Therefore, our objective function should define the profit.In this case, profit depends on the number of square boxes created and the number of triangular boxes created. Specifically, this company’s profit is P=4x+5y.Note that this function is a line, not an inequality. In particular, it looks like a line written in standard form.Now, to maximize this function, we need to find the graphical region represented by our constraints. Then, we need to test the vertices of this region in the function P.

The Graph

Now, let’s consider the graph of this function. We can first graph each of our inequalities. Then, remembering that linear programming problem constraints are connected by a mathematical “and,” we will shade the region that is a solution to all four inequalities. This graph is shown below.This problem has three vertices. The first is the point (15, 10). The second is the point (20, 5). The third is the point (22.5, 5).Let’s plug all three values into the profit function and see what happens.(15, 10): P=4(15)+5(10)=60+50=110.(20, 5): P=4(20)+5(5)=105.(22.5, 5): P=4(22.5)+5(5)=90+25=115.This suggests that the maximum is 115 at 22.5 and 5. But, in context, this means that the company must make 22.5 square boxes. Since it cannot do that, we have to round down to the nearest whole number and see if this is still the maximum.At (22, 5), P=4(22)+5(5)=88+25=113.This is still greater than the other two outputs. Therefore, the company should make 22 square boxes and 5 triangular boxes to satisfy the client’s demands and maximize its own profit.

Example 3

A woman makes craft jewelry to sell at a seasonal craft show. She makes pins and earrings. Each pin takes her 1 hour to make and sells for a profit of $8. The pairs of earrings take 2 hours to make, but she gets a profit of $20. She likes to have variety, so she wants to have at least as many pins as pairs of earrings. She also knows that she has approximately 40 hours for creating jewelry between now and the start of the show. She also knows that the craft show vender wants sellers to have more than 20 items on display at the beginning of the show. Assuming she sells all of her inventory, how many each of pins and earring pairs should the woman make to maximize her profit?

Example 3 Solution

This problem is similar to the one above, but it has some additional constraints. We will solve it in the same way.

Constraints

Let’s begin by identifying the constraints. To do this, we should first define some variables. Let x be the number of pins the woman makes, and let y be the number of pairs of earrings she makes.We know that the woman has 40 hours to create the pins and earrings. Since they take 1 hour and 2 hours respectively, we can identify the constraint x+2y≤40.The woman also has constraints on the number of products she will make. Specifically, her vender wants her to have more than 20 items. Thus, we know that x+y>20. Since, however, she cannot make part of an earring on pin, we can adjust this inequality to x+y≥21.Finally, the woman has her own constraints on her products. She wants to have at least as many pins as pairs of earrings. This means that x≥y.In addition, we have to remember that we cannot have negative numbers of products. Therefore, x and y are both positive too.Thus, in summary, our constraints are:X+2y≤40X+y≥21x≥yx≥0y≥0.

The Objective Function

The woman wants to know how she can maximize her profits. We know that the pins give her a profit of $8, and earrings earn her $20. Since she expects to sell all of the jewelry she makes, the woman will make a profit of P=8x+20y. We want to find the maximum of this function.

The Graph

Now, we need to graph all of the constraints and then find the region where they all overlap. It helps to first put them all in slope-intercept form. In this case, then, we havey≤–¹/₂x+20y≥-x+21y≤xy≥0x≥0.This gives us the graph below.Unlike the previous two examples, this function has 4 vertices. We will have to identify and test all four of them.Note that these vertices are intersections of two lines. To find their intersection, we can set the two lines equal to each other and solve for x.We’ll move from left to right. The far left vertex is the intersection of the lines y=x and y=-x+21. Setting the two equal gives us:x=-x+21.2x=21.Therefore x=²¹/₂, 0r 10.5 When x=10.5, the function y=x also is 10.5. Thus, the vertex is (10.5, 10.5).The next vertex is the intersection of the lines y=x and y=-¹/₂x+20. Setting these equal gives us:X=-¹/₂x+20³/₂x=20.Therefore, x=⁴⁰/₃, which is about 13.33. Since this is also on the line y=x, the point is (⁴⁰/₃, ⁴⁰/₃).The last two points lie on the x-axis. The first is the x-intercept of y=-x+21, which is the solution of 0=-x+21. This is the point (21, 0). The second is the x-intercept of y=-¹/₂x+20. That is the point where we have 0=-¹/₂x+20. This means that -20=-¹/₂x, or x=40. Thus, the intercept is (40, 0).Therefore, our four vertices are (10.5, 10.5), (⁴⁰/₃, ⁴⁰/₃), (21, 0), and (40, 0).

Finding the Maximum

Now, we test all four points in the function P=8x+20y.(10.5, 10.5)=294(⁴⁰/₃, ⁴⁰/₃)=1120/3 (or about 373.33)(0, 21)=168(0, 40)=320.Now, the maximum in this case is the point (⁴⁰/₃, ⁴⁰/₃). However, the woman cannot make ⁴⁰/₃ pins or ⁴⁰/₃ pairs of earrings. We can adjust by finding the nearest whole number coordinate that is inside the region and testing it. In this case, we have (13, 13) or (14, 13). We will choose the latter since it will obviously yield a larger profit.Then, we have:P=14(8)+13(20)=372.Thus, the woman should make 14 pins and 13 pairs of earrings for the greatest profit given her other constraints.

Example 4

Joshua is planning a bake sale to raise funds for his class field trip. He needs to make at least $100 to meet his goal, but it is okay if he goes above that. He plans to sell muffins and cookies by the dozen. The dozen muffins will sell for a profit of $6, and the dozen cookies will sell for a profit of $10. Based on sales from the previous year, he wants to make at least 8 more bags of cookies than bags of muffins.The cookies require 1 cup of sugar and ³/₄ cups of flour per dozen. The muffins require ¹/₂ cup of sugar and ³/₂ cups of flour per dozen. Joshua looks into his cabinet and finds that he has 13 cups of sugar and 11 cups of flour, but he does not plan to go get more from the store. He also knows that he can only bake one pan of a dozen muffins or one pan of a dozen cookies at a time. What is the fewest number of pans of muffins and cookies Joshua can make and still expect to meet his financial goals if he sells all of his product?

Example 4 Solution

As before, we will have to identify our variables, find our constraints, identify the objective function, graph the system of constraints, and then test the vertices in the objective function to find a solution.

Constraints

Joshua wants to know how the minimum number of pans of muffins and cookies to bake. Thus, let’s let x be the number of pans of muffins and y be the number of pans of cookies. Since each pan makes one dozen baked goods and Joshua sells the baked goods by the bag of one dozen, let’s ignore the number of individual muffins and cookies so as not to confuse ourselves. We can instead focus on the number of bags/pans.First, Joshua needs to make at least $100 to meet his goal. He earns $6 by selling a pan of muffins and $10 by selling a pan of cookies. Therefore, we have the constraint 6x+10y≥100.Joshua also has a limitation based on his flour and sugar supplies. He has 13 total cups of sugar, but a dozen muffins calls for ¹/₂ cup and a dozen cookies calls for 1 cup. Thus, he has the constraint ¹/₂x+1y≤13.Likewise, since a dozen muffins requires ³/₂ cups of flour and a dozen cookies requires ³/₄ cups of flour, we have the inequality ³/₂x+³/₄y≤11.Finally, Joshua cannot make fewer than 0 pans of either muffins or cookies. Thus, x and y are both greater than 0. He also wants to make at least 8 more pans of cookies than muffins. Therefore, we also have the inequality y-x≥10Therefore, our system of linear inequalities is:6x+10y≥100¹/₂x+y≤13³/₂x+³/₄y≤11y-x≥8x≥0y≥0

The Objective Function

Remember, the objective function is the function that defines the thing we want to minimize or maximize. In the previous two examples, we wanted to find the greatest profit. In this case, however, Joshua wants a minimum number of pans. Thus, we want to minimize the function P=x+y.

The Graph

In this case, we are finding the overlap of 6 different functions!Again, it is helpful to turn our constraint inequalities into y-intercept form so they are easier to graph. We get:y≥³/₅x+10y≤–¹/₂x+13y≥x+8x≥0y≥0When we create the polygonal shaded region, we find that it has 5 vertices, as shown below.

The Vertices

Now, we need to consider all 5 vertices and test them in the original function.We have two vertices on the y-axis, which come from the lines y=-³/₅x+10 and y=-¹/₂x+13. Clearly, these two y-intercepts are (0, 10) and (0, 13).The next intersection, moving from left to right is the intersection of the lines y=-¹/₂x+13 and y=-2x+⁴⁴/₃. Setting these two functions equal gives us:–¹/₂x+13=-2x+⁴⁴/₃.Moving the x values to the left and the numbers without a coefficient to the right gives us³/₂x=⁵/₃.x=¹⁰/₉.When x=¹⁰/₉, we have y=-2(¹⁰/₉)+44/3=-²⁰/₉+¹³²/₉=¹¹²/₉, which has the decimal approximation 12.4. Thus, this is the point (¹⁰/₉, ¹¹²/₉) or about (1.1, 12.4).The next vertex is the intersection of the lines y=-³/₅x+10 and y=x+8. Setting these equal, we have:–³/₅x+10=x+8–⁸/₅x=-2.Solving for x then gives us ⁵/₄. At ⁵/₄, the function y=x+8 is equal to 37/4, which is 9.25. Therefore, the point is (⁵/₄, ³⁷/₄) or (1.25, 9.25) in decimal form.Finally, the last vertex is the intersection of y=x+8 and y=-2x+⁴⁴/₃. Setting these equal to find the x-value of the vertex, we have:X+8=-2x+⁴⁴/₃.Putting the x-values on the left and numbers without a coefficient on the right gives us3x=²⁰/₃.Thus, solving for x gives us ²⁰/₉ (which is about 2.2). When we plug this number back into the equation y=x+8, we get y=²⁰/₉+⁷²/₉=⁹²/₉. This is approximately 10.2. Therefore, the last vertex is at the point (²⁰/₉, ⁹²/₉), which is about (2.2, 10.2).

Finding the Minimum

Now, we want to find the minimum value of the objective function, P=x+y. That is, we want to find the fewest number of pans of muffins and cookies Joshua has to make while still satisfying all the other constraints.To do this, we have to test all five vertices: (0, 13), (0, 10), (¹⁰/₉, ¹¹²/₉), (⁵/₄, ³⁷/₄), (²⁰/₉, ⁹²/₉)(0, 13): 0+13=13.(0, 10): 0+10=10.(¹⁰/₉, ¹¹²/₉): ¹⁰/₉+¹¹²/₉=¹¹²/₉, which is about 13.5.(⁵/₄, ³⁷/₄): ⁵/₄+³⁷/₄, which is ⁴²/₄=10.5.(²⁰/₉, ⁹²/₉): ²⁰/₉+⁹²/₉=¹¹²/₉. This is about 12.4.Therefore, it seems Joshua’s best bet is to make 0 muffins and 10 cookies. This probably makes the baking simple anyway!If, however, he wanted to make as many products as possible, (that is, if he wanted the maximum instead of the minimum), he would want to make ¹⁰/₉ muffins and ¹¹²/₉ cookies. This is not possible, so we would have to find the nearest whole number of cookies and muffins. The point (1, 12) is inside the shaded region, as is (0, 13). Either of these combinations would be the maximum.

Note

It is possible to have shaded regions with even more vertices. For example, if Joshua wanted a minimum number of bags of muffins or a maximum number of bags of cookies, we would have another constraint. If he wanted a minimum number of total bags of baked goods, we would have another constraint. Additionally, we could develop more constraints based on the number of ingredients. Things like eggs, butter, chocolate chips, or salt could work in this context. In some cases, a solution could become so complex so as not to have any feasible answers. For example, it is possible that the region not include any solutions where both x and y are whole numbers.

Example 5

Amy is a college student who works two jobs on campus. She must work for at least 5 hours per week at the library and two hours per week as a tutor, but she is not allowed to work more than 20 hours per week total. Amy gets $15 per hour at the library and $20 per hour at tutoring. She prefers working at the library though, so she wants to have at least as many library hours as tutoring hours. If Amy needs to make 360 dollars, what is the minimum number of hours she can work at each job this week to meet her goals and preferences?

Example 5 Solution

As with the other examples, we need to identify the constraints before we can plot our feasible region and test the vertices.

Constraints

Since Amy is wondering how many hours to work at each job, let’s let x bet the number of hours at the library and y the number of hours at tutoring.Then, we know x≥5 and y≥2.Her total number of hours, however, cannot be more than 20. Therefore, x+y≤20.Since she wants to have at least as many library hours as tutoring hours, she wants x≥y.Each hour at the library earns her $15, so she gets 15x. Likewise, from tutoring, she earns 20y. Thus, her total is 15x+20y, and she needs this to be more than 360. Therefore, 15x+20y≥360.In sum, then Amy’s constraints arex≥5y≥2x+y≤20x≥y15x+20y≥360

The Objective Function

The total number of hours that Amy works is the function P=x+y. We want to find the minimum of this function inside the feasible region.

The Feasible Region

To graph the feasible region, we need to first convert all of the constraints to slope-intercept form. In this case, we have:x≥5y≥2y≤-x+20y≤xy≥-³/₄x+18.This graph looks like the one below.Yes. This graph is blank because there is no overlap between all of these regions. This means that there is no solution.

Alternative Solution?

Perhaps Amy can persuade herself to get rid of the requirement that she work fewer hours at tutoring than at the library. What is the fewest number of hours she can work at tutoring and still meet her financial goals?Now, her constraints are just x≥5, y≥2, y≤-x+20, and y≥–³/₄x+18.Then, we end up with this region.In this case, the objective function is just minimizing the number of hours Amy works at tutoring, namely Therefore, P=y, and we can see from looking at the region that the point (8, 12) has the lowest y-value. Therefore, if Amy wants to meet her financial goals but work as few hours as possible at tutoring, she has to work 12 hours at tutoring and 8 hours at the library.