It's always entertaining when your teacher gets stuck on a homework problem during a review session for an exam. The problem in question, Exercise 17 from Sec. 7.3, concerns a greeting card company that stashes its cards in two warehouses and wants to ship them as economically as possible to its outlets in San Jose and Memphis. Since I think you're owed a proper explanation of how to solve the problem, let me pick apart the many components of this exercise and try to give you a good and reasonably straightforward solution.
First of all, we're given a broad (and perhaps confusing) hint about what to use as variables. Let's assign them this way: x will be the number of boxes of cards shipped from Warehouse I to San Jose and y will be the number of cards shipped from Warehouse I to Memphis. Since San Jose really wants 350 boxes, it will still need 350 − x boxes (if any) after receiving the shipment of x boxes from Warehouse I. Therefore the balance, 350 − x, must come from Warehouse II. Similarly, since Memphis wants 250 boxes, it will receive y from Warehouse I and 250 − y from Warehouse II.
The object of this exercise is to minimize the total shipping costs in filling the orders from the two stores. We're given this cost grid:
We conclude therefore, that the total cost of shipping the cards from the two warehouses to the two stores will be
z = 25x + 23(x − 350) + 22y + 21(250 − y).
I'm expressing the cost in pennies so as to dispense with the decimal points for now. As we saw in class, when you multiply this out and collect like terms, the object function reduces to
z = 2x + y + 13,300.
Now we need to find a feasible region in the xy plane at whose vertices we can check the object function. Let's list what we know:
Warehouse I has only 500 boxes of cards in stock, so
x + y ≤ 500.
Warehouse II has only 290 boxes of cards in stock, so
(350 − x) + (250 − y) ≤ 290.
When we remove the parentheses and collect like terms, this becomes
600 − x − y ≤ 290,
so
−x − y ≤ −310,
and (dividing by −1 and reversing the inequality)
x + y ≥ 310.
When we graph these two inequalities together, we get two parallel lines and the region between them:
We already know that x and y are both nonnegative, so we care only about points in quadrant I. We must also have 350 − x ≥ 0 and 250 − y ≥ 0 since these are the number of boxes being shipped from Warehouse II. The first condition implies that x ≤ 350 and the second requires that y ≤ 250. When we include these conditions on the graph, we get our feasible region for this problem:
We can now start reading off our vertices. The points (310, 0) and (350, 0) lie on the x axis. The points (350, 150) and (250, 250) are also easy to read from the graph. The remaining vertex lies on the intersection of the line y = 250 with the line x + y = 310. If we plug in 250 for y, we find that x must be 60. Our last point is therefore (60, 250). We can fill in our points and compute the values of the object function at each one:
As you can see, the object function is minimized when x = 60 and y = 250. That means San Jose gets 60 boxes from Warehouse I and 350 − x = 350 − 60 = 290 boxes from Warehouse II, while Memphis gets all of its order from Warehouse I (nothing from Warehouse II). Since we've been expressing the cost in pennies, we should convert it to dollars as we conclude that the minimum shipping cost is $136.70.
Note: This problem could have been done as a four-variable linear programming problem, using the techniques that appear later in this chapter. However, with a creative choice of variables it was possible to solve it with only two variables. That permitted us to do it with a graph in the xy plane. Unfortunately, we won't be going on to those sections of the book that allow us to do more complicated linear programming problems.
No comments:
Post a Comment