Because QiX) is a sum of convex functions, must be a positive semidefinite matrix. To solve problem (9.2), introduce the Lagrange multiplier and form the Lagrangian function ,\) = - -l). Taking the first partial derivative of L{X,\) with respect to the vector X and equating to zero gives 2BX - 1\X = 0. Using the w X w identity matrix given by /, we may write:

{B - \I)X = 0. (9.3)

Solving this system of linear equations produces a nontrivial solution X if, and only if, X is an eigenvalue of the matrix B, and X is the corresponding eigenvector. Premultiplying both sides of expression (9.3) by X and substituting XX = 1 gives:

= XBX = Q{X).

(9.4)

With the eigenvalues ranked in increasing order, the eigenvector gives the best solution, with the eigenvalue being its objective value. The least eigenvalue, Xq = 0, produces the solution X = {\/4rn,\/yJrn,...,\l4m), which is disregarded.

Example 9.5 We now apply the Hall method to the problem given in Table 9.3 and Figure 9.3. Because distances are rectangular, this layout problem is essentially one-dimensional with the equivalent required pattern as shown in Figure 9.10. The W matrix is given by:

0 50 20 100

50 0 30 10

20 30 0 70

100 10 70 0

The D and matrices are as follows:

170 -50 -20 -100

-50 90 -30 -10

-20 -30 120 -70

-100 -10 -70 180

The four eigenvectors Eo, E„ Ej, £3 of matrix and their associated eigenvalues Xo, X,, X2, x3 are given in Table 9.26.

Using E (because E provides no information and is disregarded) the cost minimizing layout is the sequence 2,1,4,3 shown in Figure 9.11. This agrees with the branch-and-bound solution given earlier and is thus optimal.

Figure 9.10 Layout Pattern Equivalent to Figure 9.3.

Table 9.26 Eigenvectors and Eigenvalues for Example 9.5.

Eigenvectors

1 4 3

-♦• X

-1,0 0

Figure 9.11 One-Dimensional Layout Using £,.

Two-Dimensional Problems

Let Y = CKi,J2,--,y,„) be the vector of y-coordinates of the m points. Then the two-dimensional layout problem with weighted squared Euclidean distances can be written:

minimize Q(X,Y) = XBX + YBY X,Y

subject to

XX = 1 and YY = 1.

(9.5)

To solve problem (9.5), introduce two Lagrange multipliers a and /3, and form the Lagrangian function

L{X,Y,a,p) = XBX + YBY - aXX - 1) - (3( - 1).

Taking first partial derivatives with respect to X and Y and equating to zero gives:

/ = 2BX - 2aX = 0 BL/dY = 2BY - 20Y = 0.

(9.6) (9.7)

The solutions to these two systems of equations are provided by the eigenvectors of matrix associated with the eigenvalues a and /3, respectively. If both sides of expressions (9.6) and (9.7) are premultiplied by X and Y, respectively, and the constraints XX = 1 and = 1 are substituted, the result is that Q(X, ) = « + /3- Let the m eigenvalues of be given by 0 = X„ < X, < X2 < ... X,„ ,. The cases for which a \ and/or = correspond to the trivial solutions wherein all the x, and/or all the j, are equal. Such solutions are generally unsatisfactory. The most satisfactory choice in general is to let a = X, and /3 = X2. The vectors X and are the eigenvectors associated with a and 0, respectively. With this choice the facilities are optimally located in the direction of the first coordinate axis and located "next-to-optimal" in the direction of the second coordinate axis.

The method can be extended to problems in three dimensions. In this case the eigenvalues used generally would be X,, 2, and X3, and Q{X,Y,Z) is given by QiX,Y,Z) = X, -b 2 + X3. The vectors of the coordinates of the points in three-dimensional space are given by the eigenvectors associated with X, 2, and X,.

Example 9.6 To demonstrate the use of the Hall method in two dimensions, consider the following example with m = 12 facilities. The interfacility weights are given in Table 9.27, the first eight eigenvalues and eigenvectors in Table 9.28, and the plot of points with coordinates from and Ej is given in Figure 9.12. The required layout pattern is 3 X 4, ie, unit square locations with three rows and four columns. The distance measure is rectangular. From Figure 9.12, several possible assignments of facilities to locations suggest themselves. Two of these are

Table 9.27 Interfacility Weights for Example 9.6.

Table 9.28 Eigenvectors and Eigenvalues for Example 9.6.

given in Figures 9.13 and 9.14. The associated costs using rectangular distances and assuming unit square locations are 302 and 310, respectively. Because these layouts are based on squared Euclidean distances and the shapes and sizes of the locations are not predetermined, they

Figure 9.12 Plot of Points for Example 9.6.

£2

1.0- -

-1.0

9»8» 11

-1.0--

First initial solution (suggested layout from Figure 9.13)

Figure 9.13 Possible 3X4 Layout of Facilities (Cost = 302).

Figure 9.14 Possible 3X4 Layout of Facilities (Cost = 310).

£2

3 9 7 12

11 4

2 10 6 5

Second initial solution (suggested layout from Figure 9.14)

9 12

1 11 7 4

2 10 6 5

should be tested for possible improvement. Using these two layouts as starting solutions for the HC63-66 algorithm, the following improved layouts were obtained:

From first initial solution (cost = 289)

From second initial solution (cost = 291)

Bazaraa and Elshafei (1979) state that the least cost for this problem is 289.

Several points are worth emphasizing. Even when provided with a very good smarting solution (as indicated in Figure 9.14), the pair-exchanging heuristic was unable to achieve the optimal solution. The first Hall solution (indicated in Figure 9.13) was only one pair-exchange away from the optimal solution. The Hall method is computationally feasible for large problems. It incorporates a great deal of flexibility because it is not restricted to predetermined location sizes or shapes. For problems having the requirement of unit square locations, a good procedure seems to be to use the Hall method to generate several initial layouts and then use a heuristic such as CRAFT or HC63-66 to improve upon these layouts.

EXERCISES

9.1 Six disk-shaped departments, each 20 feet in diameter, are to be located on a rectangular floor that is 40 feet by 60 feet. Assume that traflic flows occur along straight paths between the centers of the disks. The interfacility traffic flow matrix is given as follows: