Linear Programming

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.

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
3x + 2y = 36
Use x and y intercepts.

To find x intercept, set y = 0
3x + 2(0) = 36
3x = 36
x = 12, (12, 0) is x intercept
To find y intercept, set x = 0
3(0) + 2y = 36
2y = 36
y = 18, (0, 18) is y intercept

Next, we want to graph the line
x + 4y = 32
Use x and y intercepts.

To find x intercept, set y = 0
x + 4(0) = 32
x = 32
(32, 0) is x intercept
To find y intercept, set x = 0
0 + 4y = 32
4y = 32
y = 8, (0, 8) is y intercept

Solve each inequality for y:

inequal.gif (2554 bytes)

Since both inequalities have less than symbols ,< , the feasible solution is below each line.

x ł 0 , y ł 0 means the x and y values are positive. To the right of the y axis and above the x axis . (quadrant I)

Note: If the inequality has a greater than symbol, ł , the feasible solution is above the line.

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.

Corner Point	Value
(0,0)	7(0) + 4(0) = 0 + 0 = 0
(0,8)	7(0) + 4(8) = 0 +32 = 32
(12,0)	7(12) + 4(0) = 84 + 0 = 84
(6,8)	7(6) + 4(8) = 42 + 32 = 74
Maximum is 84

The maximum value 84 occurs at the point (12,0)

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?

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.

The minimum cost of $67,000 is achieved at (4,3).
Open refinery I for 4 days and refinery II for 3 days.

	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	?

		This is the first inequality in red with x-int (10,0) and y-int (0,5) The solution lies above the line
		This is the 2nd inequality in blue with x-int (5,0) and y-int (0,10) The solution lies above the line
		This is the 3rd inequality in purple with x-int (6,0) and y-int (0,9) The solution lies above the line
		The feasible solution is blue area.

-.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

high grade	100x + 200y ł 1000
medium grade	200x + 100y ł 1000
low grade	300x + 200y ł 1800