Explore BrainMass
Share

all-integer linear program

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

Given the following all-integer linear program:

MAX 3x1 + 2x2

such that
3x1 + x2 <= 9
x1 + 3x2 <= 7
-x1 + x2 <= 1
x1, x2 >= 0 and integer

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 x1 and x2.
b. What is the solution obtained by rounding fractions greater than or 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 x1 and x2 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.

© BrainMass Inc. brainmass.com October 17, 2018, 1:01 am ad1c9bdddf
https://brainmass.com/math/linear-programming/all-integer-linear-program-320887

Solution Preview

Problem/Case Study:

Given the following all-integer linear program:

MAX 3x1 + 2x2
s. t. 3x1 + x2 < 9
x1 + 3x2 < 7
-x1 + x2 < 1
x1, x2 > 0 and integer

a. Solve the problem as a linear program ignoring the integer constraints. Show that the optimal solution to ...

Solution Summary

An all-integer linear program is scrutinized.

$2.19
Similar Posting

Integer Linear Programming: Example Problem

Enclosed problem in attachment.

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.

View Full Posting Details