8. A machine shop is to house six facilities, with the amount of material handling between them as given below:

1 2 3 4 5 6 1 7 0 3 2 5 2 2 8 5 1 3 6 4 2 4 1 0 5 4 6

The layout available for locating the facilities is shown below:

1 2 3 4 5 6 Assuming the distance between adjacent locations to be unity, the distance matrix is given below:

1 2 3 4 5 6 1 1 2 1 2 3 2 1 2 1 2 3 3 2 1 4 1 2 5 1 6

The industrial engineer has recommended the layout given below:

1 2 3 4 2 1 4 5 6 3 5 6 Find the lower-bound to the problem and also prove that the recommended layout is actually the optimal one.