Linear Programming Please show all work Solve the integer kn

Linear Programming. Please show all work

Solve the integer knapsack problem max 16x_1 + 19x_2 + 28x_3 + 23x_4 s.t. 2x_1 + 3x_2 + 5x_3 + 4x doubleintegral 7 x_i greaterthanorequalto 0 and integer Forall i = 1, 2, 3, 4 by B&B.; Use most fractional variable when selecting branching variable and select B&B; nodes in a best-bound search fashion. Use lowest index to break any ties. To solve each relaxed problem, you can use a linear optimization package (e.g. Xpress, or Excel Solver, ...).

Solution

say x1 is x , x2 is y,x3 is z and x4 is w

then ptimal Solution: p = 56; x = 3.5, y = 0, z = 0, w = 0

Tableau #1
x y z w s1 s2 s3 s4 s5 p   
2 3 5 4 1 0 0 0 0 0 7
1 0 0 0 0 -1 0 0 0 0 0
0 1 0 0 0 0 -1 0 0 0 0
0 0 1 0 0 0 0 -1 0 0 0
0 0 0 1 0 0 0 0 -1 0 0
-16 -19 -28 -23 0 0 0 0 0 1 0

Tableau #2
x y z w s1 s2 s3 s4 s5 p   
2 3 5 4 1 0 0 0 0 0 7
-1 0 0 0 0 1 0 0 0 0 0
0 1 0 0 0 0 -1 0 0 0 0
0 0 1 0 0 0 0 -1 0 0 0
0 0 0 1 0 0 0 0 -1 0 0
-16 -19 -28 -23 0 0 0 0 0 1 0

Tableau #3
x y z w s1 s2 s3 s4 s5 p   
2 3 5 4 1 0 0 0 0 0 7
-1 0 0 0 0 1 0 0 0 0 0
0 -1 0 0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 -1 0 0 0
0 0 0 1 0 0 0 0 -1 0 0
-16 -19 -28 -23 0 0 0 0 0 1 0

Tableau #4
x y z w s1 s2 s3 s4 s5 p   
2 3 5 4 1 0 0 0 0 0 7
-1 0 0 0 0 1 0 0 0 0 0
0 -1 0 0 0 0 1 0 0 0 0
0 0 -1 0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0 -1 0 0
-16 -19 -28 -23 0 0 0 0 0 1 0

Tableau #5
x y z w s1 s2 s3 s4 s5 p   
2 3 5 4 1 0 0 0 0 0 7
-1 0 0 0 0 1 0 0 0 0 0
0 -1 0 0 0 0 1 0 0 0 0
0 0 -1 0 0 0 0 1 0 0 0
0 0 0 -1 0 0 0 0 1 0 0
-16 -19 -28 -23 0 0 0 0 0 1 0

Tableau #6
x y z w s1 s2 s3 s4 s5 p   
0.4 0.6 1 0.8 0.2 0 0 0 0 0 1.4
-1 0 0 0 0 1 0 0 0 0 0
0 -1 0 0 0 0 1 0 0 0 0
0.4 0.6 0 0.8 0.2 0 0 1 0 0 1.4
0 0 0 -1 0 0 0 0 1 0 0
-4.8 -2.2 0 -0.6 5.6 0 0 0 0 1 39.2   

Tableau #7
x y z w s1 s2 s3 s4 s5 p   
0 0 1 0 0 0 0 -1 0 0 0
0 1.5 0 2 0.5 1 0 2.5 0 0 3.5
0 -1 0 0 0 0 1 0 0 0 0
1 1.5 0 2 0.5 0 0 2.5 0 0 3.5
0 0 0 -1 0 0 0 0 1 0 0
0 5 0 9 8 0 0 12 0 1 56