Consider the following pure integer programming problem with slack variables x₃ and x₄:

Maximize Z = 18x₁ +12 x₂

Subject To 2x₁ x₂+ x₃= 5

2x₁ +3x₂ + x₄ = 13

x_i >= 0, i =1,2,3,4

A.Graph the linear programming relaxation. Show the grid points that are feasible for the integer program.

B. Solve this model with regular simplex.

C. Employ Gomorys Cutting Plane Algorithm to solve the model to integer optimality. Always choose the topmost fractional row of the tableau as the source row to generate each Gomorys cut and always add cuts to the bottom of the tableau.

D. Show the effect of the Gomorys cuts on the graph of the linear programming relaxation. Tips: The cuts may not be in only the x₁ and x₂ space needed for graphing. Solve for slack variables in (1) and (2) and use those values to plug into the Gomorys cut generated and simplify. For the second Gomorys cut, do the same thing for the new slack variable from the first Gomorys cut get it in terms of only x₁ and x₂.