Lesson All about Linear Programming

Learning Objectives

After this lesson, students should be able to:

• Describe linear programming as finding the “best” solution to a problem.
• Define and apply the following engineering design terms: constraint, feasible, optimize.
• Use linear programming to solve example real-world engineer design problems.

Educational Standards

Each TeachEngineering lesson or activity is correlated to one or more K-12 science, technology, engineering or math (STEM) educational standards.

All 100,000+ K-12 STEM standards covered in TeachEngineering are collected, maintained and packaged by the Achievement Standards Network (ASN), a project of D2L (www.achievementstandards.org).

In the ASN, standards are hierarchically structured: first by source; e.g., by state; within source by type; e.g., science or mathematics; within type by subtype, then by grade, etc.

NGSS: Next Generation Science Standards - Science

Common Core State Standards - Math

International Technology and Engineering Educators Association - Technology

State Standards

Worksheets and Attachments

Pre-Req Knowledge

A familiarity with graphing linear inequalities.

Introduction/Motivation

(Be ready to write on the classroom board. Have ready printouts of a problem statement to hand to each student. To do this, cut apart enough copies of the Lesson Problem Statement; each sheet has the problem statement written five times. Alternatively, write the problem statement on the classroom board. In addition, have ready copies of the Linear Programming Practice Problems Worksheet, one per student. Also make sure students have pencils and calculators handy.)

(IF STUDENTS HAVE previously completed the Optimizing Pencils in a Tray activity, read the following paragraph.) A few class periods ago, we experimented with some pencils of varying lengths to see if we could determine how many pencils of each size were needed to maximize a few quantities such as number of pencils in the tray, or total length of pencils in the tray. Engineers frequently want to maximize quantities like these, or minimize quantities, such as cost, in order to determine the best solutions to problems. It turns out that if the situation is well-defined, a more efficient, analytical approach can be taken to find the answer. We are going to examine a similar problem to the one we solved last time in this new way.
(IF STUDENTS HAVE NOT previously completed the Optimizing Pencils in a Tray activity, read the following paragraph.) When creating a solution to an engineering design problem, engineers want to determine the best possible solution. Sometimes, the best solution may be the cheapest one or perhaps the strongest one. It turns out that if the situation is well-defined, an efficient, analytical approach can be taken to maximize a quantity like strength, or minimize a quantity like cost. We are going to examine a problem to learn about this method.

(Show students a written copy of the following problem, either by handout or writing it on the classroom board.) Here’s the problem statement. Your objective is to place some pencils in a tray such that they are stable. This means that you must align the long axes of the pencils with the groove in the tray. You know that a golf pencil (x) is 3.5-inches long and a regular pencil (y) is 7.5-inches long. The tray has room for no more than 52.5 linear inches of pencils (the groove is 52.5 inches long). How many of each pencil are needed in order to maximize the total number of pencils in the tray? (If students rapidly arrive at the intuitive solution—to just use as many of the short golf pencils as fit [15 of them]—tell them the following.) Although that sounds reasonable, instead of guessing the answer, we are going to develop a process to guarantee the correct solution AND give us a mathematical method that can be used for more complicated problems that are not as straightforward to guess.

In this problem, many different ways are possible to place pencils in the tray. For instance, we could place two long pencils, five short pencils, one of each, etc. We could try each one of these options and come up with a solution that way (trial and error), but in order to do that we would need a list of all the possible options. If we could define for ourselves which combinations of pencils are possibilities, we would have a much clearer perspective on the problem. In order to do that, we want to look at the limiting cases. What numbers of pencils either don’t make sense or are not allowed in this problem?

(If students struggle to respond at this point, call attention to a number line. Either point to one in your classroom or draw one on the board. Remind them of the following.) X represents the number of golf pencils and Y represents the number of regular pencils, but without further information, X and Y are just variables that represent numbers. This means they can take any value on the number line. Do any values on the number line not make sense for either the number of golf pencils in the tray (X) or the number of regular pencils in the tray (Y)?

(It is important that students come up with the following two restrictions.) Yes, that’s right: X cannot be negative, and Y cannot be negative. This is because having a negative number of pencils in a tray does not make sense. (Students may also come up with the restriction that X and Y must be integers because the problem does not permit us to cut the pencils into pieces or sharpen them to be shorter. This restriction is not critical to solving the problem since it has been designed to produce integer solutions already, but is a valid discussion point, so acknowledge it as such if it is suggested.)

