Use Implicit Enumeration to solve the following 0-1 IP.MAX Z=3X1+X2+2X3-X4+X5
ST 2X1+X2-3X4<=1
X1+2X2-3X3-X4+2X5=>2
Xi=0 or 1Please show enumeration tree. If a node is fathomed, indicate why it is fathomed. Provide the sequence of problems solved, eg. P1->P3->P4. Clearly indicate what the optimal solution is. Branch on x1 first.I need to understand the process, so no LINGO solution or any other program please. Steps have to be done by hand.MAX Z=3X1+X2+2X3-X4+X5
ST 2X1+X2-3X4<=1
X1+2X2-3X3-X4+2X5=>2
Xi=0 or 1
Branch on x1
P1: x1=1
P2:x1=0At P1 x1=1,
The subproblem is
MAX Z=3+x2+2×3-x4+x5
s.t.
2+x2-3×4<=1
1+2x2-3x3-x4+2x5>=2Or
MAX Z=3+x2+2×3-x4+x5
s.t.
x2-3×4<= -1
2x2-3x3-x4+2x5>=1
By looking at the first constraint, x4 has to be 1, otherwise x2<=-1 is invalid, since x2=1 or 0.
So x4=1
Therefore
X2-3<=-1
2x2-3x3-1+2x5>=1
Or
X2<=2
2x2-3x3+2x5>=2
The first constraint is redundant, since x2= 1 or 0, both satisfying x2<=2.
By looking at the second constraint, we see x3 has to be 0, otherwise
2x2-3+2x5>=2
2×2+2×5>=5 is infeasible, since 2×2+2×5<=2+2=4.
So x4=1, x3=0, x1=1.
To maximize 3X1+X2+2X3-X4+X5, we choose x2=x5=1
Therefore the optimal solution at P1 is (1,1,0,1,1), with objective value=3+1+0-1+1=4
This is the most current lower bound of the original problem. Any other sub-problem with objective value<=4 will be fathomed.At P2: x1=0
The subproblem is
MAX Z=x2+2x3-x4+x5
s.t.
x2-3x4<=1
2 x2-3 x3-x4+2 x5>=2
We then branch on x2.
At P3: x2=1
The subproblem is
MAX Z=1+2×3-x4+x5
s.t.
1-3×4<=1
2 -3 x3-x4+2 x5>=2
Or
3×4>=0 (redundant)
3×3+x4-2×5<=0Branch on x3
At P4: x3=1
The subproblem is
MAX Z=1+2-x4+x5
s.t.
3x4>=0 (redundant)
3+x4-2×5<=0
Or
-x4+2x5>=3
This is infeasible, since 2×5-x4<=2*1-x4<=2. So P4 is fathomed.At P5: x3=0
The subproblem is
MAX Z=1+0-x4+x5
s.t.
3x4>=0 (redundant)
x4-2×5<=0
Branch on x4At P6: x4=1
The subproblem is
MAX Z=1+0-1+x5
s.t.
1-2x5<=0
Or
2x5>=1, so x5=1
The solution is x5=1, with objective value=1-1+1=1, which less than the current lower bound=4
So this branch is fathomedAt P7: x4=0
The subproblem is
MAX Z=1+0-0+x5
s.t.
0-2×5<=0
Or
2x5>=0, so x5=1 is the optimal solution, with objective value=1+1=2, , which less than the current lower bound=4
So this branch is fathomedNow we start from branching at x2=0
At P8: x2=0
The subproblem is
MAX Z=0+2×3-x4+x5
s.t.
-3×4<=1
-3 x3-x4+2 x5>=2
Or
3×4>= – 1
3×3+x4-2×5<=2
The first constraint is invalid, since x4>=0
So this branch is fathomed.Therefore the only unfathomed branch is
(x1,x2,x3,x4,x5)=(1,1,0,1,1), with objective value=4, which is optimal.Branch tree:
Why Choose Us
- 100% non-plagiarized Papers
- 24/7 /365 Service Available
- Affordable Prices
- Any Paper, Urgency, and Subject
- Will complete your papers in 6 hours
- On-time Delivery
- Money-back and Privacy guarantees
- Unlimited Amendments upon request
- Satisfaction guarantee
How it Works
- Click on the “Place Order” tab at the top menu or “Order Now” icon at the bottom and a new page will appear with an order form to be filled.
- Fill in your paper’s requirements in the "PAPER DETAILS" section.
- Fill in your paper’s academic level, deadline, and the required number of pages from the drop-down menus.
- Click “CREATE ACCOUNT & SIGN IN” to enter your registration details and get an account with us for record-keeping and then, click on “PROCEED TO CHECKOUT” at the bottom of the page.
- From there, the payment sections will show, follow the guided payment process and your order will be available for our writing team to work on it.