Minimisation of shelving cost problem

Question

A library must build shelving to shelve $200$ 4-inch high books, $100$ 8-inch high books, and $80$ 12-inch high books. Each book is 0.5-inch thick.

The library has several ways to store books. For example, an 8-inch high shelf may be built to store all books of height no more than $8$ inches, and a 12-inch high shelf may be built for the 12-inch high books. Alternatively, a 12-inch high shelf may be built to store all books. The library believes it costs ${\it£}2300$ to build a shelf and that a cost of ${\it£}5$ per square inch is incurred for book storage. (Assume that the area required to store a book is given by the height of storage area times book thickness.)

Formulate and solve a shortest path problem that could be used to help the library determine how to shelve the books at minimum cost. (Hint: Have nodes $0$, $4$, $8$, and $12$, with being the total cost of shelving all books of height $> i$ and $\le j$ on a single shelf.)

I went on with the hint, and I discovered that the cost is minimised when we build only one shelf which is for all books (a 12-inch shelf). So the cost would be the cost of shelving all the 4-inch, 8-inch and 12-inch books) plus that of building the shelve which is $2000+2000+2400+2300$, or ${\it£}8700$.

Would this be the correct answer? I'm confused since this is a pretty obvious answer, which I think is not correct.

There is an answer on Chegg solutions which gives me the following table of costs:

\begin{array}{rr}\hline\text{Shelves}&\text{Books}&\text{Building}&\text{Storage Costs}&\text{Unshelved}\\&&\text{Costs}&&\\\hline4''&4''&{\it£}2300&200\times0.5\times5\times4={\it£}2000&8'',12''\\8''&8''&{\it£}2300&100\times0.5\times5\times8={\it£}2000&4'',12''\\8''&4'',4''&{\it£}2300&2\times200\times0.5\times5\times4={\it£}4000&8'',12''\\12''&12''&{\it£}2300&80\times0.5\times5\times12={\it£}2400&4'',8''\\12''&4'',4'',4''&{\it£}2300&\small{\it£}2000+{\it£}2000+{\it£}2000+{\it£}2400={\it£}8400&8''\\12''&\small4'',8'',12''&{\it£}2300&{\it£}2000+{\it£}2000+{\it£}2400={\it£}6400&-\\\hline\end{array}

For reference, this is the shortest path problem they're trying to optimize:

In the above table, the building cost is given to be ${\it£}2300$. From the above table, it is clear that four nodes are to be taken, that is $0$, $4$, $8$ and $12$ with $C_{i,j}$ being the total cost of shelving all books of height $>i$ and $\le j$ on a single shelf. The network will have four nodes ($0$, $4$, $8$ and $12$). The network for minimizing cost is given below.

and they calculate the cost of building a shelf for the 4-inch books only with the following formula:

Now $X_{i,j}=$ one unit of flow from node $i$ to node $j$ through $x(i,j)$. It is now seen that the length of any path from node $0$ to node $12$ is the net cost incurred. The cost from node $0$ to node $4$ is calculated as below. \begin{align}C_{0,4}=\frac{\text{Building cost}+\text{Storage cost}}{\text{Number of books}\times\text{per square inch cost}}=\frac{{\it£}2300+{\it£}2000}{200\times5}=\frac{{\it£}4300}{1000}={\it£}4.3.\end{align}

Why, in the above way of calculating $C_{0,4}$ , do they divide by (number of books per square inch x cost per square inch) . What is the logic behind this? If someone could explain if this is the right path to the solution and if not, explain how would I solve this.

Answer 1

I do not understand why the formula for $C_{0,4}$ is as such. A simple check reveals that the unit on the RHS are pounds / (pounds / inch²) = inch² whereas the unit for the cost is pounds.

---

We have only three cases to consider here:

1. 12'' shelf,

2. 8'' shelf + 12'' shelf,

3. 4'' shelf + 8'' shelf + 12'' shelf.

The general formula for the total cost is given by \begin{align}C=2300\times\#\,\text{shelves}&+200\times\text{thickness}_{4''}\times\text{height of storage}_{4''}\times5\\&+100\times\text{thickness}_{8''}\times\text{height of storage}_{8''}\times5\\&+80\times\text{thickness}_{12''}\times\text{height of storage}_{12''}\times5.\end{align} We know that the thickness is 0.5'' no matter the height of the book, and that the height of storage for the 12'' books must be, of course, 12''. The other heights depend on the number of shelves, so \begin{align}\small C&=\small2300\times\#\,\text{shelves}+0.5\times5\times(200\times\text{height of storage}_{4''}+100\times\text{height of storage}_{8''}+80\times12)\\&=\small2300\times\#\,\text{shelves}+2.5\times(200\times\text{height of storage}_{4''}+100\times\text{height of storage}_{8''}+960)\\&=\small2300\times\#\,\text{shelves}+250\times(2\times\text{height of storage}_{4''}+\text{height of storage}_{8''})+2400\end{align} after tidying up terms.

1. If only a 12'' shelf is used to store all books, $\#\,\text{shelves}=1$ and $\text{height of storage}_{4''}=\text{height of storage}_{8''}=12$. This gives $$C=2300+250\times(2\times12+12)+2400={\it£}13,700.$$

2. If one 8'' (to store 4'' and 8'' books) and one 12'' shelf (to store 12'' books) are used, $\#\,\text{shelves}=2$ so $\text{height of storage}_{4''}=\text{height of storage}_{8''}=8$. This gives $$C=2300\times2+250\times(2\times8+8)+2400={\it£}13,000.$$

3. If one 4'' shelf, one 8'' shelf and one 12'' shelf are used to store books of their corresponding heights, $\#\,\text{shelves}=3$ so $\text{height of storage}_{4''}=4$ whereas $\text{height of storage}_{8''}=8$. This gives $$C=2300\times3+250\times(2\times4+8)+2400={\it£}13,300.$$

Evidently, the shortest path problem is solved when one 8'' shelf and one 12'' shelf are used. The error in your solution is due to the height of storage, not the height of each book.