Question

There are six cities (cities 1-6) th Kilroy County. The county must deicrmine where to build fire stations. The county wants to build the minimum number of fire stations needed to ensure that at least one fire station is within 15 minutes (driving time) of each city. The times (in minutes) required to drive between the cities in Kilroy County are shown in Table 6, Formulate an IP that will tell Kilroy how many fire stations should be built and where they should be located. City I o 1020 30 30 City 2 10 25 35 20 City 3 20 25 15 30 20 City 4 30 355 0 5 25 City 5 30 20 30 1 10 15 5 20 15 5 20 20iss20

Answer 1

	Within 15 Minutes
City 1	1, 2
City 2	1, 2, 6
City 3	3, 4
City 4	3, 4, 5
City 5	4, 5, 6
City 6	2, 5, 6

min z = x1 + x2 + x3 + x4 + x5 + x6

From the table above the constraints are formulated below.

s.t. x1 + x2 >= 1 (City 1 constraint)

s.t. x1 + x2 + x6 >= 1 (City 2 constraint)

s.t. x3 + x4 >= 1 (City 3 constraint)

s.t. x3 + x4 + x5 >= 1 (City 4 constraint)

s.t. x4 + x5 + x6 >= 1 (City 5 constraint)

s.t. x2 + x5 + x6 >= 1 (City 6 constraint)

xi 0 or 1 (i 1, 2, 3, 4, 5, 6)

Solving this using Excel Solver,

The minimum fire station required is 2, and should be placed at City 2 & City 4.