(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
. 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
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 “
” 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 “
” 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 “
” 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 “
” or “
” 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.)
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.)
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.)