Algebra 1 Linear Programming
Math-Prof HOME Algebra 1 Table of Contents Ask A Question PREV  

Get With the Program
Linear Programming

 
 Sometimes you are handed a bunch of inequalities
 to graph all at once.
 
 A group of inequalities like this
 are usually called constraints.
 
 Maybe you have something like ...
 
X + Y 5
 X 1
 Y 0
 X 4
 
 Here's what you do ...
 
 1) Choose any one of the inequalities and graph it.
 Shade the correct side of the line VERY LIGHTLY
 Check the side to shade using the point (0,0) if possible.
 

 
 2) Choose a different inequality and graph it 
 on the same set of axis.
 Shade the correct side VERY LIGHTLY.
 Check using the point (0,0) if possible ...
 

 
 3) Erase the shading in any area shaded 
 by only one of the two inequalities.
 What is left is the area shaded by both inequalities.

 Also find the point where the two lines cross.

 

 
 4) Choose another inequality and graph it 
 on the same set of axis. Shade the correct side.
 

 
 5) Leave shaded only that area shaded 
 by all of the inequalities.
 Find any new points where 2 lines cross.
 

 
 6) Repeat the process for all other inequalities in the group.
 Here, there is only one more left to do ...
 

 
 When you do one of these, if everything works out right,
 you get some shaded shape that has borders on all sides,
 and labels on all of the corners.
 
 Well that's just wonderful!
 
 BUT WHAT IS IT GOOD FOR???
 
 OK, You might see a word problem 
 that goes something like this ...
 
 Example:
 
 Maximize the value of 3X + 2Y subject to these constraints ...
 
X + Y 5
 X 1
 Y 0
 X 4
 
 What we need to do is find the maximum value
 that we can get from 3X + 2Y.
 
 The problem is that the values we choose for X and Y
 must make all of the constraints true.
 That means they are somewhere 
 in the shaded area of the graph.
 
 That's what we were doing so far on this page.
 Finding all of the values of X and Y
 that make all 4 constraints true.
 
 The problem is that even a small area 
 contains a heck of a lot of points.
 
 If we didn't have any more help
 the problem could still take forever.
 
 We do get more help. 
 Here it is ...
 
 THE ANSWER TO ONE OF THESE TYPE OF PROBLEMS 
 IS ALWAYS ONE OF THE CORNER POINTS!
 
 They talk about why in later math courses,
 for now, just be glad it's true and use it!
 
 We've already figured out what the corner points are.
 Now we just plug them into 3X + 2Y and see which one
 gives us the biggest answer ...
 
3X + 2Y
 
(1, 0) 3(1) + 2(0) = 3
(1, 4) 3(1) + 2(4) = 11
(4, 0) 3(4) + 2(0) = 12
(4, 1) 3(4) + 2(1) = 14
 
 So the greatest value (14) happens when X = 4 and Y = 1.
 
 SOME VARIATIONS
 
 1) Instead of finding the greatest value,
 we might want to find the least value.
 
 The answer to this one is still one of the corner points
 of the constraints.
 Just plug them all in and see which one 
 gives you the smallest answer.
 
 For example, the point X = 1, Y = 0 
 gives the least value for 3X + 2Y
 when subject to our constraints.
 
 2) The inequality used by some constraints 
 might be > or <.
 
 When this happens, do all of the same steps
 that we did in the example.
 Use dotted lines instead of solid lines
 for any inequality using > or <
 Find all of the corner points and check them.
 If the answer is a corner point formed 
 using one or two dotted lines,
 THE PROBLEM HAS NO ANSWER.
 
 3) If the constraints don't form an enclosed shape,
 but an open one like this ...
 

 
 A) Find the value of the corner points we do have.
 
 B) Pick some point on each of the open lines.
 

 
 If a1 or b1 is a better answer than any of the corner points
 THE PROBLEM HAS NO ANSWER.
 If neither a1 or b1 is a better answer,
 go to the next step.
 
 C) Pick two more points further down the open lines ...
 

 
 If a1 is a better answer than a2 
 and b1 is a better answer than b2
 the answer is the best corner point.
 
 If a2 is a better answer than a1 
 OR b2 is a better answer than b1
 THE PROBLEM HAS NO ANSWER.
 

   copyright 2005 Bruce Kirkpatrick

Math-Prof HOME Algebra 1 Table of Contents Ask A Question PREV