Section 3-4:  Linear Programming
 
 
Demo: Linear Programming
Try the quiz at the bottom of the page!
go to quiz
 
 Linear programming is a method used to identify optimal maximum or minimum values.  It is used in business for practical planning, decision-making problems, and many other problems that can be done using a computer.  Each different resource can be written as a linear inequality called a constraint.  These constraints can be resources like the number of workers, amount of time on a given shift, number of machines, availability of these machines, etc., etc.  By using what we call the corner point theorem, we can find an optimal solution(s) for our problem.  When we graph these constraints, we will get a feasible region that contains our solutions.  The corner point theorem says that if a maximum or minimum value exists, it will occur at a corner point of this feasible region.

 
Sample problem
1)  Find and graph the feasible region for the following constraints:
x + y < 5
2x + y > 4
x > 0, y > 0
 
        First step is to write each of these inequalities isolating for y
y < -x + 5
y > -2x + 4
x > 0, y > 0
 
        Now graph all 4 of the constraints.  The first inequality has a slope of -1 and y-intercept of 5.  The second has a slope of -2 and y-intercept of 4.  The third is a vertical line (y-axis) and the fourth is a horizontal line (x-axis).
 
The area that we want is below the blue line, above the green line, to the right of the purple line and above the red line.  The feasible region looks like:
The feasible region is outlined in black!!
 
    Now, let's find the maximum value if the function we want to maximize is:
P = 3x + 5y
 
        To find the maximum value, we need to use the corner point theorem.  The graph above is easy to find the corner points.  They are: (0, 4), (0, 5),
(2, 0) and (5, 0).  Plug these four values in the function and take the largest value.
 
Point function Value
(0, 4) 0 + 5(4) 20
(0, 5) 0 + 5(5) 25
(2, 0) 3(2) + 0 6
(5, 0) 3(5) + 0 15
The maximum value from this chart would be at (0, 5), with a maximum of 25!

 
2)  Minimize the function C = x + 4y under the following constraints:
x + y < 10
5x + 2y > 20
-x + 2y > 0
x > 0, y > 0
        First, write all constraints isolated for y.
y < -x + 10
y > -2.5 x + 10
y > .5x
x > 0, y > 0
        The first line has slope -1 and y-intercept 10.  The second has slope -2.5 and y-intercept 10.  The third has slope .5 and y-intercept 0.  The next two are vertical and horizontal lines.
We want the area below the blue line, to the right of the green line and above the purple line.  The area forms a triangle like the next picture.
Now to find the corner points, you need to find the intersection of two lines solving simultaneously.
       x + y = 10
 -2x - 2y = -20
  5x + 2y = 20
       3x = 0
         x = 0
Intersects at (0, 10)
 x + y = 10
-x + 2y = 0
        3y = 10
           y = 10/3
x = 30/3 - 10/3 = 20/3
Intersects at (20/3, 10/3)
     -x + 2y = 0
   x   - 2y = 0
  5x + 2y = 20
       6x = 20
x = 20/6 = 10/3
10/3 -2y = 0
-2y = -10/3
y = 10/6 = 5/3
Intersects at (10/3, 5/3)
        Now plug each of these into the original function C = x + 4y
 
 
Point  Function Value
(0, 10) 0 + 4(10) 40
(20/3, 10/3) 20/3 + 4(10/3) 20
(10/3, 5/3) 10/3 + 4(5/3) 10
 
The minimum value of 10 happens at (10/3, 5/3)

 
3)  A studio sells photographs and prints.  It cost $20 to purchase each photograph and it takes 2 hours to frame it.  It costs $25 to purchase each print  and it takes 5 hours to frame it.   The store has at most $400 to spend and at most 60 hours to frame.  It makes $30 profit on each photograph and $50 profit on each print.  Find the number of each that the studio should purchase to maximize profits.
 
Photos Prints Total
Cost 20x 25y < 400
Time 2x 5y < 60
Profit 30x 50y
 
20x + 25y < 400
2x + 5y < 60
x > 0, y > 0
P = 30x + 50y
 

 
 
Current quizaroo #  3
 
 
 
 
1)  Solve the inequality | 2x - 3|  < 5
 
a)  x < -1 or x > 4
b)  x > 4
c)  -1 < x < 4
d)  x < 4
e)  x > 0
 
2) Solve the inequality  | 4x - 5| > 8

          a)  x > 13/4 or x < -3/4

b)  x > 13/4
c)  -3/4 < x < 13/4
d)  x > 0
e)  x < 0
 
 
3)  Solve the inequality (x - 5)(x + 3) > 0
a)  -3 < x < 5
b)  x < -3 or x > 5
c)  x < -3
d)  x > 5
e)  empty set
 
4)  Solve the inequality (x - 3)2 /(x - 4) < 0
a)  3 < x < 4
b)  x > 4
c)  x < 3
d)  x < 4
e)  x < 4, but not including 3
 
 
  5)  
     The inequalities of the above graph are y < x + 1 and y > -x + 3.  Identify the region that represents the intersection.
a)  section 1
b)  section 2
c)  section 3
d)  section 4
e)  empty set
 
 
 
 
 click here for answers!!