Linear Programming



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 learn to graph inequalities.

Goal: The students will discover how to graph inequalities, and how to determine the algebraic representation of a half-plane

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 displayed graph, i.e., how is the boundary? How is the region to the right?

________________________________________________________________________________________________________________________________________________

It should look like the following:

[pic]

4. Let’s try to characterize the points on the shaded region called a half-plane. What does the shaded region represent?

________________________________________________________________________________________________________________________________________________

5. Let’s check to see if you are correct. Create a point P that is in the shaded region and display its coordinates. Do the coordinates of P satisfy the given inequality?

________________________________________________________________________________________________________________________________________________

6. Grab and move point P on the shaded region. Do the coordinates of P keep satisfying the inequality at every position?

________________________________________________________________________

7. Now, pick a point Q that is located on the line and display its coordinates. Do the coordinates of Q satisfy the given inequality? What equation do the coordinates seem to satify?

________________________________________________________________________________________________________________________________________________

8. Grab and move point Q on the line. Do the coordinates of Q keep satisfying the equation at every position?

________________________________________________________________________

9. Now, pick a point R that is located on the non-shaded region (also called a half-plane) and display its coordinates. Do the coordinates of R satisfy the given inequality? What inequality do the coordinates seem to satisfy?

________________________________________________________________________________________________________________________________________________

10. Grab and move point R on the non-shaded region. Do the coordinates of R keep satisfying the inequality at every position?

________________________________________________________________________

11. In general we know that the graph of a linear equation in two variables is a line. The line divides the plane in three regions: two half-planes and the line itself. What algebraic expressions have you discovered represent each half-plane?

________________________________________________________________________

________________________________________________________________________

12. The shaded region representing the solution to a linear inequality is known as the feasible region. In your own words, define feasible region.

________________________________________________________________________________________________________________________________________________

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?

________________________________________________________________________________________________________________________________________________

It should look like the following:

[pic]

4. What is the feasible region?

________________________________________________________________________________________________________________________________________________

5. Let’s check to see if you are correct. Create a point P that is not in the shaded region and display its coordinates. Do the coordinates satisfy the given inequality?

________________________________________________________________________________________________________________________________________________

6. Now, pick a point Q that is located on the line and a point R that is located in the shaded region and display their coordinates. Do the coordinates of both points satisfy the given inequality?

________________________________________________________________________________________________________________________________________________

7. Comparing the resulting graphs on the two inequalities studied, how does the inclusion of the equal sign impacts the graph of the inequality?

________________________________________________________________________________________________________________________________________________

Extension:

1. Create a new Graphs & Geometry page.

2. Graph the inequalities: y < 3x and y ≤ -2x + 10

3. What is different about the shading regions of this graph? What is the feasible region of this set of inequalities? How can you confirm your answer?

________________________________________________________________________________________________________________________________________________

It should look like the following:

[pic]

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.

[pic]

________________________________________________________________________________________________________________________________________________

5. Check to see if your predictions were correct using the coordinates of each point and the two inequalities given. In the following space, show all work.

6. If your prediction(s) were incorrect, what is the reason(s) for them being incorrect?

________________________________________________________________________________________________________________________________________________

7. Describe what you have learned about inequalities in your own words.

________________________________________________________________________________________________________________________________________________

Activity 2: Determine the optimal solution.

Goal: Given a set of inequalities (called constrains) and a function (called the function), the students will determine the maximum and minimum (if they exist) values of the function on the feasible region.

Definition: A constraint for a linear programming problem is an inequality that takes part in defining the feasible region.

Definition.

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 (why?), so we know the feasible region will be to the right of the y-axis)

[pic]

What polygon do the feasible region form in this case?

3. 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.

__________________________________________________________________________________________________________________________________________

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.

4. Is the feasible region convex? ____________________________________________

Using these constraints, we want to maximize the function f(x,y) = 2x + 3y.

5. Determine the coordinates of the vertices of the feasible region.

__________________________________________________________________________________________________________________________________________

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:

[pic]

6. Next, we want to find the optimal solution for the equation f(x,y) = 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 5. Show all of your work in the space provided below.

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.

What do you notice about the values of these points in relation to the values of the coordinates that make up the feasible region?

__________________________________________________________________________________________________________________________________________

8. Generalize your findings from step 7.

__________________________________________________________________________________________________________________________________________

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?

__________________________________________________________________________________________________________________________________________

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:

[pic]

Using these constraints, we want to maximize the function f(x,y) = 2x + 3y.

3. Is this region convex? Explain your reasoning.

__________________________________________________________________________________________________________________________________________

4. Are you able to determine the maximum of f(x,y) = 2x + 3y under these constraints? If yes, give the coordinates of the point and the maximum value. If no, explain the reason(s) why.

__________________________________________________________________________________________________________________________________________

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.

Let x = ____________________________________________________________

Let y = ____________________________________________________________

3. Determine the objective of this linear programming problem and give its equation.

________________________________________________________________________________________________________________________________________________

4. Determine the equations of the constraints:

Processing: ______________________________________________________________

Costs: __________________________________________________________________

Federal Regulations: ______________________________________________________

5. We also have the implied constraints of x ≥ 0 and y ≥ 0. What is the reason for this?

________________________________________________________________________________________________________________________________________________

6. Graph the constraints. Your graph should look like the following:

[pic]

7. Give the coordinates of the feasible region.

________________________________________________________________________________________________________________________________________________

8. Look at the feasible region. Does it appear to be convex? Justify your answer.

________________________________________________________________________________________________________________________________________________

9. Based on your answer is 8, is there a theorem that may be helpful in solving this linear programming problem? State the theorem.

________________________________________________________________________________________________________________________________________________

10. Next, evaluate the equation for the amount of gold yielded using the coordinates of the feasible region. Show all of your work in the space provided.

11. Based on your results, determine the optimal solution. (Give the point and the maximum amount of gold yielded) Interpret your results.

________________________________________________________________________________________________________________________________________________

Extension:

Using the same format for this activity, complete the following optimization problem:

A farmer has 10 acres to plant in wheat and rye. He has to plant at least 7 acres. However, he has only $1200 to spend and each acre of wheat costs $200 to plant and each acre of rye costs $100 to plant. Moreover, the farmer has to get the planting done in 12 hours and it takes an hour to plant an acre of wheat and 2 hours to plant an acre of rye. If the profit is $500 per acre of wheat and $300 per acre of rye how many acres of each should be planted to maximize profits?

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download