Super Sleep is a company making matresses for king-size beds. Matresses can be shipped directly from either of its plants to retail store customers, or they may be transshipped through the company’s single warehouse. The table that follows shows the unit cost of shipping matresses from the plants and the warehouse to Super Sleep’s 2 customers. Shipping from either plant to the warehouse costs $15 per matress. The table also shows the number of matresses that can be produced at each plant over the next week and the number demanded by each customer.

Shipping Costs j • 1 j • 2 Capacity Plant 1 25 30 400 Plant 2 45 23 600 Warehouse 11 14 —

Demand 160 700 —

Super Sleep seeks a minimum total shipping cost way to supply its customers.

(a) Formulate a linear program to determine an optimal shipping plan.

(b) Use class optimization software to compute an optimal solution to your LP.

(c) Show that your LP can be represented as a minimum cost flow model (with total supply = total demand) by sketching the corresponding digraph and labeling as in Exercise 10-1.

(d) Classify nodes in your digraph as source, sink, or transshipment.