Question

3. Consider the following all-integer linear program: Max 1x1+1x2 s.t. 4x1+6x2 ?22 1x1+5x2 ?15 2x1+1x2 ?9 x1, x2 ?0 and integer

a. Graph the constraints for this problem. Use dots to indicate all feasible integer solutions.

b. Solve the LP Relaxation of this problem.

c. Find the optimal integer solution.

Answer 1

The Formulation

Maximize Z= 1x1+1X2

Subject to

4x1+6x2<= 22

1x1+5x2<=15

2x1+1x2<=9

x1, x2>=0 and integer

a) Graph of the constraints

step

First, make the constraints to equality and put one variable as zero to find the value of other variable and vice versa

For example in the first constraint put 4x1+6x2=22

then put x2= 0 so x1 = 22/4 = 5.5 and again putting x1 = 0, x2= 3.67 and then plot the two points in the graph to get the constraint line

Repeat the procedure for all other constraints

The graph is shown below

As this is a maximization problem and we got 4 feasible points from which there are 2 integer points i.e. (4,1) and (0,3)

b) LP relaxation solving involves not considering x1 and x2 as integer and finding the optimal solution from all the 4 feasible points

point (0,3) value of objective= 1*0+1*3= 3

Point(1.42, 2.78)= 1.42+2.78 =4.2

Point(4,1) = 4+1 = 5

Point(4.5,0) = 4.5+0 = 4.5

so optimal solution is (4,1) as the maximized value is 5

c) optiml integer solution only consdier the feasible integer points

Among all the integer points (4,1) gives highest value of 5 so it is the optimal integer solution

Please comment if any doubt

Rate me

thanks