3. A publisher has orders for 600 copies of a certain text from San Francisco and 400 copies from Sacramento. The company has 700 copies in a warehouse in Novato and 800 copies in a warehouse in Lodi. It costs $5 to ship a text from Novato to San Francisco, but it costs $10 to ship it to Sacramento. It costs $15 to ship a text from Lodi to San Francisco, but it costs $4 to ship it from Lodi to Sacramento. How many copies should the company ship from each warehouse to San Francisco and Sacramento to fill the order at the least cost?

Steps

0. Read the whole problem.
1. Define your unknowns.
2. Express the objective function
3. Express the constraints.
4. Graph the constraints.
5. Find the cornerpoints to the region of feasible solutions.
6. Evaluate the objective function at all the feasible corner points.

Step 1. Define the unknowns

After reading the whole problem we see that they want to know how many books to ship from each warehouse to each bookstore. There are four unknowns

Let

x = the number of books from Novato to San Francisco
y = the number of books from Novato to Sacramento
z = the number of books from Lodi to San Francisco
w = the number of books from Lodi to Sacramento.

Step 2. Express the objective function

Thge objective is to minimize the cost

cost = 5x + 10y + 15z + 4w

Step 3. Express the constraints

The first two constraints have to do with the orders.

San Francisco

x + z = 600

Sacramento

y + w = 400

These are equations. San Francisco has an order for 600 books. They have to get exactly 600 books. More or less will not do. If they get less than 600 books, students will be going without texts, but if they get more than 600 texts, they will say, "We only orderd 600 texts. We're not paying for any more." Similarly, Sacramento needs exactly 400 texts. As a result, we can solve these equations to express z and w in terms of x and y.

z = 600 - x
w = 400 - y

The next two cnstraints have to do with the supplies

There are only 700 books in Novato.

x + y < 700

There are only 800 books in Lodi.

z + w < 800

If we substitute for z and w, we can express this constraint in terms of x and y.

600 - x + 400 - y < 800

1000 - x - y < 800

200 < x + y

  The total order is for 1000 books. There are only 800 books in Lodi. At least 200 books will have to come from Novato.

Then there are the implied constraints.

x > 0
y > 0
z > 0
w > 0

When we substitute into the last two, we get

600 - x > 0
400 - y > 0

or

600 > x
400 > y

Let us summarize our constraints expressed using only x and y.

x + y < 700
x + y > 200
x < 600
y < 400
x > 0
y > 0

  Step 4. Graph the constraints

 

Step 5. Find the feasible corner points

The feasible corner points are

(0, 400)
(0, 200)
(200, 0)
(600, 0)
(600, 100)
((300, 400)

We now evaluate the objective function at all of the feasible corner points. The coordinates tell us how many books are being shipped from Novato to San Francisco and Sacramento. Once we know that we can figure how many books are going to be shipped from Lodi. We will ship enough books from Lodi to fill the orders.

At (0, 400) we would be shipping 400 books from Novato to Sacramento. That would fill the Sacramento order, so we would not need to ship any books from Lodi to Sacramento, but San Francisco still needs its 500 copies. Those would all come from Lodi. This would probably be the worst solution. All of the books would be shipped to the most expensive places.

At (0, 200), 200 copies would go from Novato to Sacramento, and none from Novato to San Francisco. All 600 copies to San Francisco would come from Lodi. Sacramento would still need 200 copies which would also come from Lodi. This is a feasible solution, because there would be 800 copies coming from Lodi, and there are 800 copies in Lodi. This would be a better solution than the first one because not all copies are going to the most expensive places. The constraint upon which we find these two solutions is the one where there are no copies going from Novato to San Francisco.

At (200, 0), There would be 200 copies going from Novato to San Francisco and none from Novato to Sacramento. San Francisco would still need 400 copies from Lodi, and all 400 copies to Sacramento would be coming from Lodi. Again this would involve using all 800 copies from the Lodi warehouse. The constraint upon which we find these last two solution are the constaint that comes from the fact that Lodi has only 800 copies. The other 200 copies in the total order will come from Novato.

At (600, 0), There would be 600 copies coming from Novato to San Francisco. This would fill the San Francisco order. If there are no copies going from Novato to Sacramento, then the entire Sacramento order of 400 copies must come from Lodi. The constraint upon which we find these last two solutions is the one where there are no copies going from Novato to Sacramento. This is good, because it costs more money to send books from Novato to Sacramento than it does to send them from Novato to San Francisco.

At (600, 100), after filling the San Francisco order with books from Novato, the other 100 copies in the Novato warehouse go to Sacramento. San Francisco would not get any copies from Lodi. Lodi would fill the remainder of the Sacramento order and send them 300 copies. Tshe constraint upon which these last two solutions find themselves comes from filling the San Francisco order with books from Novato.

Finally, at (300, 400), the entire Sacramento order is filled from Novato, and the remaining 300 copies in the Novato warehouse would go to Sacramento. At this point, Lodi would need to send 100 copies to Sacramento to fill their order, but would not have to send anything to San Francisco. The constraint upon which we find these last two solutions is the constraint that comes from the fact that there are 700 copies in the Novato warehouse.

Step 6. Evaluate the objective function at all of the feasible corner points

Now that we know the number of copies from each warehouse to each retailer, we can plug these numbers into the objective function. There is another way that we have gone over in class. We can express the objective function

5x + 10y + 15z + 4w

using only x and y by substituting z = 600 - x and w = 400 - y

5x + 10y + 15(600 - x) + 4(400 - y)

= 5x + 10y + 9000 - 15x + 1600 - 4y

= 10600 - 10x + 6y

The $10600 would be the cost of shipping all 600 copies from Lodi to San Francisco and all 400 copies from Lodi to Sacramento. Of course this is not a feasible solution. there are only 800 copies on Lodi. We will have to ship some books from Novato. This objective function expresses the fact that we save money by shipping books from Novato to San Francisco, but it will cost more money to ship them from Novato to Sacramento. As a result we will see that the solution which involves shipping the most books from Novato to San Francisco and the fewest books from Novato to Sacramento will be best.

(0, 400)

= 10600 - 10(0) + 6(400) =10600 - 0 + 2400

= $13000

(0, 200)

= 10600 - 10(0) + 6(200) = 10600 - 0 + 1200

= $11800

(200, 0)

= 10600 - 10(200) + 0 = 10600 - 2000 + 0

= $8600

(600, 0)

= 10600 - 10(600) + 6(0) = 10600 - 6000 + 0

= $4600

(600, 100)

=10600 - 10(600) + 6(100) = 10600 - 6000 + 600

= $5200

(300, 400)

= 10600 - 10(300) + 6(400) = 10600 - 3000 + 2400

= $10000

The least cost of $4600 is found at (600, 0). This makes sense if you think about it. You are fillling the entire San Francisco order with copies from Novato, which is cheaper, and filling the entire Sacramento order with copies from Lodi, which is also cheaper. One could arrive at this solution by common sense, but it is good if our techniques validate common sense.

Return to test