(Write the word “constraints” on the board and underline it.) I’m going to write down your ideas so I don’t lose track. For now, I’m just going to call them “constraints.” By “constraint” we just mean a rule or restriction—something that must be obeyed in solving a problem—and I think that is a good description for all of your ideas so far. (If desired, make note of the term “constraint” on a class vocabulary list elsewhere on the board.)

(Write “X cannot be negative” below the underline, and “Y cannot be negative” under that. Also write “X must be an integer” and “Y must be an integer” IF students came up with those ideas.) So far, we have that X cannot be negative and Y cannot be negative. What are some ideas you have for different ways to write these statements? For example, how could you rephrase these statements using different words, or represent them using numbers and symbols?

(Ultimately, we want to get to the inequalities X ≥ 0 and Y ≥ 0. If students come up with X or Y must be positive as an alternate rephrasing, ask them the following.) Do all the positive numbers and all the negative numbers taken together represent everything on the number line? (See if students provide the following response.) Zero is neither positive or negative, and so saying X or Y must be positive leaves out zero, which perfectly meets the original constraint that X or Y cannot be negative, since zero is not negative. A way to say “either positive or zero” more cleanly is to say “non-negative.” (Write “X must be non-negative” and “Y must be non-negative” next to the original two constraints IF students choose to rephrase before coming up with mathematical symbol representations.) Yet another way to say “either positive or zero” is “at least zero.” (Write this on the board next to the original constraints as well.) What do you remember about how to write “at least zero” using a symbol and the number zero? (If students struggle, remind them that it has something to do with the word “inequality.” Expect them to eventually get to X ≥ 0 and Y ≥ 0. Once they do, write this next to the corresponding verbal representations.)

Great! This is pretty cool, since now we have managed to come up with some concise math notation out of a wordy word problem. Seeing X ≥ 0 and Y ≥ 0 reminds me of something. What do you remember about graphing inequalities? (Expect students to recall that you first graph the line represented by the inequality, which is dashed if there is no “or equals” and solid otherwise, then shade the appropriate side of it.) I’m going to graph these inequalities to see if it helps me get a better handle on what combinations of pencils are allowed. (Graph the inequalities. Refer to Figure 1 to see how the lines for these are shown as lines AC and AB, respectively, although the shading, which would be to the right and above these lines, respectively, is not shown.) Hmmm… So if I graph these two inequalities, I am left with all of quadrant 1. I feel like this cannot be right though, because quadrant 1 contains some really large ordered pairs that I don’t think make sense in this problem. For instance, (1000, 1000) exists in this quadrant, but I don’t think I could possibly fit 1,000 golf pencils and 1,000 regular pencils in a 52.5-inch slot. What ideas do you have about how we may be able to get through this dilemma?

(Expect students to come up with the limitation that the total length of pencils must be less than 52.5 inches. Write this under “constraints” as the third item in the list.) We know that X is the total number of golf pencils, which are each 3.5-inches long, and that Y is the total number of regular pencils, which are each 7.5-inches long. We should be able to write this as 3.5x + 7.5y ≤ 52.5. (Write this next to the third verbal constraint.) I can graph this one the same as the others, but I just need to isolate Y first. When I do, I get y ≤ -7/15*x + 7. (Graph this inequality. The line for this inequality can be seen as line BC in Figure 1, although the shading, which would be to the lower left of this line, is not shown.) Oh, now the shaded region is a triangle! This makes a lot more sense since now that I cannot include those really big values.

The shaded region is the area of the coordinate plane containing coordinate pairs that meet all three constraints. Let’s not just call it the “shaded region” anymore since that is pretty vague. Let’s start calling it the “feasibility region.” What does feasible mean? (See what students think.) “Feasible” has a similar meaning to “plausible” or “possible.” This is a fitting name since the values in the feasibility region are all the possible values that X and Y can take. (Write “feasibility region” on the class vocabulary list.)

