Grave City is considering the relocation of several police substations to obtain better enforcement in high-crime areas. The locations under consideration together with the areas that can be covered from these locations are given in the following table. A one in the table below indicates that the substation covers the area and a 0 indicates it does not cover the area.

	Substation L	Substation M	Substation N	Substation O	Substation P	Substation Q	Substation R
Area 1	0	0	1	0	1	1	1
Area 2	0	0	0	1	0	1	0
Area 3	1	0	1	0	0	0	0
Area 4	1	1	0	1	0	0	0
Area 5	0	1	1	1	1	1	1
Area 6	1	1	0	0	1	0	0
Area 7	0	0	0	0	1	1	1

(a)

Formulate an integer programming model that could be used to find the minimum number of locations necessary to provide coverage to all areas. (Let x_i = 1 if substation i is chosen, 0 otherwise, for i = L, M, N, O, P, Q, R.)

Min _____

s.t.

Area 1 ______

Area 2 ______

Area 3 ______

Area 4 ______

Area 5 ______

Area 6 ______

Area 7 ______

x_i = 0, 1 for i = L, M, N, O, P, Q, R

(b)

Build a spreadsheet model for this problem. Solve the model. Which locations are chosen? (Select all that apply.)

Substation L

Substation M

Substation N

Substation O

Substation P

Substation Q

Substation R

	Substation L	Substation M	Substation N	Substation O	Substation P	Substation Q	Substation R
Area 1	0	0	1	0	1	1	1
Area 2	0	0	0	1	0	1	0
Area 3	1	0	1	0	0	0	0
Area 4	1	1	0	1	0	0	0
Area 5	0	1	1	1	1	1	1
Area 6	1	1	0	0	1	0	0
Area 7	0	0	0	0	1	1	1