Print-friendly page

Linear Programming: An Example &
  How to Set Up Word Problems (page 2 of 5)

Sections: Optimizing linear systems, Setting up word problems

• Given the following constraints, maximize and minimize the value of z = –0.4x + 3.2y.

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":

y = –x + 7 y = x + 5	y = –x + 7 x = 5	x = 5 y = 0
–x + 7 = x + 5 2 = 2x 1 = x y = (1) + 5 = 6	y = –(5) + 7 = 2	[nothing to do]
corner at (1, 6)	corner at (5, 2)	corner at (5, 0)

y = 0 y = –( 1/2 )x + 2	y = –( 1/2 )x + 2 x = 0	x = 0 y = x + 5
–( 1/2 )x + 2 = 0 2 = (1/2)x 4 = x	y = –( 1/2 )(0) + 2 y = 0 + 2 y = 2	y = (0) + 5 = 5
corner at (4, 0)	corner at (0, 2)	corner at (0, 5)

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
(5, 2):  z = –0.4(5) + 3.2(2) = –2.0 + 6.4   =   4.4
(5, 0):  z = –0.4(5) + 3.2(0) = –2.0 + 0.0   = –2.0
(4, 0):  z = –0.4(4) + 3.2(0) = –1.6 + 0.0   = –1.6
(0, 2):  z = –0.4(0) + 3.2(2) = –0.0 + 6.4   =   6.4
(0, 5):  z = –0.4(0) + 3.2(5) = –0.0 + 16.0 = 16.0

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.

• At a certain refinery, the refining process requires the production of at least two gallons of gasoline for each gallon of fuel oil. To meet the anticipated demands of winter, at least three million gallons a day will need to be produced. The demand for gasoline, on the other hand, is not more than 6.4 million gallons a day.

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

x: gallons of gasoline produced
y: gallons of fuel oil 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 x > 2y. For graphing, of course, I'll use the more manageable form "y < ( ¹/₂ )x".

The winter demand says that y > 3,000,000; note that this constraint the eliminates the need for the "y > 0" constraint. The gas demand says that x < 6,400,000.

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:
x > 0
x < 6,400,000   Copyright © Elizabeth Stapel 2006-2008 All Rights Reserved
y > 3,000,000
y < ( ¹/₂ )x

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, you 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).

<< Previous  Top  |  1 | 2 | 3 | 4 | 5  |  Return to Index  Next >>

  Copyright © 2006-2008  Elizabeth Stapel   |   About   |   Terms of Use

 Feedback   |   Error?