1. Integer programming formulation: Grave City is considering the relocation of several police substations next summer 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: Potential Locations for Substations A B D E F G Areas Covered 1,5,7 1, 2,5,7 1, 3,5 2.4.5 3,4,6 4, 5, 6 1.5, 6, 7 Formulate an integer programming model that could be used to find the minimum number of locations necessary to provide coverage to all areas. 2. Integer programming formulation: The following questions refer to a capital budgeting problem with six projects represented by 0-1 variables x1, X2, X3, X4, X5, and x6: a. Write a constraint modeling a situation in which two of the projects 1, 3, 5, and 6 must be undertaken. b. Write a constraint modeling a situation in which, if projects 3 and 5 must be undertaken, they must be undertaken simultaneously. Write a constraint modeling a situation in which project 1 or 4 must be undertaken, but not both. d. Write constraints modeling a situation where project 4 cannot be undertaken unless projects 1 and 3 also are undertaken. e. In addition to the requirement in part (d), assume that when projects 1 and 3 are undertaken, project 4 also must be undertaken. 3. Integer program graphical solution: Consider the following all-integer linear program: Max 1x + 1x2 s.t. 4x1 + 6x2 = 22 1x1 + 5x2 = 15 2x + 1x2 5 9 x1, x2 0 and integer a. Graph the constraints for this problem. Use dots to indicate all feasible integer solutions. b. Solve the LP Relaxation of this problem. (Graphically) c. Find the optimal integer solution. (Graphically)