Given the Following All-Integer Linear Program

Question

Examlex · Accepted Answer

The Answer is
a. From the graph on the next page, the optimal solution to the linear program is x₁ = 2.5, x₂ = 1.5, z = 10.5.
b. By rounding the optimal solution of x₁ = 2.5, x₂ = 1.5 to x₁ = 3, x₂= 2, this point lies outside the feasible region.
c. By rounding the optimal solution down to x₁ = 2, x₂ = 1, we see that this solution indeed is an integer solution within the feasible region, and substituting in the objective function, it gives z = 8.
d. There are eight feasible integer solutions in the linear programming feasible region with z values as follows:

a. From the graph on the next page, the optimal solution to the linear program is x<sub>1</sub> = 2.5, x<sub>2</sub> = 1.5, z = 10.5. b. By rounding the optimal solution of x<sub>1</sub> = 2.5, x<sub>2</sub> = 1.5 to x<sub>1</sub> = 3, x<sub>2 </sub>= 2, this point lies outside the feasible region. c. By rounding the optimal solution down to x<sub>1</sub> = 2, x<sub>2</sub> = 1, we see that this solution indeed is an integer solution within the feasible region, and substituting in the objective function, it gives z = 8. d. There are eight feasible integer solutions in the linear programming feasible region with z values as follows: x<sub>1</sub> = 3, x<sub>2</sub> = 0 is the optimal solution. Rounding the LP solution (x<sub>1</sub> = 2.5, x<sub>2</sub> = 1.5) would not have been optimal.

x₁ = 3, x₂ = 0 is the optimal solution. Rounding the LP solution (x₁ = 2.5, x₂ = 1.5) would not have been optimal.

Given the Following All-Integer Linear Program

Definitions: