Given the following all-integer linear program:

Max	15x1	+	2x2
s.t.
	7x1	+	x2		22
	3x1		x2		4

x₁,x₂0 and integer

(a)Solve the problem as an LP, ignoring the integer constraints.

(x₁,x₂) =

(b)What solution is obtained by rounding up values with fractional to the nearest integer? (If this solution is infeasible, enter INFEASIBLE.)

(x₁,x₂) =

Is this the optimal integer solution? Explain.Yes, this is the optimal integer solution since no other solutions produce a higher objective value.Yes, this solution is feasible, therefore it must be the optimal integer solution. No, this solution is feasible, but there is another solution that produces a higher objective value.No, this solution is infeasible.(c)What solution is obtained by rounding down all values with fractional parts? (If this solution is infeasible, enter INFEASIBLE.)

(x₁,x₂) =

Is this the optimal integer solution? Explain.Yes, this is the optimal integer solution since no other solutions produce a higher objective value.Yes, this solution is feasible, therefore it must be the optimal integer solution. No, this solution is feasible, but there is another solution that produces a higher objective value.No, this solution is infeasible.(d)Show that the optimal objective function value for the ILP (integer linear program) is lower than that for the optimal LP relaxation.The optimal objective function value for the LP relaxation in part (a) was .Solving the ILP produces an optimal objective function value of at

(x₁,x₂) =

.

(e)Why is the optimal objective function value for the ILP problem always less than or equal to the corresponding LP relaxation's optimal objective function value?None of the feasible solutions to the LP relaxation are feasible solutions to the ILP.Additional integer constraints restrict the feasible region further. The optimal solution to the ILP is always found by rounding down the optimal solution to the LP relaxation.The optimal solution to the ILP is always found by rounding up the optimal solution to the LP relaxation.Additional insteger constraints allow the other constraints of the LP relaxation to be ignored.When would the optimal objective function values be equal?They would be equal if the optimal solution to the ILP is the same as the optimal solution to the LP relaxation, except rounded down.They would be equal if the LP relaxation has an optimal solution with integer values. They would be equal if the optimal solution to the ILP is a feasible solution to the LP relaxation.They would be equal if the optimal solution to the ILP is the same as the optimal solution to the LP relaxation, except rounded up.They would be equal if the LP relaxation only uses integer values in the objective function and constraints.Comment on the optimal objective function of the MILP (mixed-integer linear program) compared to the corresponding LP and ILP.The relationship between the optimal objection function values for these three types of linear programs can be summarized as ---Select--- ILPMILPLP ILPLPMILP MILPLPILP LPILPMILP MILPILPLP LPMILPILP