Question

In: Operations Management

Solve the LP relaxation of the following binary linear program and report the optimal solution as...

Solve the LP relaxation of the following binary linear program and report the optimal solution as well as the optimal objective function value for the LP relaxation.

Maximize 10X1 + 18X2 + 17X3 + 5X4 + 3X5 + 11X6

Subject to: 7X1 + 8X2 + 11X3 + 6X4 + 4X5 + 6X6 <= 15

X1 , X2 , X3 ,X4 ,X5 ,X6 are all binary values

Solutions

Expert Solution

Hi,

Please find answer as below. If you like the answer, please up vote.

Answer

I have used excel solver to solve the problem. I have attached the snapshot of Input data, formulas and constraints used along with the optimal solution.

While performing LP relaxation for Binary linear program, it is important to note that the variables X1,X2,X3,X4,X5,X6 can take any values between 0 to 1 including 0 and 1, unlike without LP relaxation, variables can take only binary values.

Maximize 30.55
Variables Values
X1 0
X2 1
X3 0.09
X4 0
X5 0
X6 1

1. Snapshot of Input Data

2. Snapshot of Formulas Used

3. Snapshot of Constraints Used

4. Snapshot of Optimal Solution

keosha answered 1 month ago
Next > < Previous

Related Solutions

Solve the LP problem. If no optimal solution exists because there is no Solution Set, enter...
Solve the LP problem. If no optimal solution exists because there is no Solution Set, enter EMPTY. If no optimal solution exists because the region is unbounded, enter UNBOUNDED. Note that an unbounded region can still have an optimal solution while a bounded region is guaranteed to have optimal solutions. HINT [See Example 1.] Maximize and minimize p = x + 2y subject to x + y ≥ 4 x + y ≤ 10 x − y ≤ 4 x...
Solve the LP problem. If no optimal solution exists because there is no Solution Set, enter...
Solve the LP problem. If no optimal solution exists because there is no Solution Set, enter EMPTY. If no optimal solution exists because the region is unbounded, enter UNBOUNDED. Note that an unbounded region can still have an optimal solution while a bounded region is guaranteed to have optimal solutions. HINT [See Example 1.] Minimize c = 2x − 2y subject to x 6 ≤ y y ≤ 2x 3 x + y ≥ 10 x + 2y ≤ 35...
Required: Formulate and solve the LP Relaxation of the problem. Solve it graphically, and round down...
Required: Formulate and solve the LP Relaxation of the problem. Solve it graphically, and round down to find a feasible solution. Explain/show what excel parameters and cells should be entered into the excel to come up with the answer. Consider the following all-integer linear program: ??? 10?1 + 3?2 ?.?. 6?1 + 7?2 ≤ 40 3?1 + 1?2 ≤ 11 ?1,?2 ≥ 0 and integer
Solve this linear programming (LP) problem using the transportation method. Find the optimal transportation plan and...
Solve this linear programming (LP) problem using the transportation method. Find the optimal transportation plan and the minimum cost. (Leave no cells blank - be certain to enter "0" wherever required. Omit the "$" sign in your response.) Minimize 8x11 + 2x12 + 5x13 + 2x21 + x22 + 3x23 + 7x31 + 2x32 + 6x33 Subject to x11 + x12 + x13 = 90 x21 + x22 + x23 = 105 x31 + x32 + x33 = 105 x11...
Solve the LP problem. If no optimal solution exists, indicate whether the feasible region is empty...
Solve the LP problem. If no optimal solution exists, indicate whether the feasible region is empty or the objective function is unbounded. HINT [See Example 1.] (Enter EMPTY if the region is empty. Enter UNBOUNDED if the function is unbounded.) Minimize c = 0.2x + 0.3y subject to 0.2x + 0.1y ≥ 1 0.15x + 0.3y ≥ 1.5 10x + 10y ≥ 80 x ≥ 0, y ≥ 0. c = (x, y) =
solve the following LP. Formulate and algebraically solve the problem. what is the new optimal z...
solve the following LP. Formulate and algebraically solve the problem. what is the new optimal z value show that the current basis is optimal max z=65x1+25x2+20x3 8x1+6x2+x3<=48 4x1+2x2+1.5x3<=20 2x1+1.5x2+0.5x3<=8 x2<=5 x1,x2,x3>=0
Identify the type of optimal solution for the following LP problems by the graphical solution method....
Identify the type of optimal solution for the following LP problems by the graphical solution method. Show your work (1)   Min    2X1 + 3X2             S.T.   2X1 - 2X2    <=   2                   -2X1 +   X2    <=   1                   X1 => 0,    X2 => 0 If the objective function of the above formulation is changed from Min 2X1 + 3X2 to Max 2X1 + 3X2, what type of optimal solution does this problem provide? Note that all constraints remain...
Solve the following linear programming problem using Solver. Be sure to write in your optimal solution...
Solve the following linear programming problem using Solver. Be sure to write in your optimal solution below the problem. Max Z = 20X1 + 30X2 + 25X3 + 32X4 s.t. 4X1 + 8X2 + 5X3 + 6X4 ≤ 40 X1 + X2 ≥ 3 (X1 + X2) ≤ (X3 + X4) ?1 ?2 ≥ 3 2 X1 = __________ X2 = ___________ X3 = ___________ X4 = ___________ Z = ____________
Solve the following linear programming problem using Solver. Be sure to write in your optimal solution...
Solve the following linear programming problem using Solver. Be sure to write in your optimal solution below the problem. Max Z = 20X1 + 30X2 + 25X3 + 32X4 s.t. 4X1 + 8X2 + 5X3 + 6X4 ≤ 40 X1 + X2 ≥ 3 (X1 + X2) ≤ (X3 + X4) x1/x2 ≥ 3/2 X1 = __________X2 = ___________X3 = ___________X4 = ___________Z = ____________
For the following LP problem, determine the optimal solution by the graphical solution method. Min Z=...
For the following LP problem, determine the optimal solution by the graphical solution method. Min Z= 3x1+2x2 Subject to 2x1+x2 >10                    -3x1+2x2 < 6                      X1+x2 > 6                      X1,x1 > 0 Graph and shade the feasible region
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT