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.

enter image description here

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.

  • $\begingroup$ If this is a homework question, please 1) read our policy regarding homework questions and 2) use homework tag. $\endgroup$
    – EhsanK
    Commented Nov 11, 2019 at 14:28
  • $\begingroup$ it's not a homework question, no. It's from my lecture notes, it doesn't have a solution. Half of my question are actually from Winston: Operations and research. He does not explain some things in details and that's why I refer to this site $\endgroup$
    – Slim Shady
    Commented Nov 11, 2019 at 14:29
  • $\begingroup$ Your computation is incorrect. Storing all 4-inch books on a 12-inch shelf has a cost of 6000 (200 books * 0.5 inch thickness * 12 inch height * 5 pounds), similarly the cost of storing all 8-inch books is 3000. $\endgroup$
    – Renaud M.
    Commented Nov 27, 2019 at 12:48
  • $\begingroup$ Would you see Shelf Space Optimization? $\endgroup$
    – A.Omidi
    Commented Dec 27, 2019 at 17:02

1 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 / inch2) = inch2 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.