back start next
[start] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [ 41 ] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51]
41 Table 9.7 Subtract from Each Column the Diagonal Entry in that Column: = 30 + 40 + 60 + 50 + 70 + 100 = 350. Location Pair    Facility Pair                                                   
Table 9.8 Subtract from Each Row the Minimum Entry of that Row: = 350 + 0 + (10) + (10) + (30) + (30) t(30) = 240. Location Pair    Facihty Pair                                                   
row entries is continued, as shown in Tables 9.9, 9.10, and 9.11, at which point R = 350. The beginning node of the branchandbound tree corresponds to being able to make any assignment, feasible or not. The minimum total cost has a lower bound of 350. This corresponds to the cost of the diagonal assignment. Let an entry in the row and /" column of the cost matrix be denoted by c,j. In general, branching to the right from a node will imply the assignment of a particular pair of facilities to a particular pair Table 9.9 Subtract Diagonal Entries from Each Column: R + 0 + 10 H 10 + 30 + 30 + 30 = 350. Location Pair    Facility Pair                                                   
Table 9.10 Subtract Minimum Entry from Each Row: = 350 + 0 + 0 4 0 t (10) + (10) + (10) = 320. Location    Facility Pair          Pair                      D                             Table 9.11  Subtract Diagonal Entries from Each Column: R   320 + 0 +  0 + 0 +  10 f 10 +  10 =  350.    Location    Facility Pair          Pair                                                 
of locations. We will use the notation: A D * 1  3, for example, to denote the assignment of facilities 1 and 3 to the locations A and D. A branch to the left means the particular assignment is to be prohibited. We will denote this by: AD 1  3, for example. Each succeeding node to be chosen is decided by the following rule: Selection of Next NodeChoose an entry c in cost matrix for the next node so that: = max { ,} where e,i = smallest entry in row i, omitting c,j + smallest entry in column , j, omitting c,j. Table 9.12 indicates the flf values in the upper right of each cell; max [e,j] = 10 = Branching to the left is denoted on the tree by AD, branching to the right by AD. The new lower bound of the left branch node is equal to the lower bound of the previous node plus dj. The new lower bound of the right branch node is equal to the lower bound of the previous node plus the reducing constants obtained after cost matrix is restricted. Restriction consists of an examination of remaining entries in cost matrix to see if they correspond to acceptable assignments. If an entry
Table 9.12  Values for Each Assignment.      Facilily Pair    Pair                                                 
is not acceptable, the entry is deleted to remove it from further consideration. Consider a hypothetical example with five facilities as shown in Table 9.13. Suppose facility pair 34 has been assigned to location pair B E (facility 3 is at location or E, with facility 4 at the other location). The entries in the B E row and the 3  4 column have been deleted except the intersection Cg,o, which is equated to zero. Then the location pairs not assigned are A C, A D, and CD. In the rows with these labels, keep those entries whose column labels are facility pairs not assigned (in this case 12, 15, and 2  5); but delete entries from columns labeled 1  3, 1 4, 2  3, 24, 3  5, and 45, as they have a 3 or a 4 in their labels. In the remaining rows (labeled AB, AE, B C, BD, BE, CE, DE), keep entries from columns 13, 14, 23, 24, 3  5, and 4  5, but delete entries with columns labeled 12, 15, and 25. Any reduction can now be made, ignoring deleted entries. Using these rules, the branchandbound method is applied to the example in Tables 9.14 to 9.24. Table 9.13 Xs Indicate Entry Retained in the Matrix (Partial Assignment, BE 34). Location Pair      Facility Pair             25 34                                                                                                     
Table 9.14 Restriction as Result of 6,, Assigning 24 to AD: Reduction Now Possible on Row 5. Location Pair Facility Pair AD AC BD AB BC CD Table 9.15 Reducing Constant 10 Added to 350 for Lower Bound on Right Branch [branching will continue from left node (AD Location Pair AD AC BD .350 Ail Possible (Assignmentsl Table 9.16 Branch on Node AD 24 (c,, is set equal to oo to block assignment of 24 to AD; row 1 reduced by 10; 0„  10 selects node AD  13). Facility Pair Location Pair    23 1    1 4                       A                     
Table 9.17 Restriction as a Result of e, Assigning 13 to AD (the entries in AD row and 1 3 column deleted; zero entered in reduction now possible on row 5). Location Pair    Facility Pair                                                   
Table 9.18 Reducing Constant 20 Added to 360 to Become the Lower Bound for Node AD 13 (branching continues at node AD 24, which now has the least lower bound of any of the active nodes). Location Pair    Facility Pair       1 2    A D                                          
Table 9.19 Branching on Node AD 24 Where = 20 = max {e,j\ (bound for node AC 23 thus becomes 360 + 20 = 380; Table 9.19 derives directly from Table 9.14). Location Pair    Facility Pair                                                   
At this point the branch to the right from node AD 2  4 to node AC < 2  3 specifies the complete assignment . This 2 13 4 assignment has a total cost of 430. The next branch is thus from node AD < 1  3, which has a lower bound of 370. The complete branchandbound tree appears in Figure 9.4 with the two optimal solutions. Possible lAssignmentsl
[start] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [ 41 ] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51]
