Question 2 Suppose you are faced with the following problem: your company is thinking of opening new depots to supply wood to sofa manufacturers in Lancashire. Six locations have been identified which are suitable to open a depot which can store wood. However, there is a constraint that you can only open at most 4 out of the possible 6 depots. There are 7 clients (sofa manufacturers) in Lancashire and each of these clients should be supplied from exactly one depot. There is no restriction on the number of clients that can be supplied from each depot. The problem is to decide which depots to open and how to assign each client to exactly one paned depot such that total profits are maximized. The profit matrix is given below: (000 ) Depot 1 Depot 2 Depot 3 Depot 4 Depot 5 Depot 6 Client 1 2 3 7 3 6 1 Client 23 1 1 8 10 4 Client 36 3 1 2 7 2 Client 48 1 4 2 3 Client 5 4 4 3 3 4 3 Client 62 8 3 6 3 2 5 Client 76 IN 4 + (a) Devise a local search heuristic and comment on the size of the neighbourhood. (35% of marks) (b) Find the local optimum in the neighbourhood proposed in part (a). Explain if this local optimum is also the global optimum by clearly giving the reasoning. Is this true in general for any profit matrix? (30% of marks) ) Give an integer programming fomulation for the problem. (35% of marks) Question 2 Suppose you are faced with the following problem: your company is thinking of opening new depots to supply wood to sofa manufacturers in Lancashire. Six locations have been identified which are suitable to open a depot which can store wood. However, there is a constraint that you can only open at most 4 out of the possible 6 depots. There are 7 clients (sofa manufacturers) in Lancashire and each of these clients should be supplied from exactly one depot. There is no restriction on the number of clients that can be supplied from each depot. The problem is to decide which depots to open and how to assign each client to exactly one paned depot such that total profits are maximized. The profit matrix is given below: (000 ) Depot 1 Depot 2 Depot 3 Depot 4 Depot 5 Depot 6 Client 1 2 3 7 3 6 1 Client 23 1 1 8 10 4 Client 36 3 1 2 7 2 Client 48 1 4 2 3 Client 5 4 4 3 3 4 3 Client 62 8 3 6 3 2 5 Client 76 IN 4 + (a) Devise a local search heuristic and comment on the size of the neighbourhood. (35% of marks) (b) Find the local optimum in the neighbourhood proposed in part (a). Explain if this local optimum is also the global optimum by clearly giving the reasoning. Is this true in general for any profit matrix? (30% of marks) ) Give an integer programming fomulation for the problem. (35% of marks)