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 agoRelated 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
ADVERTISEMENT
Latest Questions
- Write a C++ program to read in various types of test questions (multiple choice and True/False)...
- Write a C program that accepts a port number as a command line argument, and starts...
- Given that labor is a resource that needs to be used efficiently, what responsibility do you...
- When you develop a research project, you need to have a reliable and valid method of...
- Suppose you have a list containing exactly three integer numbers. Each number could be positive, negative,...
- Explain the relation between muscles, ATP energy, and the calcium ion
- Vertical Analysis of Income Statement The following comparative income statement (in thousands of dollars) for the...
ADVERTISEMENT