Given the Following All-Integer Linear Program ASolve the Problem as a Linear Program Ignoring the Integer

question 45

Essay

Given the following all-integer linear program:
$$\begin{array} { l l } \text { Max } & 3 x _ { 1 } + 2 x _ { 2 } \\\\\text { s.t. } & 3 x _ { 1 } + x _ { 2 } \leq 9 \\& x _ { 1 } + 3 x _ { 2 } \leq 7 \\& - x _ { 1 } + x _ { 2 } \leq 1 \\& x _ { 1 } , x _ { 2 } \geq 0 \text { and integer }\end{array}$$ a.Solve the problem as a linear program ignoring the integer constraints.Show that the optimal solution to the linear program gives fractional values for both x₁ and x₂.
b.What is the solution obtained by rounding fractions greater than of equal to 1/2 to the next larger number? Show that this solution is not a feasible solution.
c.What is the solution obtained by rounding down all fractions? Is it feasible?
d.Enumerate all points in the linear programming feasible region in which both x₁ and x₂ are integers, and show that the feasible solution obtained in (c) is not optimal and that in fact the optimal integer is not obtained by any form of rounding.