Linear Programming
Lesson summary:
In this activity, students will use inequalities to determine the feasible region and conclude the optimal solution given certain constraints of a linear programming problem.
Key Words:
Inequality, Feasible Region, Optimal Solution, Constraint
Background Knowledge:
This activity will have the students exploring inequalities to determine the optimal solution to maximize a profit for a company. Students should have a general understanding of how to work with inequalities. They should also have a basic knowledge of how to use the TI-Nspire CAS handheld components such as Calculator, Function Tables, and Graphs & Geometry.
Materials:
TI-Nspire CAS handheld
Worksheet
Computer
Suggested Procedure:
Students will be put into groups of two or three. The students will then open the file on their computer that will guide them through the activities. There are questions that will provide a place to record their observations. Remind the students that they are looking to maximize profit. Discuss and review how to use different applications on the TI-Nspire CAS handheld, such as Calculator, Function Tables, and Graphs & Geometry. Instruct the groups to open the activity document, and have the teams complete the activity.
Standards: Patterns, Functions and Algebra Standard
7. Use symbolic algebra (equations and inequalities), graphs and tables to represent
situations and solve problems
9. Solve linear equations and inequalities graphically, symbolically and using technology
Benchmark/ Grade Level Indicator:
F. Solve and graph linear equations and inequalities.
Assessment: Check students progress in class on the TI-Nspire CAS handheld. Have the students submit their completed activities.
***Note: The TI-Nspire CAS calculator at this time is a new piece of technology for many students. In the future students will be more knowledgeable with the TI-Nspire. Throughout the lesson, comment boxes explaining how to complete procedures are included. In the future, once students are comfortable with the TI-Nspire, the comment boxes may be removed.
Activity 1: Inequalities. In this activity, you will be working with inequalities.
Goal: The students will discover the true meaning of inequalities
Students’ Names: ______
1. Start by creating a new document. Choose Graphs & Geometry.
2. Graph the inequality: y < 3x
In f1(x), delete the = sign. Then, type in the portion “< 3x”. Then hit enter.
3. What do you notice about the graph?
The line y = 3x is a dotted line. Also, the area to the right of the line is shaded.
It should look like the following:
4. What does the shaded region represent?
The shaded region represents the values that make the inequality true.
5. Let’s check to see if you are correct. Create a point that is not in the shaded region. Does this point satisfy the equation?
There can be many different answers. One example would be the point (0, 2). This evaluates to 2 < 0, which is false.
6. Now, pick a point that is located on the line and a point that is located in the shaded region. What do you observe?
Pick the point (1, 3). This evaluates to 3 < 3. This is false. Thus, we can conclude that points on the line do not fit in the solution set. Pick the point (2, 0). The inequality evaluates to 0 < 6. This satisfies the inequality.
7. We can conclude that the shaded region is known as the feasible region. In your own words, define feasible region.
The feasible region for an inequality is the region of points that satisfies the inequality.
Next, graph the following equation in a new page. y ≤ -2x + 10
1. Start by creating a new page.
2. Graph the inequality y ≤ -2x + 10
In f1(x), delete the “=” sign. To get the “≤” sign, hit ctrl, < . Fill in the rest of the equation and hit enter.
3. What do you notice about this graph?
The line of y = 2x + 10 is a solid line. Everything to the left of the line is shaded.
It should look like the following:
4. What is the feasible region?
The feasible region is all of the points that are contained on the line and to the left of it.
5. Let’s check to see if you are correct. Create a point that is not in the shaded region. Does this point satisfy the equation?
Pick the point (10, 0). This evaluates to 0 ≤ -10. This is false. This shows that everything not shaded is not in the feasible region of the inequality.
6. Now, pick a point that is located on the line and a point that is located in the shaded region. What do you observe?
Pick the point (0, 10). This evaluates to 10 ≤ 10. This is true. Therefore, the points on the line satisfy the inequality. Pick point (0, 0). This evaluates to 0 ≤ 10. This is true. Therefore all of the points in the shaded area satisfy the inequality.
7. What do you notice to be different between the two inequalities? Why is this so?
The difference between the two inequalities is the role the line plays. In the first, the points on the line do not satisfy the inequality. The reason for this is it is only a less than inequality, not less than or equal to. The inequality in the second example is less than or equal to, so the points on the line are in the feasible region.
Extension:
1. Create a new Graphs & Geometry page.
2. Graph the inequalities: y < 3x and y ≤ -2x + 10
3. What do you notice about this graph? What is the feasible region of this set of inequalities?
The graph has three shaded regions, one of which is darker than the others. The darkest region depicts the feasible region. The feasible region is the solution set that lies to the left of y = -2x + 10 (including the line) and the right of y = 3x (not including the line).
It should look like the following:
4. Consider the points: (-7, 2), (2, -5), (2, 6), and (12, 5). Based on the graph alone, determine if the points satisfy the set of inequalities. Explain your reasoning.
The only point that satisfies the set of inequalities is (2, -5). The other points only satisfy one of the two inequalities.
5. Check to see if your predictions were correct. In the following space, show all work.
Point y < 3x y ≤ -2x + 10
(-7, 2): 2 < -21 False 2 ≤ 24 True
(2, -5): -5 < 6 True -5 ≤ 6 True
(2, 6): 6 < 6 False 6 ≤ 6 True
(12, 5): 5 < 36 True 5 ≤ -12 False
6. If your prediction(s) were incorrect, what is the reason(s) for them being incorrect?
The answers here will be based on individual students.
7. Describe what you have learned about inequalities in your own words.
The feasible region of a set of inequalities is the set of points that satisfies all of the inequalities. If the inequality is strictly less than or greater than, then it is represented with a dotted line.
Activity 2: Determine the optimal solution.
Goal: The students will determine the maximum and minimum (if they exist) values for a system of inequalities.
1. Create a new Graphs & Geometry page.
2. Graph the following set of inequalities:
x ≥ 0
y ≥ 0
y ≤ -2x + 10
This is how your window should look: (Note: We cannot graph x ≥ 0, so we know the feasible region will be to the right of the y-axis)
Using these constraints, we want to maximize the function k = 2x + 3y.
Definition: A constraint for a linear programming problem is an inequality that takes part in defining the feasible region.
3. Determine the coordinates of the feasible region.
The coordinates are: (0, 0) (0, 10) and (5, 0).
To determine the coordinates, you must create points. Press menu, 6: Points & Lines, 3: Intersection Point(s). Then, click the x-axis and y-axis. After you create this point, choose the y-axis and the inequality y ≤ -2x + 10. Finally, choose the inequality and the x-axis. Next, you may need to get the labels for these points. Press menu, 1: Actions, 6: Coordinates and Equations. Then, click on the points.
Your graph should look like the following:
4. Look at the feasible region. Suppose we pick any two points on the perimeter of the region, if we connect them with a line, will the line be totally contained in the feasible region? If not, give an example of two such points.
Yes, no matter what points are chosen, the line will be completely contained within the region.
Definition: A region is said to be convex if any two points of the region can be joined by a line segment totally contained in the region.
5. Is the feasible region convex?
Yes, the feasible region is convex.
6. Next, we want to find the optimal solution for the equation k = 2x + 3y.
Definition: An optimal solution is a solution to an optimization problem that maximizes (or minimizes) the corresponding function.
Evaluate the equation using the points we found in step 3. Show all of your work in the space provided below.
Point k = 2x + 3y
(0, 0) k = 0
(0, 10) k = 30
(5, 0) k = 10
7. Next, we must check some of the interior points of the feasible region. Choose five interior points and evaluate the equation in the space provided below.
Point k = 2x + 3y
(2, 0) k = 4
(0, 2) k = 6
(1, 2) k = 8
(2, 2) k = 10
(7, 1) k = 17
What do you notice about the values of these points in relation to the values of the coordinates that make up the feasible region?
There are no values that are as small, or as large as the extreme values of the coordinates of the feasible region.
8. Generalize your findings from step 7.
The critical points, i.e. maximum and minimum values for the set of inequalities, occurs on one of the vertices of the region.
9. It turns out that your generalization from step 8 is an actual theorem. It states:
The point (x0, y0) of a convex region that produces the maximum value of a quantity k = ax + by, where a and b are positive, will be at a vertex of the region.
10. Based on this theorem, what point maximizes the equation k = 2x + 3y under the specified constraints? What is the value of the maximum?
The point that maximizes the equation is (0, 10). The maximum value of k is 30.
Extension:
1. Suppose we have the constraints:
x ≥ 0
y ≥ 0
y < -2x + 10
2. Graph these inequalities in a new page. It should look like the following:
Using these constraints, we want to maximize the function k = 2x + 3y.
3. Is this region convex? Explain your reasoning.
This region is not convex. Pick the points (0, 10) and (5, 0). If you construct the line containing these points, the line is not contained in the feasible region for the set of inequalities.
4. Are you able to determine the maximum of k = 2x + 3y under these constraints? If yes, give the coordinates of the point and the maximum value. If no, explain the reason(s) why.
No. Since the region is not convex, the theorem does not apply. We know from the last example that (0, 10) is the maximum if the line is included. Since the line is not included, there is no definite point that we can take that is close to (0, 10) without finding a point that has a bigger value. In other words, we can always find a point to the left of 10 that is closer than the previous point. Therefore, there is no maximum for this equation.
Activity 3: A Linear Programming Example
Goal: The students will be able to use their recent findings to determine the optimal solution for the following linear programming example.
Problem: A gold processor has two sources of gold ore, source A and source B. In order to keep his plant running, at least three tons of ore must be processed each day. Ore from source A costs $20 per ton to process, and ore from source B costs $10 per ton to process. Costs must be kept to less than $80 per day. Moreover, Federal Regulations require that the amount of ore from source B cannot exceed twice the amount of ore from source A. If ore from source A yields 2 oz. of gold per ton, and ore from source B yields 3 oz. of gold per ton, how many tons of ore from both sources must be processed each day to maximize the amount of gold extracted subject to the above constraints?
1. Start by creating a new Graphs & Geometry page.
2. Next, we must define our variables in the problem above.