Section 34: Linear
Programming
Demo: Linear Programming
go to quiz
Linear programming is
a method used to identify optimal maximum or minimum values. It is
used in business for practical planning, decisionmaking 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 yintercept of 5. The second has a slope of 2 and yintercept
of 4. The third is a vertical line (yaxis) and the fourth is a horizontal
line (xaxis).
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 yintercept 10. The second has slope
2.5 and yintercept 10. The third has slope .5 and yintercept 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.
The first thing to do
is to organize the information into a chart. Let x = the number of
photographs and y = the number of prints

Photos 
Prints 
Total 
Cost 
20x 
25y 
< 400 
Time 
2x 
5y 
< 60 
Profit 
30x 
50y 

Write the constraints
for the problem from the above chart:
20x + 25y <
400
2x + 5y < 60
x > 0, y >
0
Write the profit function
from the chart above:
P = 30x + 50y
Now graph the constraints
like we did in the first two examples. Notice that the last
two constraints put the graph in the first quadrant.
The corner points are (0, 0),
(0, 12), (20, 0). The last corner point is found by the intersection
of the two lines.
20x + 25y = 400
2x + 5y
= 60
10x  25y = 300
10x = 100
x = 10
The other corner point is (10,
8)
Now set up a chart to find
the maximum value for the profit function.
Point 
function 
value 
(0, 0) 
30(0) + 50(0) 
0 
(0, 12) 
30(0) + 50(12) 
600 
(20, 0) 
30(20) + 50(0) 
600 
(10, 8) 
30(10) + 50(8) 
700 
The maximum value happens at
(10, 8) for a profit of $700. This means to purchase 10 photos and
8 prints.
Bring on the practice test!!
No, I better go back and study
more!!!