Max x1+ x2 s.t. x1 + 3x2 ≤ 9 −4 x1 + x2 ≥ −9 4 x1 + x2 ≥ 3 x1, x2 ≥ 0, and x1, x2 integer?
Max x1+ x2
s.t.
x1 + 3x2 ≤ 9
−4 x1 + x2 ≥ −9
4 x1 + x2 ≥ 3
x1, x2 ≥ 0, and
x1, x2 integer
1. Plot the feasible region for this problem.
2. What is the optimal solution?
3. What is the optimal solution to the linear programming (LP) relaxation? (The LP relaxation of an integer programming problem is the LP obtained by ignoring the integrality constraints.)
Update:I still have no idea how to even begin to graph this or figure out what the optimal solution is... I read the book and i'm totally confused.
More Questions From This User See All
Answers & Comments
Verified answer
Draw a coordinate grid with x1 across and x2 up.
Each of the constraints is one side of a line. The line is the inequality written as an equation. Decide which side of the line by testing any point not on it (the origin is the easiest point to use if it is not on the line).
In nearly all linear programming situations where integral solutions are not required, the optimum solution is at a corner of the acceptable region (in rare cases it can be anywhere along one side).
You may not be able to see the exact values of x1 and x2 at the corners by reading from the graph. If so, you can find the exact values of x1, x2 at the corners by solving pairs of simultaneous equations for the lines that join at each corner.
Find the value of x1 + x2 at each corner and take the maximum. For the tighter condition that x1 and x2 must be integers look at the points near corners of the acceptable region where both are integers.
EDIT. Yes probably, unless you can see why some would be unnecessary.
Take it in individual sections... y2-y1 is (-7-3) it is -10. x2-x1 is (5--2)... double unfavourable is a good, so 5+2, it is 7. So, -10/7 is the actual question... it is -a million.4285714.