BOOK STORAGE PROBLEM
In-Class Case
A library can store books according to their subject, author, or by size. This exercise concerns an optimal storage of books by their size to minimize the storage cost for a given collection of books. Suppose that we know the heights and thicknesses of all the books in a collection (assuming that all widths fit on the same shelving, we consider only a two-dimensional problem and ignore book widths). Suppose that we have arranged the book heights in ascending order of their n known heights H1, H2, … , Hn; that is, H1 < H2 < … < Hn. Since we know the thicknesses of the books, we can compute the required length of shelving for each height class. Let Li denote the length of shelving for books of height Hi. If we order shelves of height Hi for length xi, we incur cost equal to Fi + cixi; Fi is a fixed ordering cost (and is independent of the length ordered) and Ci is the cost of the shelf per unit length C1 ≤ C2 ≤ …≤ Cn. Notice that in order to save the fixed cost of ordering, we might not order shelves of every possible height because we can use a shelf of height Hi to store books of smaller heights. We want to determine the length of shelving for each height class that would minimize the total cost of the shelving. 1. Formulate this problem as a shortest path problem. 2. Solve the compact book storage problem with the following data: 3. Show that the storage problem is trivial if the fixed cost of ordering shelves is zero.