The Bayside Art Gallery is considering installing a video camera security system to reduce its insurance premiums. A diagram of the eight display rooms that Bayside uses for exhibitions is shown in the figure below; the openings between the rooms are numbered 1 through 13.

A blueprint of a gallery with eight rooms, one entrance and thirteen doorways is shown. The gallery is laid out in a grid of three columns and four rows. Some rooms take up more than one row. The left-hand side contains rooms 1 and 2, the middle column rooms 3, 4, 5, and 6, and the right-hand side rooms 7 and 8. The following list contains each doorway and the rooms it connects.

• Entrance: Room 1
• Opening 1: Rooms 1 and 3
• Opening 2: Rooms 3 and 7
• Opening 3: Rooms 3 and 4
• Opening 4: Rooms 1 and 4

• Opening 5: Rooms 4 and 7
• Opening 6: Rooms 1 and 2
• Opening 7: Rooms 4 and 5
• Opening 8: Rooms 2 and 5
• Opening 9: Rooms 5 and 7

• Opening 10: Rooms 5 and 6
• Opening 11: Rooms 7 and 8
• Opening 12: Rooms 2 and 6
• Opening 13: Rooms 6 and 8

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 4, rooms 1 and 4 would be covered; if a camera were located at opening 11, rooms 7 and 8 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 two-way cameras.

(a)

Formulate a 0-1 integer linear programming model that will enable Bayside's management to determine the locations for the camera systems. (Let x_i be the 0-1 which is 1 if a camera is installed at opening i, and 0 otherwise, for i = 1, 2, ..., 13.)

Min

s.t.Room 1

Room 2

Room 3

Room 4

Room 5

Room 6

Room 7

Room 8

x_i = 0, 1, for i = 1, 2, , 13

(b)

Solve the model formulated in part (a) to determine how many two-way cameras to purchase and where they should be located.

The gallery should install cameras with (x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈, x₉, x₁₀, x₁₁, x₁₂, x₁₃) =

.

(c)

Suppose that management wants to provide additional security coverage for room 7. Specifically, management wants room 7 to be covered by two cameras. Which constraint would have to change?

Room 1Room 2 Room 3Room 4Room 5Room 6Room 7Room 8

What should the new constraint be?

(d)

With the policy restriction specified in part (c), determine how many two-way camera systems will need to be purchased and where they will be located.

The gallery should install cameras with (x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈, x₉, x₁₀, x₁₁, x₁₂, x₁₃) =

.