(Note: The graph of this feasibility region along with the intersection points is shown in Figure 1. The optimization equation is z = x + y. In this case, point B is the winner, since the values of z for points A, B and C are 0, 15 and 7, respectively. Note that the total length of the tray has been changed from the Optimizing Pencils in a Tray associated activity. This is because 52.5, as also explained in the Lesson Background section, is the minimum length that allows for the intersection points to be integers, since in the case in which the total length is 18.5 inches, the maximum number of pencils would be 5.29 golf pencils. Only integer quantities were allowed however, which is why 52.5 was chosen as the length instead.)

Now we finally have a well-defined set of possible combinations of pencils. This means we can start to think about what the problem is really asking, which is the question at the end of the word problem. “How many of each pencil should you use in order to maximize the total number of pencils on the tray?” So we want to maximize something, and the thing we want to maximize is the total number of pencils on the tray. Let’s call the total number of pencils on the tray “Z.” What ideas do you have for how we can write a mathematical definition for “Z” using the variables we already know? (Expect students to come up with z = x + y, or the sum of the number of golf pencils and the number of regular pencils.) Okay, yes, I think that z = x +y is an equation that describes our situation pretty well. Let’s call it the “maximization equation” since it is the equation describing the quantity we want to maximize. Sometimes though, we don’t want the most and would rather have the least. For instance, what if Z represented cost instead of length? Would you rather have the highest possible cost or lowest possible cost? Since sometimes we want to minimize quantities like cost and sometimes we want to maximize quantities such as length, let’s call Z the “optimization equation.” Optimize means “to create the best solution for,” which can include both maximization and minimization cases. (Add “optimization equation” to the class vocabulary list. Also write and underline “optimization equation” and write z = x + y below it.)

Now that we have everything set up, all we have to do is “plug and chug.” We have the equation we want to maximize and a set of possible X and Y coordinate pairs to use. We just need to plug each possible coordinate pair into the optimization equation and figure out which makes Z the biggest. With such a big feasibility region, that may be the most time-consuming part of this problem!

Fortunately, I know a way to take a massive shortcut. It has been mathematically proven that both the maximum value and the minimum value of an optimization equation each take place on one of the endpoints of the feasibility region. The endpoints are the points where the various inequality lines intersect. (Add “endpoints” or “corner points” to the class vocabulary list.) In this case, we have three such points. They are (0, 0), (0, 7) and (15, 0). (This corresponds to points A, C and B, respectively, in Figure 1.) This means we only need to plug each of these three values into Z and see which value is the largest. We should get z (0, 0) = 0 + 0 = 0, z (0, 7) = 0 +7 = 7 and z (15, 0) = 15 + 0 = 15. In this case, 15 is the largest value, which means that (15, 0) is the coordinate pair representing the solution. This means that in order to have the greatest number of pencils in the tray, we should place 15 golf pencils and 0 regular pencils. This makes sense since we could fit into the tray the most pencils by using only the shortest pencils. Note that if for some reason we wanted to minimize the number of pencils instead of maximize it, the entire problem would have been the same, with the only difference that we would choose (0, 0) as the solution coordinate pair since z (0, 0) = 0 was the minimum value produced out of the three.

The type of problem we just solved is called “linear programming.” Only two common ways exist to make this type of problem more difficult. One is by increasing the number of constraints to something larger than three. This means you may have four or five, etc., inequality lines on your graph. The other way is by making the optimization equation slightly more complicated than z = x + y. For instance, z = 2x-3y. Besides these two changes, the problems generally look the same.

Now, I’m going to give you a chance to work through some linear programming practice problems that represent real engineering design problems. (Hand out the worksheets.) Each person needs to fill out his/her own worksheet, however you may discuss the problems amongst the people at your table if you want to bounce ideas off of someone. If you get stuck and your table group also does not have any ideas for how to move forward, then raise your hand and I will come by to get you moving again.

(Write the following example problems on the board, which are the same problems on the worksheet. Refer to the Linear Programming Practice Problems Answer Key for the answers with the work shown.)

Problem 1: A storage solutions company manufactures large and small file folder cabinets. Large cabinets require 50 pounds of metal to fabricate, and small cabinets require 30 pounds, but the company has only 450 pounds of metal on hand. If the company can sell each large cabinet for $70 and each small cabinet for $58, how many of each cabinet should it manufacture in order to maximize income? (Answer: 15 small cabinets.)

