Section 3-4: Linear
Programming
Demo: Linear Programming (Exploremath - requires Shockwave)
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.
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!!! 
