An Art Gallery is considering installing a video camera security system to reduce its insurance premiums. A diagram of the eight display rooms that the art gallery uses for exhibitions is shown in the figure below (i.e., Rooms A, B, C , H); the openings between the rooms are numbered 1 through 11.

A security firm proposed that two-way cameras be installed at some room openings. Each camera has the ability to monitor the two rooms between which the camera is located. For example, if a camera were located at opening number 3, rooms A and D would be covered; if a camera were located at opening 10, rooms G and H would be covered; and so on. Management decided not to locate a camera system at the entrance to the display rooms. The objective is to provide security coverage for all eight rooms using the minimum number of cameras.

1. Formulate a 0-1 integer linear programming model that will enable the art gallery's management to determine the locations for the camera systems.

Make sure to fully specify the objective function and constraint(s).

[Hint: the objective function to minimize the total number of cameras used is specified below.]

[Hint: In the objective function, x1 is a 0-1 decision variable which takes the value of 1 if a camera is installed at opening 1, and 0 if no camera is installed; x2 is a 0-1 decision variable which takes the value of 1 if a camera is installed at opening 2, and 0 if no camera is installed; x3 is a 0-1 decision variable ]

[Hint: To provide security coverage for Room A, a camera needs to be installed in at least one of the following openings: opening 3, opening 5. To provide security coverage for Room B, a camera needs to be installed in at least one of the following openings: opening 5, opening 7, opening 11. A similar logic can be applied for Rooms C, D, E, F, G, and H. Hence, you need to specify a constraint for each room.]

Minimize x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11

Subject to:

2. Use Excel Solver to find a solution for the model formulated in part (a). What is the total number of cameras that need to be purchased? Where should each of these cameras be located (i.e., which openings)?

3. Suppose that management wants to provide additional security coverage for Room D. Specifically, management wants Room D to be covered by two cameras. Which constraint would have to change? What should the new constraint be?

4. With the policy restriction specified in part (c), what is the total number of cameras that need to be purchased? Where should each of these cameras be located (i.e., which openings)?

Room C 1 Entrance Room A 2 3 Room D 4 Room G 5 + 7 Room E 8 Room B 9 10 11 Room F Room H