Problem 2: You are a civil engineer designing a bridge. The walkway needs to be made of wooden planks. You are able to use either Sitka spruce planks (which weigh 3 pounds each), basswood planks (which weigh 4 pounds each), or a combination of both. The total weight of the planks must be between 600 and 900 pounds in order to meet safety code. If Sitka spruce planks cost $3.25 each and basswood planks cost $3.75 each, how many of each plank should you use to minimize cost while still meeting building code? (Answer: 150 basswood planks.)

Lesson Background and Concepts for Teachers

Constraints are linear inequalities graphed on the x-y plane. The intersection area of all inequalities is called the “feasibility region.” The “optimization equation” is a function of x and y that you wish to maximize or minimize. It has been proven that the maximum and minimum values of the optimization equation are always at the intersection points of the inequalities (the “corners” of the feasibility region). Because of this, if the problem involves discrete quantities (as most do), it is important to design the constraints such that their intersection x and y coordinates are both multiples of the smallest discrete unit. This is typically 1, in which case the coordinates of intersection must be integers, although a problem could be designed such that the smallest discrete unit is something other than 1. For example, the problem might involve purchasing objects that are packaged and sold in half-pound quantities (in which case the intersection coordinates of the constraints are multiples of ½) or perhaps in pairs like socks (in which case the intersection coordinates of the constraints are multiples of 2).

Also note that if the optimization equation is linearly dependent on any single constraint, then all points on the portion of the line representing that constraint between the two interior intersection points on that line are valid solutions. This means that both intersection points on this line have the same value and this value is the maximum or minimum.

Also note that if any constraint is linearly dependent on two other constraints, it is simply another line that intersects the feasibility region at only the intersection of the two other constraints, and therefore does not create a new corner point. If any constraint is linearly dependent on more than two other constraints, all points on that line are outside the feasibility region as defined by the other constraints, so it also does not create any new corner points. In both cases above, the constraints are adding no new information, which is why they either only intersect the feasibility region at a pre-existing corner point, or not at all.

Lastly, note that in most linear programming problems, two of the constraints are x >= 0 and y >= 0, since in problems involving objects, negative quantities are not allowed.

Associated Activities

• Optimizing Pencils in a Tray - Student groups work with two sizes of pencils and a tray to maximize various quantities of the system. They work through three linear optimization problems with different constraints. They construct mathematical arguments for why their solutions are the best ones. Consider conducting this activity before the Linear Programming lesson.

Lesson Closure

What are some examples of when engineers want to optimize a quantity? (See what ideas students have.) Aerospace engineers who design spacecraft to fit in the payload fairing (nose cone) of the launch vehicle. Civil and architectural engineers who plan cities within the boundaries of a particular plot of land. Electrical and computer engineers who design circuit boards that fit inside the newest slim smartphone, tablet or laptop. Civil and environmental engineers who plan human-created waterways that are big enough to carry the water needed by a city during peak demand. Mechanical engineers who design engines that are small enough to fit into lawnmowers, cars, golf carts, go-karts and other equipment and appliances. What’s the key thing to remember? If the constraints are linear—that is, x and y are not raised to a power other than 1, or stuck inside another function such as sine—then linear programming can be used to design the optimal solution.

Vocabulary/Definitions

constraint: A limitation or restriction—something that must be obeyed in solving a problem. A restriction on possible values of x and y.

feasibility: Plausible or possible.

feasibility region: The intersection area of all constraints when graphed as inequalities. The values in a feasibility region are all the possible values of X and Y.

linear programming: A method to determine the best outcome in a design situation in which the requirements are represented by linear relationships. Also called linear optimization.

optimization equation: The function of x and y that you wish to maximize or minimize.

optimize: To select the best solution, with regard to some criterion, from a set of alternatives.

Assessment

Example Problems: As a class, students work through the Lesson Problem Statement about maximizing the total number of pencils that fit in a tray, given two lengths of pencils, guided by the teacher (as fully explained via the Introduction/Motivation section). Then, students individually work through two problems presented in the Linear Programming Practice Problems Worksheet. Review students’ answers and work to gauge their comprehension of the concepts.

Copyright

Contributors

Supporting Program

Acknowledgements

This activity was developed by CU Teach Engineering, a pathway to STEM licensure through the Engineering Plus degree program in the College of Engineering and Applied Science at the University of Colorado Boulder.