Programming: An Example &
First I'll solve the fourth and fifth constraints for easier graphing:
The feasibility region looks like this:
From the graph, I can see which lines cross to form the corners, so I know which lines to pair up in order to verify the coordinates. I'll start at the "top" of the shaded area and work my way clockwise around the edges:
Now I'll plug each corner point into the optimization equation, z = –0.4x + 3.2y:
(1, 6): z =
–0.4(1) + 3.2(6) = –0.4 + 19.2 = 18.8
Then the maximum is 18.8 at (1, 6) and the minimum is –2 at (5, 0).
Given the inequalities, linear-programming exercise are pretty straightforward, if sometimes a bit long. The hard part is usually the word problems, where you have to figure out what the inequalities are. So I'll show how to set up some typical linear-programming word problems.
If gasoline is selling for $1.90 per gallon and fuel oil sells for $1.50/gal, how much of each should be produced in order to maximize revenue?
The question asks for the number of gallons which should be produced, so I should let my variables stand for "gallons produced".
gallons of gasoline produced
Since this is a "real world" problem, I know that I can't have negative production levels, so the variables can't be negative. This gives me my first two constraints: namely, x > 0 and y > 0.
Since I have to have at least two gallons
of gas for every gallon of oil, then
For graphing, of course, I'll use the more manageable form "y < ( 1/2 )x".
The winter demand says that y
> 3,000,000; note that
this constraint eliminates the need for the "y
> 0" constraint. The
gas demand says that x
I need to maximize revenue R, so the optimization equation is R = 1.9x + 1.5y. Then the model for this word problem is as follows:
R = 1.9x +
1.5y, subject to:
Using a scale that counts by millions (so "y = 3" on the graph means "y is three million"), the above system graphs as follows:
Taking a closer look, I can see the feasibility region a little better:
When you test the corner points at (6.4m, 3.2m), (6.4m, 3m), and (6m, 3m), you should get a maximal solution of R = $16.96m at (x, y) = (6.4m, 3.2m).