Based on Ravindran (1971). A library must build shelving to shelve 200 4-inch-high books, 600 8-inchhigh books, and 500 12-inch-high books. Each book is 0.5 inch thick. The library has several ways to store the books. For example, an 8-inch-high shelf can be built to store all books of height less than or equal to 8 inches, and a 12-inch-high shelf can be built for the 12-inch books. Alternatively, a 12-inch-high shelf can be built to store all books. The library believes it costs $2300 to build a shelf and that a cost of $5 per square inch is incurred for book storage. (Assume that the area required to store a book is given by the height of the storage area multiplied by the book’s thickness.) Determine how to shelve the books at minimum cost. (Hint: We agree that this is not a very realistic problem in terms of how a library operates, but it is a good modeling challenge. Create nodes 0, 4, 8, and 12, and make the cost associated with the arc joining nodes i and j equal to the total cost of shelving all books of height greater than i and less than or equal to j on a single shelf.)
