Question

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 following figure; the openings between the rooms are numbered 1–13. 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 binary integer linear programming model that will enable Bayside’s management to determine the locations for the camera systems.

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

c. Suppose that management wants to provide additional security coverage for room 7. Specifically, management wants room 7 to be covered by two cameras. How would the model you formulated in part a have to change to accommodate this policy restriction?

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.

Answer 1

a)

Consider the 0-1 integer linear programming:

Show the objective of the function as follows:

Minimize

Show the constraints for the 0-1 integer linear program as follows:

b)

Enter the objective (Minimize) and constraint of the function.

Assume the values for .

Show the objective and constraints of the function as in Spreadsheet as in Figure (1).

Use the solver tool to find the optimal solution as in Figure (2).

Solve the function and find the optimal solution as in Figure (3).

Show the final answers for constraints as in Figure (4).

Refer to Figures (3) and (4):

The optimal solution for the linear programming is given as follows:

The value of is .

The value of is .

The value of is .

The value of is .

Thus, the camera should be placed at the openings of 1,7,11, and 12.

Thus, the optimal solution is .

c)

Change the constraint for the room 7.

d)

Enter the objective (Minimize) and constraint of the function.

Assume the values for .

Show the objective and constraints of the function in Spreadsheet as in Figure (5).

Use the solver tool to find the optimal solution as in Figure (6).

Solve the function and find the optimal solution as in Figure (7).

Show the final answers for constraints as in Figure (8).

Refer to Figures (7) and (8):

The optimal solution for the linear programming is given as follows:

The value of is .

The value of is .

The value of is .

The value of is .

The value of is .

Thus, the camera should be placed at the openings of 2, 4, 6, 10, and 11.

Thus, the optimal solution is .