Given the Following All-Integer Linear Program:
​
Max $3 x _ { 1 } + 2 x _ { 2 }$

question 51

Essay

Given the following all-integer linear program:
​
Max $3 x _ { 1 } + 2 x _ { 2 }$
s.t.
$\begin{array} { l l } \text { M.t. } & 3 x _ { 1 } + 2 x _ { 2 } \\ & 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.