A German city has six neighborhoods (labeled N1 - N6).The city must determine where to locate its fire stations.The city council wants to build the fire stations to ensure that at least one fire station is within 15 minutes driving time of each neighborhood (i.e. no neighborhood should be more than 15 minutes away from every fire station).The times (in minutes) required to drive between the neighborhoods are shown below.Each fire station must be placed within a neighborhood.

N1 N2 N3 N4 N5 N6

N1 0 10 20 30 30 20

N2 10 0 25 35 20 10

N3 20 25 0 15 30 20

N4 30 35 15 0 15 25

N5 30 20 30 15 0 14

N6 20 10 20 25 14 0

The cost of building a fire station differs across neighborhoods. This cost (in millions of euros) is given by:

Cost N1 N2 N3 N4 N5 N6

1.7 2.9 1.1 3.2 0.95 1.8

The city council wants to minimize the cost of building the fire stations. Your task is to formulate this as an appropriate optimization problem and determine where the fire stations should be located.

a)Clearly define the decision variables for this problem. What is the city council's objective function? What are the constraints?

b)Solve this problem using Excel. Attach an image of your solution as Exhibit B (use the FORMULATEXT function to clearly display all of your formulae).

c)How many fire stations need to be built and where are they located? What is the total cost of building the fire stations?

d)How would you formulate the following additional constraints? [You do not need to re-solve the problem. Just state the constraints here.]

"If there is a fire station in N2, then there must be a fire station in N4 as well."

"If there is a fire station in N2, then a fire station is not placed in N6."