Question

Consider the following IP problem.

Max z = 5x1+x2
s.t. − x1 + 2x2 ≤ 4
x1 − x2 ≤ 1
4x1 + x2 ≤ 12
x1,x2 ∈Z+
1. Solve graphically
2. Solve the LP relaxation of the problem graphically. Round this solution to the nearest integer solution and check whether it is feasible. Then enumerate all the rounded solutions by rounding this solution for the LP relaxation in all possible ways (i.e., by rounding each non-integer value both up and down). For each rounded solution, check for feasibility and, if feasible, calculate z. Are any of these feasible rounded solutions optimal for the IP problem?

Answer 1

See Annex

Explanation:

The relaxation of any Linear Programming problem, consists of eliminating the integer constraint condition, keeping the original constraint and the objective function, solving the problem as continuous variables. If in such new condition we find that optimal solution consist of integer solution we have found optimal solution already, if not we need to go ahead with the branching procedure of making variables integer above and down of the fractional values.

In this particular case ( see GeoGebra graphic solution attached changing x₁ and x₂ by x and y respectively ), and Objective Function in red we got integer solution :

z(max) = 11

x₁ = x = 2

x₂ = y = 1