Linear Programming  Tutorial 
 Section 6.8  
The book does an excellent job developing and explaining linear programming . Read this section thoroughly and if necessary many times. I strongly recommend using the tables to organize your data.
Linear Programming
A Graphical Approach

Maximize the objective function 7x + 4y subject to the following constraints. 
The question is : Find the value for the objective function that is the largest. In order to find that value, we need to graph the inequalities.
First, we want to graph the
line


Next, we want to graph the line


Solve each inequality for y: 





Now that the feasible set is shaded in, we need to find the corner points. I count 4 corner points.  
The first 3 corner points are obvious. (0, 0), (0, 8), and (12, 0) . Use the equations to the right to find the other point.  
Find the remaining corner point by setting the equations equal to each other and solve for x.  
Multiply both sides by 4  
We get...  
adding 6x and subtracting 32 from both sides  40 = 5x  
The ordered pair is (8,6)  x = 8, then  
(8, 6), (0, 0), (0, 8), and (12, 0) are the four corner points.  
Finally, test each corner point in
the objective function. Maximize the objective function 7x + 4y subject to the following constraints.


The maximum value 84 occurs at the point (12,0) 
An oil company owns 2 refineries. 

An order is received for 1000 barrels of high grade oil, 1000 barrels of medium grade oil, and 1800 barrels of low grade oil. How many days should each refinery be operated to fill the order at the least cost?
Solution:
Let's start by making a table.
Refinery I  Refinery II  Ordered  
high grade  100 barrels  200 barrels  1000 barrels 
medium grade  200 barrels  100 barrels  1000 barrels 
low grade  300 barrels  200 barrels  1800 barrels 
Cost  $10,000  $9,000  ? 
Now, write the inequalities:
high grade 
100x + 200y ³ 1000 
medium grade 
200x + 100y ³ 1000 
low grade 
300x + 200y ³ 1800 
Write the inequalities in standard form by rewrite solving for y.

This is the first inequality in red with
xint (10,0)
and yint (0,5)
The solution lies above the line 

This is the 2nd inequality in blue with
xint (5,0)
and yint (0,10)
The solution lies above the line 

This is the 3rd inequality in purple with
xint (6,0)
and yint (0,9)
The solution lies above the line 

The feasible solution is blue area. 
Next find the corner points. By looking at the graph and knowing x ³ 0 and y ³ 0 means the solution is in the first quadrant we get (10,0) and (0,10) as corner points. We must calculate the remaining corner points by setting the corresponding inequalities equal to each other.
.5x + 5 = 1.5x + 9  x = 4, then y = .5(4) + 5 = 3  (4,3) 
2x + 10 = 1.5x + 9  x = 2, then y = 2(2) + 10 = 6  (2,6) 
Note : The red and blue line intersection is outside the feasible region.  
Finally, let's check the cost function 10,000x + 9,000y we want to minimize.  
(0,10)  10,000(0) + 9,000(10) = 90,000 
(4,3)  10,000(4) + 9,000(3) = 67,000 
(2,6)  10,000(2) + 9,000(6) = 74,000 
(10,0)  10,000(10) + 9,000(0) = 100,000 
The
minimum cost of $67,000 is achieved at (4,3).
Open refinery I for 4 days and refinery II for 3 days.
Tutorials and Applets by
Joe McDonald
Community College of Southern Nevada