Linear Programming

Linear programming is used to determine the maximum or minimum value of a set of inequalities.
The easiest method of demonstrating this is to provide an example, so I will use #39 on page 581 of our textbook.
It reads: A merchant plans to sell two models of compact disc players at costs of $250 and $400. The $250 model yields a profit of $45, and the $400 model yields a profit of $50. The merchant estimates that the total monthly demand will not exceed 250 units. The merchant does not want to invest more than $70,000 in inventory for these products. Find the number of units of each model that should be stocked in order to maximize profit.

We must first set up the inequalities and determine that x is to represent the $250 model and y is to represent the $400 one. The first inequality will relate the dollar amounts of the items, while the second will relate the number stocked. Also, we must include two "hidden" inequalities, which dictate that there cannot be a negative number of either model of CD players.

250x + 400y ≤ $70,000
x + y             ≤ 250
x                   ≥ 0
y                   ≥ 0

We should also create an equation to find the maximum profit. We will set z equal to the profit of the $200 model times x plus the profit of the $400 model times y:

z = 45x + 50y

Next we should put the first two inequalities in slope-intercept form (y = mx + b) so that we can graph them (since the last two inequalities are already in an easily graph-able state, we can leave them as-is). This produces:

y ≤ (5/8)x + 175
y ≤ -x + 250

To find the vertices, or the points of intersection, we can use elimination or substitution and solve the inequalities as we would with systems of equations. The x and y values we get as a result will be formatted as an ordered pair (x, y).
We now get the following ordered pairs as vertices:

(0, 0), (250, 0), (0, 175), (200, 50)

All we have to do now is substitute each of these ordered pairs into the equation we created earlier for z and determine which gives the greatest profit:

45(0) + 50(0) = $0
45(250) + 50(0) = $11,250
45(0) + 50(175) = $8,750
45(50) + 50(200) = $11,500

Given that the ordered pair (200, 50) produced the greatest profit, our answer will be:

200 of the $250 CD players
50 of the $400 CD players