1. (50 pts)Consider the problem of designing a complex of six novelty and craft shops A, B, C, D, E, F in a resort area. The six shops are to be located in a rectangular building consisting of six locations arranged as two rows and three columns. The corresponding six cells or sites in a rectangular grid of the floor of the building are numbered from left to right and top to bot-tom as 1, 2, 3 for the first row and 4, 5, 6 for the second row. Each of the six sites is a candidate for the location of each shop. The travel costs between locations, shown in the left-hand matrix below, are proportional to the rectilinear distances. Distances are measured in units of site widths, between the centers of sites. The right-hand matrix shows the number of trips between facilities. (a) What kind of model can be used for solving this problem? (b) Find a lower bound on the total cost. (c) If shops A, B, C, D, E, and F are assigned to locations 2, 4, 5, 3, 1, and 6, respectively, find the total cost of this assignment. 012123 101212 210321 123012 212101 321210 0462 4 4 4042 2 8 6402 6 2220 6 26 2 42260 10 4862 10 0