Problem 4: Multiple Choice (15 pts) For each question, circle all the statements which are true (you do not need to justify your answer). 1. Assume that x,y and z are decision variables, which of the following is a valid objective function for alinear programming problem? a. Maximize (x + y) 5. Consider a symmetric traveling salesman problem with 5 nodes. When solving the problem by iteratively adding subtour elimination constraints, we encounter the subtour ABCA. Select the subtour elimination constraint('s) that will eliminate this subtour from subsequent iterations: a. Xa +186 +XA 3 b. Xe + Xpe +XAS2 C. +XE +XA XA +Xe +X 2. A linear program is infeasible if the number of solutions that satisfies all constraints is: a. At least 1 b. Zero c. An infinite number d. At least 2 3. A linear program is an optimization problem with the following properties: a. The problem has a single objective function b. The decision variables are restricted to integer values C. The objective function is linear with respect to the decision variables d. None of the above 4. Consider a maximization linear program and denote Zu the optimal (maximum) objective function value. Denote zip the optimal objective value if we add integrality constraints on the variables of the linear program, then: a. ZP SL b. Zip 2 LP c. The inequality between Zup and zip is binding (becomes an equality) only if at least one of the optimal solutions of the linear program is integer d. The inequality between up and zip is binding (becomes an equality) only if all the feasible solutions of the linear program are integer e. None of the above